Tuukka Toivonen on Thu, 30 May 2002 21:43:13 +0300 (EEST)

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

Re: detecing non quadratic residue in sqrt/trapping errors

On Thu, 30 May 2002, Bill Allombert wrote:

>For this particular case, you can use issquare().
>Yes, with the trap(,,) function, but it is an experimental feature.

Thanks for these! Both were straight from the manual, I was just too blind
to find them.

Actually, my goal to begin with is to compute divisions and square roots of
polynomial rings, modulo a polynomial, with coefficients from a finite
ring, either integer modulo q or even another polynomial ring! Not to even
speak yet about non-unique factorization of the polynomials...

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).

Currently I use a C program to try all possible elements in the ring. This
is slow, but possible since my modulus q is usually less than 32 bits.

Any references and advice is welcome.

About myself: I'm an engineer who desperately tries to learn number theory
to make some applications :)