Cryptography Reference
In-Depth Information
11.6.1 Das Polynom
In der einfachsten Form wählt man das quadratische Polynom
X
√
N
2
(
)=
+
−
f
X
N
(
)
∈
Z
und versucht
f
a
für
a
über der Faktorbasis
F
ganz in Primfaktoren zu
zerlegen. Gelingt das, so gilt
a
√
N
2
)
ν
0
(
a
)
p
ν
1
(
a
)
1
p
ν
r
(
a
)
+
≡
(
−
·····
(
)
1
mod
N
.
r
Das ist eine Kongruenz der Form, wie sie in Abschnitt 11.4.3 beschrieben wurde.
Das Polynom ist so gewählt, dass die Werte
f
(
)
relativ
klein
sind, und so eine
gute Chance haben, über der Faktorbasis
F
zu zerfallen.
a
Bemerkung
Beim
Multiple Polynomial Quadratic Sieve (MPQS)
werden mehrere Polynome der
Form
g
aX
2
0,
b
2
b
2
(
)=
+
+
>
−
>
|
−
X
2
bX
c
mit
a
ac
0 und
N
ac
benutzt.
2
Es gilt dann
ag
und man kann Kongruenzen wie oben
finden. Das oben benutzte Polynom
f
ist ein Spezialfall davon.
(
X
)
≡
(
aX
+
b
)
(
mod
N
)
Der eigentliche Trick besteht darin, nicht
jeden
Wert durch alle Primzahlen der
Faktorbasis zu teilen, wie es im vorher beschriebenen Verfahren der Fall war,
sondern nur diejenigen, die wirklich teilbar sind. Dazu dient das
Sieb
.
11.6.2 Das Sieb
Zunächst wird durch geeignete Wahl einer Schranke
S
∈
N
das
Siebintervall
=[
−
]
∩
Z
−
I
:
S
,
S
festgelegt. Das ist die Menge aller ganzen Zahlen zwischen
S
und
S
. Nun bestimmt man
f
(
a
)
für alle
a
∈
I
. In der Praxis wird
S
so gewählt,
−
<
(
)
<
dass
N
, es muss also nicht modulo
N
reduziert werden.
Das Vorzeichen von
f
N
f
a
(
a
)
ist das von
a
und
f
(
0
)
<
0, sodass
ν
0
(
a
)
∈{
0, 1
}
trivial
zu bestimmen ist.
Es sei
a
p
eine Nullstelle von
f
modulo
p
. Dann ist
f
(
a
p
+
kp
)
≡
0
(
mod
p
)
für
alle
k
∈
Z
. Anders ausgedrückt
p
|
f
(
a
p
+
kp
)
für die beiden Nullstellen von
f
∈
Z
in
. Weil
N
ein Quadrat modulo
p
ist, existieren diese Nullstel-
len. Um sie zu bestimmen muss nur eine Wurzel
N
p
aus
N
modulo
p
berechnet
werden, d. h.
N
p
≡
Z
p
und alle
k
(
)
N
mod
p
(vgl. dazu die Bemerkung auf Seite 175). Dann
sind
√
N
√
N
=
−
+
=
−
−
a
p
N
p
und
b
p
N
p
die beiden Nullstellen von
f
modulo
p
(außer im Fall
p
=
2, da gibt es nur eine,
nämlich
N
2
=
1). Wir suchen
a
p
im Siebintervall
I
und wissen, dass ausgehend
