Elliptic Curve - Elliptic Curves Over Finite Fields

Elliptic Curves Over Finite Fields

Further information: arithmetic of abelian varieties

Let K = Fq 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(Fq) is a finite abelian group. It is always cyclic or the product of two cyclic groups. For example, the curve defined by

over F71 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 Fq is facilitated by the introduction of the local zeta function of E over Fq, defined by a generating series (also see above)

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

Moreover,

\begin{align} Z \left(E/K, {1 \over qT} \right) &= Z(E/K, T)\\ \left(1 - aT + qT^2 \right) &= (1 - \alpha T)(1 - \beta T) \end{align}

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 F2 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 Fq). Also, the group structure of elliptic curves is generally more complicated.

Read more about this topic:  Elliptic Curve

Famous quotes containing the words curves, finite and/or fields:

    “One way to do it might be by making the scenery penetrate the automobile. A polished black sedan was a good subject, especially if parked at the intersection of a tree-bordered street and one of those heavyish spring skies whose bloated gray clouds and amoeba-shaped blotches of blue seem more physical than the reticent elms and effusive pavement. Now break the body of the car into separate curves and panels; then put it together in terms of reflections.”
    —Vladimir Nabokov (1899–1977)

    “All finite things reveal infinitude:”
    —Theodore Roethke (1908–1963)

    “It would not be an easy thing to bring the water all the way to the plain. They would have to organize a great coumbite with all the peasants and the water would unite them once again, its fresh breath would clear away the fetid stink of anger and hatred; the brotherly community would be reborn with new plants, the fields filled with to bursting with fruits and grains, the earth gorged with life, simple and fertile.”
    —Jacques Roumain (1907–1945)