• Previous Article
    New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours
  • AMC Home
  • This Issue
  • Next Article
    Further results on 2-uniform states arising from irredundant orthogonal arrays
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. BosC. CostelloH. 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.  Google Scholar

[2]

H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer, Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9.  Google Scholar

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

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

[5]

S. D. GalbraithX. 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.  Google Scholar

[6]

R. P. GallantR. 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.  Google Scholar

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

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

[9]

D. HankersonA. J. Menezes and S. Vanstone, Guide to elliptic curve cryptography, Springer, Heidelberg, 281 (2004), 311-314.  doi: 10.1016/s0012-365x(04)00102-5.  Google Scholar

[10]

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

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

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

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

[14]

J. M. MiretR. 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.  Google Scholar

[15]

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

[16]

J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106. Springer, New York, 2009. doi: 10.1007/978-0-387-09494-6.  Google Scholar

[17]

J. Vélu, Isogenies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273 (1971), 238-241.   Google Scholar

[18]

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

[19]

Z. ZhouZ. HuM. 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.  Google Scholar

show all references

References:
[1]

J. W. BosC. CostelloH. 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.  Google Scholar

[2]

H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer, Heidelberg, 1993. doi: 10.1007/978-3-662-02945-9.  Google Scholar

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

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

[5]

S. D. GalbraithX. 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.  Google Scholar

[6]

R. P. GallantR. 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.  Google Scholar

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

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

[9]

D. HankersonA. J. Menezes and S. Vanstone, Guide to elliptic curve cryptography, Springer, Heidelberg, 281 (2004), 311-314.  doi: 10.1016/s0012-365x(04)00102-5.  Google Scholar

[10]

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

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

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

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

[14]

J. M. MiretR. 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.  Google Scholar

[15]

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

[16]

J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106. Springer, New York, 2009. doi: 10.1007/978-0-387-09494-6.  Google Scholar

[17]

J. Vélu, Isogenies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273 (1971), 238-241.   Google Scholar

[18]

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

[19]

Z. ZhouZ. HuM. 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.  Google Scholar

Figure 1.  A lattice diamond in $ \mathbb{Z}[\omega] $
Table 1.  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 & 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]

Stefano Marò. Relativistic pendulum and invariant curves. Discrete & Continuous Dynamical Systems, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139

[13]

Gian-Italo Bischi, Laura Gardini, Fabio Tramontana. Bifurcation curves in discontinuous maps. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 249-267. doi: 10.3934/dcdsb.2010.13.249

[14]

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

[15]

Vladimir Georgiev, Eugene Stepanov. Metric cycles, curves and solenoids. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1443-1463. doi: 10.3934/dcds.2014.34.1443

[16]

Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1

[17]

Lawrence Ein, Wenbo Niu, Jinhyung Park. On blowup of secant varieties of curves. Electronic Research Archive, , () : -. doi: 10.3934/era.2021055

[18]

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

[19]

Adrian Tudorascu. On absolutely continuous curves of probabilities on the line. Discrete & Continuous Dynamical Systems, 2019, 39 (9) : 5105-5124. doi: 10.3934/dcds.2019207

[20]

Nicholas Hoell, Guillaume Bal. Ray transforms on a conformal class of curves. Inverse Problems & Imaging, 2014, 8 (1) : 103-125. doi: 10.3934/ipi.2014.8.103

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (32)
  • HTML views (129)
  • Cited by (0)

Other articles
by authors

[Back to Top]