Il metodo di fattorizzazione di Fermat
Il metodo di fattorizzazione di Fermat è un algoritmo per scomporre un numero intero \( n \) in due fattori, basato sulla rappresentazione di \( n \) come differenza di due quadrati:\[ n = x^2 - y^2 = (x + y)(x - y) \]
Come funziona?
Ecco la procedura di calcolo
- Considero un numero intero \( n \) dispari: Se \( n \) è pari, lo divido ripetutamente per 2 fino a ottenere un numero dispari.
- Cerco il più piccolo intero \( k \) tale che \[ k^2 \geq n \] In altre parole trovo \( k = \lceil \sqrt{n} \rceil \), ovvero il primo intero maggiore o uguale alla radice quadrata di \( n \).
- Cerco un valore \( x \) tale che \( x^2 - n = y^2 \) sia un quadrato a partire da $ x=k $.
- Se il test fallisce incremento \( x \) e ripeto il test \( x^2 - n \).
- Se il risultato è un quadrato perfetto \( x^2-n = y^2 \), allora \( n \) lo posso scrivere come: \[ n = (x+y) \cdot (x-y) \] I numeri $ x $ e $ y $ sono la fattorizzazione del numero $ n $.
I fattori ottenuti non sono necessariamente dei numeri primi.
Se i fattori ottenuti non sono primi, ripeto il procedimento su ciascuno dei fattori.
Nota. Il metodo di Fermat è molto efficiente quando i due fattori di \( n \) sono vicini tra loro, cioè quando \( n \) è prodotto di due numeri grandi e simili. Se invece i fattori sono molto sbilanciati (uno grande e uno piccolo), il metodo diventa inefficiente, perché servono molti tentativi prima di trovare un quadrato perfetto.
Un esempio pratico
Voglio fattorizzare il numero intero \( n = 5959 \).
Per prima cosa calcolo \( k \):
\[ \sqrt{5959} \approx 77.2 \Rightarrow k = 78 \]
Poi calcolo \( k^2 - n \):
\[ 78^2 - 5959 = 6084 - 5959 = 125 \]
Il numero 125 non è un quadrato perfetto perché $ \sqrt{125} \approx 11.18 $, quindi incremento \( k \) di una unità.
\[ 79^2 - 5959 = 6241 - 5959 = 282 \]
Il risultato non è ancora un quadrato perfetto perché $ \sqrt{79} \approx 8.89 $.
Cos'è un quadrato perfetto. Un quadrato perfetto è un numero intero che può essere scritto come il quadrato di un altro numero intero. $$ y=x^2 $$ Ad esempio, $ y=25 $ è un quadrato perfetto perché $ y=5^2 $. Per riconoscere un quadrato perfetto basta calcolare la radice quadrata del numero, se la radice $ \sqrt{y} \in \mathbb{Z} $ è un numero intero allora il radicando è un quadrato perfetto. Ad esempio $ \sqrt{25} = 5 $.
Quindi, continuo a incrementare fino a trovare un valore valido.
\[ 80^2 - 5959 = 6400 - 5959 = 441 \]
\[ 81^2 - 5959 = 6561 - 5959 = 602 \]
\[ 82^2 - 5959 = 6724 - 5959 = 765 \]
\[ 83^2 - 5959 = 6889 - 5959 = 930 \]
\[ 84^2 - 5959 = 7056 - 5959 = 1097 \]
\[ 85^2 - 5959 = 7225 - 5959 = 1266 \]
\[ 86^2 - 5959 = 7396 - 5959 = 1437 \]
\[ 87^2 - 5959 = 7569 - 5959 = 1610 \]
\[ 88^2 - 5959 = 7744 - 5959 = 1785 \]
\[ 89^2 - 5959 = 7921 - 5959 = 1962 \]
\[ 90^2 - 5959 = 8100 - 5959 = 2141 \]
Finalmente, ottengo un quadrato perfetto.
\[ 91^2 - 5959 = 8281 - 5959 = 2322 = 48^2 \]
Pertanto, posso scrivere la fattorizzazione come differenza di due quadrati.
\[ n = x^2 - y^2 = (x + y)(x - y) \]
In questo caso $ x =91 $ e $ y = 48 $
\[ 5959 = (91 + 48) \cdot (91 - 48) = 139 \times 43 \]
Dunque, \( 5959 = 139 \times 43 \), e ho trovato due fattori del numero.
In questo caso sia 139 che 43 sono numeri primi, quindi la fattorizzazione è definitiva.
Per verificarlo, controllo se hanno divisori primi diversi da 1 e da se stessi.
Il numero 139 è primo perché:
- È dispari, quindi non è divisibile per 2.
- La somma delle cifre è 1 + 3 + 9 = 13, che non è divisibile per 3.
- Non termina con 0 o 5, quindi non è divisibile per 5.
- Controllando con i numeri primi fino a \( \sqrt{139} \approx 11.79 \) ovvero 2, 3, 5, 7, 11, nessuno divide 139.
Il numero 43 è primo perché:
- È dispari, quindi non è divisibile per 2.
- La somma delle cifre è 4 + 3 = 7, che non è divisibile per 3.
- Non termina con 0 o 5, quindi non è divisibile per 5.
- Se controllo i numeri primi dino a \( \sqrt{43} \approx 6.56 \), ovvero 2, 3 e 5, nessuno divide 43.
Esempio 2
Il metodo di fattorizzazione di Fermat è molto rapido quando il numero $ n $ ha dei fattori vicini a $ \sqrt{n} $.
Ad esempio, considero il numero
$$ n = 127433 $$
Calcolo il valore iniziale \( k \):
\[ \sqrt{127433} \approx 356.97 \Rightarrow k = 357 \]
Poi calcolo \( k^2 - n \):
\[ 357^2 - 127433 = 127449 - 127433 = 16 = 4^2 \]
Poiché $ 16 $ è un quadrato perfetto, dopo un solo passaggio ottengo i fattori del numero.
\[ n = x^2 - y^2 = (x + y)(x - y) \]
In questo caso $ x =357 $ e $ y = 4 $
\[ 127433 = (357 + 4) \cdot (357 - 4) = 361 \cdot 353 \]
Note
Alcune considerazioni aggiuntive sul metodo di Fermat
- Il metodo di Fermat ha una complessità esponenziale
Il metodo di Fermat è interessante e semplice, ma ha una complessità esponenziale nel caso peggiore. Per la fattorizzazione di numeri grandi, è generalmente poco pratico, e viene sostituito da algoritmi più efficienti come il Crivello Quadratico o il Crivello dei Campi di Numeri.Nota. Il metodo di Fermat è efficace solo quando i fattori di \( n \) sono vicini tra loro, cioè quando il numero è il prodotto di due fattori \( a \) e \( b \) tali che: \[ a \approx b \approx \sqrt{n} \] Tuttavia, la sua complessità diventa esponenziale quando uno dei due fattori è molto più grande dell’altro.
E così via.
