Welcome to the resource topic for 2021/090
Title:
A New Twofold Cornacchia-Type Algorithm and Its Applications
Authors: Bei Wang, Yi Ouyang, Honggang Hu, Songsong Li
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 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.
ePrint: https://eprint.iacr.org/2021/090
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 .