Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?

[hermann@stamm-wilbrandt.de]

On 2023-06-23 12:25, Karim Belabas wrote:
> Note that the current 'master' branch currently computes 
> sqrt(Mod(-1,p))
> quickly in all cases.
>
> The branch origin/bill-Fp_sqrts implements a slightly more general
> solution: besides -1, 0% of quadratic residues allow a faster algorithm
> to compute their square root, it costs nothing to try to use it.
Thanks Karim.

I added whut you proposed:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1.gp

$ git diff .
diff --git a/pari/sqrtm1.gp b/pari/sqrtm1.gp
index 46a65ae..bdf290f 100644
--- a/pari/sqrtm1.gp
+++ b/pari/sqrtm1.gp
@@ -21,3 +21,6 @@ p=lift(Mod(qnr, n)^(n\4));
 ##
 write("/dev/stderr", p);
 assert(p^2 % n == n-1, "p^2 % n != n-1: ", p);
+q=lift(sqrt(Mod(-1, n)));
+##
+assert(q^2 % n == n-1, "q^2 % n != n-1: ", q);
$


Then I did pull latest on master branch, did make clean, ./Configure, 
make and make install.

I chose a slightly bigger 36401-digit prime to get some more runtime, 
but not hours.
The times reported are the same for 2.15 and 2.16 gp, and for 
"lift(Mod(qnr, n)^(n\4))" and "lift(sqrt(Mod(-1, n)))".
So still on master branch determination of "sqrt(-1) (mod p)" is 16% 
slower than with libgmp "powm()".
Since gp uses GMP kernel, why is that runtime differennce?


$ 
n='34*((10^36400-1)\9)-42000040044444004000024*10^2264*(10^36400-1)\9\((10^4550-1)\9)-1' 
 gp-2.15 -q < sqrtm1.gp 2>err
2
  ***   last result computed in 1min, 12,922 ms.
  ***   last result computed in 1min, 13,615 ms.
$
$ 
n='34*((10^36400-1)\9)-42000040044444004000024*10^2264*(10^36400-1)\9\((10^4550-1)\9)-1' 
 gp-2.16 -q < sqrtm1.gp 2>err
2
  ***   last result computed in 1min, 13,003 ms.
  ***   last result computed in 1min, 13,841 ms.
$


Regards,

Hermann.