# Prime number algorithm

## Main Question or Discussion Point

i am sorry guys, the last time i posted this problem it was completely different but this time if we
Let x12+x22=1 be a unit circle upon a finite field Zp where p is prime. Is there any algorithm which can give all the possible solutions (x1,x2) an element of Zp*Zp as well as the total number of such solutions? If exists, what is the complexity of it?

Related Linear and Abstract Algebra News on Phys.org
CRGreathouse
Homework Helper
You could check all possibilities. That takes something like O(p^2 log^2 p).

Now you just need a *good* way to solve it.

all right, but what i actually need is that good way of solving it

i need a solution to such an equation for stregthening my extended essay,anibody with a gud way of solving it?

If I understood correctly, you are looking for two quadratic residues that add up to 1. It may be easier for primes congruent to 1 modulo 4, because quadratic residues for those primes are 'symmetric': r is a quadratic residue iif p-r is. In this case you just look for contiguous quadratic residues on the lower half, from 2 to (p-1)/2: if r and r+1 are quadratic residues, then p-r also is, and (p-r)+(r+1) add to 1. My 2 cents.