From: bumby@lagrange.rutgers.edu (Richard Bumby) Subject: Re: Quadratic equations in Zp Date: 7 Jan 2000 12:50:33 -0500 Newsgroups: sci.math Summary: Extracting square roots mod p "Philo D." writes: >In article <3875efa5@readers.ip.pt>, Luis Filipe Roçadas > wrote: >> Hi, >> >> Can anyone tell me if there is a algorthimic process to solve quadratic >> equations in the fields Zp ? ... >p is prime? Zp means integers mod p? Then the quadradic >formula is still correct (p not 2). So it boils down to the >question of extracting squareroots. ... Yes, and no. Recognizing squares is *fast*, *sure* and *easy*, but if you want an algorithm to find the square root, you may need to settle for two out of three from this list of virtues. However, if you accept a sufficiently strong Riemann hypothesis, you can prove that you won't need to wait long for probabilistic methods to give an answer. In particular, as soon as you know one quadratic non-residue mod p, the method described in D. Shanks, Five number-theoretic algorithms, Congr. Numer. 7 (1973) gives a quick method of finding a square root of every quadratic residue mod p. -- R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor 1992--1996 bumby@math.rutgers.edu || Telephone: [USA] 732-445-0277 (full-time message line) FAX 732-445-5530