Cryptography Reference
In-Depth Information
11.5.2 Der Algorithmus
Wir schildern nun den Algorithmus von Morrison-Brillhardt. Die Kongruenz aus
Satz 11.5 zeigt, dass
N
modulo jeden Primteilers von
V
k
ein Quadrat ist. Daher
werden nur solche Primzahlen in die Faktorbasis
F
=
{
p
0
,...,
p
r
}
aufgenom-
men, wie im vorigen Abschnitt 11.4.4 beschrieben.
Satz 11.5 zeigt, dass für alle
k
2
√
N
. Wählt
man die Schranke
B
geeignet, so darf man hoffen, dass viele der
V
k
ganz in Prim-
faktoren aus der Faktorbasis
F
zerfallen, um die gewünschten Kongruenzen zu
erhalten. Anders ausgedrückt: Viele der
V
k
sind
B
-glatt.
Für die Rechnung brauchen wir nur die Zähler
P
k
der Näherungsbrüche, und
diese auch nur modulo
N
.
∈
N
die ganze Zahl
V
k
klein
ist:
V
k
<
Bestimme die Schranke
B
und die zugehörige Faktorbasis
F
;
Berechne die Folgen
(
U
k
)
,
(
V
k
)
,
(
x
k
)
,
(
a
k
)
schrittweise mit der Rekursion
(
♣
)
.
Berechne iterativ
P
k
≡
a
k
P
k
−
1
+
P
k
−
2
(
mod
N
)
,0
≤
P
k
<
N
, mit den Startwer-
=
=
ten
P
0,
P
1.
−
2
−
1
und
V
k
:
≡
(
)
=
Setze
ν
0
k
k
mod 2
V
k
.
Für alle Primzahlen
p
i
aus der Faktorbasis bestimme die höchste Potenz
j
mit
V
k
≡
V
k
p
j
i
mod
p
j
i
0 ersetze
V
k
durch
(
)
>
=
0
; falls
j
und setze
ν
ik
:
j
.
V
k
Jedes
k
, für das am Ende
=
1 gilt, liefert eine Kongruenz gemäß Ab-
schnitt 11.4.3.
)
ν
0
k
p
ν
1
k
1
p
ν
rk
P
k
≡
(
−
···
(
)
1
mod
N
.
r
Evtl. liefert die
Large Prime Variation
noch weitere Kongruenzen, wenn
V
k
eine
Primzahl ist.
Da der Kettenbruch nach Korollar 11.4 periodisch ist, kann es passieren, dass die
Periode
zu
k
lein ist, sod
ass
man zu wenige Kongruenzen findet. Man wählt
dann statt
√
N
eine Zahl
√
mN
mit einem
kleinen
quadratfreien
Multiplikator
m
und versucht es erneut.
Bemerkung
Die asymptotische Laufzeit des vorgestellten Algorithmus beträgt
O
exp
.
2 log
N
(
·
log log
N
)
Er war damit der erste subexponentielle Algorithmus zur Faktorisierung.
11.6 Das quadratische Sieb
Wir schildern wie beim quadratischen Sieb die Kongruenzen konstruiert werden.
