标题： 计算超奇异端末环的不可分端末方法 显示英文标题

标题： Computing supersingular endomorphism rings using inseparable endomorphisms

摘要： 我们给出了一种计算定义在$\mathbb F_{p^2}$上的超奇异椭圆曲线$E$的不可分自同态的算法，该算法在广义黎曼假设（GRH）下，预计在$O(p^{1/2}(\log p)^2(\log\log p)^3)$次位操作内运行，并需要$O((\log p)^2)$的存储空间。 这与计算非平凡超奇异自同态的最佳条件性算法的时间和存储复杂度相匹配，例如 Eisenträger-Hallgren-Leonardi-Morrison-Park 和 Delfs-Galbraith 提出的那些算法。 与这些先前的算法不同，这些算法需要两条从$E$到定义在$\mathbb F_p$上的曲线的路径，我们引入的算法只需要一条；因此，当与 Corte-Real Santos-Costello-Shi 的算法结合时，我们的算法在实际应用中会更快。 此外，我们的算法生成具有可预测判别式的自同态，使我们能够证明它们所生成的阶的性质。 通过两次调用我们的算法，我们可以有效地计算出$\operatorname{End}(E)$的 Bass 子阶。 在此基础上，假设广义黎曼猜想 (GRH) 成立，该结果被用于一个算法，用于计算基底 $\operatorname{End}(E)$，且具有相同的时间复杂度。 我们还论证了，基于关于这些自同态判别式分布的一个启发式假设，在条件 GRH 下，$\operatorname{End}(E)$可以通过调用我们的算法 $O(1)$次以及多项式开销来计算。 在假设 GRH 和这一附加启发式假设的条件下，这将得到一个计算 $\operatorname{End}(E)$的 $O(p^{1/2}(\log p)^2(\log\log p)^3)$算法，所需的存储量为 $O((\log p)^2)$。 显示英文摘要

摘要： We give an algorithm for computing an inseparable endomorphism of a supersingular elliptic curve $E$ defined over $\mathbb F_{p^2}$, which, conditional on GRH, runs in expected $O(p^{1/2}(\log p)^2(\log\log p)^3)$ bit operations and requires $O((\log p)^2)$ storage. This matches the time and storage complexity of the best conditional algorithms for computing a nontrivial supersingular endomorphism, such as those of Eisentr\"{a}ger-Hallgren-Leonardi-Morrison-Park and Delfs-Galbraith. Unlike these prior algorithms, which require two paths from $E$ to a curve defined over $\mathbb F_p$, the algorithm we introduce only requires one; thus when combined with the algorithm of Corte-Real Santos-Costello-Shi, our algorithm will be faster in practice. Moreover, our algorithm produces endomorphisms with predictable discriminants, enabling us to prove properties about the orders they generate. With two calls to our algorithm, we can provably compute a Bass suborder of $\operatorname{End}(E)$. This result is then used in an algorithm for computing a basis for $\operatorname{End}(E)$ with the same time complexity, assuming GRH. We also argue that $\operatorname{End}(E)$ can be computed using $O(1)$ calls to our algorithm along with polynomial overhead, conditional on a heuristic assumption about the distribution of the discriminants of these endomorphisms. Conditional on GRH and this additional heuristic, this yields a $O(p^{1/2}(\log p)^2(\log\log p)^3)$ algorithm for computing $\operatorname{End}(E)$ requiring $O((\log p)^2)$ storage.