Cryptography Reference
In-Depth Information
Hat man
y
gefunden, so folgt aus Aufgabe 11.4, dass dieser Algorithmus mit
Wahrscheinlichkeit
≥
0.5 abbricht und einen echten Teiler von
N
liefert.
Das eigentliche Problem ist, die Zahl
y
zu finden. Um das zu bewerkstelligen, feh-
len uns noch zwei wichtige Schritte, die wir im Anschluss beschreiben. Der erste
Schritt ist allen Verfahren gemeinsam. Erst im zweiten Schritt unterscheiden sich
die verschiedenen Verfahren. Das ist der Schritt, der die Laufzeit entscheidend
beeinflusst.
11.4.3 Die Kongruenzen
Um
y
zu konstruieren, werden Kongruenzen der folgenden Form produziert:
)
ν
01
p
ν
11
1
p
ν
r
1
x
1
≡
(
−
···
(
)
1
mod
N
,
r
)
ν
02
p
ν
12
1
p
ν
r
2
x
2
≡
(
−
1
···
(
mod
N
)
,
r
.
.
.
)
ν
0
s
p
ν
1
s
1
x
s
p
ν
rs
r
≡
(
−
1
···
(
mod
N
)
,
wobei die
p
i
Primzahlen aus einer sogenannten
Faktorbasis
sind. Zur Vereinfa-
chung der Schreibweise setzen wir
p
0
1.
Die Verfahren unterscheiden sich in der Art, wie diese Kongruenzen gewonnen
werden. Gemeinsam ist allen, dass
geeignete
Zahlen
x
i
=
−
quadriert werden, dann
−
modulo
N
reduziert (mit Resten zwischen
N
und
N
) und anschließend die Res-
te - soweit möglich - faktorisiert werden. Dabei werden nur die Primzahlen aus
der gegebenen Faktorbasis getestet. Es werden dann (mit evtl. Ausnahmen) nur
die Kongruenzen weiter verwendet, bei denen diese Faktorisierung vollständig
möglich ist.
Ist es gelungen, genügend viele solcher Kongruenzen zu erzeugen, so kann man
hoffen, dass es
μ
i
∈{
0, 1
}
gibt mit
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
μ
0
μ
1
.
.
μ
s
0
0
.
.
0
⎛
⎝
⎞
⎠
ν
01
ν
02
......
ν
0
s
ν
11
ν
12
......
ν
1
s
(
∗
)
≡
(
)
mod 2
.
.
.
ν
r
1
ν
r
2
......
ν
rs
und
μ
j
=
0 für mindestens ein
j
. Das System
(
∗
)
kann man als lineares Glei-
chungssystem über dem Körper
Z
2
auffassen. Hat das System mehr Spalten als
Zeilen, so existiert eine nichttriviale Lösung
(
μ
0
,...,
)
μ
s
. Setzt man für eine nicht-
triviale Lösung von
(
∗
)
s
i
=
1
x
μ
i
r
i
=
0
p
2
∑
j
=
1
ν
ij
μ
j
x
:
=
und
y
:
=
,
i
i
