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 gerechnet werden, wenn p nicht bekannt ist. Allerdings gibt es für p | n einen Ringhomomorphismus
und es kann versucht werden, zunächst mit
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
bzw.
dividiert wird. In
ist diese Division genau dann durchführbar, wenn diese Nenner zu
n teilerfremd sind. Die Berechnungen von
für
und
scheitern also genau dann, wenn ein größter gemeinsamer Teiler
von n und
oder
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
wobei
eine Funktion ist mit
.
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
bits gilt das RSA-Verfahren damit als unbrauchbar !). Die elliptischen
Kurven sind aber auch in diesem Zusammenhang noch nicht aus dem Blickfeld.