Tonelli-Shanks algorithm

David Gillies daggillies at
Wed Apr 17 00:01:40 CEST 2013

OK, fair enough, good point, then the prototype should be changed to int
modular_sqrt(mpz_t x,mpz_t q,mpz_t n); for clarity

On Tue, Apr 16, 2013 at 3:38 PM, David Harvey <d.harvey at> wrote:

> On Apr 17, 2013, at 6:30 AM, David Gillies wrote:
> > There was a bit of discussion last week about finding quadratic residues,
> > so I decided to implement Tonelli-Shanks for fun. I coded it up last
> night
> > and here it is. It seems to work but if anyone can spot any glaring holes
> > then let me know.
> no comment on the code, I only want to correct a nomenclature problem that
> has occurred a few times on this list:
> you mean finding a (modular) square root, not a quadratic residue. Finding
> a quadratic residue is a much easier problem!
> david

David Gillies
San Jose
Costa Rica

More information about the gmp-discuss mailing list