imported>BRLeopold: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-04-15T19:09:49Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

'''Dixons Faktorisierungsmethode,''' auch '''Dixons Zufallsquadrate-Methode''',<ref name="Kleinjung10">Thorsten Kleinjung u. a.: ''Factorization of a 768-bit RSA modulus.'' Version 1.4, 18. Februar 2010, S. 3 ([https://eprint.iacr.org/2010/006.pdf PDF]).</ref> ist ein [[Faktorisierungsverfahren]], d. h. ein [[Algorithmus]] zur Berechnung der [[Primfaktorzerlegung]] einer gegebenen [[Zusammengesetzte Zahl|zusammengesetzten]] [[Natürliche Zahl|natürlichen Zahl]].

Die Methode wurde vom [[Mathematiker]] John D. Dixon an der [[Carleton University]] entwickelt und im Jahr 1981 publiziert.<ref name="Dixon81">John D. Dixon: ''Asymptotically Fast Factorization of Integers.'' In: ''Mathematics of Computation.'' Band 36, Nr. 153, Januar 1981, S. 255–260 ([https://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/S0025-5718-1981-0595059-1.pdf PDF]).</ref> Der Zweck war die theoretische Untersuchung von Faktorbasis-Verfahren und nicht die praktische Anwendung, denn es gab zu dieser Zeit bereits die [[Kettenbruchmethode]] als effizienteren Vertreter dieser Klasse von Faktorisierungsverfahren.

== Funktionsprinzip ==

Sei <math>N</math> die zu faktorisierende Zahl. Die Methode von Dixon beruht darauf, eine [[Kongruenz (Zahlentheorie)|Kongruenz]] von [[Quadratzahl]]en

{{GL | <math> x^2 \equiv y^2 \pmod N</math> | 1}}
{{GL | <math>\text{mit} \;\; x \not\equiv y, \, x \not\equiv -y \pmod N</math> | 2}}

zu ermitteln. Dann sind die [[Größter gemeinsamer Teiler|größten gemeinsamen Teiler]] <math> \operatorname{ggT}(x+y,N)</math> und <math> \operatorname{ggT}(x-y,N)</math> [[Echter Teiler|echte Teiler]] von <math>N</math>. Wegen '''(1)''' ist <math>N</math> Teiler von <math> x^2 - y^2 = (x+y)(x-y)</math>, aber wegen '''(2)''' weder von <math>x+y</math> noch von <math>x-y</math>, sodass sich die [[Primfaktor]]en von <math>N</math> auf <math>x+y</math> und <math>x-y</math> aufteilen.

Es wäre ineffizient, nach einer Kongruenz '''(1)''' direkt zu suchen. Stattdessen wählt man zunächst eine Faktorbasis, die aus allen Primzahlen <math>p_1 = 2</math> bis <math>p_k</math> besteht. Dann bestimmt man Kongruenzen

{{GL | <math> x_i^2 \equiv a_i \pmod N,</math> | 3}}

deren <math>a_i</math> keinen Primfaktor größer als <math>p_k</math> enthalten. Man nennt solche Zahlen <math>p_k</math>-[[Glatte Zahl|glatt]]. Anschließend multipliziert man eine geeignete nicht[[Leere Menge|leere]] Auswahl <math>M</math>, um eine Kongruenz von Quadraten zu erhalten (denn es gilt <math>a \equiv b, c\equiv d \, \Rightarrow \, ac \equiv bd</math>):

{{GL | <math> x^2 = \prod_{i \in M} x_i^2 \, \equiv \, y^2 = \prod_{i \in M} a_i \pmod N</math> | 4}}

Indem man sich auf <math>p_k</math>-glatte <math>a_i</math> beschränkt, braucht man nur eine überschaubare Anzahl von Kongruenzen '''(3),''' nämlich etwa <math>k</math>, damit eine Auswahl <math>M</math> von <math>a_i</math> existiert, deren Produkt eine Quadratzahl ist. Außerdem sind dadurch die <math>a_i</math> genügend schnell faktorisierbar, z. B. durch [[Probedivision]]. Ist deren Primfaktorzerlegung

:<math>a_i = \prod_{j=1}^k p_j^{e_{ij}}</math>

bekannt, kann man eine Auswahl <math>M</math> effizient bestimmen. Damit das Produkt der gewählten <math>a_i</math> ein Quadrat ist, muss die [[Primfaktorzerlegung#Definitionen|Vielfachheit]] jedes Primfaktors gerade sein. Man verwendet dafür Methoden der [[Lineare Algebra|linearen Algebra]] modulo 2 auf der [[Matrix (Mathematik)|Matrix]] der Vielfachheiten <math>(e_{ij})</math>.

Man kann zeigen: Wenn <math>N</math> mindestens zwei verschiedene Primfaktoren enthält, also keine Potenz einer [[Primzahl]] ist, dann erfüllt mindestens die Hälfte der Kongruenzen von Quadratzahlen <math> x^2 \equiv y^2 \pmod N</math> mit <math>x, y</math> teilerfremd zu <math>N</math> die Bedingung <math>x \not\equiv \pm y \pmod N</math>.

== Vorgehen ==

Man wählt eine Zahl <math>k</math> und bestimmt die Faktorbasis <math>\{2, 3, 5, \dotsc, p_k\}</math> mit den <math>k</math> kleinsten Primzahlen. Es wird empfohlen, die Primzahlen bis zu einer Schranke in der Größenordnung von <math>p_k \approx \exp\left(\tfrac{1}{2} \sqrt{\ln N \ln \ln N}\right)</math> in die Faktorbasis aufzunehmen.

Dann erzeugt man <math>x_i</math> im Bereich <math>\left\lceil \sqrt N \right\rceil \le x_i < N</math> und versucht, <math>a_i = x_i^2 \bmod N</math> zu faktorisieren. Dixons Methode sieht vor, dass (Pseudo-)[[Zufallszahl]]en als <math>x_i</math> verwendet werden, aber das ist nicht zwingend; man kann z. B. auch die Glieder einer regelmäßigen [[Folge (Mathematik)|Folge]] wie etwa <math>x_{i+1} = x_i + 1</math> nehmen.

Die Paare <math>(x_i, a_i)</math> mit <math>p_k</math>-glatten <math>a_i</math> werden aufbewahrt, zusammen mit der Faktorisierung der <math>a_i</math> in Form der Vielfachheiten <math>e_{ij}</math>. Wenn man eine ausreichend erscheinende Anzahl davon zur Verfügung hat (am besten ein wenig mehr als <math>k</math>), versucht man eine Auswahl <math>M</math> dieser Paare zu bestimmen, die miteinander multipliziert eine Kongruenz von Quadratzahlen entsprechend '''(4)''' ergeben.

Das kann z. B. mit der [[Gaußsches Eliminationsverfahren|Gauß-Elimination]] geschehen: Man bildet eine binäre Matrix, die für jedes der gefundenen Paare <math>(x_i, a_i)</math> eine Zeile und für jeden Faktor der Faktorbasis eine Spalte enthält. In einem Matrixelement ist eine 1 eingetragen, wenn der betreffende Faktor mit ungerader Vielfachheit in dem <math>a_i</math> dieser Zeile enthalten ist, und ansonsten eine 0. Man bringt die Matrix mit den Operationen „Spalten vertauschen“ und „eine Spalte zu einer anderen modulo 2 addieren (also [[Kontravalenz|XOR]]-Verknüpfen)“ in eine Dreiecksform, an der man ablesen kann, welche (nicht leere) Auswahl der Zeilen den [[Nullvektor]] ergibt. Dann enthält das Produkt der <math>a_i</math> dieser Zeilen jeden Faktor mit gerader Vielfachheit und ist ein Quadrat.

Hat man eine solche Auswahl gefunden, berechnet man

:<math>x = \prod_{i \in M} x_i \bmod N; \quad y = \sqrt{\prod_{i \in M} a_i} \bmod N = \prod_{j=1}^k p_j^{\tfrac{1}{2} \sum_{i \in M} e_{ij}} \bmod N</math>

und anschließend <math>\operatorname{ggT}(x-y,N)</math> oder <math>\operatorname{ggT}(x+y,N)</math>. Wenn dies keinen echten Teiler von <math>N</math> liefert, dann ist offenbar <math> x \equiv \pm y \pmod N</math> und man muss eine andere Kombination der <math>(x_i, a_i)</math> probieren, ggfs. muss man weitere solcher Paare sammeln.

== Eigenschaften ==

Dixons Methode besitzt bei optimaler Wahl der Größe der Faktorbasis eine [[Zeitkomplexität]] in <math>\operatorname{O}\left( \exp \left(2\sqrt{2\ln N \ln \ln N} \right) \right)</math> (siehe [[Landau-Symbole]]). Es ist das einzige Faktorbasis-Verfahren, für das man eine Zeitkomplexitäts-Schranke kennt, die nicht von Annahmen über die Glattheits-Eigenschaften der Werte bestimmter Polynome abhängt.

Es ist ein allgemeines Faktorisierungsverfahren, d. h., es kann auf nahezu alle zusammengesetzten <math>N</math> angewandt werden. Nur wenn <math>N</math> eine Primpotenz ist, also von der Form <math>N = p^m</math>, versagt das Verfahren. Dieser Fall kann aber leicht vorab geprüft werden.

Die Zeit zum Faktorisieren eines bestimmten <math>N</math> hängt nur von der Größe von <math>N</math> ab (mit einer gewissen Streuung), aber nicht von der Größe der enthaltenen Primfaktoren. Zum Auffinden kleiner Faktoren gibt es viel effizientere Verfahren, z. B. die Probedivision oder die [[Pollard-Rho-Methode]]. Diese sollten zunächst versucht werden, wenn <math>N</math> auch kleine Faktoren enthält oder enthalten könnte, um dann evtl. ein Faktorbasisverfahren wie Dixons Methode auf den unfaktorisierten Teil von <math>N</math> anzuwenden.

== Verbesserungen ==

Man kann die <math>a_i</math> auch zu <math>a_i = x_i^2 - N</math> berechnen. Das ist etwas effizienter, weil die [[Subtraktion]] in der Regel schneller ist als die Modulo-Division.
Wichtiger ist aber, dass man dann die Primzahlen <math>p</math>, für die <math>N</math> kein [[quadratischer Rest]] modulo <math>p</math> ist, nicht in die Faktorbasis aufnehmen muss. Nur wenn es ein <math>x</math> gibt mit <math>x^2 \equiv N \pmod p</math>, kann <math>a_i</math> durch <math>p</math> teilbar sein.

Außerdem ist es günstig, sich auf solche <math>x_i</math> zu beschränken, die in der Nähe von <math>\sqrt N</math> liegen und dadurch ein <math>a_i</math> mit relativ kleinem Betrag liefern, das mit höherer Wahrscheinlichkeit über der Faktorbasis vollständig zerfällt. Es können auch <math>x_i</math> verwendet werden, die kleiner als <math>\sqrt N</math> sind, wenn der Faktor <math>-1</math> in die Faktorbasis aufgenommen wird, um die negativen <math>a_i</math> darzustellen. Auch der Exponent von <math>-1</math> muss dann gerade sein, damit ein positives Produkt der <math>a_i</math> entsteht, d. h., der Faktor <math>-1</math> kann beim Ermitteln der Auswahl <math>M</math> genauso wie die Primfaktoren behandelt werden.

Die <math>a_i</math> können auch dann verwendet werden, wenn sie glatt sind bis auf einen einzigen Primfaktor größer <math>p_k</math>. Wenn nach dem Abdividieren der Faktoren <math>p_1</math> bis <math>p_k</math> ein Teil größer <math>1</math> und kleiner <math>p_{k+1}^2</math> übrig ist, muss er prim sein, und <math>a_i</math> ist damit vollständig faktorisiert. Man erhält dadurch wesentlich mehr Kongruenzen, die man gemäß '''(4)''' kombinieren kann, bei unverändertem Aufwand für die Zerlegung der <math>a_i</math>. Die Bestimmung der Auswahl <math>M</math> wird dann allerdings komplizierter, denn es müssen auch die Zusatzfaktoren größer <math>p_k</math> im Produkt der <math>a_i</math> eine gerade Vielfachheit haben.

Eine weitere Möglichkeit ist es, von den <math>a_i</math> zunächst nur die kleinsten Primfaktoren <math>2, \dotsc, p_r</math> abzudividieren und dann diejenigen, deren unfaktorisierter Rest größer als eine geeignet gewählte Grenze ist, zu verwerfen, denn diese sind nur mit geringer Wahrscheinlichkeit <math>p_k</math>-glatt. Nur die übrigen werden anschließend auch durch <math>p_{r+1}, \dotsc, p_k</math> dividiert.

Es gibt auch effizientere Verfahren zur Bestimmung der Auswahl <math>M</math>, z. B. das Block-[[Lanczos-Verfahren]], das die dünne Besetzung der Matrix <math>(e_{ij})</math> nutzt. Dadurch vermeidet man die kubische Komplexität (in <math>k</math>) der Gauß-Elimination.

Das Prinzip, Kongruenzen '''(3)''' zu sammeln und zu einer Lösung für '''(1)''' zu kombinieren, wird auch von anderen, effizienteren Faktorbasis-Verfahren genutzt, wie dem [[Quadratisches Sieb|Quadratischen Sieb]], dem [[Zahlkörpersieb]] und der [[Kettenbruchmethode]]. Diese unterscheiden sich im Wesentlichen nur in der Methode, wie sie Kongruenzen finden, die dann zu einer Kongruenz von Quadraten kombiniert werden. Einige der genannten Verbesserungen können bei diesen Verfahren ebenfalls angewandt werden. Dixons Methode könnte man hinsichtlich der Funktionsweise als Prototyp dieser Verfahren ansehen, auch wenn die Kettenbruchmethode als erste entwickelt wurde.

== Weblinks ==

* {{MathWorld|id=DixonsFactorizationMethod|title=Dixon’s Factorization Method}}

== Einzelnachweise ==
<references />

[[Kategorie:Faktorbasisverfahren]]

Dixons Faktorisierungsmethode - Versionsgeschichte

imported>BRLeopold: /* growthexperiments-addlink-summary-summary:2|0|0 */