next up previous
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 $ \mathbb {F}$, 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 $ \mathbb {F}$ we have

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

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

If A is any finite dimensional $ \mathbb {F}$-algebra, then a $ \mapsto$ 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 $ \mathbb {F}$. From this one can show that the intersection of the diagonal $ \Delta_{X}^{}$ with the graph $ \Gamma_{F}^{}$ of the Frobenius in X×X is precisely X($ \mathbb {F}$); the points of X over $ \mathbb {F}$.

Now for any regular scheme X over $ \mathbb {F}$, 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 $ \mathbb {G}$a plus the free group on [$ \infty$] (which can be any $ \mathbb {F}$ point of X) and the group Pic0(X). Moreover, there is a group scheme J so that Pic0(X) = J($ \mathbb {F}$). 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 $ \ell$ be a prime that is invertible the field $ \mathbb {F}$. On can show that the points of order $ \ell$ in J(E) for a large enough field extension E of $ \mathbb {F}$ form a vector space of rank 2g over $ \mathbb {Z}$/$ \ell$$ \mathbb {Z}$ (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 $ \ell$. 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 $ \mathbb {F}$. 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$\scriptstyle \ell$(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 $ \ell$ for a number of primes $ \ell$. The additional inequality | a| $ \leq$ 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 $ \ell$-torsion in the Jacobian J. From the action of the Frobenius on this we can write down the coefficients of P(T) modulo $ \ell$. The inequalities resulting from the knowledge of the absolute value of the complex roots can then be used to bound the number of $ \ell$ for which this needs to be done in order to determine the coefficients uniquely.


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