Re: detecting non quadratic residue in sqrt/trapping errors

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, May 30, 2002 at 09:43:13PM +0300, Tuukka Toivonen wrote:
> The real difficulty is that I can't find programs or much even algorithms
> for computing over these rings. Division of integers (i.e. solving a*x=1
> mod q, q nonprime) is easy, but even square roots (solving x*x=a mod q) is
> over the capabilities of my programs, including Pari (or maybe I just don't
> know how to use them).

There is a GP script available that do just that. It use standard
Shanks algorithm for prime, Hensel lift for prime power, and chinese remainder
theorem solving the general case from the prime power one.

It is written by Fernando Rodriguez-Villegas and Ariel Pacetti.
it is available at
<http://www.ma.utexas.edu/users/villegas/cnt/bforms.gp>
this is the function sqrtmod

Cheers,

Bill.