# American Institute of Mathematical Sciences

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

show all references

##### References:
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 & 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 & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021299 [13] Stefano Marò. Relativistic pendulum and invariant curves. Discrete & 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 & 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 & 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] 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

2020 Impact Factor: 0.935

## Tools

Article outline

Figures and Tables