|
##''d''=MCD(''x'',''y'');
#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 ==
|
