Dixons factorisatiemethode

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de getaltheorie, een deelgebied van de wiskunde, wordt de Dixons factorisatiemethode (ook wel Dixons algoritme genoemd) algemeen gebruikt voor de factorisatie van positieve gehele getallen in priemgetallen; het is een methode voor de factorisatie van gehele getallen. Het algoritme is in 1981 opgesteld door John Dixon, een wiskundige van de Carleton Universiteit.

Basisidee[bewerken]

Dixons methode is gebaseerd op het vinden van gelijke kwadraten, modulo het gehele getal N, waarvoor we de factoren proberen te vinden. Fermats factorisatie-algoritme vindt zulke gelijke waarden door willekeurig (random) of pseudorandom (begrensd tot een beperkte waarde) keuzes voor x, hopend dat het gehele getal x2 mod N het kwadraat is van een geheel getal:

x^2 \equiv y^2 \pmod N ,x \not\equiv \pm y

Neem bijvoorbeeld N=84923. We starten met zoeken bij 292, omdat dit het eerste getal groter dan √N is en nemen iedere keer een geheel getal verder. We zien dat 342^2 mod 84923 is 32041, wat weer het kwadraat is van 179. Dit betekent dus ook dat (342 – 179)(342 + 179) = 0 mod N. Bereken de ggd van 342 – 179 en N, met gebruikmaking van het algoritme van Euclides. Het geeft als grootste gemene deler 163, dit is een factor van N. In de praktijk zal het een te lange tijd kosten om random x-waarden te selecteren die gelijke kwadraten geven, dit omdat er zo weinig kwadraten kleiner zijn dan N. Daarom vervangt Dixons methode de voorwaarde ‘is de kwadraat van een geheel getal’ met de veel zwakkere voorwaarde ‘heeft alleen kleine priemfactoren’. Bijvoorbeeld, er zijn 290 kwadraten kleiner dan 84923, 662 getallen waarvan de priemfactoren alleen 2, 3, 5 of 7 zijn en 4767 waarvan de priemfactoren allemaal kleiner zijn dan 30.

We hebben een groot getal N wat we moeten factoriseren. Dit doen we met behulp van een aantal getallen a_1 \ldots a_n. Deze getallen kwadrateren we en nemen we modulo N (wat overblijft noemen we r). Vervolgens factoriseren we r tot een product van kleine priemgetallen. In formule:

a_i^2 \mod n = \prod_{j=1}^m b_i^{e_{ij}}

Waarbij b_1 \ldots b_m een vaste verzameling kleine priemgetallen is, modulo 2, op de matrix e_{ij}. Dit geeft ons een deelverzameling waarvan de kwadraten combineren tot een product van kleine priemgetallen met een even macht. Dit is een deelverzameling van de a_i waarvan deze kwadraten combineren met een kwadraat.

Methode[bewerken]

De eerste stap is het kiezen van een verzameling priemgetallen kleiner dan de grens B. Deze verzameling priemgetallen wordt de factorbasis genoemd. Gebruik daarna de polynoom

p(x)=x^2\pmod{n}.

waardoor veel waarden van x worden getest om te zien of de p(x)-factoren compleet over de factorbasis gaan. Als dit het geval is, wordt het paar (x, p(x)) opgeslagen. Zo’n paar wordt een relatie genoemd. Vervolgens gaan we, zodra het aantal verzamelde relaties de grootte van de factorbasis overschrijdt, naar de volgende stap.

De p(x)-waarden worden gefactoriseerd (dit is gemakkelijk omdat we zeker zijn dat zij compleet over de factorbasis factoriseren) en de exponenten van de priemgetallen geconverteerd worden in een exponent vector modulo 2. Bijvoorbeeld, als de factorbasis {2, 3, 5, 7} is en de p(x) waarde is 75600, hebben we:

75600=2^4\cdot3^3\cdot 5^2\cdot 7^1.

Dit geeft een exponent vector van: \mathbf{v}_i=\begin{bmatrix}4 \\ 3 \\ 2 \\ 1\end{bmatrix}=\begin{bmatrix}0 \\ 1 \\ 0 \\ 1\end{bmatrix}\hbox{ mod 2}.

Als we een manier kunnen vinden om deze exponent-vectoren bij elkaar op te tellen (gelijkwaardig aan het vermenigvuldigen van de corresponderende relaties met elkaar) om de vector 0 (mod 2) te produceren, dan kunnen we een congruentie van kwadraten krijgen. Hierdoor kunnen we de exponent-vectoren bij elkaar in een matrix zetten en een vergelijking formuleren:

c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_n\mathbf{v}_n=\mathbf{0}\hbox{ (mod 2)}.

Dit kan geconverteerd worden in een matrix vergelijking:

\begin{bmatrix}
v_{11} & v_{12} & \cdots & v_{1n}\\
v_{21} & v_{22} & \cdots & v_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
v_{n1} & v_{n2} & \cdots & v_{nn}
\end{bmatrix}\begin{bmatrix}c_1 \\ c_2 \\ \vdots \\ c_n\end{bmatrix}=\begin{bmatrix}0\\0\\ \vdots\\0\end{bmatrix}\hbox{ (mod 2)}.

Deze matrix vergelijking is dan opgelost om de vector c te vinden. Dan:

\prod_{k}x_k^2\equiv\prod_{k}p(x_k)\pmod{n}

Waar de producten alle k overnemen waarvoor geldt ck = 1. Minstens een van de ck moet er één zijn. Wegens de manier van oplossen voor c, is de rechterkant van de bovenstaande congruentie een kwadraat. We hebben een congruentie van kwadraten.

Voorbeelden[bewerken]

Voorbeeld 1[bewerken]

Neem de factorbasis {2,3,5,7}, we zullen proberen om 65621 te factoriseren.

261^2 \mod 65621 = 2500 = 2^2 \cdot 5^4

Vanwege het feit dat de exponent van de priemgetallen allemaal even zijn, kunnen we gelijk naar de volgende stap gaan:

(261 - 2 \cdot 5^2)(261 + 2 \cdot 5^2)\mod 65621 =0

We maken hierbij gebruik van:

x^2 - y^2\mod N =0

oftewel:

 (x - y)(x + y)\mod N =0

We weten nu hoe we 65621 kunnen ontbinden in priemgetallen:

65621 = 211 \cdot 311

Voorbeeld 2[bewerken]

We proberen nu 94563 te factoriseren.

Neem de factorbasis {2,3,5,7,11,13}

831^2 \mod 94563 = 12100 = 2^2 \cdot 5^2 \cdot 11^2
(831 - 2\cdot 5 \cdot 11)(831 + 2\cdot 5 \cdot 11)\mod  94563 =0
94563 = 711 \cdot 931\mod  94563 = 0

We gaan nu verder om 711 en 931 te ontbinden.

We starten met 711.

27^2 \mod 711 = 18 = 2\cdot 3^2
31^2 \mod 711 = 250= 2\cdot 5^3
33^2 \mod 711 = 378 = 2\cdot 3^3\cdot 7
114^2 \mod 711 = 189 = 3^3\cdot 7
(27\cdot 33\cdot 114 - 2\cdot 3^3\cdot 7)(27\cdot 33\cdot 114 + 2\cdot 3^3\cdot 7)\mod 711 =0

Dus:

234\cdot 79\mod 711 =0 en ggd(234,711)=9.

We kunnen nu 711 ontbinden:

711 = 3^2\cdot 79

Vervolgens gaan we verder met 931:

53^2 \mod 931 = 16 = 2^4
(53 - 2^2)(53 + 2^2)\mod 931 =0

Dus:

931 = 49\cdot 57\mod 931 =0

We kunnen nu ook 931 ontbinden:

931 = 7^2\cdot 19

We gaan nu terug naar 94563 om dit te ontbinden in priemgetallen, namelijk:

94563 = 3^2\cdot7\cdot19\cdot79

De kwadratische zeef is een optimalisering van Dixons methode. Het geeft kwadratische overeenstemming om geschikte x-waarden veel sneller te vinden dan door eenvoudig random te selecteren. Dit is duidelijk uit deze twee voorbeelden te zien.

Bronnen, noten en/of referenties