Next: 10 Symmetric Cryptosystems Up: 9 Hyperelliptic Cryptosystems Previous: 9.4 Computing with the

## 9.5 Frobenius Endomorphism

Since all our varieties are defined over a finite field , there is a special endomorphism to consider. Let q be the number of elements of the field, then for any element of the field a = aq. Thus for any polynomial f (t1,..., tr) with coefficients in we have

f (t1,..., tr)q = f (t1q,..., trq)

Now consider the endomorphism of k given by (X0 : ... : Xk) (X0q : ... : Xkq). If X = V(F1,..., Fp;G1,..., Gq) is a subscheme of k and the polynomials Fi and Gj have coefficients in , then this endomorphisms sends X to itself. This endomorphism of X is called the Frobenius Endomorphism F : XX.

If A is any finite dimensional -algebra, then a aq gives a ring homomorphism from A to itself. Moreover if A is local, then the only elements of A that are fixed under this homomorphism are elements of . From this one can show that the intersection of the diagonal with the graph of the Frobenius in X×X is precisely X(); the points of X over .

Now for any regular scheme X over , the Frobenius F is a flat morphism and thus gives an endomorphism of K0(X). The latter group thus acquires some structure'' in addition to being an abelian group. In the case when X is a curve (or more specifically a hyperelliptic curve) this has additional consequences. As we remarked above K0(X) is decomposed as the free group on a plus the free group on [] (which can be any point of X) and the group Pic0(X). Moreover, there is a group scheme J so that Pic0(X) = J(). Thus, one way to determine the order of the group Pic0(X) is to determine the fixed points for the action of Frobenius on this group scheme. Now, let be a prime that is invertible the field . On can show that the points of order in J(E) for a large enough field extension E of form a vector space of rank 2g over / (here g is the genus of the curve X). Moreover, there is a polynomial P(T) of degree 2g with integer coefficients that is satisfied by the automorphism of this vector space that is given by the Frobenius endomorphism; the important point is that this polynomial is independent of . Another important fact is that this polynomial has roots that are complex numbers of absolute value q1/2. Finally, given P(T) one can determine the number of elements in J(E) for any finite extension of . These results were proved by Weil and were generalised to other varieties in the form of the Weil conjectures'' which were proved by Grothendieck, Deligne and others.

This approach was used by Schoof to calculate the order of Pic0(T) in the case T is an elliptic curve (or a hyperelliptic curve of genus 1). In this case P(T) is a quadratic polynomial of the form T2 + aT + q; moreover, J = T in this case. One can write polynomials f(x) that are satisfied by the x co-ordinates of points of order l. Thus we can use the action of the Frobenius on this polynomial to determine a modulo for a number of primes . The additional inequality | a| q1/2, can then we used to determine a. One could attempt to generalise this to other hyperelliptic curves. One must write down the equations that define the -torsion in the Jacobian J. From the action of the Frobenius on this we can write down the coefficients of P(T) modulo . The inequalities resulting from the knowledge of the absolute value of the complex roots can then be used to bound the number of for which this needs to be done in order to determine the coefficients uniquely.

Next: 10 Symmetric Cryptosystems Up: 9 Hyperelliptic Cryptosystems Previous: 9.4 Computing with the
Kapil Hari Paranjape 2002-10-20