Faktorisierungsmethode von Lehman

Die Faktorisierungsmethode von Lehman ist ein von R. Sherman Lehman im Jahre 1974 vorgestellter Algorithmus um die Primfaktorzerlegung einer Zahl zu bestimmen. Gleichzeitig kann man diese Methode auch benutzen, um von einer Zahl nachzuweisen, dass sie eine Primzahl ist. 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 Probedivision war.

Table of contents
1 Funktionsweise
2 Laufzeit
3 Literatur

Funktionsweise

Der Algorithmus bassiert auf einem Satz, der in nachfolgendem Expertenbereich genauer erläutert ist. Im Wesentlichen beschreibt der Satz, wie man eine Zahl faktorisiert, die das Produkt von genau zwei Primzahlen ist.

{| border=1 style="border:0px" | style="border:1px" |              | style="border:1px solid #448800; padding:0; background-color:#EEFFEE" |

Expertenabschnitt: Dieser Abschnitt enthält tiefergehende Informationen, für die zum Teil zusätzliches Fachwissen notwendig ist.

Satz (von Lehman)

Ist n=pq eine ungerade natürliche Zahl, sind p und q Primzahlen und ist 1 ≤ r < n1/2 mit ((n/(r+1))1/2 < p ≤ n1/2, so gibt es natürliche Zahlen x, y und k mit den folgenden Eigenschaften:

  • x2-y2=4kn
  • x ≡ k+1 (mod 2)
  • x ≡ k+n (mod 4) falls k ungerade
  • (4kn)1/2 ≤ x ≤ (4kn)1/2 + (1/4)(r+1)(n/k)1/2

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

Die optimale Wahl von r ist r = O(n1/3) | style="border:1px" |              |}

Der Algorithmus prüft zunächst durch Probedivision bis n1/3, ob die Zahl aus mehr als zwei Faktoren besteht. Ist dies nicht der Fall, so wird der Satz von Lehman benutzt, indem nach Zahlen x, y und k wie im Satz gesucht wird. Der Algorithmus sieht dann wie folgt aus:

   Algorithmus zur Faktorisierung einer Zahl nach Lehman.

   Führe Probedivision bis n1/3 aus und beende falls ein Teiler gefunden wurde.

   Für 1 ≤ k ≤ n1/3 und
       für (4kn)1/2 ≤ x &le (4kn)1/2 + n1/6/4k1/2
           überprüfe, ob y2 := x2-4kn eine Quadratzahl ist.
           Falls ja, ist ggT(x+y,n) ein echter Teiler von n.

   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.

Laufzeit

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

Literatur