\\ An implementation of Pollard's factoring
\\ as improved by Brent and others.
f(x)=
{
	x^2-c;
}

pollardrho(N,c,x,s)=
{
	local(y,halfway,tte,g);

	c=Mod(c,N);
	x=Mod(x,N);
	tte=1; \\ tte = 2^e
	y=0;
	halfway=1;
	
	while( pollardloop(s) == 0,
		\\ No loop was found so reset
		halfway=tte;tte=2*tte;halfway=halfway+tte;
		y=x;
	);
	\\ Found a loop
	for(i=1,s,
		g=gcd(lift(x-y),N);
		if(g != 1, return(g)); \\ Will happen!
		y=f(y)
	);
	return(0); \\ Will not happen
}
\\ This is the main loop for pollard
\\ parameter for the function computation
\\ y=x is x_{2^e-1};halfway=tte+tte/2; and tte=2^e

pollardloop(s)=
{
	local(P,t);
	
	P=Mod(1,N);
	t=s;

	for(k=tte,halfway-1,x=f(x)); \\ check-free iterations

	for(k=halfway, 2*tte-1,
		x=f(x); 
		P=(x-y)*P; \\ The pollard accumulation
		t=t-1;
		if( t == 0, \\ Check the accumulator
			if( gcd(lift(P), N) != 1,
					return(1), \\ found a loop
					t=s; P=Mod(1,N) \\ No loop
			)
		)
	);
	if( t != 0,
		if( gcd(lift(P), N) != 1, return(1)) \\ found a loop
	);
	return(0) \\ No loop
}