/*********************************************************
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"));
}