Cryptology ePrint Archive: Report 2021/220

A New Twofold Cornacchia-Type Algorithm

Bei Wang; Yi Ouyang; Songsong Li; 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.

Category / Keywords: public-key cryptography / Elliptic curves; 4-GLV decompositions; Twofold Cornacchia-type algorithm

Date: received 26 Feb 2021, last revised 4 Mar 2021

Contact author: wangbei at mail ustc edu cn

Available format(s): PDF | BibTeX Citation

Version: 20210304:134629 (All versions of this report)

Short URL: ia.cr/2021/220


[ Cryptology ePrint archive ]