La fattorizzazione con il metodo di Fermat

Qualche tempo fa (precisamente in questo articolo) abbiamo parlato di come fattorizzare un numero con il metodo brute force. Ci siamo detti che è un metodo semplice ma estremamente lento, e anche che ha senso utilizzarlo soltanto quando il numero da fattorizzare è molto piccolo. Oggi parleremo di un metodo decisamente più interessante dal punto di vista pratico: il metodo di Fermat.

Partiamo con un teorema che probabilmente avete studiato alle scuole medie. Se avete due numeri (che per semplicità chiameremo A e B), allora il quadrato del primo numero meno il quadrato del secondo numero è uguale al prodotto della somma per la differenza. In pratica:

A2 - B2 = (A + B)(A - B)

Questo risultato di matematica viene spesso chiamato “differenza di due quadrati“.

Quando diciamo che è un numero è un quadrato, intendiamo dire che la radice quadrata di quel numero è senza la virgola. Nella tabella qui sotto (colonna di sinistra) trovate l’elenco dei numeri da 1 a 100 che sono quadrati:

Numeri quadrati	Radice quadrata
1	1
4	2
9	3
16	4
25	5
36	6
49	7
64	8
81	9
100	10

Una nota importante: dato un numero N, indicheremo la sua radice quadrata con sqrt(N). Ad esempio:

• 5 = sqrt(25) perché 5 è la radice quadrata di 25
• 10 = sqrt(100) perché 10 è la radice quadrata di 100
• 12 = sqrt(144) perché 12 è la radice quadrata di 144

L’ idea alla base del metodo di Fermat è quella di scrivere il numero da fattorizzare come differenza di due quadrati. Supponiamo che un hacker di nome Oscar decida di fattorizzare un numero N che è il prodotto di due numeri primi distinti. (Nota bene: se i passaggi scritti sotto vi sembrano complicati, non demordete! Tra poco farò un esempio che dovrebbe rendervi tutto più chiaro). Ecco come procede Oscar:

1. Oscar calcola N + 1. Se sqrt(N + 1) è un numero senza la virgola, allora vuol dire che N + 1 è un numero quadrato e che N è la differenza di due quadrati: N + 1 e 1. Se invece sqrt(N + 1) è un numero con la virgola, allora Oscar prosegue con il passo successivo del metodo.
2. Oscar calcola N + 4. Se sqrt(N + 4) è un numero senza la virgola, allora vuol dire che N + 4 è un numero quadrato e che N è la differenza di due quadrati: N + 4 e 4. Se invece sqrt(N + 4) è un numero con la virgola, allora Oscar prosegue con il passo successivo del metodo.
3. Oscar calcola N + 9. Se sqrt(N + 9) è un numero senza la virgola, allora vuol dire che N + 9 è un numero quadrato e che N è la differenza di due quadrati: N + 9 e 9. Se invece sqrt(N + 9) è un numero con la virgola, allora Oscar prosegue con il passo successivo del metodo.
4. Oscar calcola N + 16. Se sqrt(N + 16) è un numero senza la virgola, allora vuol dire che N + 16 è un numero quadrato e che N è la differenza di due quadrati: N + 16 e 16. Se invece sqrt(N + 16) è un numero con la virgola, allora Oscar prosegue con il passo successivo del metodo.
5. e così via ………………………………………………………………………………………………………………………………………………………………………

Tutto poco chiaro? Vi faccio un esempio. Supponiamo che il numero da fattorizzare sia 3869. Ecco come procede il nostro hacker:

1. Oscar calcola 3869 + 1 = 3870. Il numero che ha ottenuto non è un quadrato perché la sua radice quadrata è sqrt(3870) = 62,2093. Oscar prosegue quindi con il passo successivo del metodo.
2. Oscar calcola 3869 + 4 = 3873. Il numero che ha ottenuto non è un quadrato perché la sua radice quadrata è sqrt(3873) = 62,2334. Oscar prosegue quindi con il passo successivo del metodo.
3. Oscar calcola 3869 + 9 = 3878. Il numero che ha ottenuto non è un quadrato perché la sua radice quadrata è sqrt(3878) = 62,2736. Oscar prosegue quindi con il passo successivo del metodo.
4. Oscar calcola 3869 + 16 = 3885. Il numero che ha ottenuto non è un quadrato perché la sua radice quadrata è sqrt(3885) = 62,3298. Oscar prosegue quindi con il passo successivo del metodo.
5. e così via …………………………………………………………………………………………………………………………………………………………
6. Al passo 10, Oscar calcola 3869 + 100 = 3969. Il numero che ha ottenuto stavolta è un quadrato perché sqrt(3969) = 63. Questo significa che: 3869 = 3969 – 100 = (63 + 10)(63 – 10) = 53 x 73 Oscar ha così scoperto che il numero 3869 si fattorizza nel prodotto di 53 e 73.

Il metodo di Fermat è veloce? Dipende. Se il numero da fattorizzare è il prodotto di due primi e la differenza tra i due primi è piccola (dove con “differenza” si intende “il più grande meno il più piccolo”), allora il metodo di Fermat è veloce. Se invece non è così, allora il metodo di Fermat diventa un metodo lento. Nella pratica, però, il metodo di Fermat non è quasi mai utilizzato. C’è infatti un altro metodo, detto di Dixon (e sarebbe bello poterne parlare un giorno su questo blog!) che risulta efficace negli stessi casi in cui lo è quello di Fermat ma che è molto più veloce! L’unica “pecca” del metodo di Dixon è che è leggermente più complicato dal punto di vita matematico. In ogni caso, sarà per un’altra puntata del blog. Nel frattempo, scrivete pure nei commenti se avete dubbi o domande riguardanti la fattorizzazione con il metodo di Fermat. Buona crittografia! xD