La fattorizzazione con il metodo (p – 1) di Pollard

In questo articolo scopriremo come fattorizzare il prodotto di due numeri primi con il metodo “(p – 1) di Pollard”.

Supponiamo che un hacker di nome Oscar sia intenzionato a fattorizzare un numero N che è il prodotto di due numeri primi. Ecco come procede Oscar:

1. Oscar sceglie un numero naturale A coprimo con N
2. Oscar sceglie un numero naturale B abbastanza piccolo
3. Oscar calcola B!, ovvero il fattoriale di B
4. Oscar calcola A^B! (mod N) – 1 e chiama il risultato D. A questo punto:
   • Se D = 0, allora Oscar torna al punto 1. del metodo e sceglie un altro valore possibile per A
   • Se D è diverso da zero, allora Oscar prosegue con il suo metodo
5. Oscar calcola il massimo comune divisore tra N e D. A questo punto:
   • Se il risultato è diverso da 1, allora P coincide con il massimo comune divisore tra N e D
   • Se il risultato è uguale a 1, allora Oscar torna al punto 1. del metodo e sceglie un altro valore possibile per A
6. Oscar calcola Q = N/P

Facciamo un esempio:

1. Supponiamo che l’obiettivo di Oscar sia scoprire la chiave privata di un cifrario RSA con chiave pubblica N = 2813 ed E = 5
2. Oscar sceglie un numero naturale A coprimo con 2813. Supponiamo A = 2
3. Oscar sceglie un numero naturale B abbastanza piccolo. Supponiamo B = 7
4. Oscar calcola il fattoriale di 7. Il risultato è 7! = 2 x 3 x 4 x 5 x 6 x 7 = 5040
5. Oscar calcola D = 2⁵⁰⁴⁰ (mod 2813) – 1 = 0
6. Siccome con A = 2 l’algoritmo non funziona, Oscar sceglie un altro valore possibile per A. Supponiamo A = 5
7. Oscar calcola D = 5⁵⁰⁴⁰ (mod 2813) – 1 = 581 – 1 = 580
8. Oscar calcola il massimo comune divisore tra 2813 e 580 usando il metodo di Euclide. Il risultato è P = 29
9. Oscar calcola Q = 2813/29 = 97

Rimane ora da risolvere un’ ultima questione:

Perché il metodo “(p – 1) di Pollard” si chiama così?

• Il metodo di cui abbiamo discusso in questo articolo si chiama di Pollard perché è stato inventato nel 1974 dal matematico inglese John Pollard
• L’ appellativo “(p – 1)” è invece legato ad una osservazione di carattere matematico. La velocità o meno del metodo di Pollard applicato ad N = P x Q è infatti legata alla fattorizzazione di (P – 1) e di (Q – 1). (Per i dettagli vi rimando ai prossimi articoli! xD)

Il nostro articolo sul metodo “(p – 1) di Pollard” termina qui. Ovviamente scrivete senza freno nei commenti se avete dubbi o domande a riguardo. Buona crittografia! xD