Welcome to the resource topic for 2021/220
Title:
A New Twofold Cornacchia-Type Algorithm
Authors: 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.
ePrint: https://eprint.iacr.org/2021/220
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .