Algoritmo rho di Pollard: differenze tra le versioni

Versione delle 22:25, 6 ott 2009

Versione attuale delle 17:20, 21 nov 2022

(20 versioni intermedie di 17 utenti non mostrate)

Riga 3:

== Algoritmo ==

L'algoritmo si basa sulla generazione di una sequenza [[Numeri pseudo-casuali|pseudo-casuale]] di numeri [[aritmetica modulare|modulo]] ''n'' (che è il numero che si cerca di fattorizzare): una sequenza ampiamente usata è

:<math>\begin{cases}x_0=2\\ f(x_{i+1})=x_i^2+1\mod n\end{cases}</math>

dove ''x_k'' è il ''k''-esimo numero della sequenza.

Se la successione è "sufficientemente casuale", allora si dovrebbe osservare un ciclo dopo circa <math>\sqrt{n\pi/2}</math> iterazioneiterazioni; se però ''p'' è un fattore di ''n'', allora la sequenza si ripeterà anche modulo ''p'', ma dopo circa <math>\sqrt{p\pi/2}</math> passi.

Poiché tuttavia ''p'' non è conosciuto, bisogna ricorrere ad un altro metodo per verificare le eventuali ripetizioni, e cioè calcolare il [[massimo comun divisore]] tra ''n'' e la differenza ''x_i''-''x_j'', per ogni coppia (''i'',''j''). Nella pratica, tuttavia, calcolare il massimo comun divisore per ogni coppia di indici renderebbe il test molto lento, quasi quanto il metodo delle divisioni per tentativi: si può dimostrare però che è sufficiente considerare le differenze ''x_2i''-''x_i'', velocizzando notevolmente l'esecuzione dell'algoritmo.

È possibile tuttavia che il massimo comun divisore sia ''n'': in tal caso l'algoritmo ha fallito, ed è necessario riprovare con un'altra sequenza, oppure con un diverso punto di partenza. Se ''n''' è primo, il metodo fallisce per ogni successione e ogni punto di partenza.

La [[complessità computazionale]] dell'algoritmo è, nella notazione [[O-grande]], <math>O(p^{1/2}\ln^2(n))</math> dove ''p'' è il fattore di ''n''; volendolo esprimere in funzione di quest'ultimo, è <math>O(n^{1/4}\ln^2(n))</math> (perché se ''n'' non è primo allora ha almeno un fattore primo <math>p \leq n^{\frac{1}{2}}</math>).

=== Pseudocodice ===

#''x''=2, ''y''=2, ''d''=1;

#SeWhile (''d''=1)

##''x''=''f''(''x'');

##''y''=''f''(f''(''x''y));''

##''d''=MCD(''|x-y|'',''yn'');

#Se ''d''=''n'' l'algoritmo fallisce; altrimenti ''d'' divide ''n''

=== Implementazione| PARI-GP ===

/*

* P-1 Factorization (Pollard)

* N numero da fattorizzare

* B numero della base dei fattori (i primi B primi)

* s=1 è opzionale ed indica il numero di base a scelta casuale

*/

M_P(n,B,s=1)= local(m, a, p, j, d, g, l, i, lgn, status=1);{

if(n <= 1 | !bittest(n,0) | s<= 0, error("Input non valido"); return);

l= floor(lgn/log(2));

for(i=1,s,

until(a, a=random()%n); /* genero a finche' a non divide n */

/* print("base scelta numero ", i, ": a = ",a); */

g=gcd(a,n);

if(g > 1, print(g," e` un fattore di ",n); status=0; return(status););

p = 3;

j = 1;

d = 1;

lgn = log(n);

while(d == 1 && j <= B,

a = lift(Mod(a,n)^(p^floor(lgn/log(p))));

d = gcd(a-1, n);

if(d > 1 && d < n , print(d," e` un fattore di ",n); status=0; return(status););

j = j++;

p = nextprime(p++);

);

m = 1;

while(d == 1 && m <= l,

a = lift(Mod(a,n)^2);

d = gcd(a-1,n);

if(d > 1 && d < n, print(d," e` un fattore di ",n); status=0; return(status););

m = m++;

);

);

if(d == 1 | d == n, print("Prova ad incrementare B"));

return(status);

}

== Bibliografia ==

*Harold Davenport, ''Aritmetica superiore'', Bologna, Zanichelli, 1994. ISBN 880809154688-08-09154-6

== Collegamenti esterni ==

*{{en}} [http://www.pitt.edu/~dickinsm/1020-2071/pollard_rho.pdf Spiegazione didattica]

{{portale|matematica}}

[[Categoria:Algoritmi numericiper la matematica|Rho di Pollard]]

[[Categoria:Teoria dei numeri]]

[[ca:Algorisme rho de Pollard]]

[[de:Pollard-Rho-Methode]]

[[en:Pollard's rho algorithm]]

[[es:Algoritmo rho de Pollard]]

[[fr:Algorithme rho de Pollard]]

[[he:אלגוריתם rho של פולרד]]

[[ja:ポラード・ロー素因数分解法]]

[[nl:Pollard's rho algoritme]]

[[pl:Algorytm faktoryzacji rho Pollarda]]

[[ru:Ρ-алгоритм Полларда]]