Kalkulačka Fermatovy faktorizace

O této kalkulačce

Fermatova faktorizační metoda využívá toho, že každé liché celé číslo N lze zapsat jako rozdíl dvou čtverců, N = a² − b² = (a−b)(a+b). Algoritmus začíná v a = ⌈√N⌉ a v každém kroku zvyšuje a o 1, přičemž kontroluje, zda je a² − N samo dokonalým čtvercem (b²); jakmile ano, N se okamžitě rozloží na (a−b)(a+b). Tato kalkulačka tuto smyčku provede a ukáže každý krok, který k nalezení činitelů udělala.

Metoda konverguje ve velmi malém počtu kroků, když jsou oba činitelé N blízko sebe — její hlavní slabina je zároveň jejím nejdůležitějším praktickým využitím: studenti kryptografie a bezpečnostní výzkumníci pomocí Fermatovy faktorizace ukazují, proč musí být moduly RSA sestaveny z prvočísel, která jsou od sebe daleko, protože prvočísla zvolená příliš blízko sebe činí modul triviálně prolomitelným. Je to také standardní cvičení v kurzech teorie čísel pro ilustraci uvažování o rozdílu čtverců.