2.4.4 Quadratische Siebfaktorisierung

Folgende Idee steckt hinter der quadratischen Faktoriasierung:
Seien x, y ∈ Z, mit x² ≡ y² (mod n), aber x ≠ y (mod n). Dann teilt n: x² - y² = (x - y) ⋅(x + y) aber n teilt weder (x - y) noch (x + y). Daher muss ggT(x - y, n) ein nicht- trivialer Faktor von n sein. Eine gewöhnliche Strategie, um x und y zu finden ist Folgende:
Sei S = {p₁, p₂, ..., p_t } die Menge der ersten t Primzahlen (= Faktor- Basis). Finde Paare (a_i , b_i ) mit:
(i) a_i² ≡ b_i (mod n) und
(ii) b_i = ∏^t_j=1 p_j^{e _ij} , e_ij ≥ 0, d.h. b_i ist p_t - glatt.

Als nächstes finde eine Untermenge, so dass b_i eine perfekte Quadratzahl ist. D.h. die Hochzahlen der p_j müssen alle gerade sein. Zur Vereinfachung identifiziere den binären Vektor v_i = (v _i1 , v_i2 , ..., v_it ) mit dem Exponenten- Vektor (e_i1 , e_i2 , ..., e_it ), so dass v _ij = e_ij mod 2 ist. Falls t + 1 Paare (a_i ,b_i ) auftauchen, sind die t- dimensionalen Vektoren v₁ ,v ₂ , ..., v_t+1 linear abhängig über Z₂. ⇒ ∃ eine Untermenge T ⊆ {1, 2, ..., t + 1} mit ∑ _{i ∈ T} v_i = 0 über Z₂. Damit ist ∏ _{i ∈ T} b_i eine Quadratzahl. Klar ist, dass ∏ _{i ∈ T} a_i² ebenfalls eine Quadratzahl ist. Damit kann man x = ∏ _{i ∈ T} a_i setzen und y als Quadratwurzel von ∏ _{i ∈ T} b_i. Dies liefert uns ein Paar (x, y) mit x² ≡ y² (mod n). Falls für dieses Paar auch gilt x ≠ y (mod n), so liefert uns ggT(x - y, n) einen nicht- trivialen Faktor von n. Sonst kann man einige der Paare (a_i , b_i ) durch neue Paare ersetzen.

Definition: (Legendre- Symbol)
Das Legendre- Symbol (a/b) für a, b ∈ Z ist wie folgt definiert:
(a/b) = 0, falls p | a,
(a/b) = 1, falls a quadratischer Rest modulo p
(a/p) = -1, falls a Rest modulo p aber nicht quadratischer Rest.

Die Quadratische Siebfaktorisierung verwendet nun eine effiziente Methode um solche Paare (a_i , b_i ) zu finden:
Sei dazu m = ⌊ √n ⌋ , und betrachte q(x) = x2 + 2mx + m² - n ≈ x² + 2mx welches klein (bezüglich n) ist, falls x klein ist. Der Siebalgorithmus wählt a_i = (x + m) und testet ob b_i = (x + m)² - n p_t - glatt ist . Merke: a_i² = (x + m)² ≡ b_i (mod n). Außerdem sei noch gesagt, dass falls eine Primzahl p b_i teilt, dann ist (x + m)² ≡ n (mod p) und damit ist n ein quadratrischer Rest modulo p. Folglich muss die Faktor- Basis nur solche Primzahlen p beinhalten, für welche das Legendre- Symbol (n/p) = 1 ist. Ferner sollte, wegen negativen b_i's, "-1" in der Faktor- Basis beinhaltet sein.

Beispiel:
1. Man wähle als Mächtigkeit der Faktor- Basis t = 6 um nicht- triviale Faktoren von n = 24961 zu finden.
Damit ist S = {-1, 2, 3, 5, 13, 23} (Für 7, 11, 17, 19 ist (n/p) = -1)
2. Man berechne m = ⌊ √24961 ⌊ = 157.
3. Nun berechne man 7 a_i's und b_i's mit verschiedenen x in q(x) = (x + m)² - n, so dass q(x) 23- glatt ist.
Das führt zu folgenden Werten:
x₁ = 0, q(x₁ )= -312 = -2³⋅3⋅13, a₁ = 157, v₁ = (1, 1, 1, 0, 1, 0)
x₂ = 1, q(x₂ )= 3, a₂ = 158, v₂ = (0, 0, 1, 0, 0, 0)
x₃ = -1, q(x₃ )= -625 = -5⁴, a₃ = 156, v₃ = (1, 0, 0, 0, 0, 0)
x₄ = 2, q(x₄ )= 320 = 2⁶⋅5, a₄ = 159, v₄ = (0, 0, 0, 1, 0, 0)
x₅ = -2, q(x₅ )= -936 = -2³⋅3² ⋅13, a₅ = 155, v₁ = (1, 1, 0, 0, 1, 0)
x₆ = 4, q(x₆ )= 960 = 2⁶⋅3⋅5, a₆ = 161, v₆ = (0, 0, 1, 1, 0, 0)
x₇ = -6, q(x₇ )= -2160 = -2⁴⋅3³ ⋅5, a₇ = 151, v₇ = (1, 0, 1, 1, 0, 0)
4. Für T = {1, 2, 5} ist z.B. v₁ + v₂ + v₅ = 0
5. x = (a₁ ⋅a₂ ⋅a₅ mod n) = 936
6. l₁ = 1, l₂ = 3, l₃ = 2, l₄ = 0, l₅ = 1, l₆ = 0
7. y = -2³ ⋅ 3² ⋅ 13 mod n = 24025 8. Da 936 ≡ -24025 (mod n), muss ein anderes T gefunden werden 9 Für T = {3, 6, 7} ist jetzt v₃ + v₆ + v₇ = 0
10. x = (a₃ ⋅a₆ ⋅a₇ mod n) = 23045
11. l₁ = 1, l₂ = 5, l₃ = 2, l₄ = 3 , l₅ = 0, l₆ = 0
12. y = -2⁵ ⋅ 3² ⋅ 5³ mod n = 13922 13. Nun ist 23405 ≠ 13922 (mod n), damit ist ggT(x - y, n) = ggT(9483, 24961) = 109.
Damit sind zwei nicht triviale Faktoren von 24961 109 und 229.

Applet quadratische Siebfaktorisierung

Quellcode:
QuadAlgSF.java - Appletoberfläche
QuadAlg.java - Algorithmenklasse
Matrix.java - Matrixklasse

2.5 Shanks Algorithmus