Empirical optimization of divisor arithmetic on hyperelliptic curves over \mathbb{F}_{2^m}

Previous Article
The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$
AMC Home
This Issue
Next Article
Correlation of binary sequence families derived from the multiplicative characters of finite fields

November 2013, 7(4): 485-502. doi: 10.3934/amc.2013.7.485

Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$

Laurent Imbert ^1, and Michael J. Jacobson, Jr. ^2,

1.	CNRS, LIRMM, Université Montpellier 2, 161 rue Ada, F-34095 Montpellier, France
2.	Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada

Received December 2012 Published October 2013

Abstract
Related Papers

A significant amount of effort has been devoted to improving divisor arithmetic on low-genus hyperelliptic curves via explicit versions of generic algorithms. Moderate and high genus curves also arise in cryptographic applications, for example, via the Weil descent attack on the elliptic curve discrete logarithm problem, but for these curves, the generic algorithms are to date the most efficient available. Nagao [22] described how some of the techniques used in deriving efficient explicit formulas can be used to speed up divisor arithmetic using Cantor's algorithm on curves of arbitrary genus. In this paper, we describe how Nagao's methods, together with a sub-quadratic complexity partial extended Euclidean algorithm using the half-gcd algorithm can be applied to improve arithmetic in the degree zero divisor class group. We present numerical results showing which combination of techniques is more efficient for hyperelliptic curves over $\mathbb{F}_{2^n}$ of various genera.

Keywords: Cantor’s algorithm, Hyperelliptic curve, NUCOMP, half-gcd algorithm., divisor addition.

Mathematics Subject Classification: Primary: 94A60, 14H45; Secondary: 14Q0.

Citation: 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

References:

[1]	R. Avanzi, M. J. Jacobson, Jr. and R. Scheidler, Efficient divisor reduction on hyperelliptic curves, Adv. Math. Commun., 4 (2010), 261-279. doi: 10.3934/amc.2010.4.261.
[2]	D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp., 48 (1987), 95-101. doi: 10.1090/S0025-5718-1987-0866101-0.
[3]	H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1996.
[4]	H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, Boca Raton, 2006.
[5]	C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, in Selected Areas in Cryptography, 2011, 92-117.
[6]	X. Ding, Acceleration of algorithm for the reduced sum of two divisors of a hyperelliptic curve, in Information Computing and Applications, Springer, 2011, 177-184. doi: 10.1007/978-3-642-16336-4_24.
[7]	A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith., 102 (2002), 83-103. doi: 10.4064/aa102-1-6.
[8]	G. Frey, Applications of arithmetical geometry to cryptographic constructions, in Proceedings of the Fifth International Conference on Finite Fields and Applications, Springer, 2001, 128-161.
[9]	P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology, 15 (2002), 19-46. doi: 10.1007/s00145-001-0011-x.
[10]	P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp., 76 (2007), 475-492. doi: 10.1090/S0025-5718-06-01900-4.
[11]	L. Imbert, M. J. Jacobson, Jr. and A. Schmidt, Fast ideal cubing in imaginary quadratic number and function fields, Adv. Math. Commun., 4 (2010), 237-260. doi: 10.3934/amc.2010.4.237.
[12]	M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc., 16 (2001), 231-260.
[13]	M. J. Jacobson, Jr. and A. J. van der Poorten, Computational aspects of NUCOMP, in Algorithmic Number Theory - ANTS-V, Springer-Verlag, Berlin, 2002, 120-133. doi: 10.1007/3-540-45455-1_10.
[14]	M. J. Jacobson, Jr., R. E. Sawilla and H. C. Williams, Efficient ideal reduction in quadratic fields, Int. J. Math. Comp. Sci., 1 (2006), 83-116.
[15]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, in Advances in Coding Theory and Cryptology, World Scientific Publishing, 2007, 201-244. doi: 10.1142/9789812772022_0013.
[16]	M. J. Jacobson, Jr. and H. C. Williams, Solving the Pell Equation, Springer-Verlag, 2009.
[17]	D. E. Knuth, The Art of Computer Programming, Third edition, Addison-Wesley, Reading, MA, 1997.
[18]	N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209. doi: 10.1090/S0025-5718-1987-0866109-5.
[19]	N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150. doi: 10.1007/BF02252872.
[20]	V. Miller, Use of elliptic curves in cryptography, in Advances in Cryptology - CRYPTO '85, 1986, 417-426. doi: 10.1007/3-540-39799-X_31.
[21]	M. Musson, Another Look at the Gaudry, Hess and Smart Attack on the Elliptic Curve Discrete Logarithm Problem, Ph.D thesis, University of Calgary, 2011.
[22]	K. Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves, in Algorithmic Number Theory (Leiden, 2000), Springer, Berlin, 2000, 439-447. doi: 10.1007/10722028_28.
[23]	V. Shoup, NTL: A Library for doing Number Theory, Software, 2010. Available from: http://www.shoup.net/ntl.
[24]	E. Teske, An elliptic curve trapdoor system, J. Cryptology, 19 (2006), 115-133. doi: 10.1007/s00145-004-0328-3.
[25]	M. D. Velichka, M. J. Jacobson, Jr. and A. Stein, Computing discrete logarithms on high-genus hyperelliptic curves over even characteristic finite fields, Math. Comp., to appear. doi: 10.1090/S0025-5718-2013-02748-2.

show all references

References:

[1]	R. Avanzi, M. J. Jacobson, Jr. and R. Scheidler, Efficient divisor reduction on hyperelliptic curves, Adv. Math. Commun., 4 (2010), 261-279. doi: 10.3934/amc.2010.4.261.
[2]	D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp., 48 (1987), 95-101. doi: 10.1090/S0025-5718-1987-0866101-0.
[3]	H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1996.
[4]	H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, Boca Raton, 2006.
[5]	C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, in Selected Areas in Cryptography, 2011, 92-117.
[6]	X. Ding, Acceleration of algorithm for the reduced sum of two divisors of a hyperelliptic curve, in Information Computing and Applications, Springer, 2011, 177-184. doi: 10.1007/978-3-642-16336-4_24.
[7]	A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith., 102 (2002), 83-103. doi: 10.4064/aa102-1-6.
[8]	G. Frey, Applications of arithmetical geometry to cryptographic constructions, in Proceedings of the Fifth International Conference on Finite Fields and Applications, Springer, 2001, 128-161.
[9]	P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology, 15 (2002), 19-46. doi: 10.1007/s00145-001-0011-x.
[10]	P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp., 76 (2007), 475-492. doi: 10.1090/S0025-5718-06-01900-4.
[11]	L. Imbert, M. J. Jacobson, Jr. and A. Schmidt, Fast ideal cubing in imaginary quadratic number and function fields, Adv. Math. Commun., 4 (2010), 237-260. doi: 10.3934/amc.2010.4.237.
[12]	M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc., 16 (2001), 231-260.
[13]	M. J. Jacobson, Jr. and A. J. van der Poorten, Computational aspects of NUCOMP, in Algorithmic Number Theory - ANTS-V, Springer-Verlag, Berlin, 2002, 120-133. doi: 10.1007/3-540-45455-1_10.
[14]	M. J. Jacobson, Jr., R. E. Sawilla and H. C. Williams, Efficient ideal reduction in quadratic fields, Int. J. Math. Comp. Sci., 1 (2006), 83-116.
[15]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, in Advances in Coding Theory and Cryptology, World Scientific Publishing, 2007, 201-244. doi: 10.1142/9789812772022_0013.
[16]	M. J. Jacobson, Jr. and H. C. Williams, Solving the Pell Equation, Springer-Verlag, 2009.
[17]	D. E. Knuth, The Art of Computer Programming, Third edition, Addison-Wesley, Reading, MA, 1997.
[18]	N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209. doi: 10.1090/S0025-5718-1987-0866109-5.
[19]	N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150. doi: 10.1007/BF02252872.
[20]	V. Miller, Use of elliptic curves in cryptography, in Advances in Cryptology - CRYPTO '85, 1986, 417-426. doi: 10.1007/3-540-39799-X_31.
[21]	M. Musson, Another Look at the Gaudry, Hess and Smart Attack on the Elliptic Curve Discrete Logarithm Problem, Ph.D thesis, University of Calgary, 2011.
[22]	K. Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves, in Algorithmic Number Theory (Leiden, 2000), Springer, Berlin, 2000, 439-447. doi: 10.1007/10722028_28.
[23]	V. Shoup, NTL: A Library for doing Number Theory, Software, 2010. Available from: http://www.shoup.net/ntl.
[24]	E. Teske, An elliptic curve trapdoor system, J. Cryptology, 19 (2006), 115-133. doi: 10.1007/s00145-004-0328-3.
[25]	M. D. Velichka, M. J. Jacobson, Jr. and A. Stein, Computing discrete logarithms on high-genus hyperelliptic curves over even characteristic finite fields, Math. Comp., to appear. doi: 10.1090/S0025-5718-2013-02748-2.

[1]	Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038
[2]	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
[3]	Serap Ergün, Sirma Zeynep Alparslan Gök, Tuncay Aydoǧan, Gerhard Wilhelm Weber. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra's algorithm. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1085-1100. doi: 10.3934/jimo.2018086
[4]	Mary Wilkerson. Thurston's algorithm and rational maps from quadratic polynomial matings. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2403-2433. doi: 10.3934/dcdss.2019151
[5]	Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
[6]	Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545
[7]	Xiaojun Zhou, Chunhua Yang, Weihua Gui. State transition algorithm. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1039-1056. doi: 10.3934/jimo.2012.8.1039
[8]	Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics and Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005
[9]	Jonathan Newton, William H. Sandholm. Stochastic dynamics and Edmonds' algorithm. Journal of Dynamics and Games, 2021 doi: 10.3934/jdg.2021029
[10]	François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 261-310. doi: 10.3934/dcds.2004.11.261
[11]	Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial and Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049
[12]	Elena Beretta, Markus Grasmair, Monika Muszkieta, Otmar Scherzer. A variational algorithm for the detection of line segments. Inverse Problems and Imaging, 2014, 8 (2) : 389-408. doi: 10.3934/ipi.2014.8.389
[13]	Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[14]	J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[15]	Yuying Shi, Ying Gu, Li-Lian Wang, Xue-Cheng Tai. A fast edge detection algorithm using binary labels. Inverse Problems and Imaging, 2015, 9 (2) : 551-578. doi: 10.3934/ipi.2015.9.551
[16]	Simai He, Min Li, Shuzhong Zhang, Zhi-Quan Luo. A nonconvergent example for the iterative water-filling algorithm. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 147-150. doi: 10.3934/naco.2011.1.147
[17]	Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[18]	Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[19]	Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics and Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020
[20]	Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Laurent Imbert Michael J. Jacobson, Jr.
on Google Scholar
Laurent Imbert Michael J. Jacobson, Jr.

[Back to Top]