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

[Charles Greathouse <crgreathouse@gmail.com>]

Schoof’s algorithm works mod p; if you are working mod a composite, again all of your time is spent factoring.

Schoof’s algorithm isn’t practical compared to Berlekamp or whatever sorcery PARI does under the hood. Its advantage is that it doesn’t need a nonresidue, which are easy to find in practice and with high probability, but without strong hypotheses we can’t probably find in polynomial time.

On Tue, Oct 1, 2024 at 9:38 AM <hermann@stamm-wilbrandt.de> wrote:

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.