Kalkulator faktoryzacji Fermata

O tym kalkulatorze

Metoda faktoryzacji Fermata wykorzystuje fakt, że każdą nieparzystą liczbę całkowitą N można zapisać jako różnicę dwóch kwadratów, N = a² − b² = (a−b)(a+b). Algorytm zaczyna od a = ⌈√N⌉ i w każdym kroku zwiększa a o 1, sprawdzając, czy a² − N samo jest kwadratem liczby całkowitej (b²); gdy tak jest, N natychmiast rozkłada się na (a−b)(a+b). Kalkulator uruchamia tę pętlę i pokazuje każdy krok, który wykonał, by znaleźć czynniki.

Metoda zbiega w bardzo niewielu krokach, gdy dwa czynniki N są blisko siebie — jej główna słabość jest też jej najważniejszym zastosowaniem w praktyce: studenci kryptografii i badacze bezpieczeństwa używają faktoryzacji Fermata, aby pokazać, dlaczego moduły RSA muszą być budowane z liczb pierwszych leżących daleko od siebie, ponieważ liczby pierwsze wybrane zbyt blisko siebie czynią moduł banalnie łatwym do złamania. To także standardowe ćwiczenie na zajęciach z teorii liczb do ilustrowania rozumowania na różnicy kwadratów.