Karim Belabas on Fri, 23 Jun 2023 12:30:27 +0200


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

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

* hermann@stamm-wilbrandt.de [2023-06-23 12:15]:
> My Linux gp-2.15 runs with GMP kernel:
> 
> $ gp-2.15
> Reading GPRC: /etc/gprc
> GPRC Done.
> 
>                   GP/PARI CALCULATOR Version 2.15.3 (released)
>           amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
> ...
> 
> I used sqrtm1.cc
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/c%2B%2B/sqrtm1.cc
> 
> to efficiently determine "sqrt(-1) (mod p)" for primes up to 1million
> digits.
> I had to hardcode the primes in C source, a bit ugly.
> 
> 
> Now I implemented sqrtm1.gp doing the same:
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/sqrtm1.gp
> 
> Nice feature here is that because of "eval(getenv())" I can pass formulas.
> The program flow is the same as in sqrtm1.cc, with determination of smallest
> quadratic non-residue as learned from Bill:
> https://pari.math.u-bordeaux.fr/archives/pari-users-2306/msg00044.html
[...]

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.

? p=2^1000*5^3148+1;
? for(i=1,100,Mod(3,p)^((p-1)/4))
time = 10,690 ms.
? for(i=1,100,sqrt(Mod(-1,p)))
time = 10,299 ms.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/