\\ Application of the p-1 factorisation method
pmin1stg1(N,B,x,s,f)=
{
	local(t,y,P,pow,i,g,j,q);

	x=Mod(x,N);i=1;q=prime(i);
	t=s;y=x;P=Mod(1,N);j=i;
	while(q<=B,
		pow=1; while( pow <= B, pow=pow*q);
		x=x^pow; P=P*(x-1); t=t-1;
		if( t == 0,
			g=gcd(lift(P),N);
			if( g != 1,
				break,
				t=s;y=x;P=Mod(1,N);j=i;
			)
		);
		i=i+1;q=prime(i);
	);

	if( t != 0, g=gcd(lift(P),N));
	
	if( g != 1, 
		i=j;t=s;x=y;
		while(t != 0,
			t=t-1; q=prime(i); i=i+1;
			pow=1; while( pow <= B, pow=pow*q);
			x=x^pow; g=gcd(lift(x-1),N);
			if( g != 1, return(g))
		)
	);

	if( f == 0,
		return(0),
		return(-lift(x))
	);
}

\\ B is the small primes bound
\\ C is the medium primes bound
\\ D is the number of primedifferences expected between B and C

pmin1stg2(N,B,C,D,x,s)=
{
	local(t,y,P,pow,g,diff,p,q,r);

	b=pmin1stg1(N,B,x,s,1);
	if( b > 0, return(b));
	b=-b;

	x=mod(b,N);b=x;
	pow=vector(D); 

	q=precprime(B);x=b^q;
	P=Mod(1,N);t=s;y=x;r=q;
	while(q<=C,
		p=nextprime(q+1);
		diff=p-q;
		if(pow[diff] == 0, pow[diff] = b^diff);
		x = x*pow[diff];
		P = P*(x-1); t=t-1;
		if ( t == 0,
			g=gcd(lift(P),N);
			if( g != 1,
				break,
				P=Mod(1,N);t=s;y=x;r=p
			)
		);
		q=p;
	);
	if( t != 0, g=gcd(lift(P),N));

	if( g != 1,
		x=y;
		forprime(q=r,p,
			x = x*pow[diff];
			g=gcd(lift(x-1),N);
			if( g != 1, return(g) );
		);
	);
	return(0);
}