Cryptography Reference
In-Depth Information
Die Bedingung
N ist Quadrat modulo p
i
ist speziell für die zu betrachtenden Ver-
fahren. Sie ist im Allgemeinen durch eine andere, oder gar keine Bedingung zu
ersetzen. Die Abschätzung
p
i
≤
B
ist allen Faktorbasen gemeinsam.
Das folgende Lemma gibt Auskunft, wie man die
p
i
für unseren Fall bestimmen
kann.
Lemma 11.1
Es sei p
∈
Z
p
=
2
eine Primzahl. Das Element N
ist genau dann ein Quadrat, wenn
N
p
−
1
≡
1
(
mod
p
)
.
2
a
2
ein Quadrat, so folgt die angegebene Kongruenz direkt aus
dem Satz 6.9 (a) von Euler, wenn man
a
2
für
N
einsetzt.
Nach dem Satz von Euler sind alle Elemente aus
=
Beweis.
Ist
N
Z
p
Nullstellen des Polynoms
X
p
−
1
1
X
p
−
1
1
X
p
−
1
−
+
=
−
1.
2
2
−
Davon gibt es insgesamt
p
1. Nach Korollar 9.2 sind die Hälfte dieser Elemen-
te Quadrate. Weil die Quadrate alle Nullstellen von
X
p
−
1
−
1 sind, und dieses
2
1
2
Nullstellen haben kann, müssen die Nichtquadrate
Nullstellen des Polynoms
X
p
−
1
p
−
Polynom nicht mehr als
+
1 sein. Das zeigt die Behauptung.
2
Bemerkung
Mit dem
Legendre-Symbo
l
u
nd dem
quadratischen Reziprozitätsgesetz
kann man
ebenfalls entscheiden, ob
N
ein Quadrat in
Z
p
ist oder nicht.
Bei der Erzeugung der Kongruenzen müssen gewisse Zahlen über der Faktorba-
sis in Primfaktoren zerlegt werden, wobei in manchen Verfahren nur Potenzen
p
ν
F
mit
p
ν
≤
∈
B
akzeptiert werden. Diese Zerlegung gelingt
genau für
B
-glatte bzw.
B
-potenzglatte Zahlen. Nun kann es passieren, dass die
Zerlegung nur fast gelingt. Das soll bedeuten, dass nur ein zu großer Primteiler
q
übrig bleibt. Eine solche Kongruenz hat die Form
von Primzahlen
p
)
ν
01
p
ν
11
1
p
ν
r
1
x
1
≡
(
−
···
·
(
)
1
q
mod
N
.
r
Natürlich nützt das so nichts, aber wenn eine zweite solche Kongruenz
)
ν
02
p
ν
12
1
p
ν
r
2
x
2
≡
(
−
1
···
·
q
(
mod
N
)
.
r
gefunden wird, kann man die beiden Kongruenzen zu einer brauchbaren Kon-
gruenz kombinieren:
)
ν
01
+
ν
02
p
ν
11
+
ν
12
1
p
ν
r
1
+
ν
r
2
x
1
x
2
q
−
1
2
(
)
≡
(
−
···
(
)
1
mod
N
,
r
wobei
q
−
1
modulo
N
zu bestimmen ist.
Wenn solche Primzahlen im Zerlegungsalgorithmus berücksichtigt werden, so
spricht man von der
Large Prime Variation
.
