---
abstract: 'This paper provides a probabilistic algorithm to determine generators of the $m$-torsion subgroup of the Jacobian of a hyperelliptic curve of genus two.'
address: |
    Department of Mathematical Sciences\
    University of Aarhus\
    Ny Munkegade\
    Building 1530\
    DK-8000 Aarhus C
author:
- Christian Robenhagen Ravnshøj
title: Generators of Jacobians of Hyperelliptic Curves
---

[^1]

Introduction {#sec:intro}
============

Let $C$ be a hyperelliptic curve of genus two defined over a prime field ${\mathbb{F}}_p$, and ${\mathcal{J}_{C}}$ the Jacobian of $C$. Consider the rational subgroup ${\mathcal{J}_{C}}({\mathbb{F}}_p)$. ${\mathcal{J}_{C}}({\mathbb{F}}_p)$ is a finite abelian group, and $${\mathcal{J}_{C}}({\mathbb{F}}_p)\simeq{\mathbb{Z}}/n_1{\mathbb{Z}}\oplus{\mathbb{Z}}/n_2{\mathbb{Z}}\oplus{\mathbb{Z}}/n_3{\mathbb{Z}}\oplus{\mathbb{Z}}/n_4{\mathbb{Z}},$$ where $n_i\mid n_{i+1}$ and $n_2\mid p-1$. [@frey-ruck] shows that if $m\mid p-1$, then the discrete logarithm problem in the rational $m$-torsion subgroup ${\mathcal{J}_{C}}({\mathbb{F}}_p)[m]$ of ${\mathcal{J}_{C}}({\mathbb{F}}_p)$ can be reduced to the corresponding problem in ${\mathbb{F}}_p^\times$ [@frey-ruck corollary 1]. In the proof of this result it is claimed that the non-degeneracy of the Tate pairing can be used to determine whether $r$ random elements of the finite group ${\mathcal{J}_{C}}({\mathbb{F}}_p)[m]$ in fact is an independent set of generators of ${\mathcal{J}_{C}}({\mathbb{F}}_p)[m]$. This paper provides an explicit, probabilistic algorithm to determine generators of ${\mathcal{J}_{C}}({\mathbb{F}}_p)[m]$.

In short, the algorithm outputs elements $\gamma_i$ of the Sylow-$\ell$ subgroup ${\Gamma}_\ell$ of the rational subgroup ${\Gamma}={\mathcal{J}_{C}}({\mathbb{F}}_p)$, such that ${\Gamma}_\ell=\bigoplus_i{\langle \gamma_i \rangle}$ in the following steps:

1.  Choose random elements $\gamma_i\in{\Gamma}_\ell$ and $h_j\in{\mathcal{J}_{C}}({\mathbb{F}}_p)$, $i,j\in\{1,\dots,4\}$.\[choose:intro\]

2.  Use the non-degeneracy of the tame Tate pairing $\tau$ to *diagonalize* the sets $\{\gamma_i\}_i$ and $\{h_j\}_j$ with respect to $\tau$; i.e. modify the sets such that $\tau(\gamma_i,h_j)=1$ if $i\neq j$ and $\tau(\gamma_i,h_i)$ is an $\ell^{\mathrm{th}}$ root of unity.\[step:diagonaliser\]

3.  If $\prod_i|\gamma_i|<|{\Gamma}_\ell|$ then go to step \[choose:intro\].

4.  Output the elements $\gamma_1$, $\gamma_2$, $\gamma_3$ and $\gamma_4$.

The key ingredient of the algorithm is the diagonalization in step \[step:diagonaliser\]; this process will be explained in section \[sec:generators\].

We will write ${\langle \gamma_i|i\in I \rangle}={\langle \gamma_i \rangle}_i$ and $\bigoplus_{i\in I}{\langle \gamma_i \rangle}=\bigoplus_i{\langle \gamma_i \rangle}$ if the index set $I$ is clear from the context.

Hyperelliptic curves
====================

A hyperelliptic curve is a smooth, projective curve $C\subseteq{\mathbb{P}}^n$ of genus at least two with a separable, degree two morphism $\phi:C\to{\mathbb{P}}^1$. In the rest of this paper, let $C$ be a hyperelliptic curve of genus two defined over a prime field ${\mathbb{F}}_p$ of characteristic $p>2$. By the Riemann-Roch theorem there exists an embedding $\psi:C\to{\mathbb{P}}^2$, mapping $C$ to a curve given by an equation of the form $$y^2=f(x),$$ where $f\in{\mathbb{F}}_p[x]$ is of degree six and have no multiple roots [see @cassels chapter 1].

The set of principal divisors $\mathcal{P}(C)$ on $C$ constitutes a subgroup of the degree zero divisors $\operatorname{Div}_0(C)$. The Jacobian ${\mathcal{J}_{C}}$ of $C$ is defined as the quotient $${\mathcal{J}_{C}}=\operatorname{Div}_0(C)/\mathcal{P}(C).$$ Consider the subgroup ${\mathcal{J}_{C}}({\mathbb{F}}_p)<{\mathcal{J}_{C}}$ of ${\mathbb{F}}_p$-rational elements. There exist numbers $n_i$, such that $$\label{eq:rank4}
    {\mathcal{J}_{C}}({\mathbb{F}}_p)\simeq{\mathbb{Z}}/n_1{\mathbb{Z}}\oplus{\mathbb{Z}}/n_2{\mathbb{Z}}\oplus{\mathbb{Z}}/n_3{\mathbb{Z}}\oplus{\mathbb{Z}}/n_4{\mathbb{Z}},$$ where $n_i\mid n_{i+1}$ and $n_2\mid p-1$ [see @hhec proposition 5.78, p. 111]. We wish to determine generators of the $m$-torsion subgroup ${\mathcal{J}_{C}}({\mathbb{F}}_p)[m]<{\mathcal{J}_{C}}({\mathbb{F}}_p)$, where $m\mid |{\mathcal{J}_{C}}({\mathbb{F}}_p)|$ is the largest number such that $\ell\mid p-1$ for every prime number $\ell\mid m$.

Finite abelian groups
=====================

[@miller] shows the following theorem.

\[teo:ssh-generator\] Let $G$ be a finite abelian group of torsion rank $r$. Then for $s\geq r$ the probability that a random $s$-tuple of elements of $G$ generates $G$ is at least $$\frac{C_r}{\log\log|G|}$$ if $s=r$, and at least $C_s$ if $s>r$, where $C_s>0$ is a constant depending only on $s$ (and not on $|G|$).

[@miller theorem 3, p. 251]

Combining theorem \[teo:ssh-generator\] and equation , we expect to find generators of ${\Gamma}[m]$ by choosing $4$ random elements $\gamma_i\in{\Gamma}[m]$ in approximately $\frac{\log\log |{\Gamma}[m]|}{C_4}$ attempts.

To determine whether the generators are independent, i.e. if ${\langle \gamma_i \rangle}_i=\bigoplus_i{\langle \gamma_i \rangle}$, we need to know the subgroups of a cyclic $\ell$-group $G$. These are determined uniquely by the order of $G$, since $$\{0\}<{\langle \ell^{n-1}g \rangle}<{\langle \ell^{n-2}g \rangle}<\dots<{\langle \ell g \rangle}<G$$ are the subgroups of the group $G={\langle g \rangle}$ of order $\ell^n$. The following corollary is an immediate consequence of this observation.

\[kor:UGsnit\] Let $U_1$ and $U_2$ be cyclic subgroups of a finite group $G$. Assume $U_1$ and $U_2$ are $\ell$-groups. Let ${\langle u_i \rangle}<U_i$ be the subgroups of order $\ell$. Then $$U_1\cap U_2=\{e\}\Longleftrightarrow{\langle u_1 \rangle}\cap{\langle u_2 \rangle}=\{e\}.$$ Here $e\in G$ is the neutral element.

The tame Tate pairing
=====================

Let ${\Gamma}={\mathcal{J}_{C}}({\mathbb{F}}_p)$ be the rational subgroup of the Jacobian. Consider a number $\lambda\mid\gcd(|{\Gamma}|,p-1)$. Let $g\in{\Gamma}[\lambda]$ and $h=\sum_ia_i P_i\in{\Gamma}$ be divisors with no points in common, and let $$\overline{h}\in{\Gamma}/\lambda{\Gamma}$$ denote the class containing the divisor $h$. Furthermore, let $f\in{\mathbb{F}}_{p}(C)$ be a rational function on $C$ with divisor $\operatorname{div}(f)=\lambda g$. Set $f(h)=\prod_if(P_i)^{a_i}$. Then $$e_\lambda(g,\overline{h})=f(h)$$ is a well-defined pairing ${\Gamma}[\lambda]\times{\Gamma}/\lambda{\Gamma}\longrightarrow{\mathbb{F}}_{p}^\times/({\mathbb{F}}_{p}^\times)^\lambda$, the *Tate pairing*; cf. [@galbraith]. Raising to the power $\frac{p-1}{\lambda}$ gives a well-defined element in the subgroup $\mu_\lambda<{\mathbb{F}}_{p}^\times$ of the $\lambda^{\mathrm{th}}$ roots of unity. This pairing $$\tau_\lambda:{\Gamma}[\lambda]\times{\Gamma}/\lambda{\Gamma}\longrightarrow\mu_\lambda$$ is called the *tame Tate pairing*.

Since the class $\overline{h}$ is represented by the element $h\in{\Gamma}$, we will write $\tau_\lambda(g,h)$ instead of $\tau_\lambda(g,\overline{h})$. Furthermore, we will omit the subscript $\lambda$ and just write $\tau(g,h)$, since the value of $\lambda$ will be clear from the context.

[@hess] gives a short and elementary proof of the following theorem.

\[teo:tatepairing\] The tame Tate pairing $\tau$ is bilinear and non-degenerate.

\[kor:tatepairing\] For every element $g\in{\Gamma}$ of order $\lambda$ an element $h\in{\Gamma}$ exists, such that $\mu_\lambda={\langle \tau(g,h) \rangle}$.

[@sil corollary 8.1.1., p. 98] gives a similar result for elliptic curves and the Weil pairing. The proof of this result only uses that the pairing is bilinear and non-degenerate. Hence it applies to corollary \[kor:tatepairing\].

In the following we only need the existence of the element $h\in{\Gamma}$, such that $\mu_\lambda={\langle \tau(g,h) \rangle}$; we do not need to find it.

Generators of ${\Gamma}[m]$ {#sec:generators}
===========================

As in the previous section, let ${\Gamma}={\mathcal{J}_{C}}({\mathbb{F}}_p)$ be the rational subgroup of the Jacobian. We are searching for elements $\gamma_i\in{\Gamma}[m]$ such that ${\Gamma}[m]=\bigoplus_i{\langle \gamma_i \rangle}$. As an abelian group, ${\Gamma}[m]$ is the direct sum of its Sylow subgroups. Hence, we only need to find generators of the Sylow subgroups of ${\Gamma}[m]$.

Set $N=|{\Gamma}|$ and let $\ell\mid\gcd(N,p-1)$ be a prime number. Choose four random elements $\gamma_i\in{\Gamma}$. Let ${\Gamma}_\ell<{\Gamma}$ be the Sylow-$\ell$ subgroup of ${\Gamma}$, and set $N_\ell=|{\Gamma}_\ell|$. Then $\frac{N}{N_\ell}\gamma_i\in {\Gamma}_\ell$. Hence, we may assume that $\gamma_i\in {\Gamma}_\ell$. If all the elements $\gamma_i$ are equal to zero, then we choose other elements $\gamma_i\in{\Gamma}$. Hence, we may assume that some of the elements $\gamma_i$ are non-zero.

Let $|\gamma_i|=\lambda_i$, and re-enumerate the $\gamma_i$’s such that $\lambda_i\leq\lambda_{i+1}$. Since some of the $\gamma_i$’s are non-zero, we may choose an index $\nu\leq 4$, such that $\lambda_\nu\neq 1$ and $\lambda_i=1$ for $i<\nu$. Choose $\lambda_0$ minimal such that $\lambda=\frac{\lambda_\nu}{\lambda_0}\mid p-1$. Then ${\mathbb{F}}_p$ contains an element $\zeta$ of order $\lambda$. Now set $g_i=\frac{\lambda_i}{\lambda}\gamma_i$, $\nu\leq i\leq 4$. Then $g_i\in{\Gamma}[\lambda]$, $\nu\leq i\leq 4$. Finally, choose four random elements $h_i\in{\Gamma}$.

Let $$\tau:{\Gamma}[\lambda]\times{\Gamma}/\lambda{\Gamma}\longrightarrow{\langle \zeta \rangle}$$ be the tame Tate pairing. Define remainders $\alpha_{ij}$ modulo $\lambda$ by $$\tau(g_i,h_j)=\zeta^{\alpha_{ij}}.$$ By corollary \[kor:tatepairing\], for any of the elements $g_i$ we can choose an element $h\in{\Gamma}$, such that $|\tau(g_i,h)|=\lambda$. Assume that ${\Gamma}/\lambda{\Gamma}={\langle \overline{h}_1,\overline{h}_2,\overline{h}_3,\overline{h}_4 \rangle}$. Then $\overline{h}=\sum_iq_i\overline{h}_i$, and so $$\tau(g_i,h)=\zeta^{\alpha_{i1}q_1+\alpha_{i2}q_2+\alpha_{i3}q_3+\alpha_{i4}q_4}.$$ If $\alpha_{ij}\equiv 0\pmod{\ell}$, $1\leq j\leq 4$, then $|\tau(g_i,h)|<\lambda$. Hence, if ${\Gamma}/\lambda{\Gamma}={\langle \overline{h}_1,\overline{h}_2,\overline{h}_3,\overline{h}_4 \rangle}$, then for all $i\in\{\nu,\dots,4\}$ we can choose a $j\in\{1,\dots,4\}$, such that $\alpha_{ij}\not\equiv 0\pmod{\ell}$.

Enumerate the $h_i$ such that $\alpha_{44}\not\equiv 0\pmod{\ell}$. Now assume a number $j<4$ exists, such that $\alpha_{4j}\not\equiv 0\pmod{\lambda}$. Then $\zeta^{\alpha_{4j}}=\zeta^{\beta_1\alpha_{44}}$, and replacing $h_j$ with $h_j-\beta_1h_4$ gives $\alpha_{4j}\equiv 0\pmod{\lambda}$. So we may assume that $$\alpha_{41}\equiv\alpha_{42}\equiv\alpha_{43}\equiv 0\pmod{\lambda}\qquad\textrm{and}\qquad\alpha_{44}\not\equiv 0\pmod{\ell}.$$ Assume similarly that a number $j<4$ exists, such that $\alpha_{j4}\not\equiv 0\pmod{\lambda}$. Now set $\beta_2\equiv\alpha_{44}^{-1}\alpha_{j4}\pmod{\lambda}$. Then $\tau(g_j-\beta_2g_4,h_4)=1$. So we may also assume that $$\alpha_{14}\equiv\alpha_{24}\equiv\alpha_{34}\equiv 0\pmod{\lambda}.$$ Repeating this process recursively, we may assume that $$\alpha_{ij}\equiv 0\pmod{\lambda}\qquad\textrm{and}\qquad\alpha_{44}\not\equiv 0\pmod{\ell}.$$ Again $\nu\leq i\leq 4$ and $1\leq j\leq 4$.

The discussion above is formalized in the following algorithm.

\[alg:1\] As input we are given a hyperelliptic curve $C$ of genus two defined over a prime field ${\mathbb{F}}_p$, the number $N=|{\Gamma}|$ of ${\mathbb{F}}_p$-rational elements of the Jacobian, and a prime factor $\ell\mid\gcd(N,p-1)$. The algorithm outputs elements $\gamma_i\in {\Gamma}_\ell$ of the Sylow-$\ell$ subgroup ${\Gamma}_\ell$ of ${\Gamma}$, such that ${\langle \gamma_i \rangle}_i=\bigoplus_i{\langle \gamma_i \rangle}$ in the following steps.

1.  Compute the order $N_\ell$ of the Sylow-$\ell$ subgroup of ${\Gamma}$.

2.  Choose elements $\gamma_i\in{\Gamma}$, $i\in I:=\{1,2,3,4\}$. Set $\gamma_i:=\frac{N}{N_\ell}\gamma_i$. \[step:choose-x\]

3.  Choose elements $h_j\in{\Gamma}$, $j\in J:=\{1,2,3,4\}$. \[step:choose-h\]

4.  Set $K:=\{1,2,3,4\}$.

5.  For $k'$ from $0$ to $3$ do the following:

    1.  Set $k:=4-k'$.

    2.  If $\gamma_i=0$, then set $I:=I\setminus\{i\}$. If $|I|=0$, then go to step \[step:choose-x\].

    3.  Compute the orders $\lambda_\kappa:=|\gamma_\kappa|$, $\kappa\in K$. Re-enumerate the $\gamma_\kappa$’s such that $\lambda_\kappa\leq \lambda_{\kappa+1}$, $\kappa\in K$. Set $I:=\{5-|I|,6-|I|,\dots,4\}$.

    4.  Set $\nu:=\min(I)$, and choose $\lambda_0$ minimal such that $\lambda:=\frac{\lambda_\nu}{\lambda_0}\mid p-1$. Set $g_\kappa:=\frac{\lambda_\kappa}{\lambda}\gamma_\kappa$, $\kappa\in I\cap K$.

        1.  If $g_k=0$, then go to step \[step:last\].

        2.  If $\tau(g_k,h_j)^{\lambda/\ell}=1$ for all $j\leq k$, then go to step \[step:choose-h\].

    5.  Choose a primitive $\lambda^{\mathrm{th}}$ root of unity $\zeta\in{\mathbb{F}}_p$. Compute $\alpha_{kj}$ and $\alpha_{\kappa k}$ from $\tau(g_k,h_j)=\zeta^{\alpha_{kj}}$ and $\tau(g_\kappa,h_k)=\zeta^{\alpha_{\kappa k}}$, $1\leq j<k$, $\kappa\in I\cap K$. Re-enumerate $h_1,\dots,h_k$ such that $\alpha_{kk}\not\equiv 0\pmod{\ell}$.

    6.  For $1\leq j<k$, set $\beta\equiv\alpha_{kk}^{-1}\alpha_{kj}\pmod{\lambda}$ and $h_j:=h_j-\beta h_k$.

    7.  For $\kappa\in I\cap K\setminus\{k\}$, set $\beta\equiv\alpha_{kk}^{-1}\alpha_{\kappa k}\pmod{\lambda}$ and $\gamma_\kappa:=\gamma_\kappa-\beta\frac{\lambda_k}{\lambda_\kappa}\gamma_k$.

    8.  Set $K:=K\setminus\{k\}$.

6.  Output $\gamma_1$, $\gamma_2$, $\gamma_3$ and $\gamma_4$.\[step:last\]

\[rem:runningtime\] Algorithm \[alg:1\] consists of a small number of

1.  calculations of orders of elements $\gamma\in{\Gamma}_\ell$,\[item:orden\]

2.  multiplications of elements $\gamma\in{\Gamma}$ with numbers $a\in{\mathbb{Z}}$,\[item:gange\]

3.  additions of elements $\gamma_1,\gamma_2\in{\Gamma}$,\[item:addition\]

4.  evaluations of pairings of elements $\gamma_1,\gamma_2\in{\Gamma}$ and\[item:parring\]

5.  solving the discrete logarithm problem in ${\mathbb{F}}_p$, i.e. to determine $\alpha$ from $\zeta$ and $\xi=\zeta^\alpha$.\[item:DL\]

By [@miller proposition 9], the order $|\gamma|$ of an element $\gamma\in{\Gamma}_\ell$ can be calculated in time $O(\log^3 N_\ell)\mathcal{A}_{\Gamma}$, where $\mathcal{A}_{\Gamma}$ is the time for adding two elements of ${\Gamma}$. A multiple $a\gamma$ or a sum $\gamma_1+\gamma_2$ is computed in time $O(\mathcal{A}_{\Gamma})$. By [@frey-ruck], the pairing $\tau(\gamma_1,\gamma_2)$ of two elements $\gamma_1,\gamma_2\in{\Gamma}$ can be evaluated in time $O(\log N_\ell)$. Finally, by [@pohlig-hellmann] the discrete logarithm problem in ${\mathbb{F}}_p$ can be solved in time $O(\log p)$. We may assume that addition in ${\Gamma}$ is easy, i.e. that $\mathcal{A}_{\Gamma}<O(\log p)$. Hence algorithm \[alg:1\] runs in expected time $O(\log p)$.

Careful examination of algorithm \[alg:1\] gives the following lemma.

\[lem:diagonal\] Let ${\Gamma}_\ell$ be the Sylow-$\ell$ subgroup of ${\Gamma}$, $\ell\mid p-1$. Algorithm \[alg:1\] determines elements $\gamma_i\in {\Gamma}_\ell$ and $h_i\in{\Gamma}$, $1\leq i\leq 4$, such that one of the following cases holds.

1.  $\alpha_{11}\alpha_{22}\alpha_{33}\alpha_{44}\not\equiv 0\pmod{\ell}$ and $\alpha_{ij}\equiv 0\pmod{\lambda}$, $i\neq
     j$, $i,j\in\{1,2,3,4\}$.\[case:dia1\]

2.  $\gamma_1=0$, $\alpha_{22}\alpha_{33}\alpha_{44}\not\equiv 0\pmod{\ell}$ and $\alpha_{ij}\equiv 0\pmod{\lambda}$, $i\neq
     j$, $i,j\in\{2,3,4\}$.

3.  $\gamma_1=\gamma_2=0$, $\alpha_{33}\alpha_{44}\not\equiv 0\pmod{\ell}$ and $\alpha_{ij}\equiv 0\pmod{\lambda}$, $i\neq
     j$, $i,j\in\{3,4\}$.

4.  $\gamma_1=\gamma_2=\gamma_3=0$.

If $|\gamma_i|=\lambda_i$, then $\lambda_i\leq \lambda_{i+1}$. Set $\nu=\min\{i|\lambda_i\neq 1\}$, and define $\lambda_0$ as the least number, such that $\lambda=\frac{\lambda_\nu}{\lambda_0}\mid p-1$. Set $g_i=\frac{\lambda_i}{\lambda}\gamma_i$, $\nu\leq i\leq 4$. Then the numbers $\alpha_{ij}$ above are determined by $$\tau(g_i,h_j)=\zeta^{\alpha_{ij}},$$ where $\tau$ is the tame Tate pairing ${\Gamma}[\lambda]\times{\Gamma}/\lambda{\Gamma}\to\mu_\lambda={\langle \zeta \rangle}$.

\[teo:p-1\] Algorithm \[alg:1\] determines elements $\gamma_1$, $\gamma_2$, $\gamma_3$ and $\gamma_4$ of the Sylow-$\ell$ subgroup of ${\Gamma}$, $\ell\mid p-1$, such that ${\langle \gamma_i \rangle}_i=\bigoplus_i{\langle \gamma_i \rangle}$.

Choose elements $\gamma_i,h_i\in{\Gamma}$ such that the conditions of lemma \[lem:diagonal\] are fulfilled. Set $\lambda_i=|\gamma_i|$, and let $\nu=\min\{i|\lambda_i\neq 1\}$. Define $\lambda_0$ as the least number, such that $\lambda=\frac{\lambda_\nu}{\lambda_0}\mid p-1$. Set $g_i=\frac{\lambda_i}{\lambda}\gamma_i$. Then the $\alpha_{ij}$’s from lemma \[lem:diagonal\] are determined by $$\tau(g_i,h_j)=\zeta^{\alpha_{ij}}.$$ We only consider case \[case:dia1\] of lemma \[lem:diagonal\], since the other cases follow similarly. We start by determining ${\langle \gamma_3 \rangle}\cap{\langle \gamma_4 \rangle}$. Assume that $g_3=ag_4$. Then $$1=\tau(g_3,h_4)=\tau(ag_4,h_4)=\zeta^{a\alpha_{44}},$$ i.e. $a\equiv 0\pmod{\lambda}$. Hence ${\langle \gamma_3 \rangle}\cap{\langle \gamma_4 \rangle}=\{0\}$. Then we determine ${\langle \gamma_2 \rangle}\cap{\langle \gamma_3,\gamma_4 \rangle}$. Assume $g_2=ag_3+bg_4$. Then $$1=\tau(g_2,h_3)=\tau(ag_3,h_3)=\zeta^{a\alpha_{33}},$$ i.e. $a\equiv 0\pmod{\lambda}$. In the same way, $$1=\tau(g_2,h_4)=\zeta^{b\alpha_{44}},$$ i.e. $b\equiv 0\pmod{\lambda}$. Hence ${\langle \gamma_2 \rangle}\cap{\langle \gamma_3,\gamma_4 \rangle}=\{0\}$. Similarly ${\langle \gamma_1 \rangle}\cap{\langle \gamma_2,\gamma_3,\gamma_4 \rangle}=\{0\}$. Hence ${\langle \gamma_i \rangle}_i=\bigoplus_i{\langle \gamma_i \rangle}$.

From theorem \[teo:p-1\] we get the following probabilistic algorithm to determine generators of the $m$-torsion subgroup ${\Gamma}[m]<{\Gamma}$, where $m\mid |{\Gamma}|$ is the largest divisor of $|{\Gamma}|$ such that $\ell\mid p-1$ for every prime number $\ell\mid m$.

\[alg:1a\] As input we are given a hyperelliptic curve $C$ of genus two defined over a prime field ${\mathbb{F}}_p$, the number $N=|{\Gamma}|$ of ${\mathbb{F}}_p$-rational elements of the Jacobian, and the prime factors $p_1,\dots,p_n$ of $\gcd(N,p-1)$. The algorithm outputs elements $\gamma_i\in{\Gamma}[m]$ such that ${\Gamma}[m]=\bigoplus_i{\langle \gamma_i \rangle}$ in the following steps.

1.  Set $\gamma_i:=0$, $1\leq i\leq 4$. For $\ell\in\{p_1,\dots,p_n\}$ do the following:

    1.  Use algorithm \[alg:1\] to determine elements $\tilde\gamma_i\in{\Gamma}_\ell$, $1\leq i\leq 4$, such that ${\langle \tilde\gamma_i \rangle}_i=\bigoplus_i{\langle \tilde\gamma_i \rangle}$.\[step:kandidater\]

    2.  If $\prod_i|\tilde\gamma_i|<|{\Gamma}_\ell|$, then go to step \[step:kandidater\].

    3.  Set $\gamma_i:=\gamma_i+\tilde\gamma_i$, $1\leq i\leq 4$.

2.  Output $\gamma_1$, $\gamma_2$, $\gamma_3$ and $\gamma_4$.

By remark \[rem:runningtime\], algorithm \[alg:1a\] has expected running time $O(\log p)$. Hence algorithm \[alg:1a\] is an efficient, probabilistic algorithm to determine generators of the $m$-torsion subgroup ${\Gamma}[m]<{\Gamma}$, where $m\mid |{\Gamma}|$ is the largest divisor of $|{\Gamma}|$ such that $\ell\mid p-1$ for every prime number $\ell\mid m$.

The strategy of algorithm \[alg:1\] can be applied to *any* finite, abelian group ${\Gamma}$ with bilinear, non-degenerate pairings into cyclic groups. For the strategy to be efficient, the pairings must be efficiently computable, and the discrete logarithm problem in the cyclic groups must be easy.

[99]{}

<span style="font-variant:small-caps;">J.W.S. Cassels and E.V. Flynn</span>. *Prolegomena to a Middlebrow Arithmetic of Curves of Genus $2$*. London Mathematical Society Lecture Note Series. Cambridge University Press, 1996. <span style="font-variant:small-caps;">G. Frey and T. Lange</span>. Varieties over Special Fields. In H. Cohen and G. Frey, editors, *Handbook of Elliptic and Hyperelliptic Curve Cryptography*, pp. 87–113. Chapman & Hall/CRC, 2006. <span style="font-variant:small-caps;">G. Frey and H.-G. R[ü]{}ck</span>. A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves. *Math. Comp.*, vol. 62, pp. 865–874, 1994. <span style="font-variant:small-caps;">S. Galbraith</span>. Pairings. In I.F. Blake, G. Seroussi and N.P. Smart, editors, *Advances in Elliptic Curve Cryptography*. London Mathematical Society Lecture Note Series, vol. 317, pp. 183–213. Cambridge University Press, 2005. <span style="font-variant:small-caps;">F. Hess</span>. A note on the Tate pairing of curves over finite fields. *Arch. Math.*, no. 82, pp. 28–32, 2004. <span style="font-variant:small-caps;">V.S. Miller</span>. The Weil Pairing and Its Efficient Calculation. *J. Cryptology*, no. 17, pp. 235–261, 2004. <span style="font-variant:small-caps;">S. Pohlig and M. Hellmann</span>. An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance. *IEEE Trans. Inform. Theory*, vol. 24, pp. 106–110, 1978. <span style="font-variant:small-caps;">J.H. Silverman</span>. *The Arithmetic of Elliptic Curves*. Springer, 1986.

[^1]: Research supported in part by a Ph.D. grant from CRYPTOMAThIC
