
handle: 11588/995159
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ä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.
32 pages, 2 figures. In v2, Section 4 of v1 has been incorporated into Section 3, while Section 5 of v1 has been split into Sections 4 and 5. Additionally, we have included an appendix in v2 containing technical details on the implementation of the algorithm discussed in Section 6
cryptography, Mathematics - Number Theory, Quaternion algebras, isogenies, quaternion algebras, 11Y16, 004, Curves over finite and local fields, Isogenies, Cryptography, FOS: Mathematics, [INFO]Computer Science [cs], Quaternion and other division algebras: arithmetic, zeta functions, supersingular elliptic curves, Number Theory (math.NT), [MATH]Mathematics [math], Cryptography; Isogenies; Quaternion algebras; Supersingular elliptic curves, Supersingular elliptic curves, Number-theoretic algorithms; complexity
cryptography, Mathematics - Number Theory, Quaternion algebras, isogenies, quaternion algebras, 11Y16, 004, Curves over finite and local fields, Isogenies, Cryptography, FOS: Mathematics, [INFO]Computer Science [cs], Quaternion and other division algebras: arithmetic, zeta functions, supersingular elliptic curves, Number Theory (math.NT), [MATH]Mathematics [math], Cryptography; Isogenies; Quaternion algebras; Supersingular elliptic curves, Supersingular elliptic curves, Number-theoretic algorithms; complexity
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
