Newsgroups: sci.math,sci.math.symbolic
From: masjhd@bath.ac.uk (James Davenport)
Subject: Re: Q: x^2 + y^2 + 1 = 0 (mod p) _constructive_ solutions??
Date: Tue, 8 Oct 1996 09:24:15 GMT

Henry Baker <hbaker@netcom.com> asks
>> Could anyone point me to a _constructive_ (i.e., one not involving pidgeon poop
>> or Dirichlet's drawers) solution for Euler's congruence
>> x^2 + y^2 + 1 = 0 (mod p), for p=4k+3 ??
>> Given p, I'd like to find x,y in a reasonable amount of time (not a brute
>> force search) -- i.e., less than O(p).
Surely the argument on page 125 of my father's "Higher Arithmetic"
(due to Euler) suffices to find x^2 and y^2.
We want x^2+1=-y^2.
Let -y^2 be the first non-residue in 1,2,3...
This gives y^2, and x^2=-y^2-1 = residue immediately before first non-residue.

Now we are in the business of square roots mod p, c.f.

Schoof,R.J.,
Elliptic Curves over Finite Fields and the Computation of
Square Roots mod p.
Math. Comp. 44(1985) pp. 483-494.
and cross-references.

James Davenport