/********************************************************* Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli. Capitolo 6.5.5 pag. 180 e Capitolo 9.6.3 pag. 281 *********************************************************/ \\ Metodo di Pollard p-1 . PollardpiFatt(n,B,s) in cui n e`Ê \\ il numero da fattorizzare e B e` la grandezza della base di fattori \\ (che prendiamo formata dai primi B primi) ed s indica il numero \\ di basi a scelte casualmente; di default viene usata una \\ unica base casuale. { PollardpiFatt(n,B,s=1)= local(m, a, p, j, d, g, l, i, lgn); 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); return); 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); return); 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); return); m = m++; ); ); if(d == 1 | d == n, print("Prova ad incrementare B")); }