Points on an unit circle over finite field

[rsg]

Let $$x^2_1+x^2_2=1$$ be an unit circle upon a finite field $$Z_{p}$$ where p is a prime. Is there any algorithm (other than the brute force algorithm) which can give all the possible solutions $$(x_1,x_2)\in Z_{p}\times Z_{p}$$ as well as the total number of such solutions? If exists, what is the complexity of it?

More generally, is there an answer of the same question, when, instead of a circle we consider a n-sphere $$x^2_1+x^2_2+\cdots+x^2_n=1$$? What will happen if, instead of $$Z_{p}$$ we work with $$Z_{q}$$, where $$q=p^r$$?

I am not a number theorist. So I do not know whether any thing exists in literature. Please help.

 

[Hurkyl]

This is one of the basic questions of the field of algebraic geometry. In the case of quadratic equations, though, it's actually fairly simple. The basic idea is that lines always^* intersect quadratic curves in two points. So, if you can find one point Q on your curve, then there is a 1-1 correspondence between (rational^**) points on your curve and lines through Q. In other words, there are p+1 points on the curve.

*: Caveats: if it's a tangent line, that counts as two points. One of the two points might be infinite. (Or both, if it's the line at infinity) The two points could have coordinates in the algebraic closure of Z/p but not actually be elements of Z/p... but if one is rational^**, then the other is guaranteed to be rational. If your quadratic equation is defective, or your choice of point is defective, then that can cause problems too.

**: In this context, a rational point is one whose coordinates lie in Z / p. One can more generally ask about points whose coordinates lie in the algebraic closure of Z / p.



Once you know what the theorem is, it's actually fairly easy to see. In this case, let Q = (1,0). Then any line through Q is parametrized by

(x1, x2) = (1, 0) + t (a, b) as t ranges over Z / p.​

Now, plug this into your circle equation and solve for t! There will be two solutions, (except for points at infinity: see below) and one of them is known to be Q. The converse is easy to see too; if R is any point on the circle other than Q, then there is a unique line passing through Q and R.

(p.s. Q itself corresponds to the tangent line to your circle)

The same works out, I believe, for your n-sphere. In that case, there are

(p^n - 1) / (p - 1)​

points. This can be seen by carefully counting the number of lines, or by knowing some projective geometry. (This is the number of points in projective (n-1)-space over Z / p)


Regarding points "at infinity"... there are either two or zero such points for your circle: they have projective coordinates (1:i:0) and (1:-i:0), where i is a number such that i^2 = -1 (mod p). They correspond to the lines

(x1,x2) = (1,0) + t(1,i)
(x1,x2) = (1,0) + t(1,-i)​

for which you can check intersect the circle in only one 'finite' point. Counting points at infinity for the n-sphere may or may not be tricky: I haven't thought hard about it.

(If p = 2, then these are the same point, not different points. So, there is only one point at infinity)

 

[Hurkyl]

Dealing with points over Z / p^r is probably straightforward: the main theoretical tool that is probably useful is lemma[/url]. Or, you can probably do it directly by first answering the question for Z/p, and then for any particular (a,b), figuring out how many points of Z/p^2 have coordinates (a',b') such that a=a' mod p and b=b' mod p and also satisfy the circle equation. Then repeat for Z/p^3, and so forth.

If you were instead interested in the finite field of p^r elements, then you can just apply the same technique used in Z/p.