Calculator factorizare Fermat

Despre acest calculator

Metoda de factorizare a lui Fermat exploatează faptul că orice număr întreg impar N poate fi scris ca diferență a două pătrate, N = a² − b² = (a−b)(a+b). Algoritmul pornește de la a = ⌈√N⌉ și crește a cu 1 la fiecare pas, verificând dacă a² − N este el însuși un pătrat perfect (b²); în momentul în care este, N se descompune imediat în (a−b)(a+b). Acest calculator rulează bucla respectivă și arată fiecare pas făcut pentru a găsi factorii.

Metoda converge în foarte puțini pași când cei doi factori ai lui N sunt apropiați — principala sa slăbiciune este totodată și cea mai importantă utilizare practică: studenții la criptografie și cercetătorii în securitate folosesc factorizarea Fermat pentru a demonstra de ce modulii RSA trebuie construiți din numere prime aflate departe unul de altul, deoarece numerele prime alese prea aproape unul de altul fac modulul ușor de spart. Este totodată un exercițiu standard în cursurile de teoria numerelor, pentru a ilustra raționamentul cu diferența de pătrate.