Elliptische Kurve von Lenstra factorization oder die elliptische Kurve factorization Methode (ECM) sind ein schneller Subexponentiallaufzeit-Algorithmus für die ganze Zahl factorization, der elliptische Kurven verwendet. Für das allgemeine Zweck-Factoring ist ECM die dritte schnellste bekannte Factoring-Methode. Das zweite schnellste ist das vielfache polynomische quadratische Sieb, und das schnellste ist das allgemeine Sieb des numerischen Feldes. Der Lenstra elliptische Kurve factorization wird nach Hendrik Lenstra genannt.

Praktisch das Sprechen, ECM wird als ein spezieller Zweck-Factoring-Algorithmus betrachtet, weil es am passendsten ist, um kleine Faktoren zu finden., es ist noch der beste Algorithmus für Teiler, nicht außerordentlich 20 bis 25 Ziffern (ungefähr 64 bis 83 Bit) überschreitend, weil seine Laufzeit durch die Größe des kleinsten Faktors p aber nicht durch die Größe der Nummer n beherrscht wird, um factored zu sein. Oft wird ECM verwendet, um kleine Faktoren von einer sehr großen ganzen Zahl mit vielen Faktoren zu entfernen; wenn die restliche ganze Zahl noch zerlegbar ist, dann hat sie nur große Faktoren und ist factored das Verwenden allgemeiner Zweck-Techniken. Der größte Faktor hat das Verwenden gefunden ECM hat bis jetzt 73 Ziffern und wurde am 6. März 2010 von Joppe Bos, Thorsten Kleinjung, Arjen Lenstra und Peter Montgomery entdeckt. Das Steigern der Zahl von geprüften Kurven verbessert die Chancen, einen Faktor zu finden, aber sie sind mit der Zunahme in der Zahl von Ziffern nicht geradlinig.

Die elliptische Kurve von Lenstra factorization

Die Lenstra elliptische Kurve factorization Methode, einen Faktor der gegebenen Nummer n zu finden, arbeitet wie folgt:

: Wenn der Hang der Form u/v mit gcd (u, n) =1 ist, dann bedeutet v=0 (mod n), dass das Ergebnis - Hinzufügung, der Punkt an der Unendlichkeit auf der Kurve sein wird. Jedoch, wenn gcd (v, n) weder 1 noch n ist, dann - wird Hinzufügung keinen bedeutungsvollen Punkt auf der Kurve erzeugen, die zeigt, dass unsere elliptische Kurve nicht ist, ist eine Gruppe (mod n), aber, wichtiger für jetzt, gcd (v, n) ein nichttrivialer Faktor von n.

• Wenn wir im Stande gewesen sind, alle Berechnungen oben zu beenden, ohne auf non-invertible Elemente zu stoßen (mod n), dann müssen wir mit einer anderen Kurve und Startpunkt noch einmal versuchen.
• Wenn wir in einer Bühne gefunden haben (der Punkt an der Unendlichkeit auf der elliptischen Kurve), andererseits sollten wir mit einer neuen Kurve und Startpunkt anfangen, da das Nullelement für so nach diesem Punkt ist, den wir gerade wiederholen würden.
• Wenn wir auf einen gcd (v, n) in einer Bühne gestoßen sind, die weder 1 noch n war, dann werden wir getan: Es ist ein nichttrivialer Faktor von n.

</ol>

Die Zeitkompliziertheit hängt von der Größe des Faktors ab und kann durch O (e) vertreten werden, wo p der kleinste Faktor von n, oder in der L-Notation ist.

Warum arbeitet der Algorithmus?

Wenn p und q zwei Hauptteiler von n sind, dann bezieht y = x + Axt + b (mod n) dieselbe Gleichung auch (mod p) und (mod q) ein. Diese zwei kleineren elliptischen Kurven mit - Hinzufügung sind jetzt echte Gruppen. Wenn diese Gruppen N und N Elemente beziehungsweise haben, dann für jeden Punkt P auf der ursprünglichen Kurve, durch den Lehrsatz von Lagrange, k> 0 ist solch minimal, der auf der Kurve (mod p) andeutet, dass k N teilt; außerdem. Die analoge Behauptung hält für q. Wenn die elliptische Kurve zufällig, dann N gewählt wird und N Zufallszahlen in der Nähe von p+1 und q+1 beziehungsweise (sieh unten) sind. Folglich ist es unwahrscheinlich, dass die meisten Hauptfaktoren von N und N dasselbe sind, und es ziemlich wahrscheinlich ist, dass, während wir eP rechnen werden, wir auf einen kP stoßen werden, der (mod p), aber nicht (mod q), oder umgekehrt ist. Wenn das der Fall ist, besteht kP auf der ursprünglichen Kurve nicht, und in der Berechnung haben wir einen v mit irgendeinem gcd (v, p) =p oder gcd (v, q) =q, aber nicht beide gefunden. D. h. gcd (v, n) hat einen nichttrivialen Faktor von n gegeben.

ECM ist an seinem Kern eine Verbesserung des älteren p &minus; 1 Algorithmus. Der p &minus; 1 Algorithmus findet Hauptfaktoren p solch dass p &minus; 1 ist b-powersmooth für kleine Werte von b. Für jeden e, ein Vielfache von p &minus; 1, und irgendwelcher ein relativ erster zu p durch den kleinen Lehrsatz von Fermat haben wir &equiv; 1 (mod p). Dann gcd (&minus; 1, wird wahrscheinlich n) einen Faktor von n erzeugen. Jedoch scheitert der Algorithmus, wenn p-1 große Hauptfaktoren hat, wie für Zahlen der Fall ist, die starke Blüte zum Beispiel enthalten.

ECM kommt um dieses Hindernis durch das Betrachten der Gruppe einer zufälligen elliptischen Kurve über das begrenzte Feld Z herum, anstatt die multiplicative Gruppe von Z zu denken, der immer Auftrag p &minus hat; 1.

Die Ordnung der Gruppe einer elliptischen Kurve über Z ändert sich (ganz zufällig) zwischen p + 1 &minus; 2&radic;p und p + 1 + 2&radic;p durch den Lehrsatz von Hasse, und wird wahrscheinlich für einige elliptische Kurven glatt sein. Obwohl es keinen Beweis gibt, dass eine glatte Gruppenordnung im Hasse-Zwischenraum, durch das Verwenden heuristischer probabilistic Methoden, des Canfield-Erdős-Pomerance Lehrsatzes mit angemessen optimierten Parameter-Wahlen und der L-Notation gefunden wird, können wir annehmen, L&radic;2 / 2, &radic;2 Kurven vor dem Bekommen einer glatten Gruppenordnung zu versuchen. Diese heuristische Schätzung ist in der Praxis sehr zuverlässig.

Ein Beispiel

Das folgende Beispiel ist von mit einigen hinzugefügten Details.

Wir wollen zum Faktor n=455839. Wollen wir die elliptische Kurve y = x + 5x - 5, mit dem Punkt P = (1,1) darauf wählen, und wollen wir versuchen zu rechnen (10!) P.

Zuerst rechnen wir 2P. Der Hang der Tangente-Linie an P ist s = (3x+5) / (2y) =4, und dann sind die Koordinaten 2P = (x , y ) x  = s-2x=14 und y  = s (x-x )-y=4 (1-14)-1 =-53, alle Zahlen verstanden (mod n). Um gerade zu überprüfen, dass das 2P tatsächlich auf der Kurve ist: (-53) =2809=14+5 · 14-5.

Dann rechnen wir 3 (2P). Der Hang der Tangente-Linie an 2P ist s = (3 · 14+5) / (2 (-53)) =-593/106 (mod n). Das Verwenden des Euklidischen Algorithmus: 455839=4300 · 106+39, dann 106=2 · 39+28, dann 39=28+11, dann 28=2 · 11+6, dann 11=6+5, dann 6=5+1. Folglich gcd (455839,106) =1, und umgekehrt (eine Version des verlängerten Euklidischen Algorithmus) arbeitend: 1=6-5=2·6-11=2·28-5·11=7·28-5·39=7·106-19·39=81707·106-19·455839. Folglich 106=81707 (mod 455839), und-593/106 =-133317 (mod 455839). In Anbetracht dieses s können wir die Koordinaten 2 (2P) schätzen, wie wir oben getan haben: 4P = (259851,116255). Um gerade zu überprüfen, dass das tatsächlich ein Punkt auf der Kurve ist: y=54514=x+5x-5 (mod 455839). Danach können wir rechnen.

Wir können 4 ähnlich rechnen! P, und so weiter, aber 8! P verlangt das Umkehren 599 (mod 455839). Der Euklidische Algorithmus gibt das 455839 ist durch 599 teilbar, und wir haben einen factorization 455839=599 gefunden · 761.

Der Grund, dass das gearbeitet hat, besteht darin, dass die Kurve (mod 599) 640=2 hat · 5 Punkte, während (mod 761) es 777=3 hat · 7 · 37 Punkte. Außerdem, 640 und 777 sind die kleinsten positiven ganzen Zahlen k solch das auf der Kurve (mod 599) und (mod 761) beziehungsweise. Seitdem 8! ist ein Vielfache 640, aber nicht ein Vielfache 777, wir haben auf der Kurve (mod 599), aber nicht auf der Kurve (mod 761), folglich hat die wiederholte Hinzufügung hier unten gebrochen, den factorization nachgebend.

Der Algorithmus mit projektiven Koordinaten

Bevor wir das projektive Flugzeug über / ~ denken, zuerst auf den 'normalen' projektiven Raum einen Blick werfen. Jetzt, anstatt die Punkte zu studieren, werden die Linien durch den Ursprung studiert. Die Linie kann ein Nichtnullpunkt vertreten werden, wenn Sie die Gleichwertigkeitsbeziehung ~ darauf, gegeben verwenden durch: Wenn, und nur wenn dort eine solche Nichtnullzahl dass besteht, und. Wegen dieser Gleichwertigkeitsbeziehung wird der Raum ein Flugzeug genannt. Im projektiven Flugzeug sind Punkte, die dadurch angezeigt sind, 'dasselbe' als Linien in einem dreidimensionalen Raum, die den Ursprung durchgehen. Bemerken Sie, dass der Punkt hier nicht besteht, weil diese keine Linie vertreten. Jetzt bemerken wir, dass fast alle Linien zum stufigen gehen, außer von der Linienparallele bis dieses Flugzeug. Das stellt sich auf sind im projektiven Flugzeug die 'Punkte der Unendlichkeit', die im affine stufigen oben verwendet werden.

Im Algorithmus wird nur die Gruppenstruktur einer elliptischen Kurve über das Feld verwendet. Deshalb brauchen wir nicht notwendigerweise das Feld. Ein begrenztes Feld wird auch eine Gruppenstruktur auf der elliptischen Kurve zur Verfügung stellen. Jedoch dieselbe Kurve und Operation über / ~ mit denkend, gibt nicht eine Blüte keine Gruppe. Die Elliptische Kurve-Methode macht von den Misserfolg-Fällen des Hinzufügungsgesetzes Gebrauch.

Wir setzen jetzt den Algorithmus in projektiven Koordinaten fest. Das neutrale Element wird dann durch den Punkt in der Unendlichkeit gegeben. Lassen Sie, eine (positive) ganze Zahl zu sein und die elliptische Kurve (eine Reihe von Punkten mit einer Struktur darauf) zu denken.

1. Picken Sie darin auf und lassen Sie, der Null ungleich zu sein.
2. Rechnen. Die elliptische Kurve ist dann in der Form von Weierstrass gegeben nach und nach mit projektiven Koordinaten, die die elliptische Kurve durch die homogenous Gleichung gegeben wird. Es hat den Punkt.
3. Wählen Sie einen upperbound für diese elliptische Kurve. Bemerkung: Sie werden nur Faktoren finden, wenn die Gruppenordnung der elliptischen Kurve über (angezeigt durch #) B-smooth ist, was bedeutet, dass alle Hauptfaktoren # weniger oder gleich dem sein müssen.
4. Rechnen.
5. Rechnen Sie (k Zeiten) im Ring. Bemerken Sie, dass, wenn # ist - glätten und erst ist (und deshalb ein Feld ist) das. Jedoch, wenn nur # B-smooth für einen Teiler dessen ist, könnte das Produkt (nicht 0:1:0) sein, weil Hinzufügung und Multiplikation nicht bestimmt sind, wenn nicht erst ist. In diesem Fall kann ein nichttrivialer Teiler gefunden werden!
6. Wenn nicht, dann gehen Sie zum Schritt 2 zurück. Wenn das wirklich vorkommt, dann werden Sie das bemerken, wenn Sie das Produkt vereinfachen werden.

Im Punkt 5 wird es gesagt, dass unter den richtigen Verhältnissen ein nichttrivialer Teiler gefunden werden kann. Wie hingewiesen, im Artikel von Lenstra (Ganze Factoring-Zahlen mit Elliptischen Kurven) braucht die Hinzufügung die Annahme. Wenn nicht und verschieden sind (sonst Hinzufügungsarbeiten ähnlich, aber etwas verschieden), dann arbeitet Hinzufügung wie folgt:

• Zu rechnen:

.

Wenn Hinzufügung scheitert, wird das das erwartete Rechnen sein scheitert. Insbesondere weil nicht immer berechnet werden kann, wenn nicht erst ist (und deshalb nicht ein Feld ist). Ohne davon Gebrauch zu machen, ein Feld zu sein, konnte man rechnen:

• und, vereinfachen Sie wenn möglich.

Diese Berechnung ist immer gesetzlich, und wenn die gcd - damit koordinieren, ist 1 oder so ungleich, wenn Vereinfachung scheitert, dann wird ein nichttrivialer Teiler dessen gefunden.

Gedrehte Kurven von Edwards

Der Gebrauch von Kurven von Edwards braucht weniger Modulmultiplikationen und weniger Zeit dann der Gebrauch von Kurven von Montgomery oder Kurven von Weierstrass (andere verwendete Methoden). Das Verwenden von Kurven von Edwards können Sie auch mehr Blüte finden.

Definition:

Lassen Sie, ein Feld zu sein, in dem, und damit lassen. Dann wird die gedrehte Kurve von Edwards durch gegeben

Eine Kurve von Edwards ist eine gedrehte Kurve von Edwards in der.

Es gibt fünf bekannte Weisen, eine Reihe des Punkts auf einer Kurve von Edwards zu bauen: der Satz von Affine-Punkten, der Satz von projektiven Punkten, der Satz von umgekehrten Punkten, der Satz von verlängerten Punkten und der Satz von vollendeten Punkten.

Durch den Satz von Affine-Punkten wird gegeben:.

Durch das Hinzufügungsgesetz wird gegeben. Der Punkt (0,1) ist sein neutrales Element, und die Verneinung dessen ist.

Die anderen Darstellungen werden ähnlich dem definiert, wie die projektive Kurve von Weierstrass aus dem affine folgt.

Jede elliptische Kurve in der Form von Edwards hat einen Punkt des Auftrags 4. So ist die Verdrehungsgruppe einer Kurve von Edwards entweder zu isomorph oder zu.

Die interessantesten Fälle für ECM sind und, da sie die Gruppenordnungen der Kurve modulo Blüte zwingen, durch 12 und 16 beziehungsweise teilbar zu sein.

Die folgenden Kurven haben eine Verdrehungsgruppe, die isomorph ist zu:

• mit dem Punkt wo und

• mit dem Punkt wo und

Jede Kurve von Edwards mit einem Punkt des Auftrags 3 kann in den Wegen geschrieben werden, die oben gezeigt sind.

Kurven mit der Verdrehungsgruppe, die dazu isomorph ist, und können auf http://eprint.iacr.org/2008/016 der Seite 30-32 gefunden werden.

Bühne 2

Der obengenannte Text ist über die erste Stufe der elliptischen Kurve factorisation. Dort hofft man, einen Hauptteiler solch zu finden, der das neutrale Element dessen ist.

In der zweiten Bühne hofft man, einen Hauptteiler solch gefunden zu haben, der kleine Hauptordnung darin hat.

Wir hoffen die Ordnung, zwischen zu sein, und, wo in der Bühne 1 bestimmt wird und neuer Parameter der Bühne 2 ist.

Wenn man

für eine kleine Ordnung dessen überprüft, kann durch die Computerwissenschaft modulo für jede Blüte getan werden.

Erfolgswahrscheinlichkeit mit EECM-MPFQ

Für Beschleunigungstechniken mit Kurven von Edward und Durchführungsergebnissen, sieh: http://eprint.iacr.org/2008/016 Seite 30-32.

Hyperelliptische Kurve-Methode (HECM)

Es gibt neue Entwicklungen im Verwenden hyperelliptischer Kurven zu ganzen Faktor-Zahlen. Verhätscheln Sie Shows in seinem Artikel (2010), dass man eine hyperelliptische Kurve mit der Klasse zwei bauen kann (so eine Kurve mit

des Grads 5), der dasselbe Ergebnis wie das Verwenden zwei 'normaler' elliptischer Kurven zur gleichen Zeit gibt. Indem es von der Kummer-Oberflächenberechnung Gebrauch gemacht wird, ist effizienter. Die Nachteile der hyperelliptischen Kurve (gegen eine elliptische Kurve) werden durch diese alternative Weise ersetzt zu rechnen. Verhätscheln Sie deshalb grob Ansprüche, dass das Verwenden hyperelliptischer Kurven für factorization nicht schlechter ist als das Verwenden elliptischer Kurven.

Siehe auch

• UBASIC für das praktische Programm (ECMX).

Links

• Factorization mit der Elliptischen Kurve-Methode, Java applet, der ECM verwendet und auf das Selbstinitialisierende Quadratische Sieb umschaltet, wenn es schneller ist.
• GMP-ECM, eine effiziente Durchführung von ECM.
• ECMNet, eine leichte Client/Server-Durchführung, die mit mehreren Factorization-Projekten arbeitet.
• pyecm, eine Pythonschlange-Durchführung von ECM. Viel schneller mit psyco und/oder gmpy.
• Verteiltes Rechenprojekt yoyo@Home ist Subprojekt-ECM ein Programm für die Elliptische Kurve Factorization, der durch einige Projekte verwendet wird, Faktoren für die verschiedene Art von Zahlen zu finden.