Bill Allombert on Thu, 30 May 2002 20:59:45 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: detecting non quadratic residue in sqrt/trapping errors

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
this is the function sqrtmod