Elliptic Curve - Elliptic Curves Over Finite Fields

Elliptic Curves Over Finite Fields

Let K = F_q be the finite field with q elements and E an elliptic curve defined over K. While the precise number of rational points of an elliptic curve E over K is in general rather difficult to compute, Hasse's theorem on elliptic curves gives us, including the point at infinity, the following estimate:

In other words, the number of points of the curve grows roughly as the number of elements in the field. This fact can be understood and proven with the help of some general theory; see local zeta function, Étale cohomology.

The set of points E(F_q) is a finite abelian group. It is always cyclic or the product of two cyclic groups. For example, the curve defined by

over F₇₁ has 72 points (71 affine points including (0,0) and one point at infinity) over this field, whose group structure is given by Z/2Z × Z/36Z. The number of points on a specific curve can be computed with Schoof's algorithm.

Studying the curve over the field extensions of F_q is facilitated by the introduction of the local zeta function of E over F_q, defined by a generating series (also see above)

where the field K_n is the (unique) extension of K = F_q of degree n (that is, ). The zeta function is a rational function in T. There is an integer a such that

Moreover,

with complex numbers α, β of absolute value . This result are a special case of the Weil conjectures. For example, the zeta function of over the field F₂ is given by since the curve has points over if r is odd (even, respectively).

The Sato–Tate conjecture is a statement about how the error term in Hasse's theorem varies with the different primes q, if you take an elliptic curve E over Q and reduce it modulo q. It was proven (for almost all such curves) in 2006 due to the results of Taylor, Harris and Shepherd-Barron, and says that the error terms are equidistributed.

Elliptic curves over finite fields are notably applied in cryptography and for the factorization of large integers. These algorithms often make use of the group structure on the points of E. Algorithms that are applicable to general groups, for example the group of invertible elements in finite fields, can thus be applied to the group of points on an elliptic curve. For example, the discrete logarithm is such an algorithm. The interest in this is that choosing an elliptic curve allows for more flexibility than choosing q (and thus the group of units in F_q). Also, the group structure of elliptic curves is generally more complicated.