Kalkulačka Fermatovej faktorizácie

O tejto kalkulačke

Fermatova faktorizačná metóda využíva skutočnosť, že každé nepárne celé číslo N možno zapísať ako rozdiel dvoch štvorcov, N = a² − b² = (a−b)(a+b). Algoritmus začína pri a = ⌈√N⌉ a v každom kroku zvýši a o 1, pričom kontroluje, či je a² − N samo o sebe úplný štvorec (b²); v okamihu, keď je, N sa hneď rozloží na (a−b)(a+b). Táto kalkulačka spustí túto slučku a zobrazí každý krok, ktorý na nájdenie činiteľov vykonala.

Metóda konverguje vo veľmi málo krokoch, keď sú dva činitele čísla N blízko seba — jej hlavná slabina je zároveň jej najdôležitejším reálnym využitím: študenti kryptografie a bezpečnostní výskumníci pomocou Fermatovej faktorizácie ukazujú, prečo musia byť moduly RSA zostavené z prvočísel, ktoré sú ďaleko od seba, keďže príliš blízko zvolené prvočísla robia modul triviálne prelomiteľným. Je to tiež štandardné cvičenie v kurzoch teórie čísel na ilustráciu uvažovania o rozdiele štvorcov.