Il metodo ρ di Pollard
Il metodo ρ di Pollard è un algoritmo di fattorizzazione che permette di trovare un divisore non banale di un numero composto \( n \).
L'idea principale è generare una successione di numeri \( x_0, x_1, x_2, \dots \) utilizzando una funzione iterativa e cercare ripetizioni tra i valori.
Quando si verifica una ripetizione, calcolo il MCD tra la differenza di due termini della sequenza e \( n \), ottenendo così un divisore proprio di \( n \).
Nota. Il metodo prende il nome dalla lettera greca ρ (rho) perché la sequenza generata assomiglia a una "coda seguita da un ciclo", proprio come la forma della lettera ρ. È particolarmente efficace quando \( n \) ha fattori primi piccoli, e sfrutta il principio dei cassetti di Dirichlet per individuare ripetizioni in una sequenza di numeri costruita modulo \( n \).
Come funziona?
Per fattorizzare un numero composto \( n \) devo procedere come segue:
- Scelta della funzione iterativa
Scelgo una funzione polinomiale \( f(x) \) che generi la successione, ad esempio: \[ f(x) = x^2 + 1 \] Questa funzione deve essere facile da calcolare e non deve essere biunivoca modulo \( n \). - Generazione della successione
Decido un valore iniziale \( x_0 \) arbitrario e costruisco la successione ricorsivamente: \[ x_1 = f(x_0) \mod n \] \[
x_2 = f(x_1) \mod n \] \[ x_3 = f(x_2) \mod n \\ \vdots \] Prendo alcuni valori (ad esempio una decina).Nota. Dato che l’insieme dei possibili valori è finito (\( \mathbb{Z}_n \) ha solo \( n \) elementi), prima o poi la sequenza inizierà a ripetersi, formando un ciclo. In questo caso, appena trovo due numeri uguali modulo \( n \) devo comunque fermarmi perché i numeri inizieranno a ripetersi ciclicamente. In questo caso è inutile generare altri numeri.
- Ricerca di un divisore tramite il MCD
Calcolo il massimo comune divisore (MCD) tra la differenza dei valori della sequenza \( x_i - x_j \) e \( n \): \[ MCD(|x_i - x_j|, n) \] Se il risultato è un numero maggiore di 1 e minore di \( n \), ho trovato un fattore di \( n \). Se non lo trovo, torno al passo precedente per generare nuovi numeri della successione (se ci sono).
Perché il metodo funziona?
Il metodo sfrutta il principio dei cassetti di Dirichlet: se scelgo abbastanza elementi da un insieme finito (in questo caso \( \mathbb{Z}_n \)), prima o poi due di questi devono coincidere.
Quando la sequenza si ripete, significa che i numeri condividono un divisore con \( n \), che posso trovare con il MCD.
Nota. Questo metodo è detto metodo di Pollard "lento" perché genera prima una lunga sequenza di numeri e solo dopo inizia a cercare divisori, rischiando di sprecare tempo se il fattore era già individuabile nei primi termini. Esiste anche una versione "veloce" di questo metodo che calcola il MCD a ogni passo, trovando subito un divisore appena possibile.
Un esempio pratico
Devo fattorizzare il numero \( n = 111 \)
Scelgo una funzione e valore iniziale. Ad esempio uso:
$$ f(x) = x^2 + 1 $$
E assegno come valore iniziale
$$ x_0 = 1 $$
Calcolo i primi termini modulo 111 della sequenza.
\[ x_1 = f(1) = 1^2 + 1 = 2 \pmod{111} \]
\[ x_2 = f(2) = 2^2 + 1 = 5 \pmod{111} \]
\[ x_3 = f(5) = 5^2 + 1 = 26 \pmod{111} \]
\[ x_4 = f(26) = 26^2 + 1 = 677 \equiv 11 \pmod{111} \]
\[ x_5 = f(11) = 11^2 + 1 = 122 \equiv 11 \pmod{111} \]
A questo punto, la sequenza si ripete, il ciclo si chiude perché \( x_5 \equiv x_4 \mod 111 \).
Quindi, calcolo il $ MCD(|x_i - x_j|, n) $ e cerco una coppia \( i, j \) per cui \( x_i - x_j \) ha un divisore comune con \( n \):
\[ MCD(x_2 - x_1, 111) = MCD(5 - 2, 111) = MCD(3, 111) = 3 \]
Poiché \( 3 \) è un valore diverso da $ \pm 1 \mod 111 $, è un divisore proprio di 111. In altre parole, 3 divide 111 ma non è né 1 né 111, quindi è un divisore proprio.
Una volta trovato un fattore, posso trovare l'altro con una banale divisione.
$$ \frac{111}{3} = 37 $$
Pertanto, \( 37 \) è l'altro fattore primo del numero.
Quindi, i fattori primi di 111 sono:
\[ 111 = 3 \times 37 \]
Ho trovato la fattorizzazione del numero.
Esempio 2
Provo a fattorizzare il numero 8051
\[ n = 8051 \]
Utilizzo la stessa funzione usata nell'esempio precedente ma modulo 8051.
$$ f(x) = x^2 + 1 \mod 8051 $$
Considero come valore iniziale
$$ x_0 = 2 $$
Quindi, calcolo alcuni numero della sequenza \( x_i \)
$$ x_0 = 2$$
$$ x_1 = f(2) = 2^2 + 1 = 5 $$
$$ x_2 = f(5) = 26 $$
$$ x_3 = f(26) = 26^2 + 1 = 677 $$
$$ x_4 = f(677) = 458330 \mod 8051 = 7474 $$
$$ x_5 = f(7474) = 7474^2 + 1 \mod 8051 = 2839 $$
$$ x_6 = f(2839) = 2839^2 + 1 = 8059922 \mod 8051 = 871 $$
Una volta generati alcuni numeri, calcolo i MCD tra le differenze in valore assoluto \( | x_i - x_j | \) e \( n=8051 \)
Inizialmente conviene provare con le differenze rispetto a \( x_0 \) perché i calcoli sono più facili, ma qualsiasi altra scelta va bene lo stesso.
$$ \text{MCD}(x_1 - x_0, 8051) = \text{MCD}(5-2, 8051) = \text{MCD}(3, 8051) = 1 $$
$$ \text{MCD}(x_2 - x_0, 8051) = \text{MCD}(26-2, 8051) = \text{MCD}(24, 8051) 1 $$
$$ \text{MCD}(x_3 - x_0, 8051) = \text{MCD}(677-2, 8051) = \text{MCD}(675, 8051) = 1 $$
$$ \text{MCD}(x_4 - x_0, 8051) = \text{MCD}(7474-2, 8051) = \text{MCD}(7472, 8051) = 1 $$
$$ \text{MCD}(x_5 - x_0, 8051) = \text{MCD}(2839-2, 8051) = \text{MCD}(2837, 8051) = 1 $$
$$ \text{MCD}(x_6 - x_0, 8051) = \text{MCD}(871-2, 8051) = \text{MCD}(869, 8051) = 1 $$
Tutte le differenze sono uguale a 1, quindi non ho trovato nessun divisore.
Provo con le differenze rispetto a \( x_1 = 5 \)
$$ \text{MCD}(x_2 - x_1, 8051) = \text{MCD}(26-5, 8051) = \text{MCD}(21, 8051) = 1 $$
$$ \text{MCD}(x_3 - x_1, 8051) = \text{MCD}(677-5, 8051) = \text{MCD}(672, 8051) = 1 $$
$$ \text{MCD}(x_4 - x_1, 8051) = \text{MCD}(7474-5, 8051) = \text{MCD}(7469, 8051) = 97 $$
Eccolo! Ho trovato un divisore non banale di 8051 ossia 97.
Per trovare gli altri divido 8051 per 97
$$ \frac{8051}{97} = 83 $$
Quindi i fattori del numero 8051 sono:
$$ 8051 = 83 \times 97 $$
Ho trovato la fattorizzazione del numero.
La versione veloce del metodo di Pollard
La versione veloce del metodo ρ di Pollard anticipa il controllo del massimo comune divisore al momento della generazione dei numeri.
In questo modo modo se un divisore si trova subito, viene rilasciato senza dover generare una lunga successione di numeri.
Come funziona?
Ecco i passaggi da seguire:
- Scegli una funzione semplice per generare la successione, es. \( f(x) = x^2 + 1 \mod n \), e un valore iniziale \( x=x_0 \) e \( y = x_0 \).
- Genero due successioni di numeri, una più lenta x (tartaruga) e una più veloce y (lepre)
- \( x_i = f(x_{i-1}) \mod n \) (tartaruga - avanza di 1 passo)
- \( y_i = f[f(y_{i-1})] \mod n \) (lepre - avanza di 2 passi) - Calcolo il massimo comune divisore tra \( x_i-y_i \) e \( n \) $$ d = \text{MCD}(|x - y|, n) $$
- Controllo il risultato:
- Se \( d = 1 \), torno al punto 2 e genero un altra coppia di numeri \( x_i \) e \( y_i \)
- Se \( 1 < d < n \), ho trovato un divisore
- Se \( d = n \), ricomincio dal punto 1 scegliendo un’altra funzione o un altro punto iniziale
Esempio
Rifaccio l'esempio della fattorizzazione di \( n = 8051 \) usando la versione veloce del metodo ρ di Pollard (lepre e tartaruga).
Scelgo la funzione iniziale:
$$ f(x) = x^2 + 1 \mod 8051 $$
Poi scelgo come punto iniziale $ x_0 = 2 $$
$$ x=2 $$
$$ y=2 $$
A questo punto cominciano le iterazioni
Iterazione 1
Calcolo i valori di $ x_1 $ e $ y_1 $
$$ x_1 = f(2) = 2^2 + 1 = 5 $$
$$ y_1 = f(f(2)) = f(5) = 5^2 + 1 = 26 $$
Poi calcolo il massimo comune divisore \( MCD(|x_1 - y_1|, n \)
$$ d = \text{MCD}(|5 - 26|, 8051) = \text{MCD}(21, 8051) = 1 $$
Il risultato è 1, un divisore banale di 8051, quindi non va bene.
Iterazione 2
Genero la successiva coppia di valori
$$ x_2 = f(x_1) = f(5) = 5^2 +1 = 26 $$
$$ y_2 = f(f(y_1)) = f(f(26)) = f(26^2 + 1) = f(677) = 677^2 + 1 = 458330 \mod 8051 = 7474 $$
Calcolo il MCD
$$ d = \text{MCD}(|26 - 7474|, 8051) = \text{MCD}(7448, 8051) = 1 $$
Ancora nulla. E' un divisore banale di 8051.
Iterazione 3
Genero la successiva coppia di valori
$$ x_3 = f(26) = 26^2+1 = 677 $$
$$ y_3 = f(f(7474)) = f(7474^2 + 1 \mod 8051) = f(2839) = 2839^2 + 1 = 8059922 \mod 8051 = 871 $$
Calcolo il MCD
$$ d = \text{MCD}(|871 - 677|, 8051) = \text{MCD}(194, 8051) = 97 $$
Ho trovato un divisore non banale di 8051, ossia 97, dopo sole tre iterazioni.
A questo punto, per trovare l'altro divisore devo semplicemente dividere 8051 per 97
$$ \frac{8051}{97} = 83 $$
Quindi i fattori del numero 8051 sono:
$$ 8051 = 83 \times 97 $$
Il risultato finale è lo stesso ma l'ho trovato più rapidamente.
Note
Alcune note e osservazioni su questo metodo di fattorizzazione.
- Pro e contro del metodo di fattorizzazione di Pollard
Il metodo è efficiente per numeri con fattori piccoli e non richiede test su tutti i numeri primi fino a \( \sqrt{n} \). E' facile da implementare e computazionalmente veloce per numeri di grandezza media. Tuttavia, non sempre trova un fattore subito (se il ciclo si chiude senza trovare un divisore). Diventa inefficiente per numeri con soli fattori primi grandi. Inoltre, può richiedere più tentativi con diverse funzioni \( f(x) \) e valori iniziali.
E così via.
