Reiknivél fyrir Fermat-þáttun

Um þessa reiknivél

Þáttunaraðferð Fermats nýtir þá staðreynd að sérhverja oddatölu N má rita sem mismun tveggja ferninga, N = a² − b² = (a−b)(a+b). Reikniritið byrjar á a = ⌈√N⌉ og hækkar a um 1 í hverju skrefi og athugar hvort a² − N sé sjálf fullkominn ferningur (b²); um leið og svo er þáttast N strax í (a−b)(a+b). Þessi reiknivél keyrir þessa lykkju og sýnir hvert skref sem tekið var til að finna þættina.

Aðferðin samleitir á mjög fáum skrefum þegar tveir þættir N liggja nálægt hvor öðrum — helsti veikleiki hennar er jafnframt mikilvægasta notkun hennar í raunveruleikanum: nemendur í dulritunarfræði og öryggisrannsakendur nota Fermat-þáttun til að sýna fram á hvers vegna RSA-margfeldi verða að vera smíðuð úr frumtölum sem eru langt hvor frá annarri, því að frumtölur sem valdar eru of nálægt hvor annarri gera margfeldið léttbrjótanlegt. Hún er einnig hefðbundið verkefni í námskeiðum í talnafræði til að útskýra rökhugsun um mismun ferninga.