WikiDer > Lenstra .Algorithmus

Es Algorithmus von Lenstra ist ein Algorithmus das wurde entwickelt von Hendrik Lenstra, um ein positives zu machen gerade Zahl zu faktorisieren, d.h. auch faktorisieren. Dazu verwendet der Algorithmus a elliptische Kurve. Deshalb wird dieser Algorithmus als ECM (Elliptic Curve Method) bezeichnet. Der ECM ist ein sogenannter deterministischer Algorithmus. Dies bedeutet, dass einmal zufällig eine Wahl getroffen wurde (zum Beispiel die Wahl für eine elliptische Kurve), wird der Algorithmus deterministisch, d.h. eindeutig, ausgeführt.

Andere Faktorisierungsalgorithmen

ECM ist der drittschnellste Weg, um die Faktorisierung einer Zahl zu finden. Der schnellste Weg ist der Zahlenfeldsieb, gefolgt von der quadratisches Sieb. Bei diesen Methoden handelt es sich um sogenannte 'probabilistische' Algorithmen, die Wahrscheinlichkeiten verwenden. Es ist jedoch nicht garantiert, dass ein Faktor innerhalb der erwarteten Zeit erhalten wird, der nicht trivial ist. ECM gilt als Faktorisierung mit einem hohen erwarteter Wert, die sich am besten zum Auffinden eines relativ kleinen Faktor. Häufig wird ECM verwendet, um relativ kleine Faktoren aus einer sehr großen Zahl mit vielen Faktoren zu entfernen. Wenn die verbleibende Zahl immer noch a . ist zusammengesetzte Zahl es hat nur große Faktoren und es müssen andere Techniken verwendet werden, oder es ist fast unmöglich, Faktoren zu finden. Es ist derzeit noch der beste Algorithmus, um Teiler einer Zahl mit bis zu 25 Stellen zu finden (ca. 80 .). bisschen). Hier wird die Zeit zum Finden eines Faktors mehr von der Größe des kleinsten Faktors bestimmt ${displaystyle p}$ als um die Größe der zu faktorisierenden Zahl ${displaystyle n}$ selbst. Am 24. August 2006 faktorisierte B. Dodson mithilfe von ECM eine 67-stellige Zahl. Zwar ist die Chance, einen Faktor zu finden, umso größer, je mehr Kurven verwendet werden, aber die Anzahl der verwendeten Kurven verläuft (leider) nicht linear mit der Stellenzahl der zu faktorisierenden Zahl.

Motivation für ECM

Tatsächlich ist das ECM eine Erweiterung von Pollards p-1-Methode.

Angenommen, die zu faktorisierende Zahl ${Displaystil N}$ ist das Produkt zweier Primfaktoren ${displaystyle p}$ und ${Anzeigestil q}$, So ${Anzeigestil N=pcdotq}$.

Pollards Methode funktioniert eigentlich nur, wenn ${Anzeigestil p-1}$ oder ${displaystyle q-1}$ sogenannt ${Anzeigestil B}$-glatt ist, d.h. jeder Primfaktor ist weniger als ${Anzeigestil B}$. Ist dies nicht der Fall, ist es unmöglich, mit Pollards Methode eine Zerlegung zu finden. Da das ECM mit Punktgruppen auf einer elliptischen Kurve arbeitet, besteht eine größere Chance auf das gewünschte Ergebnis.

Lenstras Algorithmus zur Faktorisierung mit der ECM

Der ECM-Algorithmus von Lenstra, um einen Faktor einer bestimmten natürlichen Zahl zu finden ${displaystyle n}$ funktioniert wie folgt:

1. Wählen Sie eine beliebige elliptische Kurve über ${displaystyle mathbb {Z} /nmathbb {Z} }$, gegeben durch die Gleichung

   ${displaystyle y^{2}=x^{3} ax b}$.

2. Wähle einen nicht trivialen Punkt ${Anzeigestil P}$ auf dieser Kurve.
3. Wähle eine Nummer ${Anzeigestil B}$, nicht zu groß und nicht zu klein. Diese Nummer wird verwendet als ${Anzeigestil B}$-glatt Nummer.
4. Finden ${displaystyle k=mathrm {kgv} (1,2,ldots,B)}$ (kleinstes gemeinsames Vielfaches). Für die weitere Berechnung ist es oft sinnvoll und daher üblich, ${displaystyle k}$binär schreiben.
5. Bestimmen ${Anzeigestil kP}$ unter Verwendung der Additionen und anderer Berechnungen, wie für elliptische Kurven definiert.
6. Bestimmen Sie für jede Zugabe ${displaystyle lambda ={frac {y_{1}-y_{2}}{x_{1}-x_{2}}}}$
7. Bestimmen ${displaystyle g=mathrm {ggd} ((x_{1}-x_{2}),n)}$ (größter gemeinsamer Teiler).
8. wenn ${displaystyle wurde in {1,n}}$, ist ${displaystyle g}$ ein nicht-trivialer Faktor von ${displaystyle n}$. Wenn dies nicht der Fall ist, dann ein anderer Punkt ${Anzeigestil P}$ oder eine andere elliptische Kurve gewählt werden.

Beispiel

der Zahl ${Anzeigestil n=5959}$ ein Faktor wird mit ECM von Lenstra gesucht.

1. Wählen Sie als elliptische Kurve
   

   ${Anzeigestil y^{2}=x^{3} 1201x 1}$ Über ${displaystyle mathbb {Z} /5959,mathbb {Z} }$

2. Wählen Sie den Punkt auf dieser Kurve ${Anzeigestil P=(0.1)}$.
3. nehmen ${Anzeigestil B=20}$.
4. Dann ist ${displaystyle k=mathrm {kgv} (1,2,ldots,20)=232792560=1101111000000010000111110000}$ (binär)
5. Berechnung ${Displaystil 2^{i}cdot P=2^{i}cdot(0.1)}$ vor dem

   ${Anzeigestil iin K={4,5,6,7,8,13,21,22,23,24,26,27}}$

6. Dann ist ${displaystyle kP=sum _{iin K}2^{i}P}$
7. Berechnen Sie Punkte von jedem Paar

   ${displaystyle lambda ={frac {y_{1}-y_{2}}{x_{1}-x_{2}}}}$

8. Bestimmen Sie für jedes Punktpaar ${displaystyle g=mathrm {ggd} ((x_{1}-x_{2}),n)}$
9. Es stellt sich heraus, dass keiner von ${displaystyle g}$ eine nicht triviale Lösung gefunden wird, also kein Faktor von 5959 gefunden wird.

Mit einer anderen elliptischen Kurve

${Anzeigestil y^{2}=x^{3} 389x 1}$ Über ${displaystyle mathbb {Z} /5959,mathbb {Z} }$

und der punkt ${Anzeigestil P=(0,1)}$ auf dieser Kurve gelangt man zu den Punkten ${Anzeigestil Q=(2051,5273)}$ und ${Anzeigestil R=(637.1292)}$. Addition in der für elliptische Kurven definierten Weise ergibt

${displaystyle lambda ={frac {y_{1}-y_{2}}{x_{1}-x_{2}}}={frac {5273-1292}{2051-637}}={frac {3981}{ 1414}}}$.

Dann ist

${displaystyle g=mathrm {ggd} (1414,5959)=101}$,

woraus der nicht-triviale Faktor 101 von 5959 folgt.