Re: What is the Mathematica "PowerMod[a, 1/2, m]" equivalent in PARI/GP?

[hermann@stamm-wilbrandt.de]

On 2024-10-01 13:05, Karim Belabas wrote:
> Note that 100% of computing time is spent factoring the modulus. If 
> many
> square roots must be computed for the same modulus, then the 
> factorization
> should be precomputed.
Thanks.

The "100% of computing time is spent factoring the modulus" can be seen
by these runtimes for 59-, 79- and 100-digit RSA numbers on AMD 7950X 
CPU:

2s, 2:24min, 6:16h


Mathworld page on qudratic residue mentions a polynomial time algorithm:
https://mathworld.wolfram.com/QuadraticResidue.html

Schoof (1985) gives an algorithm for finding x with running time 
O(ln^{10} n) (Hardy et al. 1990).
The congruence can solved by the Wolfram Language command PowerMod[q, 
1/2, p].

Since "PowerMod[]" is much slower than PARI/GP "issquare()" they likely 
did not implement
that polynomial time (10th power though) algorithm.


Regards,

Hermann.