Faktorisierung mit Hilfe elliptischer Kurven

Lenstra hat einen Faktorisierungsalgorithmus entworfen, der diese elliptischen Kurven benutzt. Angenommen n sei eine große natürliche Zahl, die nicht durch 2 und 3 teilbar ist und von der vermutet werde, daß sie einen Primfaktor p besitzt. Nun kann nicht in tex2html_wrap_inline794 gerechnet werden, wenn p nicht bekannt ist. Allerdings gibt es für p | n einen Ringhomomorphismus

displaymath800

und es kann versucht werden, zunächst mit tex2html_wrap_inline428 mod n zu rechnen. Solange es sich um Additionen und Multiplikationen handelt, ist das ohne weiteres erlaubt. Das einzige Problem besteht darin, daß in den Additions- und Verdoppelungsformeln für die Punkte auf E durch die Nenner tex2html_wrap_inline808 bzw. tex2html_wrap_inline810 dividiert wird. In tex2html_wrap_inline784 ist diese Division genau dann durchführbar, wenn diese Nenner zu n teilerfremd sind. Die Berechnungen von tex2html_wrap_inline816 für tex2html_wrap_inline818 und tex2html_wrap_inline820 scheitern also genau dann, wenn ein größter gemeinsamer Teiler von n und tex2html_wrap_inline808 oder tex2html_wrap_inline810 gefunden wird. Wenn dieser nicht zufällig gerade gleich n ist, ist aber ein nicht trivialer Faktor von n gefunden. Auf Faktor und Kofaktor wird dann ein Primzahltest angewandt und das Verfahren gegebenenfalls wiederholt.

Diese ziemlich vagen Bemerkungen lassen sich zu einem praktikablen Verfahren verdichten, bei dem es natürlich genauer darum geht, mit welchen elliptischen Kurven und Punkten gearbeitet werden soll. Für das sich dabei unter gewissen weiteren Annahmen ergebende Verfahren ergibt sich eine mittlere Laufzeit von

displaymath832

wobei tex2html_wrap_inline834 eine Funktion ist mit tex2html_wrap_inline836 .

Seit 1990 ist von Pollard eine andere Faktorisierungsmethode, das
Zahlkörpersieb entwickelt worden, das asymptotisch schneller ist als Lenstras Verfahren. (für Zahlen n mit tex2html_wrap_inline840 bits gilt das RSA-Verfahren damit als unbrauchbar !). Die elliptischen Kurven sind aber auch in diesem Zusammenhang noch nicht aus dem Blickfeld.