An optimal representation for the trace zero subgroup

We give an optimal-size representation for the elements of the trace zero subgroup of the Picard group of an elliptic or hyperelliptic curve of any genus, with respect to a field extension of any prime degree. The representation is via the coefficients of a rational function, and it is compatible with scalar multiplication of points. We provide efficient compression and decompression algorithms, and complement them with implementation results. We discuss in detail the practically relevant cases of small genus and extension degree, and compare with the other known compression methods.

We thank Tanja Lange for bringing to our attention the work of Blady and Naumann, and we are grateful to the mathematics department of the University of Zurich for access to their computing facilities. The authors were partially supported by the Swiss National Science Foundation under Grants Nos. 123393, 150207, and 151884.

Authors and Affiliations

1. Institut de mathématiques, Université de Neuchâtel, Rue Emile-Argand 11, 2000, Neuchâtel, Switzerland

   Elisa Gorla

2. School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia

   Maike Massierer

Corresponding author

Correspondence to Elisa Gorla.

Communicated by G. Korchmaros.

Appendix: Explicit equations

We compute explicit equations for compression and decompression for the cases when \(g=1\) and \(n=3,5\), or \(g=2\) and \(n=3\). We give explicit formulas for compression, while for decompression we explicitly compute a low degree polynomial, whose roots give the result of the decompression.

In addition to making the computation more efficient, the results contained in this appendix allow us to perform precise operation counts, and thus to compare our method to the other existing compression methods in Sect. 5. When computing complexities, we count squarings (S), multiplications (M), and inversions (I) in \({\mathbb {F}_q}\), but not additions or multiplications by constants.

1.1 Appendix 1: Explicit equations for \(g=1,n=3\)

In this case \(h_P = \ell _1\) is a line through the points \(P, \varphi (P), \varphi ^2(P)\). We assume that \({\mathbb {F}_q}\) does not have characteristic 2 or 3 and that E is given by an equation in short Weierstrass form

For simplicity, we also assume that \(3 \mid q-1\) and write \({\mathbb {F}}_{q^3} = {\mathbb {F}_q}[\zeta ]/(\zeta ^3-\mu )\) as a Kummer extension, where \(\mu \in {\mathbb {F}_q}\) is not a third power. Then \(1, \zeta , \zeta ^2\) is a basis of \({\mathbb {F}}_{q^3}|{\mathbb {F}_q}\). It is highly likely that there exists a suitable \(\mu \) of small size, see [33, Sect. 3.1]. When working with a field extension where \(3 \not \mid q-1\), one may use a normal basis, which yields similar but denser equations.

Compression If \(P = (X,Y) \notin E({\mathbb {F}_q})\), then the equation of \(h_P = \ell _1\) is

and \(\mathcal {R}(P) = (\gamma _0, \gamma _1)\in \mathbb {F}_q^2.\) Let

then a simple computation yields

where

are constants and can be precomputed during the setup phase of the algorithm. Hence compression takes 2S+6M+1I in \({\mathbb {F}_q}\).

When \(P \in E({\mathbb {F}_q})\), the line \(\ell _1\) is a tangent and we have

Notice that such points are in \(E[3]({\mathbb {F}_q})\) and therefore very few.

Decompression This algorithm computes the polynomial \(H_P\) and its roots over \({\mathbb {F}}_{q^3}\). We have

Computing the coefficients of \(H_P\) therefore takes 2S+1M in \({\mathbb {F}_q}\). Since the roots of this polynomial are \(X,X^q,X^{q^2}\), and using (2), we get

Hence one can solve system (3) over \({\mathbb {F}_q}\), to recover \((X_0,X_1,X_2)\). Since the solutions of the system are exactly the Frobenius conjugates of X, it suffices to find a single solution. This takes at most 3S+3M+1I, one square root, and two cube roots in \({\mathbb {F}_q}\) (see [26, Sect. 5]). Notice that, since this system is so simple, this is more efficient than factoring \(H_P\) over \({\mathbb {F}}_{q^3}\). Finally, \(Y = -\gamma _1 X - \gamma _0\), so recomputing one y-coordinate takes 1M in \({\mathbb {F}_q}\), and the other ones can be recovered via the Frobenius map. In total, decompression takes at most 5S+5M+1I, one square root, and two cube roots in \({\mathbb {F}_q}\).

1.2 Appendix 2: Explicit equations for \(g=1, n=5\)

We assume that E is given in short Weierstrass form \(E: y^2 = x^3+Ax+B\) over a field of characteristic not equal to 2 or 3.

Compression  Let \(P = (X,Y) \in T_5\) and denote by \(\lambda _1, \lambda _2, \lambda _3\) the slopes of the lines \(\ell _1, \ell _2, \ell _3\), respectively. We have

where

Computing \(\lambda _1, \lambda _2, \lambda _3\) takes a total of 3M+3I in \({\mathbb {F}}_{q^5}\). Then, \(\beta _0,\gamma _0,\gamma _1,\gamma _2\) can be computed with a total of 3S+15M in \({\mathbb {F}}_{q^5}\). Thus, compression takes a total of 3S+18M+3I in \({\mathbb {F}}_{q^5}\).

Decompression We compute

using 4S+3M in \({\mathbb {F}_q}\). Then we factor the polynomial \(H_P(x) = x^5 - S_1x^4 + S_2 x^3 - S_3 x^2 + S_4 x - S_5\), which takes \(O(\log _2q)\) operations in \({\mathbb {F}_q}\). Finally, recovering Y costs 1S+3M+1I in \({\mathbb {F}}_{q^5}\).

1.3 Appendix 3: Explicit equations for \(g=2, n=3\)

We assume \(2, 3 \not \mid |{{\mathrm{Pic}}}^0_C({\mathbb {F}}_{q^3})|\) and that the characteristic of \({\mathbb {F}_q}\) is not equal to 2 or 5. A simple transformation yields a curve equation of the shape

We assume that C is given in this form, which slightly simplifies the equations. Formulas for the general case can be worked out similarly.

The trace zero variety of hyperelliptic curves of genus 2, with respect to a degree 3 base field extension, was studied in detail by Lange [32, 33]. One of her results is that the Mumford representation of all non-trivial elements of \(T_3\) has a u-polynomial of degree 2.

Theorem 7.1

([33, Theorem 2.2]) Assume that C has genus 2 and that \(2, 3 \not \mid |{{\mathrm{Pic}}}^0_C({\mathbb {F}}_{q^3})|\). Then all non-trivial elements of \(T_3\) are represented by reduced divisors of the form

where \(P_1, P_2 \ne \mathcal {O}\) and \(P_1 \ne P_2, \varphi (P_2), \varphi ^2(P_2)\).

Corollary 7.2

Assume that C has genus 2 and that \(2,3 \not \mid |{{\mathrm{Pic}}}^0_C({\mathbb {F}}_{q^3})|\). Then all non-trivial elements of \(T_3\) are represented by reduced divisors of the form \(D=P_1+P_2-2\mathcal {O}\notin {{\mathrm{Div}}}_C({\mathbb {F}}_{q}),\) and one of the following mutually exclusive facts holds:

1. (i)

   \(P_1,P_2\in C({\mathbb {F}}_{q^3})\setminus \{\mathcal {O}\}\) and \(P_1\in \{ w(\varphi (P_2)), w(\varphi ^2(P_2))\}\),

2. (ii)

   \(P_1,P_2\in C({\mathbb {F}}_{q^3})\setminus \{\mathcal {O}\}\) and \(P_1 \ne P_2, \varphi (P_2), \varphi ^2(P_2), w(\varphi (P_2)), w(\varphi ^2(P_2))\),

3. (iii)

   \(P_1\in C({\mathbb {F}}_{q^6})\setminus C({\mathbb {F}}_{q^3})\) and \(P_2=\varphi ^3(P_1)\).

Let [u, v] be the Mumford representation of [D]. Then in cases (ii) and (iii) the divisor \(D+\varphi (D)\) is semi-reduced and \(u\not \mid h_{D,2}\), in particular \(h_{D,2}\ne 0\).

Proof

It is easy to check that (i)-(iii) are mutually exclusive, and that one must be in one of these situations. We now show that \(D+\varphi (D)\) is semi-reduced and \(u\not \mid h_{D,2}\). If we are in case (ii), then clearly \(D+\varphi (D)\) is semi-reduced. By contradiction assume that \(h_{D,2}\equiv 0 \bmod {u}\). Let \(P_j=(X_j,Y_j)\), \(j=1,2\). \(P_j-\mathcal {O}\in {{\mathrm{Div}}}_C({\mathbb {F}}_{q^3})\) is a reduced prime divisor. Since \(h_{D,2}(X_j)=0\), by Theorem 3.7(i) we have \(w(P_j)=\varphi ^i(P_j)\). Then \(X_j\in {\mathbb {F}}_{q^3}\cap {\mathbb {F}}_{q^i}={\mathbb {F}_q}\) and \(Y_j\in {\mathbb {F}}_{q^3}\cap {\mathbb {F}}_{q^{2i}}={\mathbb {F}_q}\). Hence \(D=P_1+P_2-2\mathcal {O}\in {{\mathrm{Div}}}_C({\mathbb {F}_q})\), which contradicts Theorem 7.1.

Assume now that we are in case (iii). Since D is prime, by Theorem 3.7(i), \(u\mid h_{D,2}\) if and only if \(w(D)=\varphi ^i(D)\) for some \(i=1,2\). By contradiction, assume this is the case. Then either \(w(P_1)=\varphi ^i(P_1)\) or \(w(P_1)=\varphi ^{i+3}(P_1)\). Hence \(X=X^{q^j}\in {\mathbb {F}}_{q^6}\cap {\mathbb {F}}_{q^j}\subseteq {\mathbb {F}}_{q^2}\) and \(Y=-Y^{q^j}\in {\mathbb {F}}_{q^6}\cap {\mathbb {F}}_{q^{2j}}\subseteq {\mathbb {F}}_{q^2}\) for some \(j\in \{i,i+3\}\). This shows that \(D\in {{\mathrm{Div}}}_C({\mathbb {F}}_{q^2})\cap {{\mathrm{Div}}}_C({\mathbb {F}}_{q^3})={{\mathrm{Div}}}_C({\mathbb {F}_q})\), which contradicts Theorem 7.1. Therefore \(u\not \mid h_{D,2}\) and \(D+\varphi (D)=P_1+\varphi (P_1)+\varphi ^3(P_1)+\varphi ^4(P_1)-4\mathcal {O}\) is semi-reduced. Notice that \(P_1\ne w(\varphi (P_2))\) and \(P_2\ne w(\varphi (P_1))\), since D is reduced. \(\square \)

Compression We consider elements \(0\ne [D] = [u,v] \in T_3\), \(D = P_1 + P_2 - 2\mathcal {O}\) with \(P_1\ne w(\varphi (P_2))\), \(w(\varphi ^2(P_2))\) and \(u,u^{\varphi }\) coprime. The special cases can be worked out separately, and we do not treat them here.

Proposition 7.3

Let \(0 \ne [D]=[u,v] \in T_3\), \(D = P_1 + P_2 - 2\mathcal {O}\) with \(P_1\ne w(\varphi (P_2))\), \(w(\varphi ^2(P_2))\) and \(\gcd (u,u^{\varphi })=1\). Let [U, V] be the Mumford representation of the semi-reduced divisor \(D + \varphi (D)\). Then

Proof

The divisor \(D + \varphi (D)\) is semi-reduced by Corollary 7.2. By Theorem 3.2(iii), we have \(h_D = h_{D,1} + yh_{D,2}\) with \(\deg h_{D,1} = 3\) and \(\deg h_{D,2} \le 0\). Since \(h_{D,2} \ne 0\) by Corollary 7.2, after multiplication by a constant we have \(h_D = y - \gamma (x)\) where \(\gamma \in {\mathbb {F}_q}[x]\) of degree 3. If \(P_i = (X_i,Y_i)\), then \(h_D(X_i^{q^j},Y_i^{q^j})=0\) and hence \(\gamma (X_i^{q^j}) = Y_i^{q^j}\) for \(i=1,2\), \(j=0,1,2\). But V is the unique polynomial of degree \(\le 3\) with \(V(X_i^{q^j}) = Y_i^{q^j}\) for \(i=1,2, j=0,1,2\), and therefore \(\gamma = V\).

In order to compute V, observe that it is the unique polynomial V of degree \(< \deg (u u^{\varphi }) = 4\) such that \(V \equiv v \bmod {u}\) and \(V \equiv v^{\varphi } \bmod {u^{\varphi }}. \) Keeping in mind that \(u, u^{\varphi }\) are coprime, and using the Chinese Remainder Theorem (or following the explicit formulas in [34]), we get

as claimed. \(\square \)

Denoting \(u(x) = x^2 + u_1x + u_0\) and \(v(x) = v_1x + v_0\), we compute the compression \((\beta _0,\gamma _0,\gamma _1,\gamma _2,1)\) of D according to the following formulas. We abbreviate

Then

Computing these values in the straightforward way takes 2S+32M+1I in \({\mathbb {F}}_{q^3}\). This number could probably be optimized by regrouping the terms in a more sophisticated way.

Decompression Since decompression is dominated by factoring polynomials, we do not perform an exact operation count here. The algorithm computes

over \({\mathbb {F}_q}\) to obtain \(H_D = x^6 - S_1x^5 + S_2x^4 - S_3x^3 + S_4x^2 - S_5x + S_6\). In almost all cases we are decompressing a divisor of the shape that we consider above for compression. \(H_D\) either splits over \({\mathbb {F}_q}\) into two factors of degree 3, or it is irreducible over \({\mathbb {F}_q}\). Factoring \(H_D\) over \({\mathbb {F}_q}\) takes \(O(\log q)\) operations in \({\mathbb {F}_q}\). Then we factor either two polynomials of degree 3 over \({\mathbb {F}}_{q^3}\), or one degree 6 polynomial over \({\mathbb {F}}_{q^3}\), in \(O(\log q)\) operations in \({\mathbb {F}}_{q^3}\). In all cases, we then compute the corresponding v-polynomials. It follows that the overall complexity of decompression is \(O(\log q)\) operations in \({\mathbb {F}_q}\).

Reprints and permissions