i
i
main”—2013/4/10—15:19—page146—#158
i
i
i
i
i
i
146 Elliptische Kurven
in Z/mZ gilt. Der folgende Satz stellt einen Zusammenhang zwischen der Verknüp-
fung auf beiden Pseudokurven dar. Das Hauptproblem hierbei ist, dass
P + Q in
7
E(Z/nZ)
eventuell durch andere Vorschriften berechnet werden könnte als (P mod
m)+(Q mod m)
in
7
E(Z/mZ)
.Wirzeigen,dassP +Q in diesen Fällen nicht definiert
ist.
Satz 5.7. Sei
m>1 ein Teiler von n und seien P,Q
7
E(Z/nZ) Punkte, für die P +Q
definiert ist. Dann ist (P mod m) + (Q mod m) in
7
E(Z/mZ)
definiert und es gilt
(P mod m) +(Q mod m) = (P + Q) mod m
Beweis. Wir können ohne Einschränkung P O und Q O annehmen. Sei P =
(x
1
,y
1
) und Q = (x
2
,y
2
). Der Ringhomomorphismus mod m : Z/nZ Z/mZ
ist kompatibel mit der Inversenbildung, d. h., für ggT(x, n) = 1 gilt
x
1
mod m = (x mod m)
1
wobei auf der linken Seite der Gleichung das Inverse modulo n gemeint ist und auf
der rechten das Inverse in
Z/mZ. Wenn wir zur Berechnung der Punkte in
7
E(Z/nZ)
und in
7
E(Z/mZ)
die selben Rechenvorschriften anwenden, gilt also die Aussage,
dass wir
mod m in den Rechnungen hineinziehen können. Insbesondere ist dann
(P mod m) +(Q mod m) definiert. Die verbleibenden Fälle sind:
(a)
x
1
≡ x
2
mod n und x
1
x
2
mod m
(b) x
1
x
2
mod n, y
1
y
2
≡ 0modn und y
1
≡−y
2
mod m
(c) x
1
x
2
mod n und y
1
≡±y
2
mod n
In Fall (a) ist P+Q nicht definiert, weil x
2
x
1
durch m teilbar und deshalb modulo n
nicht invertierbar ist. Damit ist die Voraussetzung der Aussage nicht erfüllt. In Fall (b)
ist
P+Q ebenfalls nicht definiert, denn es gilt 2y
1
y
1
+y
2
mod n und m | y
1
+y
2
.
Deshalb ist
2y
1
nicht invertierbar. Wenn der Fall (c) eintritt, ist P + Q auch nicht
definiert.
5.2.3 Faktorisierung mit elliptischen Kurven
Bei der Faktorisierung von Zahlen n sucht man nach nichttrivialen Teilern von n,
d. h., man versucht ein
m ∈{2,...,n1} zu finden mit m | n. Auch wenn es kei-
nen Beweis dafür gibt, gilt Faktorisierung von Binärzahlen als ein Problem, welches
nicht in polynomieller Zeit lösbar ist. Deshalb bemüht man einen Algorithmus zur
Faktorisierung erst dann, wenn man sicher weiß, dass eine Zahl keine Primzahl ist.
Wir haben bereits mehrere Primzahltests kennen gelernt. Ein weiterer typischer Vor -
bereitungsschritt ist kleine Teiler durch Probedivision auszuschließen. Die Idee, el-
liptische Kurven zur Faktorisierung einzusetzen, stammt von Hendrik Willem Lenstra
Jr. (geb. 1949). Wir stellen im Fol genden eine probabilistische Variante davon vor. Die
i
i
main”—2013/4/10—15:19—page147—#159
i
i
i
i
i
i
Anwendungen elliptischer Kurven 147
Grundidee hierzu ist die sogenannte (p 1)-Methode von Pollard, welche wir hier
noch einmal kurz wiederholen. Sei
n eine zusammengesetzte Zahl, sei p ein Prim-
teiler von
n und sei a N mit ggT(a, n) = 1 . W ir nehmen an, dass k N ein
Vielfaches von
p 1 ist. Nach dem kleinen Satz von Fermat gilt a
p1
1modp
und damit auch
a
k
1modp
Nun gilt p | a
k
1 und p | n. Falls a
k
≡ 1modn ist, liefert ggT(a
k
1,n)einen
nichttrivialen Teiler von
n. Man hat bei diesem Verfahren gewisse Wahlmöglichkeiten
für
a und k. Eine mögliche Strategie für die Wahl von k ist zu hoffen, dass p 1 in
kleine Primteiler zerfällt. Da wir
p zu diesem Zeitpunkt noch nicht kennen, bietet es
sich z. B. an
k =
C
4
log n
log
5
zu hlen, wobei C eine Zahl ist, von der wir erwarten, dass sie größer als jeder Prim-
teiler von
p 1 ist. Damit sich k in einer vernünftigen Größenordnung bewe gt, darf
C nicht zu groß sein. Bei der Wahl von a bieten sich beliebige Werte aus (Z/nZ)
an. Der Nachteil des Verfahrens ist, dass sich die Struktur von Z/nZ nicht verändern
lässt. Wenn beispielsweise
p 1 für keinen Teiler p von n aus ausschließlich kleinen
Primteilern besteht, führt Pollards
(p 1)-Algorithmus nicht zum Erfolg. Hier kom-
men die Pseudokurven ins Spiel, denn zu jedem
n gibt es sehr viele Pseudokurven
7
E(Z/nZ)
.
Bei Lenstras Verfahren wählt man auch zunächst eine Schranke
C und konstru-
iert daraus wie eben eine Zahl
k.JegrößerdieZahlC ist, desto besser sind unse-
re Chancen, einen Teiler zu finden. Allerdings dauern dann die Rechnungen auch
länger. Die Idee ist nun, zufällig eine Pseudokurve
7
E(Z/nZ)
und einen Punkt P
7
E(Z/nZ)
auf der Kurve zu wählen. Dann versucht man
k · P = P ··+P

k mal
zu berechnen. Die Hoffnung ist, dass bei diesem Versuch das Ergebnis einer Verknüp-
fung einmal nicht definiert ist. Dies liefert uns dann einen nichttrivialen Teiler von
n.
Sollte die Berechnung von
k ·P gelingen, dann wiederholen wir diesen Schritt mit ei-
ner neuen Pseudokurve und einem neuen Punkt auf dieser K urve. Dies ist bei Pollards
(p 1)-Algori thmus nicht glich.
Kommen wir nun zu den Details des Verfahrens. Man bestimmt zunächst zufällige
A, x, y ∈{0,...,n1} und berechnet dann B durch die Vorschrift:
B = y
2
x
3
Ax mod n
Wenn nun ggT(4A
3
+ 27B
2
,n) 1 gilt, dann haben wir entweder einen nichttri-
vialen Teiler von
n gefunden oder wir wiederholen diesen Prozess. Wenn wir zuerst
A und B bestimmen würden, wäre es schwieriger einen (zufälligen) Punkt auf der

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.