论文标题
超基椭圆曲线的计算内态环和与等级图中的探路的连接
Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
论文作者
论文摘要
在计算数字理论中，计算上椭圆曲线的内态环是一个重要的问题，并且它也与一些最近提出的基于ISEGEN的密码系统的安全性密切相关。在本文中，我们给出了一种新算法，用于计算在某些启发式下运行的超级椭圆曲线$ e $的内态环环（（（\ log log p）^2p^2p^{1/2}）$。该算法首先通过在Superingular $ \ ell $ - 发育图$ g（p，\ ell）$中找到一个特定形式的两个周期来起作用，生成$ $λ\ subseteq \ subseteq \ opperatorAtorname {end}（end}（e）$。然后计算所有包含$λ$的最大订单，从而扩展了Voight的工作。最后一步是确定这些最大顺序中的哪个是内态戒指。作为周期查找算法的一部分，我们在$ g中与$ j^p $相邻的所有$ j $ invariants $ j $的集合中给出了一个下限，在$ g（p，\ ell）$中回答了Arxiv中的问题：1909.077779。
Computing endomorphism rings of supersingular elliptic curves is an important problem in computational number theory, and it is also closely connected to the security of some of the recently proposed isogeny-based cryptosystems. In this paper we give a new algorithm for computing the endomorphism ring of a supersingular elliptic curve $E$ that runs, under certain heuristics, in time $O((\log p)^2p^{1/2})$. The algorithm works by first finding two cycles of a certain form in the supersingular $\ell$-isogeny graph $G(p,\ell)$, generating an order $Λ\subseteq \operatorname{End}(E)$. Then all maximal orders containing $Λ$ are computed, extending work of Voight. The final step is to determine which of these maximal orders is the endomorphism ring. As part of the cycle finding algorithm, we give a lower bound on the set of all $j$-invariants $j$ that are adjacent to $j^p$ in $G(p,\ell)$, answering a question in arXiv:1909.07779.
