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

[Max Alekseyev <maxale@gmail.com>]

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

On Fri, Jun 9, 2023, 5:26 AM <hermann@stamm-wilbrandt.de> wrote:

Bill Alombert described an efficient method to determine smallest
quadratic nonresidue:
https://pari.math.u-bordeaux.fr/archives/pari-users-2306/msg00021.html
> Note:
> To find the square root, you just need to find a small prime number l
> so
> that kronecker(l,p)==-1 and then compute Mod(l,p)^(((p-1)/4)
>

I implemented it:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/smallest_qnr.gp

For 10000-digit to 388342-digit examples I used recently, the
200700-digit prime reports maximal value of 31. Even on Raspberry Pi400
it does take 2ms only:

pi@pi400-64:~ $ gp -q <(echo "n = 3756801695685 * 2 ^ 666669 + 1") <
smallest_qnr.gp
n is 200700-digit number
   ***   last result: cpu time 2 ms, real time 2 ms.
smallest quadratic non-residue of n: 31
pi@pi400-64:~ $


Script prints format help and huge example values if no "n" is defined:

pi@pi400-64:~ $ gp -q < smallest_qnr.gp
Format: gp -q <(echo "n=value") < smallest_qnr.gp
10000/36401/100355/200700/272770/330855/388342-digit number examples:
n = (10 ^ 10000 - 1) \ 3 - 10 ^ 6333
n=34*((10^36400-1)\9)-42000040044444004000024*10^2264*((10^36400-1)\9)\((10^4550-1)\9)-1
n = 65516468355 * 2 ^ 333333 + 1
n = 3756801695685 * 2 ^ 666669 + 1
n = 1705 * 2 ^ 906110 + 1
n = 2145 * 2 ^ 1099064 + 1
n = 2996863034895 * 2 ^ 1290000 + 1
pi@pi400-64:~ $


1)
If I replace "t++" in

smallest_qnr(m) = {
   t=2;
   while(kronecker(t, m) != -1, t++;);
   t;
}

with "t=nextprime(t)", computation hangs for the bigger numbers "n".
Is that a bug?
(t=nextprime(t) should be independent from size of n)


2)
Is there a better way (like C/C++/Python argv) than I did to pass value
of "n" when executing a script with "gp .... < script.gp"?

Is "if (type(n) != "t_INT", ...)" a good way to deal with input errors?


Regards,

Hermann.