<<

. 7
( 9)



>>

p+1
für ein b ∈ Z — , so gilt für das Element a ∈ Z — (wegen p ≡ 3 (mod 4) ist
4
p p
p+1
∈ N):
4
p+1 p’1 p’1
2 +1
p+1
=b =b =b b = ±b ,
2 2
a 4

p’1 p’1
) ¤ 2, d. h. b = ±1. Es folgt, dass
2 2
da nach dem Satz 6.9 (a) von Euler gilt o(b
das Element
p+1
∈ Z—
a p := a 4
p

eine Quadratwurzel des Quadrates a modulo p ist. Damit sind ±a p die beiden
(einzigen) Quadratwurzeln von a modulo p. Man erh¤lt die Wurzeln modulo
einer Primzahl p ≡ 3 (mod 4) somit durch einfaches Potenzieren. Das wird das
Rabin-Verfahren vereinfachen.


Bemerkung
Für Primzahlen p ≡ 5 (mod 8) kann man Quadratwurzeln ebenfalls relativ ein-
fach gewinnen. Im Fall p ≡ 1 (mod 8) gibt es spezialisierte Algorithmen, wie
etwa den von Tonelli und Shanks. Mehr dazu ist in [7, § 1.5] zu ¬nden.




9.3.3 Das Verfahren

Das Rabin-Verfahren ist ein Public-Key-Verfahren. Der Empf¤nger R gibt seinen
öffentlichen Schlüssel bekannt und beh¤lt sich einen geheimen Schlüssel.

Für die Schlüsselerzeugung geht R wie folgt vor:
Schlüsselerzeugung.

R w¤hlt zwei Primzahlen p und q mit p, q ≡ 3 (mod 4) und p = q.

Es ist n = p q der öffentliche Schlüssel.

Es ist (p, q) der geheime Schlüssel.

Der Teilnehmer T möchte an den Empf¤nger R eine Nachricht senden.

C=N 2

!
T R
n=p q
176 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Verschlüsselung. Der Teilnehmer T geht für die Chiffrierung seines Klartextes
N wie folgt vor:
T besorgt sich den öffentlichen Schlüssel n von R.
T stellt seinen Klartext N als Element von Z — dar, d. h. N ∈ Z — .
n n

T berechnet den Geheimtext C = N 2 in Z — .
n

T sendet C an R.
Man beachte, dass der Geheimtext C ∈ Z — wegen n = p q, p = q, nach Lemma
n
— hat. Der Klartext N ist eine dieser vier Wurzeln.
9.1 vier Quadratwurzeln in Z n
Die vier Quadratwurzeln b1 , . . . , b4 modulo n erh¤lt man mit dem chinesischen
Restsatz aus den Quadratwurzeln w1 , . . . , w4 modulo p und modulo q (vgl. die
Bemerkung auf Seite 174). Und die Quadratwurzeln modulo p und modulo q
sind einfach zu bestimmen, da p und q kongruent 3 modulo 4 sind.
Entschlüsselung. Der Empf¤nger R geht zur Entschlüsselung des von T erhal-
tenen Geheimtextes C wie folgt vor:
p+1 q+1
R berechnet a p = C 4 ∈ Z — und aq = C 4 ∈ Z — und erh¤lt mit ±a p und
p q
±aq die vier Quadratwurzeln von C modulo p und q.
R ermittelt mit dem chinesischen Restsatz aus den vier Quadratwurzeln ±a p
modulo p und ±aq modulo q von C die vier Quadratwurzeln b1 , . . . , b4 von C
modulo n (vgl. die Bemerkung zu Lemma 9.1):
(a p , aq ) ’ b1 , (a p , ’aq ) ’ b2 , (’a p , aq ) ’ b3 , (’a p , ’aq ) ’ b4 .

R entscheidet, welche der vier Wurzeln b1 , . . . , b4 der Klartext N ist.

Bemerkung
Die Entschlüsselung liefert neben einem richtigen drei falsche Ergebnisse. Das ist
ein entscheidender Nachteil des Rabin-Verfahrens. Man könnte die Entschlüsse-
lung eindeutig machen, indem man nur Klartexte mit einer bestimmten Struk-
tur zul¤sst. Aber dadurch würde dann das Rabin-Verfahren nicht mehr algorith-
misch ¤quivalent zum Faktorisierungsproblem sein (siehe Abschnitt 9.3.4).

Beispiel
Es seien p = 3 und q = 7. Damit ist n = 21 der öffentliche Schlüssel von R. Der

Teilnehmer T will an R die Nachricht N = 10 ∈ Z21 senden und berechnet dazu
2
C = 10 = 100 = 16 .
R erh¤lt von T den Geheimtext C = 16 und ermittelt mittels der (geheimen) Prim-
zahlen p = 3 und q = 7 die vier Quadratwurzeln von 16 modulo 21; es gilt:
p+1 q+1
— —
2
= 16 = 1 ∈ Z3 und 16 = 16 = 4 ∈ Z7 .
4 4
16
9.3 Das Rabin-Verschlüsselungsverfahren * 177

Es sind also

a3 = 1 und ’a3 = ’1 = 2 die Quadratwurzeln modulo 3 von 16 und


a7 = 4 und ’a7 = ’4 = 3 die Quadratwurzeln modulo 7 von 16.


Mit dem chinesischen Restsatz ermittelt man zu den vier Kombinationen

w1 = (1, 4) , w2 = (1, 3) , w3 = (2, 4) , w4 = (2, 3)

die vier Quadratwurzeln

b1 = 4 , b2 = 10 , b3 = 11 , b4 = 17 .

Der Klartext N ist also unter den vier Wurzeln 4, 10, 11, 17 zu suchen.

(p’1) (q’1)
Wir bemerken noch, dass es wegen Korollar 9.2 in Z —q mit p = q genau
p 4
Quadrate gibt, sodass die Geheimtextmenge umfangreich ist.

9.3.4 Zur Sicherheit des Rabin-Verfahrens

Ein Angreifer, der einen Geheimtext C ∈ Z — abgefangen hat, steht vor dem Pro-
n
blem, die Quadratwurzeln von C zu bestimmen. Kann er die Zahl n faktorisieren,
d. h. die Primzahlen p und q bestimmen, so kann er ebenso wie der rechtm¤ßige
Empf¤nger R den Geheimtext C entschlüsseln. Interessant ist, dass hiervon auch
die Umkehrung gilt.

Lemma 9.3
Es seien p und q verschiedene (ungerade) Primzahlen und n = p q. Kann man zu je-
dem Quadrat c modulo n eine Quadratwurzel a modulo n bestimmen, so kann man n
faktorisieren.

Beweis. Man w¤hle zuf¤llig eine Zahl x ∈ {1, . . . , n ’ 1}. Ohne Einschr¤nkung
gelte ggT(x, n) = 1. Zu c = x2 ∈ Z — bestimme man eine Quadratwurzel a mo-
n
dulo n mit a ∈ {1, . . . , n ’ 1}: Es ist a eine der vier Quadratwurzeln modulo n
von c, und es gilt

a2 = x2 ∈ Z — ’ p q = n | (a2 ’ x2 ) = (a ’ x) (a + x) .
n

Nun gibt es vier Möglichkeiten (beachte, dass |a ’ x| ∈ {0, . . . , n ’ 1}):

p | a ’ x , q | a ’ x ’ ggT(a ’ x, n) = n ,
p | a + x , q | a + x ’ ggT(a ’ x, n) = 1 ,
p | a ’ x , q | a + x ’ ggT(a ’ x, n) = p ,
p | a + x , q | a ’ x ’ ggT(a ’ x, n) = q .
178 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Da jeder dieser vier F¤lle mit der gleichen Wahrscheinlichkeit eintritt, ist

d = ggT(a ’ x, n)

mit einer Wahrscheinlichkeit von 0.5 ein echter Teiler von n. Nach r Runden ist
die Zahl n also mit der Wahrscheinlichkeit von 1 ’ (1/2)r in ihre Primfaktoren
zerlegt.
Damit ist begründet, dass die beiden Probleme,

• n zu faktorisieren und

• Quadratwurzeln modulo n zu bestimmen,

(probabilistisch) algorithmisch ¤quivalent sind.

Bemerkung
Das Rabin-Verfahren kann durch einen Chosen-Cipher-Text-Angriff gebrochen
werden. Ein Angreifer A w¤hlt ein x ∈ {1, . . . , n ’ 1} und l¤sst den Geheim-
text C = x2 von R entschlüsseln. Dabei erh¤lt A die Quadratwurzel a modulo n
von R als mutmaßlichen Klartext zurück. Wie im Beweis zu Lemma 9.3 bestimmt
nun A mit einer Wahrscheinlichkeit von 0.5 einen Primteiler von n, indem er den
ggT der Zahlen n und a ’ x bestimmt. Wiederholt A den Angriff nur oft genug,
so erh¤lt A die Primfaktoren p und q. Auch wegen dieses Angriffs ist das Rabin-
Verfahren für die Praxis nicht relevant.


Aufgaben

9.1 Der Empf¤nger E erh¤lt den ElGamal-Chiffretext (B, c) = (6, 6). Der öffent-
liche Schlüssel von E ist (p, g, A) = (13, 2, 11). Bestimmen Sie den zugehörigen
Klartext.

9.2 Es sei n = 589 ein öffentlicher Schlüssel beim Rabin-Verfahren. Bestimmen
Sie aus dem Geheimtext C = 442 alle möglichen Klartexte.

9.3 Es ist n = 124573 der öffentliche Schlüssel beim Rabin-Verfahren. Ein An-
2
greifer l¤sst bei einem Chosen-Cipher-Text-Angriff den Text 113 entschlüsseln und
erh¤lt dabei den mutmaßlichen Klartext 110459 zurück. Bestimmen Sie hiermit
die Primfaktorzerlegung von n.
10 Diskrete Logarithmen

Die Sicherheit vieler kryptogra¬scher Verfahren basiert auf der Schwierigkeit,
diskrete Logarithmen zu bestimmen. Beispiele sind der Dif¬e-Hellman-Schlüs-
selaustausch und das ElGamal-Verfahren, auch in der Variante als Signatur-
Verfahren, das wir in Kapitel 12 besprechen werden. Das diskrete Logarithmen-
problem ist daher von großer Bedeutung für die Kryptologie.
Wir behandeln in diesem Kapitel die zwei wichtigsten, nicht spezialisierten Al-
gorithmen, die zu einem Gruppenelement a einer zyklischen Gruppe g kleiner
Ordnung den diskreten Logarithmus x, d. h. die Potenz x mit a = g x bestimmen “
den Baby-Step-Giant-Step-Algorithmus von Shanks und Pollards -Methode. Damit
erhalten wir ein grobes Maß für die Sicherheit solcher kryptogra¬scher Verfahren.
In einem letzten Abschnitt zeigen wir, dass die Wahl einer großen Gruppenord-
nung |G| alleine nicht vor den Algorithmen von Shanks und Pollard schützt.
Entscheidend ist letztlich der größte Primteiler der Gruppenordnung |G|. Dieser
muss genügend groß gew¤hlt werden. Andernfalls greifen die Algorithmen von
Shanks und Pollard zusammen mit der Reduktion der Gruppe G auf Gruppen von
der Ordnung der Primteiler von |G|.

10.1 Das diskrete Logarithmenproblem
Sowohl das Dif¬e-Hellman- als auch das ElGamal-Verfahren lassen sich in einer
beliebigen endlichen zyklischen Gruppe G = g realisieren. Beide Verfahren
sind unsicher, wenn diskrete Logarithmen berechnet werden können, d. h.:

Aus a = g x und g kann x berechnet werden.

In diesem Abschnitt bezeichne G eine zyklische Gruppe und g ∈ G ein erzeugen-
des Element von G, also G = g .

10.1.1 Der diskrete Logarithmus
Das diskrete Logarithmenproblem, kurz DLP, lautet:
Gegeben ist a ∈ G = g , gesucht ist x ∈ Z mit a = g x .
Das kleinste nichtnegative solche x heißt diskreter Logarithmus von a zur Basis
g; wir schreiben hierfür x = Logg a.
Beispiel
— 6
Es ist 2 eine Primitivwurzel modulo 13, d. h. Z13 = 2 . Wegen 2 = 12 und
8
2 = 9 gilt:
Log2 (12) = 6 und Log2 (9) = 8 .
180 10 Diskrete Logarithmen

10.1.2 Enumeration

Die naive Herangehensweise, n¤mlich das sukzessive Berechnen von

g , g2 , g3 , g4 , . . .

und Vergleich mit a = g x in jedem Schritt, hat Laufzeit O(|G|), ist also nicht
sehr ef¬zient. Diese Methode nennt man auch Enumeration. Wir besprechen im
Folgenden bessere Methoden zur Berechnung diskreter Logarithmen.


10.2 Der Baby-Step-Giant-Step-Algorithmus von Shanks
Der Baby-Step-Giant-Step-Algorithmus von Shanks ist eine Methode zur schnel-
len Berechnung diskreter Logarithmen. Die Aufgabenstellung lautet:
Gegeben ist a ∈ G = g , gesucht ist x = Logg (a).

10.2.1 Das Verfahren
Benötigt wird eine obere Schranke für die Gruppenordnung, wir setzen:

|G| = min k ∈ N ; k2 ≥ |G| ,
n :=


es ist dann n2 größer oder gleich |G|. Für jedes a ∈ G gilt somit x = Logg (a) ¤ n2 .
Wir dividieren die (gesuchte) Zahl x durch die Zahl n = |G| mit Rest:

x = q n + r , wobei r ∈ {0, . . . , n ’ 1} und q ∈ {0, . . . , n} .

Der Clou ist hierbei, dass das Element q wegen der Wahl von n in der Menge
{0, . . . , n} liegt. Wir erhalten

a = g x = gq n+r , also a g’r = gq n .

Wir ermitteln aus dieser letzten Formel nun r und q und damit den gesuchten
diskreten Logaritmus x = q n + r. Für r gibt es n Möglichkeiten, für q sind es
n + 1 Möglichkeiten. Wir erhalten zwei Listen von Gruppenelementen.

a g’r = gq n
QQQ
kk
kkk QQQ
kkk QQQ
k QQQ
kkk
ukk Q(
’r , r = 0, . . . , n ’ 1 q n , q = 0, . . . , n
g
ag

a g0 , a g’1 , a g’2 , . . . , a g’n+1
Die Baby-Step-Liste: und
g0 , gn , g2n , . . . , gnn .
die Giant-Step-Liste:
10.3 Pollards -Methode * 181

Nun vergleicht man beide Listen. Ein gemeinsames Element a g’r = gq n in bei-
den Listen liefert die Zahlen r und q und damit den diskreten Logarithmus
x = q n + r = Logg (a) .
Wir führen den Algorithmus von Shanks an einem Beispiel durch.
Beispiel

Es sei G = Z97 = 5 , also g = 5, und es sei a = 31. Wir bestimmen x = Logg (a).

Wegen 92 < |Z97 | = 96 ¤ 102 gilt n = |G| = 10. Wir erhalten die Baby-Step-
Liste:
0 1 2 3 4 5 6 7 8 9
r
’r
31 · 5 31 45 9 60 12 80 16 42 86 56
und die Giant-Step-Liste:
0 1 2 3 4 5 6 7 8 9 10
q
q 10
5 1 53 93 79 16 72 33 3 62 85 43
Für r = 6 und q = 4 erhalten wir dasselbe Ergebnis 16. Folglich ist
x = q n + r = 4 · 10 + 6 = 46 = Log5 (31) .
10.2.2 In der Praxis
Auf einem Rechner wird man die Giant-Step-Liste im Voraus berechnen, sie ist
unabh¤ngig von der Größe a, dessen diskreter Logarithmus berechnet werden
soll. Die Giant-Step-Liste kann also mehrfach benutzt werden.
Anschließend berechnet man die Baby-Step-Liste schrittweise und vergleicht
nach Berechnen jedes einzelnen Wertes diesen mit den Werten aus der Giant-
Step-Liste “ das Suchen wird vereinfacht, wenn die Giant-Step-Liste sortiert ist.
Man braucht ¤ 2 n Gruppenoperationen und muss n Gruppenelemente spei-
chern. Wir halten fest:
Lemma 10.1
Die Komplexit¤t des Baby-Step-Giant-Step-Algorithmus zur Bestimmung des diskreten
Logarithmus in einer zyklischen Gruppe G ist O( |G|).
Wegen des Zeit- und Speicherbedarfs ist der Baby-Step-Giant-Step-Algorithmus
bei der Größenordnung von |G| > 2160 nicht mehr einsetzbar “ bei einer zykli-
schen Gruppe der Größenordnung 280 ist bereits ein Speicher von einem Terabyte
nötig, falls man jedes Gruppenelement als ein Byte darstellen kann.

10.3 Pollards -Methode *
Deutlich weniger speicheraufwendig als der Baby-Step-Giant-Step-Algorithmus
ist Pollards -Methode, die wir nun schildern. Die Aufgabenstellung lautet wie
oben:
Gegeben ist a ∈ G = g , gesucht ist x = Logg (a).
182 10 Diskrete Logarithmen

10.3.1 Das Verfahren
Pollards -Methode besteht aus drei Schritten:
1. Schritt. Zerlege die Menge G in drei (etwa gleich große) Teilmengen G1 , G2 ,
G3 mit 1 ∈ G2 .
2. Schritt. Bestimme ganze Zahlen s, t mit as = gt wie folgt: Erzeuge die Folge
x0 = 1, x1 , x2 , . . . durch
§
⎨ a xi , falls xi ∈ G1
xi , falls xi ∈ G2 .
2
xi+1 :=
©
g xi , falls xi ∈ G3

Offenbar gilt x1 ∈ {a, g}, x2 ∈ {a2 , a g, g2 }, ..., d. h.

xi = a±i g βi mit ±i , β i ∈ N0 für alle i = 1, 2, . . . .

Da G endlich ist, |G| = n ∈ N, gibt es Indizes i, j, i < j mit xi = x j , und es gilt:

xi = x j ” a±i g βi = a± j g β j ” a±i ’± j = g β j ’βi .

Damit haben die Zahlen

s := ±i ’ ± j und t := β j ’ β i

die gewünschte Eigenschaft.

Bemerkung
Im Allgemeinen kann man für s und t betragsm¤ßig kleinere Zahlen w¤hlen.
Dazu reduziere man ±i ’ ± j und β j ’ β i modulo n, d. h. man teilt ±i ’ ± j und
β j ’ β i durch n mit Rest und erh¤lt:

±i ’ ± j = qs n + s und β j ’ β i = qt n + t .

Für die so erhaltenen Zahlen s, t gilt s, t ∈ {0, . . . , n ’ 1}. Wegen an = 1 = gn
(beachte den Satz 6.9 von Euler) gilt weiter:

as = aqs n+s = a±i ’± j = g β j ’βi = gqt n+t = gt .

Auf diese Weise erh¤lt man die kleinsten positiven Zahlen s und t mit as = gt .

Bei dieser Form des Algorithmus sind die Größen x0 , x1 , . . . , xi , . . . , x j zu spei-
chern. Nach dem Geburtstagsparadoxon (siehe Aufgabe 2.2) erh¤lt man die Zah-
len i < j mit xi = x j etwa nach |G| Schritten. Das Geburtstagsparadoxon ist
hier anwendbar, weil die Folge (xi ) wegen der Wahl der Rekursion einer Zufalls-
folge sehr ¤hnlich ist. Zeit- und Speicherkomplexit¤t sind damit O( |G|). Wir
werden durch eine Modi¬kation des zweiten Schrittes im Abschnitt 10.3.2 die
Speicherkomplexit¤t auf O(1) bringen.
10.3 Pollards -Methode * 183

3. Schritt. Bestimme den diskreten Logarithmus x = Logg (a) wie folgt: Mit den
Zahlen s und t aus dem 2. Schritt gilt wegen a = g x und (ii) in Lemma 6.1 (b):

gt = as = gsx , d. h. s x ≡ t (mod n) .

Folglich ist das gesuchte x eine Lösung der Kongruenzgleichung

s X ≡ t (mod n) .

Die Lösungsmenge dieser Kongruenzgleichung ist nach Korollar 4.19 die Menge
v + n Z, wobei d = ggT(s, n) und v die ohne Einschr¤nkung kleinste positive
d
Lösung der Kongruenzgleichung ist. Wir erhalten v wie in der Bemerkung nach
Korollar 4.19 geschildert mit dem euklidischen Algorithmus. Da der diskrete Lo-
garithmus x kleiner als n ist, ¬ndet man x unter den d Zahlen
n n n
v, v+ , v + 2 , . . . , v + (d ’ 1) .
d d d
n
Enumeration, d. h. Bestimmen von gv+k d , k = 0, . . . , d ’ 1, und Vergleichen des
Ergebnisses mit a liefert x.

Bemerkung
Falls d groß sein sollte, so kann es durchaus ef¬zienter sein, das Verfahren von
vorne zu beginnen, um ein kleines d zu erhalten, als die Enumeration durchzu-
führen.

Beispiel

Gegeben ist die zyklische Gruppe G = Z13 = 2 . Es ist also g = 2, und es sei
a = 9. Wir bestimmen x = Logg (a) mit Pollards -Methode.
1. Schritt: Wir w¤hlen

G1 := {1, 4, 7, 10} , G2 := {2, 5, 8, 11} , G3 := {3, 6, 9, 12} .

2. Schritt: Wir bestimmen nun die Folgenglieder x1 , . . . , xi , . . . , x j , sodass xi = x j :
0 1 2 3 4 5 6 7
i
1 9 5 12 11 4 10 12 Stop!
xi
±i 0 1 1 2 2 4 5 6
βi 0 0 1 2 3 6 6 6
Mit den Größen

i = 3 , j = 7 , ±i = 2 , ± j = 6 , β i = 2 , β j = 6

erhalten wir s = ’4 (bzw. s = 8) und t = 4.
3. Schritt: Als Lösungsmenge der Kongruenzgleichung

(’4) X ≡ 4 (mod 12)
184 10 Diskrete Logarithmen

erhalten wir wegen d = ggT(’4, 12) = 4 und da v = 2 eine Lösung der Kongru-
enzgleichung ist die Menge 2 + 12 Z = 2 + 3 Z. Folglich ist der diskrete Loga-
4
rithmus x = Logg (a) unter den Zahlen 2 , 5 , 8 , 11 zu suchen. Man testet:

2 5 8
2 = 4, 2 = 6, 2 = 9,

sodass x = Logg (a) = 8 gilt.


10.3.2 Modi¬kation des zweiten Schrittes

Bei der beschriebenen Version von Pollards -Methode sind im 2. Schritt für jedes
i die Tripel (xi , ±i , β i ) zu speichern. Wir geben nun eine Modi¬kation dieses 2.
Schrittes an, sodass fast kein Speicher benötigt wird. Dazu begründen wir vorab:

Lemma 10.2
Es seien X eine endliche Menge und f : X ’ X eine Abbildung. Für jede Folge (xi ) in
X mit xi+1 = f (xi ) gibt es ein i ∈ N mit xi = x2i .

Beweis. Es seien x1 , x2 , . . . , xv , . . . , xv+p’1 verschieden, aber xv+p = xv . Dann gilt
für alle a ∈ N:
xv+ap = xv .
Es folgt x j+ap = x j für alle j ≥ v. W¤hle nun ein i ≥ v mit p | i, etwa i = d p.
Dann gilt
x2i = xi+i = xi+dp = xi .
Damit ist ein passendes i gefunden.

Bemerkung
Nach dem Beweis dieses Lemmas kreisen die Folgenglieder xi nach einer evtl.
Vorperiode x1 , . . . , xv mit der Periode p. Vergleiche diese Veranschaulichung mit
dem griechischen Buchstaben .

Wir nutzen Lemma 10.2 um Schritt 2 zu modi¬zieren.
2. Schritt “ modi¬ziert. Wir bestimmen ganze Zahlen s, t mit as = gt . Dazu er-
zeugen wir erneut die Folgenglieder x0 = 1, x1 , x2 , . . . ∈ a±i g βi ; ±i , β i ∈ N0 ,
die durch folgende Vorschrift gegeben sind:
§
⎨ a xi , falls xi ∈ G1
xi , falls xi ∈ G2 .
2
xi+1 :=
©
g xi , falls xi ∈ G3

Nun speichern wir aber nicht alle Tripel (xi , ±i , β i ), sondern gehen wie folgt vor:
In jedem Schritt werden zwei Werte berechnet, n¤mlich xi+1 aus xi und x2 i+2 aus
x2 i , ausführlicher:
10.3 Pollards -Methode * 185

Berechne (x1 , ±1 , β 1 ) und (x2 , ±2 , β 2 ).

Falls x2 = x1 , Stop!, sonst:

Berechne (x2 , ±2 , β 2 ) und (x4 , ±4 , β 4 ).

Falls x4 = x2 , Stop!, sonst:

Berechne (x3 , ±3 , β 3 ) und (x6 , ±6 , β 6 ).

Falls x6 = x3 , Stop!, sonst:

Berechne (x4 , ±4 , β 4 ) und (x8 , ±8 , β 8 ) usw.

Da G endlich ist, gibt es nach Lemma 10.2 einen Index i mit x2 i = xi , der Algorith-
mus bricht somit ab. Wie im obigen Schritt 2 erhalten wir hieraus die gesuchten
Zahlen s und t:
s := ±i ’ ±2 i und t := β 2 i ’ β i .

Der Speicherbedarf wird durch die Modi¬kation sehr gering. Die gespeicherten
Tripel (xi , ±i , β i ) und (x2 i , ±2 i , β 2 i ) werden im Fall x2 i = xi durch die Tripel
(xi+1 , ±i+1 , β i+1 ) und (x2 i+2 , ±2 i+2 , β 2 i+2 ) überschrieben.

Beispiel

Wir betrachten erneut das Beispiel von Seite 183: Es sei G = Z13 = 2 . Wir
berechnen den diskreten Logarithmus x von a = 9 zur Basis 2 mit dem modi¬-
zierten 2. Schritt.
1. Schritt: Wir w¤hlen erneut

G1 := {1, 4, 7, 10} , G2 := {2, 5, 8, 11} , G3 := {3, 6, 9, 12} .

2. Schritt: Wir bestimmen nun die Folgenglieder x1 , . . . , xi wie oben beschrieben:

(xi , ±i , β i ) (x2 i , ±2 i , β 2 i )
i
(9, 1, 0) (5, 1, 1)
1
(5, 1, 1) (11, 2, 3)
2
(12, 2, 2) (10, 5, 6)
3
(11, 2, 3) (11, 6, 7)
4
Mit den Größen

i = 4 , j = 8 , ±i = 2 , ± j = 6 , β i = 3 , β j = 7

erhalten wir s = ’4 (bzw. s = 8) und t = 4. Nun erh¤lt man wie im Beispiel auf
Seite 183 den diskreten Logarithmus x = 8.
186 10 Diskrete Logarithmen

Bemerkung
Auch bei dieser modi¬zierten Version ist der Rechenaufwand bei Pollards -
Methode O( |G|) wegen des Geburtstagsparadoxons. Es gibt weitere Modi¬-
kationen, die in der Praxis etwas schneller laufen (siehe [7, § 8.5]). Der Vorteil
von Pollards -Methode gegenüber dem Baby-Step-Giant-Step-Algorithmus von
Shanks liegt im sehr geringen Speicherbedarf.


10.4 Die Reduktion nach Silver-Pohlig-Hellman
Auch wenn |G| beim ElGamal-Verfahren sehr groß ist, kann das DLP durch Pol-
lards -Methode oder den Baby-Step-Giant-Step-Algorithmus von Shanks sehr
einfach zu lösen sein. Das liegt daran, dass das DLP eventuell auf Gruppen klei-
ner Ordnung reduziert werden kann. Sind n¤mlich p1 , . . . , pn die Primteiler von
|G|, so l¤sst sich das DLP auf Gruppen von der Ordnung p1 , . . . , pn reduzieren.
Will man also etwa vor den Algorithmen von Shanks oder Pollard sicher sein, so
sollte der größte Primteiler von |G| sehr groß sein. Wir behandeln diese Reduktion
in diesem Abschnitt. Wir benötigen dazu ein Lemma aus der Gruppentheorie.
Lemma 10.3
Ist G = g eine endliche zyklische Gruppe der Ordnung n, so ist G zur additiven
Gruppe Z n isomorph.

Beweis. Wir betrachten den surjektiven Homomorphismus

Z G
¦: .
’ gk
k
Wegen o(g) = n ist n Z der Kern von ¦. Nach dem Homomorphiesatz auf Seite
150 gilt somit Z n = Z/n Z ∼ G.
=

10.4.1 Reduktion auf Primzahlpotenzordnung
Wir reduzieren das DLP in einem ersten Schritt auf Gruppen von Primzahlpo-
tenzordnung. Dazu beachten wir, dass wir nach den Lemmata 7.3 und 10.3 jede
zyklische Gruppe G mit
|G| = n = p11 · · · pν
ν
(kanonische Primfaktorzerlegung)
als ein direktes Produkt
G = G1 — · · · — G
mit zyklischen Gruppen G1 , . . . , G mit paarweise teilerfremden Ordnungen
|G1 | = p11 , . . . , |G | = pν schreiben können. Wir führen die Reduktion für den
ν

Fall = 2 durch, der allgemeine Fall folgt hieraus induktiv.
Ist g1 bzw. g2 ein erzeugendes Element von G1 bzw. G2 , wobei die Gruppenord-
nungen |G1 | und |G2 | teilerfremd sind, so ist offenbar g = (g1 , g2 ) ein erzeugen-
des Element von G1 — G2 . Es gilt:
10.4 Die Reduktion nach Silver-Pohlig-Hellman 187

Lemma 10.4
Es seien G1 = g1 und G2 = g2 endliche zyklische Gruppen mit teilerfremden
Ordnungen. Weiter sei g = (g1 , g2 ) ein erzeugendes Element der zyklischen Gruppe
G1 — G2 , und es sei a := (a1 , a2 ) ∈ G. Für x = Logg (a) gilt:

x ≡ Loggi (ai ) (mod |Gi |) für i = 1, 2 .

Beweis. Da x der diskrete Logarithmus von a zur Basis g ist, gilt g x = a, d. h.
(g1 , g2 ) = (a1 , a2 ). Somit gilt nach (ii) in Lemma 6.1 (b):
xx


Logg (ai )
gix = ai = gi , d. h. x ≡ Loggi (ai ) (mod |Gi |) für i = 1, 2 .
i



Damit ist bereits alles gezeigt.
Kennt man die diskreten Logarithmen xi = Loggi (ai ) für i = 1, 2, so kann man
also den diskreten Logarithmus x = Logg (a) wegen der Teilerfremdheit von |G1 |
und |G2 | mithilfe des chinesischen Restsatzes 7.4 berechnen. Mit Lemma 10.4 ist
somit das DLP in einer endlichen zyklischen Gruppe G auf das DLP in zyklischen
Gruppen von Primzahlpotenzordnung zurückgeführt. Hierbei sind eigentlich die
Kosten für den chinesichen Restsatz zu berücksichtigen, aber die sind bekanntlich
nicht sehr hoch.

Beispiel

Es ist 5 eine Primitivwurzel modulo der Primzahl p = 73, d. h. Z73 = 5 . Wir
bestimmen den diskreten Logarithmus von a = 58, d. h. x = Log5 (58). Es gilt
Z — = G1 — G2 ∼ Z8 — Z9 , wobei
=
p

9 8
G1 = 5 = 10 mit |G1 | = 8 und G2 = 5 = 2 mit |G2 | = 9 .

Für das Element a = 58 erhalten wir in G1 — G2 die Darstellung
9 8
a = 58 = (58 , 58 ) = (51, 55) .

Wir bestimmen nun die einfach zu bestimmenden Logarithmen x1 = Log10 (51)
und x2 = Log2 (55) in den Gruppen G1 und G2 z. B. mit Pollards -Methode und
erhalten:
x1 = Log10 (51) = 3 und x2 = Log2 (55) = 7 .
Nun erhalten wir den gesuchten diskreten Logarithmus, indem wir mit dem chi-
nesischen Restsatz die kleinste positive Lösung des folgenden Kongruenzglei-
chungssystems bestimmen:

X ≡ 3 (mod 8) , X ≡ 7 (mod 9) .
43
Wir erhalten x = 46, und tats¤chlich gilt 5 = 58.
188 10 Diskrete Logarithmen

10.4.2 Reduktion auf Primzahlordnung
Wir reduzieren das DLP nun auf Gruppen von Primzahlordnung.
Lemma 10.5
Es sei G = g eine endliche zyklische Gruppe mit |G| = pν für eine Primzahl p und ein
ν ∈ N). Dann l¤sst sich das DLP in G auf ν -maliges Logarithmieren in Gruppen der
Ordnung p reduzieren.
Beweis. Wir begründen die Behauptung mit Induktion nach ν. Der Fall ν = 1
ist klar. Die Behauptung gelte für ν ’ 1. Es ist U := g p nach Lemma 6.2 eine
Untergruppe von G mit |U| = pν’1 . Folglich ist |G/U| = p, G/U = g U . Es sei
a ∈ G. Bestimme ein y ∈ N mit a U = (g U)y = gy U. Dann gilt a g’y ∈ U =
g p . Nach Induktionsvoraussetzung können wir x ∈ N durch (ν ’ 1) -maliges
Logarithmieren bestimmen mit a g’y = g p x , und es gilt a = gy+x p .
Mit Lemma 10.5 ist das DLP in Gruppen der Ordnung pν auf ν DLPs in Gruppen
der Ordnung p reduziert. In der Praxis führt man die Reduktion wie im Folgen-
den beschrieben durch.
Gegeben ist die zyklische Gruppe G = g mit |G| = pν , p prim, ν ∈ N. Zu einem
Element a ∈ G ist der diskrete Logarithmus x = Logg (a) gesucht. Man schreibe
den gesuchten diskreten Logarithmus x in der p -adischen Darstellung als

x = x0 + x1 p + · · · + xν’1 pν’1 , x0 , . . . , xν’1 ∈ {0, . . . , p ’ 1} .

Wir bestimmen nun der Reihe nach die Zahlen x0 , . . . , xν’1 aus der Gleichung
ν’1
g x0 +x1 p+···+xν’1 p
(—) gx = a , =a
d. h.

und erhalten so die gesuchte Zahl x. Im Folgenden beachte man den Satz 6.9 von
ν
Euler, wonach g p = 1 gilt.
Wir bestimmen x0 : Potenziere die Gleichung g x = a mit pν’1 und erhalte
x0
ν’1 ν’1 ν’1 ν’1
= gp = gp = ap
gp x x0
.

ν’1
Berechne den diskreten Logarithmus x0 = Logg pν’1 (a p ) “ man beachte, dass
ν’1
das Element g p die Ordnung p hat. Damit ist x0 bestimmt.
ν’1
Wir bestimmen x1 : Schreibe die Gleichung in (—) um zu g x1 p+···+xν’1 p =
a g’x0 und potenziere diese Gleichung mit pν’2 und erhalte
pν’2
x1
ν’1 ν’1
= a g’x0
= gp
gp x1
.

ν’2 ν’2
g’p
Berechne den diskreten Logarithmus x1 = Logg pν’1 (a p x0 ). Damit ist
x1 bestimmt.
usw.
10.4 Die Reduktion nach Silver-Pohlig-Hellman 189

Der Algorithmus bestimmt die ν diskreten Logarithmen x0 , . . . , xν’1 in der Grup-
ν’1
pe g p der Ordnung p und damit den gesuchten diskreten Logarithmus x in
der Gruppe g der Ordnung pν .
Beispiel

Wir betrachten in der Gruppe Z251 = 6 mit 250 Elementen die zyklische Unter-
2
gruppe G = 6 = 36 mit 125 = 53 Elementen und bestimmen den diskreten
Logarithmus x von a = 4, d. h. x = Log36 (4). Dazu schreiben wir x in der 5 -
adischen Darstellung als

x = x0 + x1 5 + x2 52 mit x0 , x1 , x2 ∈ {0, . . . , 4} .

Wir bestimmen nun die Zahlen x0 , x1 , x2 aus der Gleichung

x0 +x1 5+x2 52
x
36 = 36 = 4.
x
Wir bestimmen x0 : Potenziere die Gleichung 36 = 4 mit 52 = 25 und erhalte

25
x0 25
= (36 ) x0 = 4 = 1.
219

Berechne den diskreten Logarithmus x0 = Log (1) = 0.
25
36

’0
x 5+x2 52
= 4 · 36 = 4 mit
Wir bestimmen x1 : Potenziere die Gleichung 36 1
51 = 5 und erhalte
25 x1 5
= 4 = 20 .
36

Berechne den diskreten Logarithmus x1 = Log 25 20 = 2. Damit ist x1 be-
36
stimmt.
’0’2·5
x2 52
= 4 · 36 = 149 mit
Wir bestimmen x2 : Potenziere die Gleichung 36
50 = 1 und erhalte
25 x2
= 149 .
36

Berechne den diskreten Logarithmus x2 = Log 25 149 = 4. Damit ist x2
36
bestimmt.

Wir erhalten somit für x = Log36 (4) = 0 + 2 · 5 + 4 · 52 = 110. Und tats¤chlich
110
= 4.
gilt 36



10.4.3 Volle Reduktion
Wir fassen nun die beiden Reduktionen zusammen und erhalten die volle Reduk-
tion des diskreten Logarithmenproblems auf Gruppen von Primzahlordnung.
190 10 Diskrete Logarithmen

Korollar 10.6
ν ν
Es sei G eine endliche zyklische Gruppe mit |G| = p11 · · · pr r (kanonische Primfaktor-
zerlegung). Dann l¤sst sich das DLP auf das DLP in Gruppen der Ordnung p1 , . . . , pr
zurückführen.

Hat |G| nur kleine Primteiler, so ist das DLP in G relativ leicht lösbar. Ist etwa p
eine Primzahl, sodass p ’ 1 nur kleine Primteiler hat, so ist Z — für die Verfahren
p
von Dif¬e-Hellman und ElGamal nicht brauchbar. Man w¤hle besser eine sichere
(große) Primzahl p, d. h. p = 2 q + 1 mit einer Primzahl q.

Beispiel
Die Zahl p = 2104 · 344 · 549 · 747 + 1 ist eine Primzahl mit 420 Bit. Das DLP in Z —
p
— | stecken.
ist aber sehr einfach, da nur die Primteiler 2, 3, 5, 7 in p ’ 1 = |Z p


Bemerkung
Kombiniert man die Reduktion mit einem der beiden allgemeinen Algorithmen,
√ √
so betr¤gt die Komplexit¤t O(ν1 p1 + · · · + ν p ) Gruppenoperationen. Falls

|G| einen dominanten Primteiler p enth¤lt, betr¤gt die Komplexit¤t O( p).
Falls es Gruppen gibt, für die es zur Lösung des DLP keine wesentlich besseren
Algorithmen als die in diesem Kapitel beschriebenen gibt, so ist für diese Grup-
pen die Potenzfunktion f : x ’ g x eine Einwegfunktion.


Aufgaben

Bestimmen Sie den diskreten Logarithmus von 3 in Z53 zur Basis 2 mit
10.1

(a) dem Baby-Step-Giant-Step-Algorithmus von Shanks bzw.
(b) Pollards -Methode für Gi := {a ∈ {1, . . . , 52} ; a ≡ i mod 3} für i =
1, 2, 3.

10.2 Implementieren Sie die Algorithmen von Silver-Pohlig-Hellman, Shanks
und Pollard und testen Sie diese an Beispielen.

10.3 Wenn g keine Primitivwurzel modulo p ist, muss Pollards -Methode zur
Berechnung diskreter Logarithmen nicht funktionieren. Geben Sie ein Beispiel
dafür an.

10.4 Bestimmen Sie mit dem Silver-Pohlig-Hellman-Algorithmus den diskreten

Logarithmus von 500 zur Basis 7 in Z601 .
11 Faktorisierung

Beim RSA-Verfahren werden zwei (große) Primzahlen p und q miteinander mul-
tipliziert, was sehr einfach ist. Die Zahl N = p q jedoch wieder in ihre Prim-
teiler zu faktorisieren wird als außerordentlich schwierig angesehen. Dabei ist
aber nicht bekannt, ob das Problem der Faktorisierung tats¤chlich schwierig ist. Es
könnte ja durchaus auch sein, daß es eine einfache Methode gibt, Zahlen in ihre
Primfaktoren zu zerlegen, diese bisher nur noch nicht bekannt ist. Kurz gesagt,
das Problem ist in NP , aber es ist nicht bekannt, ob es vielleicht in P liegt.
Neben der (naiven) Probedivision, bei der man einfach sukzessive N durch be-
kannte (aber kleine) Primzahlen teilt, gibt es ausgefeilte Methoden, von denen
wir einige in diesem Kapitel vorstellen. Dabei konzentrieren wir uns nicht auf
Zahlen N, die Produkt von zwei Primzahlen sind, wie es beim RSA-Verfahren
verwendet wird. Wir behandeln das Problem der Zerlegung, d. h. der Faktorisie-
rung ganzer (zusammengesetzter) Zahlen allgemein.
Die Methoden, die man dabei benutzt, greifen zum Teil bekannte Verfahren auf.
Wir werden Pollards -Methode erneut ins Spiel bringen, mit dessen Hilfe wir be-
reits diskrete Logarithmen berechnet haben, und die Kettenbrüche, mit deren Hilfe
wir einen Angriff auf RSA geschildert haben, werden wieder eine Rolle spielen.
Weiter werden wir das Verfahren von Fermat, das quadratische Sieb wie auch die
p ’ 1 -Methode von Pollard behandeln. Die Idee der letztgenannten Methode von
Pollard l¤sst sich auf elliptische Kurven übertragen. Damit gewinnt man die el-
liptic curve method, die wir aber erst nach der Einführung von elliptischen Kurven
im letzten Kapitel 14 behandeln werden.



11.1 Prinzipielles Vorgehen

Gegeben ist eine natürliche Zahl N. Nach dem Fundamentalsatz 4.14 der Arith-
metik besitzt N von der Reihenfolge der Faktoren abgesehen genau eine Zerle-
gung in Primzahlen:
N = p1 · · · p n ,

wobei die Primzahlen p1 , . . . , pn nicht verschieden sein müssen. Um die Prim-
zahlen p1 , . . . , pn zu bestimmen, suchen wir nach einem nichttrivialen Teiler d
von N. Gegebenenfalls wird das Verfahren auf d und N erneut angewendet.
d
Wir beschr¤nken uns stets darauf zu beschreiben, wie d gefunden werden kann.
Wir sagen dann, wir h¤tten eine Zerlegung für N gefunden oder N sei zerlegt
192 11 Faktorisierung

oder “ etwas schlampig “ N sei faktorisiert. Um eine Zerlegung von N zu bestim-
men, hat sich das folgende Vorgehen bew¤hrt.

Prüfe, ob N durch eine Primzahl p kleiner einer festgelegten Schranke B teilbar
ist.

Dazu bestimmt man (oder hat schon gespeichert) eine Liste aller Primzahlen
¤ B und berechnet sukzessive den Rest von N bei Division durch p. Ist er 0
wird p ausgegeben “ Stop!
Will man nur wissen, ob solche Primteiler existieren, berechnet man d =
ggT(R, N), wobei R Produkt aller Primzahlen ¤ B ist. Diese Vorgehenswei-
se ist insbesondere dann vorteilhaft, wenn nicht damit gerechnet werden
muss, dass es solche Primzahlen gibt.

Falls keine solchen Primteiler gefunden werden:

Prüfe, ob N eine Primzahl ist (vgl. Kapitel 8 über Primzahltests). Falls ja “
Stop!; falls nein:

Prüfe, ob N Potenz einer natürlichen Zahl ist (vgl. Aufgabe 8.6). Falls ja “ Stop!;
falls nein:

Erst jetzt bringt man die schweren Geschütze ins Spiel, die wir in den folgen-
den Abschnitten besprechen. Dabei emp¬ehlt sich im Allgemeinen die Rei-
henfolge (wobei nicht alle Verfahren angewendet werden müssen):

p ’ 1 -Methode mit kleiner Schranke B,
Pollards -Methode,
Kettenbruchmethode,
die elliptische Kurven Methode nach Lenstra (siehe Abschnitt 14.3),
quadratisches Sieb,
Zahlkörpersieb.

Bemerkung
Das Zahlkörpersieb werden wir in diesem Buch nicht behandeln, es sind hierzu
weit mehr Hilfsmittel aus der Algebra nötig als wir zur Verfügung haben.

Die Schranke B, bis zu der Probedivisionen durchgeführt werden, h¤ngt sehr von
der Anwendung ab. MAPLE benutzt B = 100 000, Cohen [7] schl¤gt B = 500 000
vor und diskutiert größere Schranken.
Für den Rest dieses Kapitels setzen wir N als zusammengesetzte natürliche Zahl
voraus, d. h. N ist ungleich 1 und keine Primzahl. Unser Ziel ist es, einen nicht-
trivialen Teiler d von N zu ¬nden.
11.2 Pollards -Methode * 193

11.2 Pollards -Methode *

Bei der Bestimmung diskreter Logorithmen haben wir neben dem Baby-Step-
Giant-Step-Algorithmus Pollards -Methode in Abschnitt 10.3 beschrieben. Bei
der Methode von Pollard wurde eine (unendliche) Zufallsfolge (xi ) in einer end-
lichen Menge gebildet. Dass es bei einer solchen Folge Indizes i = j mit xi = x j
gibt, ist klar “ wir nennen ein solches Tripel (xi = x j , i, j) einen Treffer “, der
Clou an der Methode war, dass ein solcher Treffer relativ schnell bestimmt wer-
den kann. In diesem Sinne ist Pollards -Methode ein Suchalgorithmus, der aus
einer (unendlichen) Folge (xi ) in einer endlichen Menge einen Treffer bestimmt.
Wir können diesen Algorithmus auch für andere Probleme benutzen, etwa zum
Bestimmen von Teilern einer natürlichen Zahl.



11.2.1 Die Idee

Die zusammengesetzte natürliche Zahl N wird von einer “ uns unbekannten “
Primzahl p geteilt. Wir suchen zwei ganze Zahlen x und y mit

x ≡ y (mod N) und x ≡ y (mod p) .

Angenommen, wir haben solche Zahlen x und y gefunden. Es ist dann

d = ggT(x ’ y, N)

ein nichttrivialer Teiler von N, da:

Aus p | x ’ y und p | N folgt p | d, sodass d = 1 gilt, und


aus N x ’ y folgt d = N.


Wie oben bemerkt ist dann eine Zerlegung von N gefunden, auf die der Algorith-
mus ggf. erneut angewendet werden kann.



11.2.2 Konstruktion der Zahlen x und y

Die Zahlen x und y ¬nden wir mit dem Algorithmus von Pollard. Dabei bilden
wir im Wesentlichen in der endlichen Menge Z p , wobei p ein unbekannter Prim-
teiler von N ist, eine (unendliche) Folge (xi ). Für einen Treffer gilt dann die ge-
wünschte Kongruenz:

xi ≡ x j (mod p) , d. h. d = ggT(xi ’ x j , N) > 1 .

Gilt zudem die Inkongruenz xi ≡ x j (mod N), so folgt d = N.
194 11 Faktorisierung

Wir de¬nieren die Zahlenfolge (xi ) rekursiv mit einer Abbildung f (x) = x2 + c,
wobei c ∈ Z \ {0, ’2} (siehe Aufgabe 11.1), und einem Startwert x0 :

xi+1 = f (xi ) .

Diese spezielle Wahl von f hat sich in der Praxis bew¤hrt, h¤u¬g wird c = 1
gew¤hlt. Im folgenden Algorithmus benutzen wir Lemma 10.2, um einen nicht-
trivialen Teiler d von N zu bestimmen.

W¤hle ein x0 ∈ {0, . . . , N ’ 1} und ein c ∈ Z \ {0, ’2}.

Berechne x1 = f (x0 ) und x2 = f ( f (x0 )) modulo N.

Falls 1 < d = ggT(x2 ’ x1 , N), Stop!, sonst:

Berechne x2 = f (x1 ) und x4 = f ( f (x2 )) modulo N.

Falls 1 < d = ggT(x4 ’ x2 , N), Stop!, sonst:

Berechne x3 = f (x2 ) und x6 = f ( f (x4 )) modulo N.

Falls 1 < d = ggT(x6 ’ x3 , N), Stop!, usw.

Der Algorithmus terminiert nach Lemma 10.2. In dem seltenen Fall d = N, in
dem nichts gewonnen ist, w¤hle man ein neues c und starte erneut. Die Wahl
eines neuen Starwertes x0 emp¬elt sich nicht. Der Fall d = N tritt ein, wenn für
alle Primteiler von N gleichzeitig Treffer auftreten.

Beispiel
Wir suchen einen nichttrivialen Teiler der (zusammengesetzten) Zahl N = 1 517.
Für c w¤hlen wir 1, d. h. f (x) = x2 + 1, und als Startwert w¤hlen wir x0 = 70.

= 350 x2 = 1141 ggT(1141 ’ 350, 1517) = 1
x1
= 1141 x4 = 1148 ggT(1148 ’ 1141, 1517) = 1
x2
= 296 x6 = 412 ggT(412 ’ 296, 1517) = 1
x3
= 1148 x8 = 1010 ggT(1010 ’ 1148, 1517) = 1
x4
= 1149 x10 = 196 ggT(196 ’ 1149, 1517) = 1
x5
= 412 x12 = 862 ggT(862 ’ 412, 1517) = 1
x6
= 1358 x14 = 825 ggT(825 ’ 1358, 1517) = 41
x7

Damit ist 1 517 = 37 · 41 zerlegt.


Pollards p ’ 1-Methode
11.3

Mit der p ’ 1-Methode ¬ndet man Primteiler p von N, für die p ’ 1 Produkt von
kleinen Primzahlen ist. Dabei spielt die Größe von p kaum eine Rolle.
11.3 Pollards p ’ 1-Methode 195

11.3.1 Die Methode

Es sei p ein “ uns unbekannter “ Primteiler von N, also N = p m mit m ∈ N >1 .
Ist a eine zu N teilerfremde natürliche Zahl, so ist a auch zu p teilerfremd. Nach
dem Satz 6.10 von Fermat gilt

a p’1 ≡ 1 (mod p) .

Jedes Vielfache k von p ’ 1 erfüllt dann ebenfalls

ak ≡ 1 (mod p) , d. h. p | ak ’ 1 .

Wegen p | ak ’ 1 liefert der euklidische Algorithmus eine Zahl d mit

p | d = ggT(ak ’ 1, N) .

Ist d = N, so ist N zerlegt. Diese p ’ 1 -Methode von Pollard ist dann sinnvoll,
wenn p ’ 1 ein Produkt von kleinen Primzahlen ist. Man w¤hlt für k das Produkt
aller Primzahlpotenzen unterhalb einer vorgegebenen Schranke B und ¬ndet so
ein Vielfaches k von p ’ 1, d. h.,

∏ qe ,
k = »(B) = kgV(1, . . . , B) = wobei qe ¤ B .
q∈P




11.3.2 Glatte Zahlen

Es sei B ∈ N. Eine Zahl m ∈ N heißt B -glatt, wenn jede Primzahl p, die m teilt,
kleiner gleich B ist:
p | m ’ p ¤ B.

Die Zahl m heißt B -potenzglatt, wenn jede Primzahlpotenz pν , die m teilt, kleiner
gleich B ist:
pν | m ’ pν ¤ B .

Glattheit spielt eine wichtige Rolle bei modernen Faktorisierungsverfahren.

Beispiel
Die Zahl N = 60 ist 5-potenzglatt, die Primzahlen 59 und 61 nicht. Übrigens ist
»(5) = 60.
Die Zahl 2104 · 344 · 549 · 747 ist 7-glatt und 747 -potenzglatt (747 ≈ 5 · 1039 ).

Bemerkung
Eine natürliche Zahl m ∈ N ist genau dann B-potenzglatt, wenn gilt m | »(B) .
196 11 Faktorisierung

11.3.3 Der Algorithmus

Im nachfolgenden Algorithmus wird es deutlich, wie man a»(B) sukzessive aus-
rechnet. Die Eingabe ist die natürliche Zahl N, die es zu faktorisieren gilt. Die
Ausgabe ist ein echter Teiler von N oder Pech gehabt.

W¤hle B ∈ N und bestimme alle Primzahlen p1 , . . . , pn kleiner gleich B, am
Besten beginnend mit p1 = 2 der Größe nach geordnet.
ν
W¤hle νi ∈ N maximal mit pi i ¤ B für alle i ∈ {1, . . . , n}.

W¤hle a0 ∈ N >1 mit ggT(a0 , N) = 1.
ν
pi i
Berechne iterativ ai ≡ (mod N) mit 0 < ai < N für i = 1, . . . , n und
ai’1
bestimme d := ggT(ai ’ 1, N).

Falls d = 1 n¤chstes i.
Falls d > 1 n¤chster Schritt.

Falls d = N, gib d zurück, sonst Pech gehabt.

Falls stets d = 1, d. h. ggT(an ’ 1, N) = 1, dann gibt es keinen B -glatten Prim-
teiler von N “ Pech gehabt.

Im sehr seltenen Fall, dass d = N ist, lohnt es sich evtl. den Algorithmus mit
einem neuen Startwert a0 nochmals zu durchlaufen. Im übrigen bedeutet d = N,
dass es Primteiler p von N gibt, für die p ’ 1 B -potenzglatt ist.

Bemerkung
In MAPLE wurde beispielsweise B = 2000 gew¤hlt. Cohen [7] schl¤gt B zwischen
105 und 106 vor. Die Wahl von B beein¬‚usst stark die Laufzeit, aber auch die
Wahrscheinlichkeit, eine Zerlegung zu ¬nden.

Die p ’ 1 -Methode von Pollard wird manchmal mit einer kleinen Schranke wie
B = 2 000 angewendet, um relativ kleine Primteiler zu ¬nden. Die Methode ist
aber auch von theoretischem Interesse, weil sie

• die Idee liefert für Lenstras Elliptische Kurven Methode (siehe Kapitel 14).

• einen Angriff auf das RSA-Verfahren darstellt. Wie schon in Abschnitt 7.4.1
erw¤hnt, sollte die Primzahlen p und q so gew¤hlt werden, dass p ’ 1 und
q ’ 1 jeweils einen großen Primteiler haben.

eine Verallgemeinerung besitzt zur sogenannten p + 1-Methode, die eben-

falls Auswirkungen auf die Wahl der Primzahlen bei RSA hat. Siehe auch
dazu Abschnitt 7.4.1.
11.4 Faktorisierung mit Differenzen von Quadraten 197

11.4 Faktorisierung mit Differenzen von Quadraten

Die Grundidee geht auf Fermat zurück und wurde bereits im Beweis zu Lem-
ma 9.3 im Zusammenhang mit dem Rabin-Verfahren verallgemeinert. Viele mo-
derne Faktorisierungsverfahren beruhen auf dieser Idee.


11.4.1 Das Verfahren von Fermat

Ist die Zahl N Produkt zweier ungef¤hr gleich großer Faktoren, so kann folgende
Strategie zum Erfolg führen:

Prüfe, ob N ∈ N.

W¤hle w = N.

Prüfe der Reihe nach, ob für i = 1, 2, . . . die Zahl yi = (w + i)2 ’ N eine
Quadratzahl ist.
√ √
Im Erfolgsfall ist N = (w + i ’ yi ) (w + i + yi ) ein Zerlegung von N.

Beispiel
Wir Faktorisieren die Zahl N = 3 240 809 nach der Methode von Fermat. Es ist

N = 1800 und man ¬ndet nach nur drei Schritten

18032 ’ N = 3 250 809 ’ 3 240 809 = 10 000 = 1002 .

Daher gilt N = (1803 ’ 100) (1803 + 100) = 1703 · 1903. Die beiden Faktoren mit
diesem Verfahren weiter zu faktorisieren, ist schon sehr mühsam.


11.4.2 Die gemeinsame Idee der Kettenbruchmethode, des quadratischen
Siebs und weiterer Verfahren

Wir schildern noch einmal die grunds¤tzliche Vorgehensweise aus dem Beweis
von Lemma 9.3. Sie stellt eine Verallgemeinerung des Verfahrens von Fermat dar.

Prüfe, ob N Potenz einer Primzahl ist (vgl. Aufgabe 8.6), falls ja “ Stop!

W¤hle x ∈ Z mit ggT(x, N) = 1 und berechne x2 modulo N.

Suche y ∈ Z mit x2 ≡ y2 (mod N).

Bestimme d := ggT(y ’ x, N).

Falls d ∈ {1, N} neues x, sonst gib d aus “ Stop!
198 11 Faktorisierung

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 ¬nden. 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
beein¬‚usst.


11.4.3 Die Kongruenzen

Um y zu konstruieren, werden Kongruenzen der folgenden Form produziert:
ν
ν
≡ (’1)ν01 p111 · · · pr r1 (mod N) ,
2
x1
ν ν
≡ (’1)ν02 p112 · · · pr r2 (mod N) ,
2
x2
. . .
. . .
. . .
ν
≡ (’1)ν0s p11s ν
· · · pr rs (mod N) ,
x2
s

wobei die pi Primzahlen aus einer sogenannten Faktorbasis sind. Zur Vereinfa-
chung der Schreibweise setzen wir p0 = ’1.
Die Verfahren unterscheiden sich in der Art, wie diese Kongruenzen gewonnen
werden. Gemeinsam ist allen, dass geeignete Zahlen xi 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 0

ν01 ν02 . . . . . . ν0s ⎜μ ⎟ ⎜0⎟
⎜ν11 ν12 . . . . . . ν1s ⎟ ⎜ . ⎟ ⎜ . ⎟
1
⎜ . ⎟ ⎜.⎟
⎜ ⎟
. ⎟ ⎜ . ⎟ ≡ ⎜ . ⎟ (mod 2)
(—) ⎜.
. ⎠⎜ ⎟ ⎜ ⎟
.
⎝. . ⎜ . ⎟ ⎜.⎟
. . .
⎝ . ⎠ ⎝.⎠.
.
νr1 νr2 . . . . . . νrs
μs 0

und μ j = 0 für mindestens ein j. Das System (—) kann man als lineares Glei-
chungssystem über dem Körper Z2 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 r 1
‘r νij μ j
μ
∏ ∏ pi
j=1
2
xi i
x := und y := ,
i=1 i=0
11.4 Faktorisierung mit Differenzen von Quadraten 199

so gilt x2 ≡ y2 (mod N), wie gewünscht. Dabei stellt die Wahl der μ j sicher, dass
‘r νij μ j für alle i gerade ist, also y ∈ N gilt.
j=1

Beispiel
Wir erzeugen ad hoc einige Kongruenzen für den Modul N = 91 über der Fak-
torbasis F = {’1, 2, 3, 5}:


≡ ’1 · 2 · 3 · 11 (mod 91)
52
≡ ’1 · 5 · 11 (mod 91)
62
≡ ’1 · 33 (mod 91)
82
≡ ’1 · 2 · 5 (mod 91)
92
≡ 2 · 3 · 5 (mod 91)
112
≡ ’1 · 2 · 19 (mod 91) .
122

Die ersten beiden und die letzte Kongruenz sind zu verwerfen. Das Gleichungs-
system aus der dritten bis fünften Kongruenz lautet
⎛ ⎞
0 ⎛ ⎞ ⎛⎞
1 1
μ 0
⎜0 1⎟ ⎝ 0 ⎠ ⎝ ⎠
1
⎜ ⎟ μ1 ≡ 0 (mod 2)
⎝3 1⎠
0
μ2 0
0 1 1

und hat als Lösung (1, 1, 1)T . Das führt auf

x = 8 · 9 · 11 = 792 , y = (’1) · 2 · 32 · 5 = ’90 und x2 ≡ y2 (mod 91) .

In der Tat gilt ggT(x + y, 91) = ggT(702, 91) = 13.

Bemerkung
Zum Lösen des linearen Gleichungssystems über Z2 bietet sich zun¤chst der
Gauß-Algorithmus an. Wenn die Parameter r, s sehr groß sind, geht das nicht
mehr. Andererseits enth¤lt die Koef¬zientenmatrix sehr viele Nullen, sodass spe-
zialisierte Verfahren erfolgversprechend sind.


11.4.4 Die Faktorbasis

In den beiden Verfahren, die wir behandeln werden, sind diejenigen Primzahlen
p2 , . . . , pr unterhalb einer gewissen Schranke B, für die N ein Quadrat modulo p
ist, zu bestimmen. Dazu kommen p0 = ’1 und p1 = 2. Diese Zahlen fassen wir
zur Faktorbasis zusammen:

F := {’1, 2 , p2 , . . . , pr } , wobei N ein Quadrat modulo pi , pi < B, für i > 1.
200 11 Faktorisierung

Die Bedingung N ist Quadrat modulo pi 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 pi ¤ B ist allen Faktorbasen gemeinsam.
Das folgende Lemma gibt Auskunft, wie man die pi für unseren Fall bestimmen
kann.

Lemma 11.1
Es sei p = 2 eine Primzahl. Das Element N ∈ Z — ist genau dann ein Quadrat, wenn
p
p’1
≡ 1 (mod p).
N 2



Beweis. Ist N = a2 ein Quadrat, so folgt die angegebene Kongruenz direkt aus
dem Satz 6.9 (a) von Euler, wenn man a2 für N einsetzt.
Nach dem Satz von Euler sind alle Elemente aus Z — Nullstellen des Polynoms
p
p’1 p’1
’1 + 1 = X p’1 ’ 1 .
X X
2 2


Davon gibt es insgesamt p ’ 1. Nach Korollar 9.2 sind die H¤lfte dieser Elemen-
p’1
te Quadrate. Weil die Quadrate alle Nullstellen von X 2 ’ 1 sind, und dieses
p’1
Polynom nicht mehr als 2 Nullstellen haben kann, müssen die Nichtquadrate
p’1
+ 1 sein. Das zeigt die Behauptung.
Nullstellen des Polynoms X 2



Bemerkung
Mit dem Legendre-Symbol und dem quadratischen Reziprozit¤tsgesetz kann man
ebenfalls entscheiden, ob N ein Quadrat in Z — ist oder nicht.
p

Bei der Erzeugung der Kongruenzen müssen gewisse Zahlen über der Faktorba-
sis in Primfaktoren zerlegt werden, wobei in manchen Verfahren nur Potenzen
pν von Primzahlen 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
ν
ν
x1 ≡ (’1)ν01 p111 · · · pr r1 · q (mod N) .
2


Natürlich nützt das so nichts, aber wenn eine zweite solche Kongruenz
ν ν
x2 ≡ (’1)ν02 p112 · · · pr r2 · q (mod N) .
2


gefunden wird, kann man die beiden Kongruenzen zu einer brauchbaren Kon-
gruenz kombinieren:

(x1 x2 q’1 )2 ≡ (’1)ν01 +ν02 p111 +ν12 · · · pr r1 +νr2 (mod N) ,
ν
ν


wobei q’1 modulo N zu bestimmen ist.
Wenn solche Primzahlen im Zerlegungsalgorithmus berücksichtigt werden, so
spricht man von der Large Prime Variation.
11.5 Die Kettenbruchmethode von Morrison-Brillhardt * 201

Bemerkung
Statt die beiden Kongruenzen mit dem großen Primteiler zu einer Kongruenz
zu kombinieren, kann man auch die Faktorbasis erweitern bzw. das lineare Glei-
chungssystem um entsprechende Zeilen erg¤nzen.

Wieder zeigt das Geburtstagsparadoxon (siehe Aufgabe 2.2), dass es gar nicht
so abwegig ist, die Large Prime Variation durchzuführen. Das Auftreten von zwei
solchen Kongruenzen mit demselben großen Primteiler ist keineswegs unwahr-
scheinlich (vgl. auch das Beispiel auf Seite 199).


11.5 Die Kettenbruchmethode von Morrison-Brillhardt *

Nach wie vor sei N eine zusammengesetzte natürliche Zahl. Wir dürfen ohne
Einschr¤nkung voraussetzen, dass N nicht Potenz einer Primzahl ist. Um Kon-
gruenzen wie im Abschnitt 11.4.3 zu bekommen, wurde vorgeschlagen, die Ket-

tenbruchentwicklung der irrationalen Zahl N zu benutzten.


N
11.5.1 Die Kettenbruchentwicklung von

Wir erinnern daran, wie die Kettenbruchentwicklung durch eine Rekursionsfor-
mel bestimmt wird (vgl. Abschnitt 7.5.4):
√ 1
x0 := N, a0 := x0 , xi+1 := , ai+1 := xi+1 .
xi ’ ai

Es ist dann a0 ; a1 , . . . der unendliche Kettenbruch zu N und die xi sind die
Restwerte.
Im vorliegenden Spezialfall einer Quadratwurzel erh¤lt man die Koef¬zienten
a0 , a1 , . . . der Kettenbruchentwicklung auch durch eine andere Methode. Wir de-
¬nieren rekursiv die Folgen (Ui ), (Vi ), (xi ) und (ai ) durch U0 := 0, V0 := 1 und
für i ∈ N0 :

N ’ Ui+1
2
N + Ui
(™) xi := , ai := xi , Ui+1 := ai Vi ’ Ui , Vi+1 := .
Vi Vi
Lemma 11.2
Für die Folgen (xi ) und (ai ) die aus der Rekursion (™) entstehen ist a0 ; a1 , a2 , . . . die

Kettenbruchentwicklung der irrationalen Zahl N, und für jedes i ∈ N0 ist xi der i-te
Restwert.

Beweis. Es gilt x0 = N, sodass die Startwerte übereinstimmen. Wir rechnen
√ √
N + Ui+1 ( N + Ui+1 ) Vi 1 1
Vi
=√
xi+1 = = =√ = .
xi ’ ai
N ’ Ui+1 N ’ Ui+1
2 N’ai Vi +Ui
Vi+1
Vi
202 11 Faktorisierung

Das ist die Rekursionsvorschrift für die Bestimmung der Koef¬zienten ai der Ket-

tenbruchentwicklung von N.
Die Rekursion (™) bietet einen vorteilhaften Weg, die Kettenbruchdarstellung zu
bestimmen, weil bei den Rechnungen fast nur kleine ganze Zahlen vorkommen.

Satz 11.3
Es sei N ∈ N kein Quadrat. Dann√ sind die Werte Ui und Vi aus (™) für alle i ∈ N

natürliche Zahlen, und es gilt Ui < N und Vi < 2 N.

Beweis. Wir beweisen die Behauptung durch Induktion nach i. Für i = 1 gilt:
√ √
U1 = N ∈Z und 0 < U1 < N,
√ √ √
2 2
V1 = N ’ U1 ∈ Z und 0 < N ’ < N’ N’1 < 2 N.
2
N

Das erledigt den Induktionsanfang. Sind nun für ein i ∈ N die Wert Ui , Vi und
Vi’1 ganzzahlig, so gilt auch Ui+1 ∈ Z. Weiter ist

N ’ Ui+1 N ’ Ui2
2
N ’ (ai Vi ’ Ui )2
= = = ’ a2 Vi + 2ai Ui
Vi+1 i
Vi Vi Vi
= Vi’1 ’ a2 Vi + 2ai Ui ∈ Z .
i

Wir nehmen nun an, dass für ein i ∈ N die Absch¤tzungen 0 < Ui < N und
Vi > 0 gelten. Nach Konstruktion ist
√ √
N + Ui Ui + Ui+1 N ’ Ui+1
(—) 0 < xi ’ ai = ’ = < 1,
Vi Vi Vi

weil die xi alle irrational sind. Das ergibt zun¤chst Ui+1 < N. Wir zeigen nun
Ui+1 > 0. Im Fall Vi > Ui folgt das direkt aus (™), weil ai ∈ N. Im Fall Vi ¤ Ui <
√ √
N erh¤lt man wegen (—) 0 < N ’ Vi < Ui+1 .

Das zeigt auch, dass N + Ui+1 positiv ist. Multipliziert man die Ungleichung
(—) mit diesem Ausdruck, so ergibt sich in der Mitte die De¬nition von Vi+1 , und

U +U
es folgt Vi+1 > 0. Schließlich hat man Vi = i a i+1 < 2 N. Damit sind alle
i
Behauptungen bewiesen.
Aus Lemma 11.2 und Satz 11.3 ergibt sich eine einfache Folgerung, die wir als

<<

. 7
( 9)



>>