Faktorisierungsmethode von Lehman - LinkFang.de





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 [math]\sqrt[3]{n}[/math] durch. Besitzt [math]n[/math] keine Teiler kleiner als [math]\sqrt[3]{n}[/math], 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 [math]x[/math], [math]y[/math] und [math]k[/math] wie im Satz gesucht wird.

1  Führe Probedivision bis [math]\sqrt[3]{n}[/math] aus und beende falls ein Teiler gefunden wurde.
2  von k [math]\leftarrow[/math] 1 bis [math]\lfloor \sqrt[3]{n} \rfloor[/math]
3      von x [math]\leftarrow[/math] [math]\lceil \sqrt{4kn}\rceil[/math] bis [math]\lfloor \sqrt{4kn} + \frac{\sqrt[6]{n}}{4\sqrt{k}} \rfloor[/math]
4           y' [math]\leftarrow[/math] [math]x^2 -4kn[/math]
5           wenn y' Quadratzahl ist
5               dann ist [math]\operatorname{ggT}(x + \sqrt{y'}, n )[/math] 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 [math]n = pq[/math] eine ungerade natürliche Zahl, [math]p[/math] und [math]q[/math] Primzahlen und 1 ≤ r < n1/2 mit (n/(r+1))1/2p ≤ n1/2, so gibt es natürliche Zahlen x, y und k mit den folgenden Eigenschaften:

[math]x^2 - y^2 = 4kn[/math]
[math]x \equiv k+1\ \pmod 2[/math]
[math]x \equiv k+n\ \pmod 4[/math] falls [math]k[/math] ungerade
[math]\sqrt{4kn} \leq x \leq \sqrt{4kn} + \frac{1}{4(r+1)} \sqrt{\frac{n}{k}}[/math]

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

Die optimale Wahl von r ist r = O(n1/3)

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.

Quellen

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

Kategorien: Faktorisierungsverfahren

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Faktorisierungsmethode von Lehman (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.