Dixons factorisatiemethode

In de getaltheorie, een deelgebied van de wiskunde, wordt de Dixons factorisatiemethode, ook wel Dixons algoritme genoemd, algemeen gebruikt om positieve gehele getallen in priemgetallen te ontbinden. Het algoritme is in 1981 door John Dixon bedacht, een wiskundige van de Carleton University in Ottawa.

Werking

Dixons methode om een geheel getal ${\displaystyle n}$ te ontbinden is gebaseerd op het uitgangspunt van Fermats factorisatiemethode door naar twee kwadraten te zoeken, die modulo ${\displaystyle n}$ equivalent zijn. Fermats factorisatiemethode vindt zulke kwadraten door systematisch alle mogelijkheden na te gaan. Dat kost in het algemeen veel rekentijd.

Daarom vervangt Dixon in zijn methode de voorwaarde ‘is het kwadraat van een geheel getal’ door de zwakkere voorwaarde ‘heeft alleen kleine priemfactoren’.

Het algoritme zoekt kwadraten ${\displaystyle z_{i}^{2}\equiv p_{1}^{m_{1}}\cdot \ldots \cdot p_{n}^{m_{n}}{\bmod {n}}}$ die modulo ${\displaystyle n}$ het product zijn van machten van een vast aantal kleine priemgetallen ${\displaystyle p_{1},\ldots ,p_{n}}$ en zoekt het product van een aantal van zulke kwadraten waarin alle machten van de priemgetallen even zijn:

${\displaystyle z_{1}^{2}z_{2}^{2}\ldots z_{r}^{2}\equiv p_{1}^{2m_{1}}\cdot \ldots \cdot p_{n}^{2m_{n}}{\bmod {n}}}$

Dan is:

${\displaystyle x^{2}\equiv z_{1}^{2}z_{2}^{2}\ldots z_{r}^{2}\equiv \left(p_{1}^{m_{1}}\cdot \ldots \cdot p_{n}^{m_{n}}\right)^{2}\equiv y^{2}{\bmod {n}}}$

en daarmee is

${\displaystyle x^{2}-y^{2}=(x+y)(x-y)}$ een veelvoud van ${\displaystyle n}$.

Kies een bovengrens ${\displaystyle B}$ voor de te gebruiken priemgetallen ${\displaystyle p_{1}=2,p_{2}=3,\ldots ,p_{k}\leq B}$. Deze verzameling priemgetallen wordt de factorbasis genoemd. Zoek daarna getallen ${\displaystyle (z_{i})}$ in het bereik ${\displaystyle \lceil {\sqrt {n}}\rceil \leq z_{i}\leq n}$ waarvan de kwadraten modulo ${\displaystyle n}$ B-glad zijn, dus alleen priemfactoren uit de factorbasis hebben.

${\displaystyle z_{i}^{2}=\prod _{j=1}^{k}p_{j}^{m_{ij}}{\bmod {n}}}$.

Vervolgens wordt uit de getallen ${\displaystyle (z_{i})}$ een selectie gemaakt, waarvan het product alleen even machten van de priemgetallen bevat. Dit kan gebeuren door gebruik te maken van methoden uit de lineaire algebra.

Zij ${\displaystyle \mathbf {M} =(m_{ij})}$ de matrix met de machten, dan wordt een vector ${\displaystyle \mathbf {c} }$ gezocht waarvoor ${\displaystyle \mathbf {Mc} \equiv 0{\bmod {2}}}$. De vector ${\displaystyle \mathbf {c} }$ geeft aan welke van de ${\displaystyle (z_{i})}$ tot de gewenste selectie behoren.

Als ${\displaystyle \operatorname {ggd} (x-y,n)}$ geen echte deler van ${\displaystyle n}$ oplevert, is kennelijk ${\displaystyle x\equiv \pm y{\bmod {n}}}$ en moet men een andere selectie proberen of andere ${\displaystyle (z_{i})}$ bepalen, eventueel met een nieuwe factorbasis.

Voorbeelden

Voorbeeld 1

Neem voor het ontbinden van het getal 65621 als factorbasis {2,3,5,7}. Er geldt: ${\displaystyle {\sqrt {65621}}>256}$. Het eerste getal waarvan het kwadraat modulo 65621 alleen factoren uit de factorbasis heeft is 261:

${\displaystyle 261^{2}\mod 65621=2500=2^{2}\cdot 5^{4}}$

Omdat de exponenten van de priemgetallen beide even zijn, kan gelijk de volgende stap worden gedaan:

${\displaystyle (261-2\cdot 5^{2})(261+2\cdot 5^{2})=211\times 311\mod 65621=0}$

Dus

${\displaystyle 65621=211\times 311}$

Voorbeeld 2

Neem voor het ontbinden van 94563 de factorbasis {2,3,5,7,11,13}.

${\displaystyle 821^{2}\mod 94563=12100=2^{2}\cdot 5^{2}\cdot 11^{2}}$

Dus geldt:

${\displaystyle (821-2\times 5\times 11)(821+2\times 5\times 11)=711\times 931{\bmod {94563}}=0}$

en

${\displaystyle 711\times 931=94563\times 7}$

711 kan door 9 worden gedeeld en 931 door 7, zodat

${\displaystyle 3^{2}\times 79\times 133=94563}$

Hoewel het duidelijk is dat

${\displaystyle 133=7\times 19}$

kan dit ook met het algoritme worden bepaald.

${\displaystyle 13^{2}\mod 133=36=2^{2}\times 3^{2}}$

${\displaystyle (13-2\times 3)(13+2\times 3)=7\times 19=133}$

Als eindresultaat volgt:

${\displaystyle 94563=3^{2}\times 7\times 19\times 79}$

Kwadratische zeef

De kwadratische zeef is een optimalisering van Dixons methode. Daarmee worden geschikte waarden voor ${\displaystyle x}$ in de buurt van ${\displaystyle {\sqrt {\ n\ }}}$ gekozen zodanig dat ${\displaystyle x^{2}{\bmod {n}}}$ klein is en de kans op het vinden van een glad getal sterk wordt vergroot.

literatuur

• JD Dixon. Asymptotically fast factorization of integers, 1981. voor Math. Comput., 36, blz 255-260.

bronvermelding

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Dixon's factorization method op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.