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.^[1] 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$ x2 − 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.

Für die Praxis lässt sich das Verfahren noch etwas beschleunigen, indem man zum einen die beiden zusätzlichen Kongruenzen im Satz von Lehman ausnutzt und indem man die Zahlen k in einer anderen Reihenfolge durchläuft, bei der Zahlen mit vielen kleinen Primfaktoren zuerst untersucht werden.

Lehman benutzt zudem eine Liste mit quadratischen Resten modulo 729 um die Überprüfung auf Quadratzahl für etliche Zahlen zu beschleunigen.

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 ≤ r < n^1/2 mit (n/(r+1))^1/2 < p ≤ n^1/2, so gibt es natürliche Zahlen x, y und k mit den folgenden Eigenschaften:

x² − y² = 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/3log 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

1. ↑ Russell Sherman Lehman: Factoring Large Integers. In: Mathematics of Computation. 28, 1974, S. 637–646

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