\\
\\---------------------------------------------------------------------------------
\\ A program that searches one prime
\\---------------------------------------------------------------------------------
\\	input: YES  -  poll(N)   N is the number we factorize
\\---------------------------------------------------------------------------------
\\
poll(NN)={
	local(cc);
\\
	N=NN;
	cc=1;
\\
	ex=2^25*3^3*5^2*7^2;
\\	1109812838400
\\	ex=3;
	bex=binary(ex);
	y0=2;
	y=2;
	for(i=2,matsize(bex)[2],
		if(bex[i],
			y=qcomp(y,y,N,cc);
			if(y<0,printf("i= %5d y0, %35d\n\n",i,-y,);return());
			y=qcomp(y,y0,N,cc);
			if(y<0,printf("i= %5d y1, %35d\n\n",i,-y,);return());
		,
			y=qcomp(y,y,N,cc);;
			if(y<0,printf("i= %5d y2, %35d\n\n",i,-y,);return());
		);
	);
\\	return();
	cit=0;
	forprime(p=11,500000000,
		y0=y;
		y=y;
		bex=binary(p);
		cit++;
		for(i=2,matsize(bex)[2],
			if(bex[i],
				y=qcomp(y,y,N,cc);
				if(y<0,printf("yy0= %6d  p= %5d  %35d\n\n",cit,p,-y);return());
				y=qcomp(y,y0,N,cc);
				if(y<0,printf("yy1= %6d  p= %5d  %35d\n\n",cit,p,-y);return());
			,
				y=qcomp(y,y,N,cc);
				if(y<0,printf("yy2= %6d  p= %5d  %35d\n\n",cit,p,-y);return());
			);
		);
	);
\\
	return();
}
\\---------------------------------------------------------------------------------
\\---------------------------------------------------------------------------------
\\		test mocniny
\\
tesm()={
	local(y,y0,a,b,c,cc,k,ex0);
\\
	NMAX=1000000;
\\	N=random(NMAX);
	N=randomprime(NMAX);
	printf("\n N=%10d\n",N);
\\
	CCMAX=20;
	cc=random(CCMAX);
	if(cc==0,cc++);
	printf("cc=%10d\n",cc);
\\
	k=random(N-1);
	printf(" k=%10d\n\n",k);
\\
	for(ex0=1,17,
		bex=binary(ex0);
		y0=k;
		y=k;
\\
		a=N^2;
		b=2*k*N;
		c=k^2+cc^2;
		D1=b^2-4*a*c;
		q1=Qfb(a,b,c);
		q1r=qfbred(q1);
		qex=q1r^ex0;
\\
		for(i=2,matsize(bex)[2],
			if(bex[i],
				y=qcomp(y,y,N,cc);
				y=qcomp(y,y0,N,cc);
\\				if(y<0,next(1));
			,
				y=qcomp(y,y,N,cc);;
			);
		);
\\
		a=N^2;
		b=2*y*N;
		c=y^2+cc^2;
		q2=Qfb(a,b,c);
		q2r=qfbred(q2);
		D2=b^2-4*a*c;
		if(D1==D2,  ,printf("D1=%10d  D2=%10d\n",D1,D2));
\\
		if(qex==q2r,  ,printf("--------------------  qex!=q2r\n"));
		printf("qex=%60s    y=%10d\n",qex,y);
		printf("q2r=%60s  moc=%10d\n\n",q2r,moc(N,cc,k,ex0));
	);
\\
	printf("\n\n");
\\
	return();
\\
}
\\---------------------------------------------------------------------------------
qcomp(x1,x2,N,cc)={
	local(xsuma,gc);
	xsuma=x1+x2;
	gc=gcd(xsuma,N);
	if(gc==1, ,return(-gc));
	return(((x1*x2-cc^2)/xsuma)%N);
}
\\---------------------------------------------------------------------------------
\\---------------------------------------------------------------------------------
moc(N,cc,y,ex)={
	local(y0);
\\
	bex=binary(ex);
	y0=y;
	y=y;
	for(i=2,matsize(bex)[2],
		if(bex[i],
			y=qcomp(y,y,N,cc);
			if(y<0,printf("i=%5d  y,y0-in  %35d\n\n",i,-y);return());
			y=qcomp(y,y0,N,cc);
			if(y<0,printf("i=%5d  y,y1-in  %35d\n\n",i,-y);return());
		,
			y=qcomp(y,y,N,cc);;
			if(y<0,printf("i=%5d  y,y2-in  %35d\n\n",i,-y);return());
		);
	);
\\
	return(y);
}
\\---------------------------------------------------------------------------------
\\---------------------------------------------------------------------------------