### A New Twofold Cornacchia-Type Algorithm

Bei Wang, Yi Ouyang, Songsong Li, and Honggang Hu

##### Abstract

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 curve. Besides, we give some applications of our new algotithm in some cuvres not considered in Longa and Sica's algorithm.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Elliptic curves4-GLV decompositionsTwofold Cornacchia-type algorithm
Contact author(s)
wangbei @ mail ustc edu cn
History
2021-03-04: last of 3 revisions
See all versions
Short URL
https://ia.cr/2021/220

CC BY

BibTeX

@misc{cryptoeprint:2021/220,
author = {Bei Wang and Yi Ouyang and Songsong Li and Honggang Hu},
title = {A New Twofold Cornacchia-Type Algorithm},
howpublished = {Cryptology ePrint Archive, Paper 2021/220},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/220}},
url = {https://eprint.iacr.org/2021/220}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.