Hva er Fermats faktoriseringsmetode?

Fermats faktoriseringsmetode er en metode for å faktorisere oddetall som har to omtrent like store faktorer.

Fremgangsmetode for å faktorisere $n$

Steg 1: Sett $a$ lik minste heltall større enn eller lik $\sqrt{n}$.

Steg 2: Undersøk om $a^2 - n$ er et kvadrattall.

• Hvis ikke, øk $a$ med én til $a^2 - n$ blir et kvadrattall.

Steg 3: Sett $b^2 = a^2 - n$ og bruk tredje kvadratsetning:

Nå har vi faktorisert $n$ i to nesten like store faktorer.

Steg 4: Sjekk resultatet: