Dixons Faktorisierungsmethode

Dixons Faktorisierungsmethode, a​uch Dixons Zufallsquadrate-Methode,[1] i​st ein Faktorisierungsverfahren, d. h. e​in Algorithmus z​ur Berechnung d​er Primfaktorzerlegung e​iner gegebenen zusammengesetzten natürlichen Zahl.

Die Methode w​urde vom Mathematiker John D. Dixon a​n der Carleton University entwickelt u​nd im Jahr 1981 publiziert.[2] Der Zweck w​ar die theoretische Untersuchung v​on Faktorbasis-Verfahren u​nd nicht d​ie praktische Anwendung, d​enn es g​ab zu dieser Zeit bereits d​ie Kettenbruchmethode a​ls effizienteren Vertreter dieser Klasse v​on Faktorisierungsverfahren.

Funktionsprinzip

Sei ${\displaystyle N}$ die zu faktorisierende Zahl. Die Methode von Dixon beruht darauf, eine Kongruenz von Quadratzahlen

${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$

( 1)

${\displaystyle {\text{mit}}\;\;x\not \equiv y,\,x\not \equiv -y{\pmod {N}}}$

( 2)

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

Es wäre ineffizient, nach einer Kongruenz (1) direkt zu suchen. Stattdessen wählt man zunächst eine Faktorbasis, die aus allen Primzahlen ${\displaystyle p_{1}=2}$ bis ${\displaystyle p_{k}}$ besteht. Dann bestimmt man Kongruenzen

${\displaystyle x_{i}^{2}\equiv a_{i}{\pmod {N}},}$

( 3)

deren ${\displaystyle a_{i}}$ keinen Primfaktor größer als ${\displaystyle p_{k}}$ enthalten. Man nennt solche Zahlen ${\displaystyle p_{k}}$-glatt. Anschließend multipliziert man eine geeignete nichtleere Auswahl ${\displaystyle M}$, um eine Kongruenz von Quadraten zu erhalten (denn es gilt ${\displaystyle a\equiv b,c\equiv d\,\Rightarrow \,ac\equiv bd}$):

${\displaystyle x^{2}=\prod _{i\in M}x_{i}^{2}\,\equiv \,y^{2}=\prod _{i\in M}a_{i}{\pmod {N}}}$

( 4)

Indem man sich auf ${\displaystyle p_{k}}$-glatte ${\displaystyle a_{i}}$ beschränkt, braucht man nur eine überschaubare Anzahl von Kongruenzen (3), nämlich etwa ${\displaystyle k}$, damit eine Auswahl ${\displaystyle M}$ von ${\displaystyle a_{i}}$ existiert, deren Produkt eine Quadratzahl ist. Außerdem sind dadurch die ${\displaystyle a_{i}}$ genügend schnell faktorisierbar, z. B. durch Probedivision. Ist deren Primfaktorzerlegung

${\displaystyle a_{i}=\prod _{j=1}^{k}p_{j}^{e_{ij}}}$

bekannt, kann man eine Auswahl ${\displaystyle M}$ effizient bestimmen. Damit das Produkt der gewählten ${\displaystyle a_{i}}$ ein Quadrat ist, muss die Vielfachheit jedes Primfaktors gerade sein. Man verwendet dafür Methoden der linearen Algebra modulo 2 auf der Matrix der Vielfachheiten ${\displaystyle (e_{ij})}$.

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

Vorgehen

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

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

Die Paare ${\displaystyle (x_{i},a_{i})}$ mit ${\displaystyle p_{k}}$-glatten ${\displaystyle a_{i}}$ werden aufbewahrt, zusammen mit der Faktorisierung der ${\displaystyle a_{i}}$ in Form der Vielfachheiten ${\displaystyle e_{ij}}$. Wenn man eine ausreichend erscheinende Anzahl davon zur Verfügung hat (am besten ein wenig mehr als ${\displaystyle k}$), versucht man eine Auswahl ${\displaystyle M}$ dieser Paare zu bestimmen, die miteinander multipliziert eine Kongruenz von Quadratzahlen entsprechend (4) ergeben.

Das kann z. B. mit der Gauß-Elimination geschehen: Man bildet eine binäre Matrix, die für jedes der gefundenen Paare ${\displaystyle (x_{i},a_{i})}$ 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 ${\displaystyle a_{i}}$ 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 ${\displaystyle a_{i}}$ dieser Zeilen jeden Faktor mit gerader Vielfachheit und ist ein Quadrat.

Hat m​an eine solche Auswahl gefunden, berechnet man

${\displaystyle 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}}}$

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

Eigenschaften

Dixons Methode besitzt bei optimaler Wahl der Größe der Faktorbasis eine Zeitkomplexität in ${\displaystyle \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 ${\displaystyle N}$ angewandt werden. Nur wenn ${\displaystyle N}$ eine Primpotenz ist, also von der Form ${\displaystyle N=p^{m}}$, versagt das Verfahren. Dieser Fall kann aber leicht vorab geprüft werden.

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

Verbesserungen

Man kann die ${\displaystyle a_{i}}$ auch zu ${\displaystyle 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 ${\displaystyle p}$, für die ${\displaystyle N}$ kein quadratischer Rest modulo ${\displaystyle p}$ ist, nicht in die Faktorbasis aufnehmen muss. Nur wenn es ein ${\displaystyle x}$ gibt mit ${\displaystyle x^{2}\equiv N{\pmod {p}}}$, kann ${\displaystyle a_{i}}$ durch ${\displaystyle p}$ teilbar sein.

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

Die ${\displaystyle a_{i}}$ können auch dann verwendet werden, wenn sie glatt sind bis auf einen einzigen Primfaktor größer ${\displaystyle p_{k}}$. Wenn nach dem Abdividieren der Faktoren ${\displaystyle p_{1}}$ bis ${\displaystyle p_{k}}$ ein Teil größer ${\displaystyle 1}$ und kleiner ${\displaystyle p_{k+1}^{2}}$ übrig ist, muss er prim sein, und ${\displaystyle a_{i}}$ 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 ${\displaystyle a_{i}}$. Die Bestimmung der Auswahl ${\displaystyle M}$ wird dann allerdings komplizierter, denn es müssen auch die Zusatzfaktoren größer ${\displaystyle p_{k}}$ im Produkt der ${\displaystyle a_{i}}$ eine gerade Vielfachheit haben.

Eine weitere Möglichkeit ist es, von den ${\displaystyle a_{i}}$ zunächst nur die kleinsten Primfaktoren ${\displaystyle 2,\dotsc ,p_{r}}$ 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 ${\displaystyle p_{k}}$-glatt. Nur die übrigen werden anschließend auch durch ${\displaystyle p_{r+1},\dotsc ,p_{k}}$ dividiert.

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

Das Prinzip, Kongruenzen (3) z​u sammeln u​nd zu e​iner Lösung für (1) z​u kombinieren, w​ird auch v​on anderen, effizienteren Faktorbasis-Verfahren genutzt, w​ie dem Quadratischen Sieb, d​em Zahlkörpersieb u​nd der Kettenbruchmethode. Diese unterscheiden s​ich im Wesentlichen n​ur in d​er Methode, w​ie sie Kongruenzen finden, d​ie dann z​u einer Kongruenz v​on Quadraten kombiniert werden. Einige d​er genannten Verbesserungen können b​ei diesen Verfahren ebenfalls angewandt werden. Dixons Methode könnte m​an hinsichtlich d​er Funktionsweise a​ls Prototyp dieser Verfahren ansehen, a​uch wenn d​ie Kettenbruchmethode a​ls erste entwickelt wurde.

Weblinks

• Eric W. Weisstein: Dixon’s Factorization Method. In: MathWorld (englisch).

Einzelnachweise

1. Thorsten Kleinjung u. a.: Factorization of a 768-bit RSA modulus. Version 1.4, 18. Februar 2010, S. 3 (PDF).
2. John D. Dixon: Asymptotically Fast Factorization of Integers. In: Mathematics of Computation. Band 36, Nr. 153, Januar 1981, S. 255–260 (PDF).