hermann on Fri, 09 Jun 2023 11:31:08 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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


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.