American Institute of Mathematical Sciences

Advanced
  • 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

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.  Google Scholar

[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.  Google Scholar

[3]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1996.  Google Scholar

[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.  Google Scholar

[5]

C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, in Selected Areas in Cryptography, 2011, 92-117.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

M. J. Jacobson, Jr. and H. C. Williams, Solving the Pell Equation, Springer-Verlag, 2009.  Google Scholar

[17]

D. E. Knuth, The Art of Computer Programming, Third edition, Addison-Wesley, Reading, MA, 1997.  Google Scholar

[18]

N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209. doi: 10.1090/S0025-5718-1987-0866109-5.  Google Scholar

[19]

N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150. doi: 10.1007/BF02252872.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

V. Shoup, NTL: A Library for doing Number Theory, Software, 2010. Available from: http://www.shoup.net/ntl. Google Scholar

[24]

E. Teske, An elliptic curve trapdoor system, J. Cryptology, 19 (2006), 115-133. doi: 10.1007/s00145-004-0328-3.  Google Scholar

[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., ().  doi: 10.1090/S0025-5718-2013-02748-2.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

H. Cohen, A Course in Computational Algebraic Number Theory, Springer, 1996.  Google Scholar

[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.  Google Scholar

[5]

C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, in Selected Areas in Cryptography, 2011, 92-117.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

M. J. Jacobson, Jr. and H. C. Williams, Solving the Pell Equation, Springer-Verlag, 2009.  Google Scholar

[17]

D. E. Knuth, The Art of Computer Programming, Third edition, Addison-Wesley, Reading, MA, 1997.  Google Scholar

[18]

N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209. doi: 10.1090/S0025-5718-1987-0866109-5.  Google Scholar

[19]

N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150. doi: 10.1007/BF02252872.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

V. Shoup, NTL: A Library for doing Number Theory, Software, 2010. Available from: http://www.shoup.net/ntl. Google Scholar

[24]

E. Teske, An elliptic curve trapdoor system, J. Cryptology, 19 (2006), 115-133. doi: 10.1007/s00145-004-0328-3.  Google Scholar

[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., ().  doi: 10.1090/S0025-5718-2013-02748-2.  Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & 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 & Games, 2021  doi: 10.3934/jdg.2021029
[10]

François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (105)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy