# American Institute of Mathematical Sciences

February  2010, 4(1): 23-47. doi: 10.3934/amc.2010.4.23

## Efficient halving for genus 3 curves over binary fields

 1 Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, Netherlands 2 Instituto de Matemática y Física, Universidad de Talca, Casilla 747, Talca, Chile

Received  March 2009 Revised  September 2009 Published  February 2010

In this article, we deal with fast arithmetic in the Picard group of hyperelliptic curves of genus 3 over binary fields. We investigate both the optimal performance curves, where $h(x)=1$, and the more general curves where the degree of $h(x)$ is 1, 2 or 3. For the optimal performance curves, we provide explicit halving and doubling formulas; not only for the most frequent case but also for all possible special cases that may occur when performing arithmetic on the proposed curves. In this situation, we show that halving offers equivalent performance to that of doubling when computing scalar multiples (by means of an halve-and-add algorithm) in the divisor class group.
For the other types of curves where halving may give performance gains (when the group order is twice an odd number), we give explicit halving formulas which outperform the corresponding doubling formulas by about 10 to 20 field multiplications per halving. These savings more than justify the use of halvings for these curves, making them significantly more efficient than previously thought. For halving on genus 3 curves there is no previous work published so far.
Citation: Peter Birkner, Nicolas Thériault. Efficient halving for genus 3 curves over binary fields. Advances in Mathematics of Communications, 2010, 4 (1) : 23-47. doi: 10.3934/amc.2010.4.23
 [1] Stefan Erickson, Michael J. Jacobson, Jr., Andreas Stein. Explicit formulas for real hyperelliptic curves of genus 2 in affine representation. Advances in Mathematics of Communications, 2011, 5 (4) : 623-666. doi: 10.3934/amc.2011.5.623 [2] Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115 [3] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [4] Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189 [5] Laurent Imbert, Michael J. Jacobson, Jr.. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$. Advances in Mathematics of Communications, 2013, 7 (4) : 485-502. doi: 10.3934/amc.2013.7.485 [6] Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022 [7] Huaiyu Jian, Hongjie Ju, Wei Sun. Traveling fronts of curve flow with external force field. Communications on Pure & Applied Analysis, 2010, 9 (4) : 975-986. doi: 10.3934/cpaa.2010.9.975 [8] Josep M. Miret, Jordi Pujolàs, Anna Rio. Explicit 2-power torsion of genus 2 curves over finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 155-168. doi: 10.3934/amc.2010.4.155 [9] Matteo Costantini, André Kappes. The equation of the Kenyon-Smillie (2, 3, 4)-Teichmüller curve. Journal of Modern Dynamics, 2017, 11: 17-41. doi: 10.3934/jmd.2017002 [10] Hayato Chiba, Georgi S. Medvedev. The mean field analysis of the Kuramoto model on graphs Ⅰ. The mean field equation and transition point formulas. Discrete & Continuous Dynamical Systems - A, 2019, 39 (1) : 131-155. doi: 10.3934/dcds.2019006 [11] Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243 [12] Amer Rasheed, Aziz Belmiloudi, Fabrice Mahé. Dynamics of dendrite growth in a binary alloy with magnetic field effect. Conference Publications, 2011, 2011 (Special) : 1224-1233. doi: 10.3934/proc.2011.2011.1224 [13] Chun-Hao Teng, I-Liang Chern, Ming-Chih Lai. Simulating binary fluid-surfactant dynamics by a phase field model. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1289-1307. doi: 10.3934/dcdsb.2012.17.1289 [14] Washiela Fish, Jennifer D. Key, Eric Mwambene. Binary codes from reflexive uniform subset graphs on $3$-sets. Advances in Mathematics of Communications, 2015, 9 (2) : 211-232. doi: 10.3934/amc.2015.9.211 [15] Yves Achdou, Manh-Khang Dao, Olivier Ley, Nicoletta Tchou. A class of infinite horizon mean field games on networks. Networks & Heterogeneous Media, 2019, 14 (3) : 537-566. doi: 10.3934/nhm.2019021 [16] Bo Su. Doubling property of elliptic equations. Communications on Pure & Applied Analysis, 2008, 7 (1) : 143-147. doi: 10.3934/cpaa.2008.7.143 [17] Denis Danilov, Britta Nestler. Phase-field modelling of nonequilibrium partitioning during rapid solidification in a non-dilute binary alloy. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1035-1047. doi: 10.3934/dcds.2006.15.1035 [18] Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 [19] Gabriella Tarantello. Analytical, geometrical and topological aspects of a class of mean field equations on surfaces. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 931-973. doi: 10.3934/dcds.2010.28.931 [20] Pierluigi Colli, Danielle Hilhorst, Françoise Issard-Roch, Giulio Schimperna. Long time convergence for a class of variational phase-field models. Discrete & Continuous Dynamical Systems - A, 2009, 25 (1) : 63-81. doi: 10.3934/dcds.2009.25.63

2018 Impact Factor: 0.879