Faktorisierungsmethode von Lehman

aus Wikipedia, der freien Enzyklopädie

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 vorgegeben 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.

Inhaltsverzeichnis 1 Algorithmus 2 Funktionsweise 2.1 Satz (von Lehman) 3 Laufzeit 4 Quellen

[Bearbeiten] Algorithmus

Der Algorithmus führt zuerst eine unvollständige Probedivision bis zur Schranke durch. Besitzt n keine Teiler kleiner als , so ist sie das Produkt zweier 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  aus und beende falls ein Teiler gefunden wurde.
2  von k  1 bis 
3      von x   bis 
4           y'  x2 − 4kn
5           wenn y' ist Quadratzahl
5               dann  ist 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.

[Bearbeiten] Funktionsweise

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

[Bearbeiten] 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

falls k ungerade

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

Die optimale Wahl von r ist r = O(n^1/3)

[Bearbeiten] 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.

[Bearbeiten] 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 Perspecitve. 2. Auflage. Springer-Verlag, New York, 2005, ISBN 0-387-25282-7, S. 193–194