# Prime number algorithm

• khotsofalang
In summary, the conversation discusses the problem of finding solutions for the equation x12+x22=1 in a unit circle on a finite field Zp, where p is a prime number. The group discusses the possibility of using an algorithm to find all possible solutions and the complexity of such an algorithm. They also mention the importance of finding a good way to solve the equation for strengthening an extended essay. One member suggests checking all possibilities, while another suggests looking for quadratic residues that add up to 1, particularly for primes congruent to 1 modulo 4.

#### khotsofalang

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?

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.