Faktorisierungsmethode von Lehman

Die Faktorisierungsmethode von Lehman ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie, insbesondere der algorithmischen Zahlentheorie. Der Algorithmus ermittelt einen nichttrivialen Teiler einer positiven ganzen Zahl, wenn einer existiert. Findet er keinen solchen Teiler, dann ist die vorgegebene Zahl eine Primzahl. Die Faktorisierungsmethode von Lehman ist somit sowohl ein Faktorisierungsverfahren als auch ein Primzahltest. Sie wurde im Jahr 1974 von Russell Sherman Lehman in einer Arbeit mit dem Titel „Factoring Large Integers“ veröffentlicht. Sowohl zur Faktorisierung als auch zur Überprüfung der Primzahleigenschaft gibt es bessere Verfahren. Die Faktorisierungsmethode von Lehman war jedoch der erste deterministische Algorithmus, der vollständig analysiert werden konnte und der asymptotisch schneller als die Probedivision war.

Algorithmus

Der Algorithmus führt zuerst eine unvollständige Probedivision bis zur Schranke ${\sqrt[{3}]{n}}$ durch. Besitzt $n$ keine Teiler kleiner als ${\sqrt[{3}]{n}}$, so ist sie das Produkt von maximal zwei Primzahlen. In diesem Fall wird der weiter unten aufgeführte Satz von Lehman benutzt, indem nach Zahlen $x$, $y$ und $k$ wie im Satz gesucht wird.

1  Führe Probedivision bis ${\sqrt[{3}]{n}}$ aus und beende, falls ein Teiler gefunden wurde.
2  von k $\leftarrow$ 1 bis $\lfloor {\sqrt[{3}]{n}}\rfloor$
3      von x $\leftarrow$ $\lceil {\sqrt {4kn}}\rceil$ bis $\lfloor {\sqrt {4kn}}+{\frac {\sqrt[{6}]{n}}{4{\sqrt {k}}}}\rfloor$
4           y' $\leftarrow$ $x^{2}-4kn$
5           wenn y' Quadratzahl ist
5               dann ist $\operatorname {ggT} (x+{\sqrt {y'}},n)$ echter Teiler von n.
6  Falls kein Teiler gefunden wurde, ist n eine Primzahl.

Wenn man viele Zahlen zu faktorisieren hat, kann man das Berechnen der Wurzeln beim Bestimmen der Grenzen der inneren Schleife über x vermeiden. Durchläuft man zuerst Zahlen k mit vielen kleinen Primfaktoren (etwa k = 2*3*i), so sind die erzeugten Zahlen häufig Quadratzahlen. Mit diesen Verbesserungen zählt dieser Algorithmus für Eingaben n mit etwa 50 Bit zu einem der schnellsten bekannten Faktorisierungsalgorithmen.

Funktionsweise

Der Algorithmus basiert auf einem Satz, der von Lehman zusammen mit der Faktorisierungsmethode veröffentlicht wurde. Im Wesentlichen beschreibt der Satz, wie man eine Zahl faktorisiert, die das Produkt zweier Primzahlen ist.

Satz (von Lehman)
Ist $n=pq$ eine ungerade natürliche Zahl, $p$ und $q$ Primzahlen und $1\leq r<{\sqrt {n}}$ mit ${\sqrt {\frac {n}{r+1}}}<p\leq {\sqrt {n}}$, so gibt es natürliche Zahlen $x,y$ und $k$ mit den folgenden Eigenschaften:

$x^{2}-y^{2}=4kn$

$x\equiv k+1\ {\pmod {2}}$

$x\equiv k+n\ {\pmod {4}}$ falls $k$ ungerade

${\sqrt {4kn}}\leq x\leq {\sqrt {4kn}}+{\frac {1}{4(r+1)}}{\sqrt {\frac {n}{k}}}$

Ist $n$ eine Primzahl, so gibt es solche $x,y$ und $k$ nicht.

Die optimale Wahl von $r$ ist $r=O(n^{1/3})$.

Laufzeit

Die Methode von Lehman benötigt $O(n^{1/3}\log \log n)$ viele Schritte. Lehman selbst kommt im unten genannten Artikel auf eine Laufzeit von $O(n^{1/3})$. Er geht dabei aber davon aus, dass man die Wurzel einer Zahl in konstanter Zeit berechnen kann, was eher unrealistisch ist.

Quellen

• Richard Crandall, Carl Pomerance: Prime Numbers. A Computational Perspective. 2. Auflage. Springer-Verlag, New York 2005, ISBN 0-387-25282-7, S. 193–194.

Implementierungen

• Hier findet man eine schnelle Java Implementierung des Lehman Algorithmus.