Tonelli-Shanks algorithm

[David Gillies]

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 unsw.edu.au> 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