Re: efficient determination of smallest quadratic non-residue / t++ works, t=nextprime(t) hangs

[hermann@stamm-wilbrandt.de]

On 2023-06-09 11:40, Max Alekseyev wrote:
> Notice that nextprime(2) gives 2, and so "t=nextprime(t)" leads to an
> infinite loop. Perhaps, you want to use "t=nextprime(t+1)" instead.
>
> Regards,
> Max
You are right, I improved script that way:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/smallest_qnr.gp

I learned from Bill Allombert that "cost of kronecker(l,p) is about the 
same as the cost of kronecker(l,p%l)
so it is very fast". So staring with small prines is a good strategy if 
only needing "a" quadratic non-residue.

In the context of factoring large semiprimes n=p*q, the number of 
quadratic non-residues (kronecker -1) and quadratic residues (kronecker 
+1) is identical. If kronecker() returns 0, a prime factor has been 
found:

? s=0; for(t=1,n-1,s+=kronecker(t,n)); s
%4 = 0
? kronecker(p,n)
%5 = 0
? kronecker(q,n)
%5 = 0
?

For quadratic non-residue a of prime p, "Mod(a^(p\4), p)" computes 
sqrt(-1) (mod p).
Now being able to determine squdratic non-residue very fats with 
"smallest_qnr()", only a single time consuming computation of 
"Mod(a^(p\4), p)" computes sqrt(-1) (mod m). (took <10min for 
100355-digit prime and 3:04h for 388342-digit prime with C++ and 
libgmpxx on i7-11850H). Computing "qbfcornacchia(1, p)" computed sum of 
squares p=x^2+y^2 in slightly less than 11h on i7-11850H. Determining 
sqrtm1 from x,y can be done in 123ms on i7-11850H:
https://forums.raspberrypi.com/viewtopic.php?p=2112433#p2112344
So C++ with libgmpxx and powm() can compute sqrtm1 in 3:04h for 
388342-digit prime, while PariGP best runtime for same is slightly less 
than 11h.


Regards,

Hermann Stamm-Wilbrandt.