1 Elliptic Curves Over Finite Fields

1 Elliptic Curves Over Finite Fields

1.1 Introduction

Definition 1.1. Elliptic curves can be defined over any field K; the formal definition of an elliptic curve is a nonsingular (no cusps, self-intersections, or isolated points) projective algebraic curve over K with genus 1 with a given point defined over K. If the characteristic of K is neither 2 or 3, then every elliptic curve over K can be written in the form

y2 = x3 - px - q

where p, q K such that the RHS does not have any double roots. If the characteristic of K is 3, then the most general equation is of the form

such that RHS has distinct roots.

y2 = 4x3 + b2x2 + 2b4x + b6

In characteristic 2, the most general equation is of the form

y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 provided that the variety it defines is non-singular. Definition 1.2. A rational point is a point whose coordinates lie in K. W denote the set of rational points as E(K) and this set forms a group.

1.2 Isogenies

Definition 1.3. A non-constant morphism : E1 E2 between elliptic curves such that (O) = O is called an isogeny. Let : E1 E2 be an isogeny. Then there is a unique isogeny ^ : E2 E1 satisfying ^ = [deg ]. ^ is called the dual of .

Remark. In the above statement, [n] denotes the isogeny which adds n times.

If E is defined over Fq and q,E : E E is the Frobenius morphism (x, y) - (xq, yq), then E(Fq) = ker(1 - q,E ). As we noted, an isogeny has finite kernel.

Lemma 1.1. Let E1 and E2 be isogenous elliptic curves defined over Fq. Then #E1(Fq) = #E2(Fq). Proof. Any isogeny : E1 E2 commutes with the Frobenius map on E1 and E2. Now, is surjective. So we have y E2(Fq) q,E2 ( (x)) = (x) x ker((1 - q,E2 ) ). Now, each -1(y) has degsep elements. Thus, #E2(Fq) = ker((1-q,E2 ) )/ degsep = # ker( (1-q,E2 ))/ degsep = # ker( (1-q,E1 ))/ degsep = degsep(1- q,E1 ) = #E1(Fq). Recall the following useful facts on degrees and dual maps

(i) + = ^ + ^

(ii) [n^] = [n] (iii) deg[n] = n2 (iv) deg ^ = deg (v) ^^ =

(vi) deg(- ) = deg( )

(vii) d( , ) := deg( + ) - deg - deg is symmetric, bilinear on Hom(E1, E2), where Ei is an elliptic curve.

(viii) deg > 0 for any isogeny

1.3 Riemann Hypothesis for Elliptic Curves

For an elliptic curve E defined over a finite field Fq, the most obvious parameter is the number of points in E(Fq).

Theorem 1.1. (Riemann hypothesis for elliptic curves (Hasse, 1934)) Let E be an elliptic curve defined over Fq. Then

|#E(Fqn ) - 1 - qn| 2qn/2

n 1

Proof. Choose a Weierstrass equation with coefficients in Fq. Since Gal(Fq/Fq) is topologically generated by x -q xq, a point P of E(Fq) lies in E(Fq) if and only if q,E (P) = P. Thus P E(Fqn ) if and only if qn,E (P) = P, i.e., E(Fqn ) = ker(1 - qn,E ). Now 1 - qn,E is a separable morphism (since its differential is the identity). Thus, #E(Fqn ) = deg(1-qn,E ). We noted that, for any two elliptic curves over a field, the function d : Hom(E1, E2)?Hom(E1, E2) Z,

( , ) - deg( + ) - deg - deg is a positive definite bilinear form. By the Cauchy-Schwarz inequality, we get

| deg(1 - qn,E ) - deg 1 - deg qn,E | 2 deg 1 deg qn,E i.e.

|#E(Fqn ) - 1 - qn| 2qn/2

1.4 The Weil Conjectures

Let Kn = Fqn . If V is a projective variety, we want to keep account of #V (Kn). We can do this by using the zeta function of V and it is defined as the formal power series

Tn

Z(V /K1 : T ) = exp

#V (Kn)

n=1

n

Note that

1 dn #V (Kn) = (n - 1)! dT n log Z(V /K1, T )|T=0

The reason for defining the zeta function in this manner is that the series n

1

#V

(Kn

)

Tn n

often looks like the log of a

rational function of T .

Let V be any smooth projective variety of dimension n, defined over K1 = Fq. Then: ? Rationality conjecture

? Functional conjecture There exists an integer such that

Z(V /K1; T ) Q(T )

? Factorization There exists a factorization

1 Z V /K1; qnT

= ?qn/2T Z(V /K1; T )

Z = P1(T )P3(T ) ? ? ? P2n-1(T ) P0(T )P2(T ) ? ? ? P2n-2(T )P2n(T )

with P0(T ) = 1 - T , P2n(T ) = 1 - qnT , each Pi(T ) Z[T ] and

1

-1 bi

Pi qnT = P2n-i(T ) T qn-i/2

where bi = deg Pi = deg P2n-i

? Riemann hypothesis Each root of Pi(T ) satisfies || = q-i/2

The conjecture was proven in its entirety by the efforts of Weil, Dwork, M. Artin, Grothendieck, Lubkin, Deligne, Laumon. But the first case for elliptic curves was solved by Hasse in 1934 before the conjectures were formulated in this generality by Weil in 1949. Weil pointed out that if one had a suitable cohomology theory for abstract varieties analogous to the usual cohomology for varieties over C, the standard properties of the cohomology would imply all the conjectures. For instance, the functional equation would follow from Poincare? duality property. Such a cohomology is the e?tale cohomology.

1.5 Tate Modules and the Weil Pairing

Let E be an elliptic curve defined over Fq. Suppose l is a prime not dividing q. We know that the l-division points of

E, i.e., E[ln] =d ker[ln] is Z/ln ? Z/ln.

The inverse limit Since each E[ln]

of the groups E[ln] with respect to is naturally a Z/ln-module, it can

the be

maps E[ln+1 checked that

] -[l] Tl (E

E [l n ] ) is a

is the Zl (=

Tliam-teZm/lond)u-lemTold(uEle).=Itliim-s aE

[ln]. free

Zl-module of rank 2.

Any isogeny : E1 E2 induces a Zl-module homomorphism l : Tl(E1) Tl(E2). In particular, we have a repre-

sentation End(E) M2(Zl), - l if l q. Note that End(E) End(Tl(E)) is injective because if l = 0 then is 0 on E[ln] for large n, i.e., = O.

Finally, let us recall the Weil pairing. This is a non-degenerate, bilinear, alternating pairing

e : Tl(E) ? Tl(E) Tl(?) =d lim- ?ln = Zl It has the important property that e( x, y) = e(x, ^y). Remark. For any general curves C, D, and a nonconstant morphism : C D, recall that : Div(D) Div(C) is a homomorphism defined by

(P) - e (Q)(Q) Q -1(P)

where e (Q) is the ramification index at Q. For C = D an elliptic curve, all the e (Q) = deginsep . For a general C and D, ordP( f ) = e (Q) ord(P)( f ) for every nonconstant rational function on D.

1.6 Weil Conjectures for Elliptic Curves

Lemma 1.2. Let End(E) and l q be a prime. Then,

det l = deg trace l = 1 + deg - deg(1 - ) In particular, det l, trace l are independent of l, and are integers.

Proof. Let (v1, v2) be a Zl- basis of Tl(E) and write

l =

ab cd

with respect to this basis. We now use the Weil pairing e which is bilinear and alternating

e(v1, v2)deg = e(deg( )v1, v2) = e((^)l( )l)v1, v2) = e(lv1, lv2) = e(av1 + cv2, bv1 + dv2) = e(v1, v2)ad-bc = e(v1, v2)detl

Since e is nondegenerate, we have that deg = deg l. Finally,

trace l = 1 + detl - det(Id - l) = 1 + deg - deg(1 - )

To prove the Weil conjectures for E, we have to compute #E(Kn), where Kn = Fqn . Now #E(Kn) = deg(1 - n) where

= q,E is the Frobenius isogeny.

A consequence of the lemma is the fact that the characteristic polynomial of l has coefficients in Z when l = charFq.

Write

det(Id ? T

- l)

=

(T

- )(T

-)

for

,

C.

Moreover,

for

all

m n

Q,

we

get

m

1

1

det n Id - l = n2 det (mId - nl) = deg(m - n ) n2 > 0

This implies = . Note by triangularizing, that det Id ? T - ln) = (T - n)(T - n), we get

Theorem 1.2. For all n 1, #E(Kn) = 1 - n - n + qn where || = q1/2. In particular,

1 - aT + qT 2 Z(E/K1; T ) = (1 - T )(1 - qT )

where

a

Z

and

1

-

aT

+

qT

2

=

(1

-

T

)(1

-

T

).

Further,

Z (E /K1 ;

1 qT

)

=

Z (E /K1 ;

T

).

Proof. We have that

and

|

|

=

q.

Hence

#E(Kn) = deg(1 - n) = det(1 - ln) = 1 - n - n + qn

log Z(E/K1; T ) = n

(1

1

-

n

-

n

+

qn)

Tn n

=

Tn n

-

( T n

)n

-

( T n

)n

+

(qT n

)n

=

log

(1 - T )(1 - T ) (1 - T )(1 - qT )

The

functional

equation

is

obvious

from

the

expression.

The

factorization

Z

=

P1 P0 P2

is

with

P1(T ) =

1 - aT

+ qT 2,

so

P1

1 qT

= (-1P/1T(T)q)2

Remark. Putting E/Fq (s) = Z(E/K1; q-s), one has 1 - aq-s + q1-2s

E/Fq (s) = (1 - q-s)(1 - q1-s) = E/Fq (1 - s)

Note that the Riemann hypothesis for Z(E/K1; T ) is equivalent to the fact that the zeros of E/Fq (s) are on the line

Re(s)

=

1 2

.

1.7 Supersingularity

Supersingular curves are a special class of elliptic curves which arise naturally. One of the most useful properties they have, as we shall prove, is that their definition forces them to be defines over a small finite field and, over any field, there are only finitely many elliptic curves isogenous to a supersingular one. Before defining supersingularity, let us recall that an elliptic curve E is said to have complex multiplication if End(E) = Z. Let us recall the following result on End(E)

Proposition 1.1. (i) End(E) has no zero divisors.

(ii) End(E) is torsion free.

(iii) End(E) is either Z, or an order in an imaginary quadratic field, or an order in a quaternion division algebra over Q.

Definition 1.4. An elliptic curve E defined over a field of characteristic p > 0 is said to be supersingular if E[p] = O.

The following characterization of supersingular elliptic curves is very useful

Proposition 1.2. Let K be a perfect field of characteristic p > 0. Then the following statements are equivalent:

(a) E is singular

(b) [p] : E E is purely inseparable and j(E) Fp2 (c) E[pr] = O for some r 1 (d) E[pr] = O for all r 1

(e) EndK(E) is an order in a quaternion division algebra over Q. Remark. By the above proposition, up to isomorphism, there are only finitely many elliptic curves isogenous to a supersingular curve. For p = 2, Y 2 + Y = X3 is the unique supersingular curve. For p > 2, we have the following theorem:

1.8 Structure of E(Fq)

Theorem 1.3. A group G of order N = q + 1 - m is isomorphic to E(Fq) for some elliptic curve E over Fq if one of the following holds:

(i) (q, m) = 1, |m| 2q, and G = Z/A ? Z/B where B|(A, m - 2) (ii) q is a square, m = ?2q, and G = (Z/A)2 where A = q 1 (iii) q is a square, p 1 mod 3, m = ?q, and G is cyclic (iv) q is not a square, p = 2 or 3, m = ?pq, and G is cyclic

(v) q is not a square, p 3 mod 4, m = 0, and G is cyclic or q is a square, p 1 mod 4, m = 0, and G is cyclic

(vi)

q is not a square,

p 3 mod 4, m = 0, and G is either cyclic or G = Z/M ? Z/2 where M =

q+1 2

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download