General 4-GLV Lattice Reduction Algorithms

Abstract

With two $\mathbb{Z}$ -linear independence endomorphisms $\Phi$ and $\Psi$ satisfying $\Phi^{2}+r\Phi+s=0$ and $\Psi^{2}-t_{\Psi}\Psi+n_{\Psi}=0$, we construct general 4-GLV lattice reduction algorithms with $\mathbb{Z}[\Psi\vert$ principal maximal orders of imaginary quadratic fields $\mathbb{Q}(\sqrt{-d})$. The algorithms can be used to calculate short bases for 4-GLV decompositions on elliptic curves (or Jacobians of genus 2 curves). Our algorithms have a theoretic upper bound of output $Cn^{1/4}$, where \begin{align*} C=\begin{cases} {\frac{4+2\sqrt{d+1}}{3-d}} (\sqrt{1+\vert r\vert +\vert s\vert }),\ &\text{if}\ \mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-d}}{2}],\ \frac{4\sqrt{d}}{(4\sqrt{d}-(d+1)}(\sqrt{1+\vert r\vert +\vert s\vert }),\ &\text{if}\ \mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-d}}{2}].\end{cases}\end{align*} Especially, our algorithms cover the case $\mathbb{Z}[\Psi]=\mathbb{Z}[\sqrt{-1}]$ of Yi et al. (SAC 2017) and the case $\mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-3}}{2}]$ of Wang et al. (AMC 2021).