Fermats factorisatiemethode

Fermats factorisatiemethode is een algoritme in de getaltheorie voor het ontbinden van een oneven samengesteld getal $n$ in twee factoren $a$ en $b$, zodat dus $n=a\cdot b$. Deze methode om een getal in twee priemfactoren te ontbinden is vooral effectief als het getal kan worden voorgesteld als een product van ongeveer even grote factoren. De methode vormt ook de basis van algemene factorisatiemethoden voor grote getallen, die minder rekentijd nodig hebben.

Pierre de Fermat beschreef in 1643 deze nu naar hem genoemde methode in een brief die vermoedelijk aan Mersenne of aan Frenicle de Bessy was gericht. Hij liet in deze brief de methode zien door het getal 2.027.651.281 in twee priemgetallen te ontbinden. Sommige historici vermoeden dat de methode al eerder bekend was.

Algoritme

Laat $n$ het oneven getal zijn dat ontbonden moet worden en $m=\lceil {\sqrt {n}}\rceil$ het kleinste gehele getal groter dan of gelijk aan ${\sqrt {n}}$. De factorisatiemethode van Fermat berekent achtereenvolgens:

$(m+0)^{2}-n$

$(m+1)^{2}-n$

$(m+2)^{2}-n$

$\vdots$

Dit gaat net zo lang door totdat de uitkomst een kwadraat is:

$(m+z)^{2}-n=y^{2}$

Dan is, met $m+z=x$,

$n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b$.

Dit levert de ontbinding van $n$ waarvoor de verhouding $a/b$, met $a\geq b$, het kleinst is.

Door het inspecteren van de laatste twee cijfers van de berekende uitkomst, kan men in veel gevallen uitsluiten dat de uitkomst een kwadaat is. Een kwadraat heeft als laatste cijfer alleen de mogelijkheid 0, 1, 4, 5, 6 en 9 en als laatste twee cijfers een van de 22 mogelijkheden: 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 en 96. Fermat gebruikte deze eigenschap van kwadraten.

voetnoten

websites

• FactHacks. Fermat's factorization method.