are there any functions for computing a square root of a modulo p (prime)?
Zimmermann Paul
Paul.Zimmermann at inria.fr
Thu Apr 11 20:37:07 CEST 2013
> *There's no API functions to calculate quadratic residues directly but you
> do have mpz_legendre() so all the tools are there to calculate it even for
> p = 1 mod 8. It's not deterministic though.*
indeed, see http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm.
The Tonelli–Shanks algorithm is so useful in many applications, that it
would make sense to have it implemented in GMP.
Paul
More information about the gmp-discuss
mailing list