# American Institute of Mathematical Sciences

• Previous Article
Balanced ($\mathbb{Z} _{2u}\times \mathbb{Z}_{38v}$, {3, 4, 5}, 1) difference packings and related codes
• AMC Home
• This Issue
• Next Article
Parameterization of Boolean functions by vectorial functions and associated constructions
doi: 10.3934/amc.2021026
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## A new twofold Cornacchia-type algorithm and its applications

 1 Key Laboratory of Electromagnetic Space Information, CAS, School of Information Science and Technology, University of Science and Technology of China, Hefei, 230027, China 2 CAS Wu Wen-Tsun Key Laboratory of Mathematics, School of Mathematical Sciences, University of Science and Technology of China, Hefei, 230026, China 3 School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

* Corresponding author: Honggang Hu

Received  April 2021 Early access July 2021

Fund Project: The second author is supported by Anhui Initiative in Quantum Information Technologies grant AHY150200, NSFC grant 11571328. The fourth author is supported by NSFC (grant 61972370 and 61632013), Fundamental Research Funds for Central Universities in China grant WK3480000007

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega = \frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C = \frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curves.

The new twofold algorithm can be used to compute $4$-GLV decompositions on two classes of curves. First it gives a new and unified method to compute all $4$-GLV decompositions on $j$-invariant $0$ elliptic curves over $\mathbb{F}_{p^2}$. Second it can be used to compute the $4$-GLV decomposition on the Jacobian of the hyperelliptic curve defined as $\mathcal{C}/\mathbb{F}_{p}:y^{2} = x^{6}+ax^{3}+b$, which has an endomorphism $\phi$ with the characteristic equation $\phi^2+\phi+1 = 0$ (hence $\mathbb{Z}[\phi] = \mathbb{Z}[\omega]$). As far as we know, none of the previous algorithms can be used to compute the $4$-GLV decomposition on the latter class of curves.

Citation: Bei Wang, Yi Ouyang, Songsong Li, Honggang Hu. A new twofold Cornacchia-type algorithm and its applications. Advances in Mathematics of Communications, doi: 10.3934/amc.2021026
##### References:
 [1] J. W. Bos, C. Costello, H. Hisil and K. Lauter, High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition, International Workshop on Cryptographic Hardware and Embedded Systems, 2013 (2013), 331-348.  doi: 10.1007/978-3-642-40349-1_19. [2] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer, Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9. [3] C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, Selected Areas in Cryptography, 7118 (2012), 92-117.  doi: 10.1007/978-3-642-28496-0_6. [4] D. M. Freeman and T. Satoh, Constructing pairing-friendly hyperelliptic curves using Weil restriction, Journal of Number Theory, 131 (2011), 959-983.  doi: 10.1016/j.jnt.2010.06.003. [5] S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curve cryptography on a Large class of curves, Journal of Cryptology, 24 (2011), 446-469.  doi: 10.1007/s00145-010-9065-y. [6] R. P. Gallant, R. J. Lambert and S. A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, Advances in Cryptology –- CRYPTO 2001, 2139 (2001), 190-200.  doi: 10.1007/3-540-44647-8_11. [7] A. Guillevic and S. Ionica, Four-dimensional GLV via the weil restriction, International Conference on the Theory and Application of Cryptology and Information Security, 2013 (2013), 79-96.  doi: 10.1007/978-3-642-42033-7_5. [8] A. Guillevic and D. Vergnaud, Genus 2 hyperelliptic curve families with explicit jacobian order evaluation and pairing-friendly constructions, Pairing-Based Cryptography-Pairing 2012, 7708 (2013), 234-253.  doi: 10.1007/978-3-642-36334-4_16. [9] D. Hankerson, A. J. Menezes and S. Vanstone, Guide to elliptic curve cryptography, Springer, Heidelberg, 281 (2004), 311-314.  doi: 10.1016/s0012-365x(04)00102-5. [10] Z. Hu, P. Longa and M. Xu, Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0., Designs, Codes and Cryptography, 63 (2012), 331-343.  doi: 10.1007/s10623-011-9558-1. [11] T. Iijima, K. Matsuo, J. Chao and S. Tsujii, Construction of frobenius maps of twists elliptic curves and its application to elliptic scalar multiplication, The 2002 Symposium on Cryptography and Information Security Shirahama, Japan, Jan.29-Feb.1, 2002–-SCIS, 2002,699–702. [12] P. Longa and F. Sica, Four-dimensional gallant-lambert-vanstone scalar multiplication, Journal of Cryptology, 27 (2014), 248-283.  doi: 10.1007/s00145-012-9144-3. [13] P. Longa, High-Speed Elliptic Curve and Pairing-Based Cryptography, Ph.D Thesis, University of Waterloo, 2011. Available from: http://hdl.handle.net/10012/5857. [14] J. M. Miret, R. Moreno Chiral and A. Rio, Generalization of Vélu's formulae for isogenies between elliptic curves, Publicacions Matemàtiques, 2007 (2007), 147-163.  doi: 10.5565/PUBLMAT_PJTN05_07. [15] F. Sica, M. Ciet and J. J. Quisquater, Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms, elliptic and hyperelliptic curves, International Workshop on Selected Areas in Cryptography, 2595 (2002), 21-36.  doi: 10.1007/3-540-36492-7_3. [16] J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106. Springer, New York, 2009. doi: 10.1007/978-0-387-09494-6. [17] J. Vélu, Isogenies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273 (1971), 238-241. [18] H. Yi, Y. Zhu and D. Lin, Refinement of the four-Dimensional GLV method on elliptic curves, International Conference on Selected Areas in Cryptography, 2017 (2017), 23-42.  doi: 10.1007/978-3-319-72565-9_2. [19] Z. Zhou, Z. Hu, M. Xu and W. Song, Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves, Information Processing Letters, 110) (2010), 1003-1006.  doi: 10.1016/j.ipl.2010.08.014.

show all references

##### References:
 [1] J. W. Bos, C. Costello, H. Hisil and K. Lauter, High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition, International Workshop on Cryptographic Hardware and Embedded Systems, 2013 (2013), 331-348.  doi: 10.1007/978-3-642-40349-1_19. [2] H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer, Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9. [3] C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, Selected Areas in Cryptography, 7118 (2012), 92-117.  doi: 10.1007/978-3-642-28496-0_6. [4] D. M. Freeman and T. Satoh, Constructing pairing-friendly hyperelliptic curves using Weil restriction, Journal of Number Theory, 131 (2011), 959-983.  doi: 10.1016/j.jnt.2010.06.003. [5] S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curve cryptography on a Large class of curves, Journal of Cryptology, 24 (2011), 446-469.  doi: 10.1007/s00145-010-9065-y. [6] R. P. Gallant, R. J. Lambert and S. A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, Advances in Cryptology –- CRYPTO 2001, 2139 (2001), 190-200.  doi: 10.1007/3-540-44647-8_11. [7] A. Guillevic and S. Ionica, Four-dimensional GLV via the weil restriction, International Conference on the Theory and Application of Cryptology and Information Security, 2013 (2013), 79-96.  doi: 10.1007/978-3-642-42033-7_5. [8] A. Guillevic and D. Vergnaud, Genus 2 hyperelliptic curve families with explicit jacobian order evaluation and pairing-friendly constructions, Pairing-Based Cryptography-Pairing 2012, 7708 (2013), 234-253.  doi: 10.1007/978-3-642-36334-4_16. [9] D. Hankerson, A. J. Menezes and S. Vanstone, Guide to elliptic curve cryptography, Springer, Heidelberg, 281 (2004), 311-314.  doi: 10.1016/s0012-365x(04)00102-5. [10] Z. Hu, P. Longa and M. Xu, Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0., Designs, Codes and Cryptography, 63 (2012), 331-343.  doi: 10.1007/s10623-011-9558-1. [11] T. Iijima, K. Matsuo, J. Chao and S. Tsujii, Construction of frobenius maps of twists elliptic curves and its application to elliptic scalar multiplication, The 2002 Symposium on Cryptography and Information Security Shirahama, Japan, Jan.29-Feb.1, 2002–-SCIS, 2002,699–702. [12] P. Longa and F. Sica, Four-dimensional gallant-lambert-vanstone scalar multiplication, Journal of Cryptology, 27 (2014), 248-283.  doi: 10.1007/s00145-012-9144-3. [13] P. Longa, High-Speed Elliptic Curve and Pairing-Based Cryptography, Ph.D Thesis, University of Waterloo, 2011. Available from: http://hdl.handle.net/10012/5857. [14] J. M. Miret, R. Moreno Chiral and A. Rio, Generalization of Vélu's formulae for isogenies between elliptic curves, Publicacions Matemàtiques, 2007 (2007), 147-163.  doi: 10.5565/PUBLMAT_PJTN05_07. [15] F. Sica, M. Ciet and J. J. Quisquater, Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms, elliptic and hyperelliptic curves, International Workshop on Selected Areas in Cryptography, 2595 (2002), 21-36.  doi: 10.1007/3-540-36492-7_3. [16] J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106. Springer, New York, 2009. doi: 10.1007/978-0-387-09494-6. [17] J. Vélu, Isogenies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273 (1971), 238-241. [18] H. Yi, Y. Zhu and D. Lin, Refinement of the four-Dimensional GLV method on elliptic curves, International Conference on Selected Areas in Cryptography, 2017 (2017), 23-42.  doi: 10.1007/978-3-319-72565-9_2. [19] Z. Zhou, Z. Hu, M. Xu and W. Song, Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves, Information Processing Letters, 110) (2010), 1003-1006.  doi: 10.1016/j.ipl.2010.08.014.
A lattice diamond in $\mathbb{Z}[\omega]$
Total cost of scalar multiplication at a 128-bit security level
 Curve Method Operation counts Global estimation $E_{1}(\mathbb{F}_{p_{1}^{2}})$ 4-GLV(Algorithm in [12-18])4-GLV(Our algorithm) $885M+580S$ $4395m$ $E_{2}(\mathbb{F}_{p_{2}^{2}})-(12)$ {4-GLV(Algorithm in [10])4-GLV(Our algorithm) $834M+560S$ $4182m$ $E_{2}(\mathbb{F}_{p_{2}^{2}})-(13)$ 4-GLV (Our algorithm) $834M+556S$ $4170m$ $J_{\mathcal{C}}(\mathbb{F}_{p})$ 4-GLV(Our algorithm) $1623m+300s$ $1923m$
 Curve Method Operation counts Global estimation $E_{1}(\mathbb{F}_{p_{1}^{2}})$ 4-GLV(Algorithm in [12-18])4-GLV(Our algorithm) $885M+580S$ $4395m$ $E_{2}(\mathbb{F}_{p_{2}^{2}})-(12)$ {4-GLV(Algorithm in [10])4-GLV(Our algorithm) $834M+560S$ $4182m$ $E_{2}(\mathbb{F}_{p_{2}^{2}})-(13)$ 4-GLV (Our algorithm) $834M+556S$ $4170m$ $J_{\mathcal{C}}(\mathbb{F}_{p})$ 4-GLV(Our algorithm) $1623m+300s$ $1923m$
 [1] M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197 [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] Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389 [4] Roberto Avanzi, Michael J. Jacobson, Jr., Renate Scheidler. Efficient reduction of large divisors on hyperelliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 261-279. doi: 10.3934/amc.2010.4.261 [5] 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 [6] Philip N. J. Eagle, Steven D. Galbraith, John B. Ong. Point compression for Koblitz elliptic curves. Advances in Mathematics of Communications, 2011, 5 (1) : 1-10. doi: 10.3934/amc.2011.5.1 [7] 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 [8] Alice Silverberg. Some remarks on primality proving and elliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 427-436. doi: 10.3934/amc.2014.8.427 [9] David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335 [10] Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101 [11] Ravi Vakil and Aleksey Zinger. A natural smooth compactification of the space of elliptic curves in projective space. Electronic Research Announcements, 2007, 13: 53-59. [12] Guilin Ji, Changjian Liu. The cyclicity of a class of quadratic reversible centers defining elliptic curves. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021299 [13] Stefano Marò. Relativistic pendulum and invariant curves. Discrete and Continuous Dynamical Systems, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139 [14] Gian-Italo Bischi, Laura Gardini, Fabio Tramontana. Bifurcation curves in discontinuous maps. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 249-267. doi: 10.3934/dcdsb.2010.13.249 [15] Carlos Munuera, Alonso Sepúlveda, Fernando Torres. Castle curves and codes. Advances in Mathematics of Communications, 2009, 3 (4) : 399-408. doi: 10.3934/amc.2009.3.399 [16] Vladimir Georgiev, Eugene Stepanov. Metric cycles, curves and solenoids. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1443-1463. doi: 10.3934/dcds.2014.34.1443 [17] Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1 [18] Lawrence Ein, Wenbo Niu, Jinhyung Park. On blowup of secant varieties of curves. Electronic Research Archive, 2021, 29 (6) : 3649-3654. doi: 10.3934/era.2021055 [19] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [20] Ananta Acharya, R. Shivaji, Nalin Fonseka. $\Sigma$-shaped bifurcation curves for classes of elliptic systems. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022067

2020 Impact Factor: 0.935