Cryptography Reference
In-Depth Information
von
f
durch
p
teilbar ist. Diese Divisionen - und nur diese
- werden ausgeführt. Anschließend wird dasselbe mit
b
p
wiederholt.
Entsprechend kann für ungerade Primzahlen mit Potenzen von
p
verfahren wer-
den. Auch hier gibt es genau zwei Lösungen der Gleichung
f
(
a
p
)
jede
p
-te Zahl
f
(
a
)
mod
p
j
)
für alle
j
(siehe Lemma 6.14). Von diesen Nullstellen ausgehend läuft man mit
Schrittweite
p
j
(nach links wie nach rechts) und kann abermals durch
p
dividie-
ren. Man dividiert nur durch
p
, weil man in den
j
(
)
≡
(
X
0
−
1 Schritten zuvor ja schon
jeweils durch
p
dividiert hat.
Für
p
1
+
√
N
ungerade ist; für
p
1
=
=
2 wird
a
so gewählt, dass
a
4 ebenso, falls
N
≡
1
(
mod 4
)
(sonst gibt es keine Lösung). Im Fall
j
>
2 gibt es vier Lösungen,
≡
(
)
aber nur wenn
N
1
mod 8
. Zusammengefasst ergibt sich:
Bestimme die Schranken
S
,
B
und die zugehörige Faktorbasis
F
.
Für alle
a
∈
Z
mit
−
S
≤
a
≤
S
berechne
f
(
a
)
, notiere das Vorzeichen in
ν
0
(
a
)
(
)
=
|
(
)
|
und setze
U
a
:
f
a
.
Für alle Primzahlpotenzen
p
j
i
<
B
mit
p
i
aus der Faktorbasis bestimme die
mod
p
j
i
(
)
≡
(
)
Nullstellen
a
p
i
der Kongruenzgleichung
f
X
0
.
kp
j
i
kp
j
i
Ersetze für alle
k
∈
Z
mit
|
a
p
i
+
|≤
S
den Eintrag
U
(
a
p
i
+
)
durch
kp
j
i
kp
j
i
(
a
p
i
+
)
(
a
p
i
+
)
U
um eins. Dieser Schritt ist der Reihe
nach auszuführen: Erst für
p
i
, dann für
p
i
, dann für
p
i
/
p
i
, und erhöhe
ν
i
usw.
(
)=
Überall dort, wo am Schluss eine 1 steht, also für solche
a
mit
U
1, ist
eine Kongruenz gemäß Abschnitt 11.4.3 gewonnen. Die zugehörigen Vektoren
(
ν
0
(
a
)
(
))
a
,...,
ν
r
a
bilden die Spalten der dort angegebenen Matrix.
(
)
Evtl. liefert die
Large Prime Variation
noch weitere Kongruenzen, wenn
U
a
eine Primzahl ist.
Da man nur
p
j
≤
B
prüft, werden - im Unterschied zur Kettenbruchmethode -
nur
B
-potenzglatte Zahlen
f
erfasst.
Der vierte Schritt unseres Faktorisierungsalgorithmus ähnelt dem
Sieb des Era-
tosthenes,
deswegen spricht man von einem
Siebverfahren.
(
a
)
Beispiel
Wir wenden das quadratische Sieb auf
N
=
589 an. Das Polynom hat die Form
2
(
)=(
+
)
−
=
f
X
X
24
N
. Mit der Schranke
B
10 ergibt sich die Faktorbasis
F
=
{−
1, 2, 3, 5, 7
}
. Für
S
wählen wir 5. Für die Nullstellen
a
p
,
b
p
erhält man
p
4
3
5
7
2
2
N
≡
...
(
mod
p
)
1
1
1
a
p
,
b
p
1
±
1
−
1,
−
2
3,
−
2
