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

Laurent Imbert; Michael J. Jacobson, Jr.

doi:10.3934/amc.2013.7.485

Article Contents

2013, Volume 7, Issue 4: 485-502. Doi: 10.3934/amc.2013.7.485

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

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
2.
Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4

Received: November 30, 2012

Published: October 2013

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.