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 durch. Besitzt keine Teiler kleiner als , 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 , und wie im Satz gesucht wird.

1  Führe Probedivision bis  aus und beende, falls ein Teiler gefunden wurde.
2  von k  1 bis 
3      von x   bis 
4           y'  
5           wenn y' Quadratzahl ist
5               dann ist  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 eine ungerade natürliche Zahl, und Primzahlen und mit , so gibt es natürliche Zahlen und mit den folgenden Eigenschaften:

falls ungerade

Ist eine Primzahl, so gibt es solche und nicht.

Die optimale Wahl von ist .

Laufzeit

Die Methode von Lehman benötigt viele Schritte. Lehman selbst kommt im unten genannten Artikel auf eine Laufzeit von . Er geht dabei aber davon aus, dass man die Wurzel einer Zahl in konstanter Zeit berechnen kann, was eher unrealistisch ist.

Quellen

Implementierungen

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

Einzelnachweise

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