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

[Aurel Page <aurel.page@normalesup.org>]

On 01/10/2024 15:37, hermann@stamm-wilbrandt.de wrote:
> 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.
The polynomial time algorithm is for the case where the modulus has 
already been factored. Computing square roots mod N is provably as hard 
as factoring N.

Best,
Aurel