Fermat'n Tekijöihinjaon Laskuri

Tietoa tästä laskurista

Fermat'n tekijöihinjakomenetelmä hyödyntää sitä, että mikä tahansa pariton kokonaisluku N voidaan kirjoittaa kahden neliön erotuksena, N = a² − b² = (a−b)(a+b). Algoritmi aloittaa arvosta a = ⌈√N⌉ ja kasvattaa a:ta yhdellä joka askeleella tarkistaen, onko a² − N itsessään täydellinen neliö (b²); heti kun on, N hajoaa välittömästi tekijöihin (a−b)(a+b). Tämä laskuri suorittaa tämän silmukan ja näyttää jokaisen askeleen, jonka se otti tekijöiden löytämiseksi.

Menetelmä suppenee hyvin harvoilla askelilla, kun N:n kaksi tekijää ovat lähellä toisiaan – sen suurin heikkous on myös sen tärkein käytännön käyttötarkoitus: kryptografian opiskelijat ja tietoturvatutkijat käyttävät Fermat'n tekijöihinjakoa osoittaakseen, miksi RSA-moduulit on rakennettava alkuluvuista, jotka ovat kaukana toisistaan, sillä liian lähelle toisiaan valitut alkuluvut tekevät moduulista triviaalisti murrettavan. Se on myös tavallinen harjoitus lukuteorian kursseilla neliöiden erotuksella päättelyn havainnollistamiseksi.