\\ 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&&d<n,print(d," is a factor of ",n));
                        j=j++;p=nextprime(p++));m=1;
    			while(d==1&&m<=floor(lgn/log(2)),b=lift(Mod(b,n)^2);
		d=gcd(b-1,n);if(d>1&&d<n,print(d," is a factor of ",n));m=m++);
                        if(d==1||d==n,print("Try increasing t")))
}