Tonelli-Shanks algorithm

David Harvey d.harvey at
Tue Apr 16 23:38:26 CEST 2013

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!


More information about the gmp-discuss mailing list