Fermo faktorizacijos skaičiuoklė

Apie šią skaičiuoklę

Fermo faktorizacijos metodas remiasi tuo, kad bet kurį nelyginį sveikąjį skaičių N galima užrašyti kaip dviejų kvadratų skirtumą: N = a² − b² = (a−b)(a+b). Algoritmas pradeda nuo a = ⌈√N⌉ ir kiekviename žingsnyje didina a vienetu, tikrindamas, ar a² − N pats yra tikslusis kvadratas (b²); kai taip nutinka, N iškart išsiskaido į (a−b)(a+b). Ši skaičiuoklė vykdo tą ciklą ir parodo kiekvieną žingsnį, kurį žengė ieškodama daugiklių.

Metodas susilieja per labai nedaug žingsnių, kai abu N daugikliai yra artimi – didžiausias jo trūkumas kartu yra ir svarbiausias praktinis panaudojimas: kriptografijos studentai ir saugumo tyrėjai Fermo faktorizaciją naudoja parodydami, kodėl RSA moduliai turi būti sudaromi iš tarpusavyje labai nutolusių pirminių skaičių, nes per arti parinkti pirminiai skaičiai modulį padaro trivialiai įveikiamą. Tai ir standartinis skaičių teorijos kursų uždavinys kvadratų skirtumo samprotavimui iliustruoti.