Faster computation of isogenies of large prime degree
Faster computation of isogenies of large prime degree
复制标题
DOI：
10.2140/obs.2020.4.39
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
D. Bernstein;L. D. Feo;Antonin Leroux;Benjamin A. Smith
中科院分区：
文献类型：
--
作者：
D. Bernstein;L. D. Feo;Antonin Leroux;Benjamin A. Smith
让 $\mathcal{E}/\mathbb{F}_q$ 是一条椭圆曲线，并且 $P$ 一点 $\mathcal{E}(\mathbb{F}_q)$ 素阶的 $\ell$． 根据维鲁公式，我们可以计算出一条商曲线 $\mathcal{E}' = \mathcal{E}/\langle{P}\rangle$ 还有定义商同构的有理映射 $\phi: \mathcal{E} \to \mathcal{E}'$ 在 $\tilde{O}(\ell)$ $\mathbb{F}_q$-operations，其中 $\tilde{O}$ 是统一的 $q$．本文展示了如何进行计算 $\mathcal{E}'$，和 $\phi(Q)$ 为了 $Q$ 在 $\mathcal{E}(\mathbb{F}_q)$，仅使用 $\tilde{O}(\sqrt{\ell})$ $\mathbb{F}_q$-operations，其中 $\tilde{O}$ 还是一样的 $q$．作为一种应用，本文加快了基于等基因的密码系统CSIDH和CSURF中的一些计算速度。
Let $\mathcal{E}/\mathbb{F}_q$ be an elliptic curve, and $P$ a point in $\mathcal{E}(\mathbb{F}_q)$ of prime order $\ell$. Velu's formulae let us compute a quotient curve $\mathcal{E}' = \mathcal{E}/\langle{P}\rangle$ and rational maps defining a quotient isogeny $\phi: \mathcal{E} \to \mathcal{E}'$ in $\tilde{O}(\ell)$ $\mathbb{F}_q$-operations, where the $\tilde{O}$ is uniform in $q$.This article shows how to compute $\mathcal{E}'$, and $\phi(Q)$ for $Q$ in $\mathcal{E}(\mathbb{F}_q)$, using only $\tilde{O}(\sqrt{\ell})$ $\mathbb{F}_q$-operations, where the $\tilde{O}$ is again uniform in $q$.As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.