• Previous Article
    Correlation of binary sequence families derived from the multiplicative characters of finite fields
  • AMC Home
  • This Issue
  • 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$
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}$

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.
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. doi: 10.3934/amc.2010.4.261.

[2]

D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve,, Math. Comp., 48 (1987), 95. 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, (2006).

[5]

C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves,, in Selected Areas in Cryptography, (2011), 92.

[6]

X. Ding, Acceleration of algorithm for the reduced sum of two divisors of a hyperelliptic curve,, in Information Computing and Applications, (2011), 177. 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. 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, (2001), 128.

[9]

P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves,, J. Cryptology, 15 (2002), 19. 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. 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. 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.

[13]

M. J. Jacobson, Jr. and A. J. van der Poorten, Computational aspects of NUCOMP,, in Algorithmic Number Theory - ANTS-V, (2002), 120. 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.

[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, (2007), 201. 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, (1997).

[18]

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

[19]

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

[20]

V. Miller, Use of elliptic curves in cryptography,, in Advances in Cryptology - CRYPTO '85, (1986), 417. 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, (2011).

[22]

K. Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves,, in Algorithmic Number Theory (Leiden, (2000), 439. doi: 10.1007/10722028_28.

[23]

V. Shoup, NTL: A Library for doing Number Theory,, Software, (2010).

[24]

E. Teske, An elliptic curve trapdoor system,, J. Cryptology, 19 (2006), 115. 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., (). 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. doi: 10.3934/amc.2010.4.261.

[2]

D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve,, Math. Comp., 48 (1987), 95. 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, (2006).

[5]

C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves,, in Selected Areas in Cryptography, (2011), 92.

[6]

X. Ding, Acceleration of algorithm for the reduced sum of two divisors of a hyperelliptic curve,, in Information Computing and Applications, (2011), 177. 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. 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, (2001), 128.

[9]

P. Gaudry, F. Hess and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves,, J. Cryptology, 15 (2002), 19. 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. 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. 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.

[13]

M. J. Jacobson, Jr. and A. J. van der Poorten, Computational aspects of NUCOMP,, in Algorithmic Number Theory - ANTS-V, (2002), 120. 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.

[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, (2007), 201. 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, (1997).

[18]

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

[19]

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

[20]

V. Miller, Use of elliptic curves in cryptography,, in Advances in Cryptology - CRYPTO '85, (1986), 417. 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, (2011).

[22]

K. Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves,, in Algorithmic Number Theory (Leiden, (2000), 439. doi: 10.1007/10722028_28.

[23]

V. Shoup, NTL: A Library for doing Number Theory,, Software, (2010).

[24]

E. Teske, An elliptic curve trapdoor system,, J. Cryptology, 19 (2006), 115. 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., (). 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 & Management Optimization, 2018, 13 (5) : 1-16. doi: 10.3934/jimo.2018086

[4]

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

[5]

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

[6]

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

[7]

Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics & Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005

[8]

François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 261-310. doi: 10.3934/dcds.2004.11.261

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Qingzhi Yang. The revisit of a projection algorithm with variable steps for variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 211-217. doi: 10.3934/jimo.2005.1.211

[18]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153

[19]

Débora A. F. Albanez, Maicon J. Benvenutti. Continuous data assimilation algorithm for simplified Bardina model. Evolution Equations & Control Theory, 2018, 7 (1) : 33-52. doi: 10.3934/eect.2018002

[20]

Liying Wang, Weiguo Zhao, Dan Zhang, Linming Zhao. A geometric inversion algorithm for parameters calculation in Francis turbine. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1373-1384. doi: 10.3934/dcdss.2015.8.1373

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]