Calcolatore della fattorizzazione di Fermat

Informazioni su questo calcolatore

Il metodo di fattorizzazione di Fermat sfrutta il fatto che ogni intero dispari N può essere scritto come differenza di due quadrati, N = a² − b² = (a−b)(a+b). L'algoritmo parte da a = ⌈√N⌉ e aumenta a di 1 a ogni passo, controllando se a² − N è a sua volta un quadrato perfetto (b²); nel momento in cui lo è, N si scompone subito in (a−b)(a+b). Questo calcolatore esegue quel ciclo e mostra ogni passo compiuto per trovare i fattori.

Il metodo converge in pochissimi passi quando i due fattori di N sono vicini tra loro; il suo principale punto debole è anche il suo uso reale più importante: studenti di crittografia e ricercatori di sicurezza usano la fattorizzazione di Fermat per mostrare perché i moduli RSA devono essere costruiti con numeri primi ben distanti tra loro, dato che primi scelti troppo vicini rendono il modulo banalmente violabile. È anche un esercizio classico dei corsi di teoria dei numeri per illustrare il ragionamento sulla differenza di quadrati.