Points on an unit circle over finite field

In summary: Just pick a point (a,b) and see how many lines through it intersect the n-sphere. This will give you the number of points on the n-sphere over the finite field Z/p^r. In summary, there is an algorithm to find all possible solutions for the n-sphere x^2_1+x^2_2+\cdots+x^2_n=1 over a finite field Z/p^r, using the theorem in algebraic geometry that states lines always intersect quadratic curves in two points. The complexity of this algorithm is dependent on the size of the finite field and can be calculated using the number of points on the n-sphere over Z/p^r. Additionally, there is a similar algorithm for the
  • #1
rsg
4
0
Let [tex]x^2_1+x^2_2=1[/tex] be an unit circle upon a finite field [tex]Z_{p}[/tex] where p is a prime. Is there any algorithm (other than the brute force algorithm) which can give all the possible solutions [tex](x_1,x_2)\in Z_{p}\times Z_{p}[/tex] 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 [tex]x^2_1+x^2_2+\cdots+x^2_n=1[/tex]? What will happen if, instead of [tex]Z_{p}[/tex] we work with [tex]Z_{q}[/tex], where [tex]q=p^r[/tex]?

I am not a number theorist. So I do not know whether any thing exists in literature. Please help.
 
Physics news on Phys.org
  • #2
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)
 
Last edited:
  • #3
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.
 
Last edited by a moderator:

What is an unit circle over finite field?

An unit circle over finite field is a mathematical concept that represents a set of points on a circle with a radius of 1, where the coordinates of the points are elements of a finite field. In other words, it is a way of visualizing and representing certain mathematical operations within a finite field.

What is a finite field?

A finite field is a mathematical structure that consists of a finite set of numbers and operations, where the operations follow specific rules and properties. It is commonly used in abstract algebra and has applications in various fields such as coding theory, cryptography, and number theory.

What are the coordinates of points on an unit circle over finite field?

The coordinates of points on an unit circle over finite field are elements of the finite field. These coordinates follow specific rules and properties and can be used to perform operations such as addition, subtraction, and multiplication within the finite field.

Why is the unit circle important in finite fields?

The unit circle is important in finite fields because it provides a visual representation of certain mathematical operations within the finite field. It also helps in understanding the properties of finite fields and their applications in various fields of mathematics and science.

What are the applications of points on an unit circle over finite field?

The applications of points on an unit circle over finite field include coding theory, cryptography, number theory, and other areas of mathematics and science. It is also used in computer science and engineering for error correction, data compression, and other applications.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
4K
Replies
6
Views
2K
  • Electromagnetism
Replies
2
Views
834
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
8
Views
2K
  • Linear and Abstract Algebra
Replies
28
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
93
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Precalculus Mathematics Homework Help
Replies
20
Views
2K
Back
Top