Dixons Faktorisierungsmethode

Dixons Faktorisierungsmethode

Dixons Faktorisierungsmethode, auch Dixons Zufallsquadrate-Methode[1] ist ein Faktorisierungsverfahren, d. h. ein Algorithmus zur Berechnung der Primfaktorzerlegung einer gegebenen zusammengesetzten natürlichen Zahl.

Die Methode wurde vom Mathematiker John D. Dixon an der Carleton University entwickelt und im Jahr 1981 publiziert.[2]

Inhaltsverzeichnis

Funktionsprinzip

Sei N die zu faktorisierende Zahl. Die Methode von Dixon beruht darauf, eine Kongruenz von Quadratzahlen

 x^2 \equiv y^2 \;\; (\bmod \, N) (1)
\text{mit} \;\; x \not\equiv y, \, x \not\equiv -y  \;\; (\bmod N) (2)

zu ermitteln. Dann sind die größten gemeinsamen Teiler  \operatorname{ggT}(x+y,N) und  \operatorname{ggT}(x-y,N) echte Teiler von N. Wegen (1) ist N Teiler von x2y2 = (x + y)(xy), aber wegen (2) weder von x + y noch von xy, so dass sich die Primfaktoren von N auf x + y und xy aufteilen.

Es wäre uneffizient, nach einer Kongruenz (1) direkt zu suchen. Statt dessen wählt man zunächst eine Faktorbasis, die aus allen Primzahlen p1 = 2 bis pk besteht. Dann bestimmt man Kongruenzen

 x_i^2 \equiv a_i \;\; (\bmod \, N), (3)

deren ai keinen Primfaktor größer als pk enthalten. Man nennt solche Zahlen pk-glatt. Anschließend multipliziert man eine geeignete nicht leere Auswahl M, um eine Kongruenz von Quadraten zu erhalten (denn es gilt a \equiv b, c\equiv d \, \Rightarrow \, ac \equiv bd):

 x^2 = \prod_{i \in M} x_i^2 \, \equiv \, y^2 = \prod_{i \in M} a_i \;\; (\bmod \, N). (4)

Eine solche Auswahl M von ai, deren Produkt eine Quadratzahl ist, existiert sicher dann, wenn man mindestens k + 1 Kongruenzen (3) zur Verfügung hat. Durch die Beschränkung auf pk-glatte ai braucht man davon also nur eine überschaubare Anzahl. Außerdem sind dadurch die ai genügend schnell, z. B. durch Probedivision, faktorisierbar. Ist deren Primfaktorzerlegung

a_i = \prod_{j=1}^k p_j^{e_{ij}}

bekannt, kann man eine Auswahl M effizient bestimmen. Damit das Produkt der gewählten ai ein Quadrat ist, muss die Vielfachheit all seiner Primfaktoren gerade sein. Man verwendet dafür Methoden der linearen Algebra modulo 2 auf der Matrix der Vielfachheiten (eij).

Man kann zeigen: wenn N mindestens zwei verschiedene Primfaktoren enthält, also keine Potenz einer Primzahl ist, dann erfüllt mindestens die Hälfte der Kongruenzen von Quadratzahlen  x^2 \equiv y^2 \; (\bmod \, N) mit x,y teilerfremd zu N die Bedingung x \not\equiv \pm y \; (\bmod \, N).

Vorgehen

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

Dann erzeugt man xi im Bereich \left\lceil \sqrt N \right\rceil \le x_i < N und versucht, a_i = x_i^2 \bmod N zu faktorisieren. Dixons Methode sieht vor, dass (pseudo-)Zufallszahlen als xi verwendet werden, aber das ist nicht zwingend; man kann z. B. auch die Glieder einer regelmäßigen Folge wie etwa xi + 1 = xi + 1 nehmen.

Die Paare (xi,ai) mit pk-glatten ai werden aufbewahrt, zusammen mit der Faktorisierung der ai in Form der Vielfachheiten eij. Wenn man eine ausreichend erscheinende Zahl davon zur Verfügung hat (am besten ein wenig mehr als k), versucht man eine Auswahl M dieser Paare zu bestimmen, die miteinander multipliziert eine Kongruenz von Quadratzahlen entsprechend (4) ergeben.

Das kann z. B. mit der Gauss-Elimination geschehen: man bildet eine binäre Matrix, die für jedes der gefundenen Paare (xi,ai) 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 ai 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 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 ai dieser Zeilen jeden Faktor mit gerader Vielfachheit und ist ein Quadrat.

Hat man eine solche Auswahl gefunden, berechnet man

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.

Wenn nun \operatorname{ggT}(x-y,N) keinen echten Teiler von N liefert, dann ist offenbar  x \equiv \pm y \; (\bmod \, N), und man muss eine andere Kombination der (xi,ai) probieren, ggfs. muss man weitere solcher Paare sammeln.

Eigenschaften

Dixons Methode besitzt bei optimaler Wahl der Größe der Faktorbasis eine Zeitkomplexität in \operatorname{O}\left( \exp \left(2\sqrt{2\ln N \ln \ln N} \right) \right) (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 N angewandt werden. Nur wenn N eine Primpotenz ist, also von der Form N = pm, versagt das Verfahren. Dieser Fall kann aber leicht vorab geprüft werden, wodurch man auch den Primfaktor p findet und N somit faktorisiert hat.

Die Zeit zum Faktorisieren eines bestimmten N hängt im Wesentlichen nur von der Größe von N ab, und 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 N auch kleine Faktoren enthält oder enthalten könnte, um dann evtl. ein Faktorbasisverfahren wie Dixons Methode auf den unfaktorisierten Teil von N anzuwenden.

Verbesserungen

Man kann die ai auch zu a_i = x_i^2 - N 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 p, für die N kein Quadratischer Rest mod p ist, nicht in die Faktorbasis aufnehmen muss. Nur wenn es ein x gibt mit x^2 \equiv N \; (\bmod \, p), kann ai durch p teilbar sein. Außerdem ist es günstig, sich auf xi in der Nähe von \sqrt N zu beschränken, die ein ai mit relativ kleinem Betrag liefern, so dass es mit höherer Wahrscheinlichkeit über der Faktorbasis vollständig zerfällt. Es können auch x_i < \sqrt N verwendet werden, wenn der Faktor − 1 in die Faktorbasis aufgenommen wird, um die negativen ai darzustellen.

Eine weitere Verbesserung ist die Verwendung effizienterer Verfahren zur Bestimmung der Auswahl M, z. B. das Block Lanczos Verfahren, das die dünne Besetzung der Matrix (eij) nutzt.

Die ai können auch dann verwendet werden, wenn sie glatt sind bis auf einen einzigen Primfaktor größer pk. Wenn nach dem Abdividieren der Faktoren p1 bis pk der verbleibende Teil kleiner als p_{k+1}^2 ist, muss er prim sein, und ai wurde 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 ai.

Das Prinzip, Kongruenzen (3) zu sammeln und zu einer Lösung für (1) zu kombinieren, wird auch von anderen, effizienteren Faktorbasis-Verfahren genutzt, für die Dixons Methode gleichsam der Prototyp ist, wie das Quadratische Sieb, die Kettenbruchmethode und das Zahlkörpersieb. Diese unterscheiden sich im Wesentlichen nur in der Methode, wie sie Kongruenzen finden, die dann zu einer Kongruenz von Quadraten kombiniert werden.

Referenzen

  1. Thorsten Kleinjung et al., "Factorization of a 768-bit RSA modulus", version 1.3 (January 24, 2010), p. 3
  2. John D. Dixon, "Asymptotically fast factorization of integers", Mathematics of Computation 36 (1981), pp. 255–260.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Faktorisierungsverfahren — Das Faktorisierungsproblem für ganze Zahlen ist eine Aufgabenstellung aus dem mathematischen Teilgebiet der Zahlentheorie. Dabei soll zu einer zusammengesetzten Zahl ein nichttrivialer Teiler ermittelt werden. Ist beispielsweise die Zahl 91… …   Deutsch Wikipedia

  • Kettenbruchmethode — Die Kettenbruchmethode (Abk.: CFRAC) berechnet zwei Teiler einer natürlichen Zahl, die keine Primzahl ist. Durch wiederholte Anwendung lässt sich so die Primfaktorzerlegung dieser Zahl ermitteln. Die Kettenbruchmethode wurde 1931 von Derrick… …   Deutsch Wikipedia

  • Quadratisches Sieb — ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d.h. die Laufzeit hängt nur von …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”