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 voor de ontbinding van het gehele getal is gebaseerd op het uitgangspunt van Fermats factorisatiemethode door te zoeken naar twee kwadraten die modulo 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 veel zwakkere voorwaarde ‘heeft alleen kleine priemfactoren’.

Het algoritme zoekt nu kwadraten die modulo het product zijn van machten van een vast aantal kleine priemgetallen en zoekt het product van een aantal van zulke kwadraten waarin alle machten van de priemgetallen even zijn:

Dan is:

en daarmee is

een veelvoud van .

Algoritme[bewerken]

Kies een bovengrens voor de te gebruiken priemgetallen . Deze verzameling priemgetallen wordt de factorbasis genoemd. Zoek daarna getallen in het bereik waarvan de kwadraten modulo B-glad zijn, dus alleen priemfactoren uit de factorbasis hebben.

.

Vervolgens wordt uit de getallen 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 nl. de matrix met de machten, dan wordt een vector gezocht waarvoor . De vector geeft aan welke van de tot de gewenste selectie behoren.

Als geen echte deler van oplevert, is kennelijk , en moet men een andere selectie proberen of andere bepalen, eventueel met een nieuwe factorbasis.

Voorbeelden[bewerken]

Voorbeeld 1[bewerken]

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

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

Dus

Voorbeeld 2[bewerken]

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

Dus geldt:

en

Eenvoudig is te zien dat 711 deelbaar is door 9, en 931 door 7, zodat

Hoewel het niet moeilijk is in te zien dat

kan dit ook met het algoritme bepaald worden.

Als eindresultaat volgt:

Kwadratische zeef[bewerken]

De kwadratische zeef is een optimalisering van Dixons methode. Daarmee worden geschikte waarden voor in de buurt van gekozen zodanig dat klein is en de kans op het vinden van een glad getal sterk vergroot wordt.