/* Modified Pollard p-1 method. Usage pollard(n,t) where n is the number to be factored and t is the size of the factor base ie the first t primes. Adjust to taste. Modified to handle case where p-1 is smooth for all p|n By Felipe Voloch. */ pollard(n,t)= {local(m,b,p,j,d,g,lgn); until(b,b=random()%n); if(n<=1,error("Invalid input")); g=gcd(b,n); if(g>1,print(g," is a factor of ",n), p=3;j=1;d=1;lgn=log(n); while(d==1&&j<=t, b=lift(Mod(b,n)^(p^floor(lgn/log(p)))); d=gcd(b-1,n); if(d>1&&d1&&d