The SEA algorithm for endomorphisms of supersingular elliptic curves

2025/01/27 by Morrison, Travis, Panny, Lorenz, Sotáková, Jana +1
#FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2501.16321

Abstract

For a prime p > 3 and a supersingular elliptic curve E defined over \mathbbF_p² with j(E)∉\0,1728\, consider an endomorphism α of E represented as a composition of L isogenies of degree at most d. We prove that the trace of α may be computed in O(n⁴(log n)² + dLn³) bit operations, where n = log(p), using a generalization of the SEA algorithm for computing the trace of the Frobenius endomorphism of an ordinary elliptic curve. When L∈ O(log p) and d∈ O(1), this complexity matches the heuristic complexity of the SEA algorithm. Our theorem is unconditional, unlike the complexity analysis of the SEA algorithm, since the kernel of an arbitrary isogeny of a supersingular elliptic curve is defined over an extension of constant degree, independent of p. We also provide practical speedups, including a fast algorithm to compute the trace of α modulo p.

Related

• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• The supersingular endomorphism ring problem given one endomorphism
• Endomorphism rings of supersingular elliptic curves over \mathbbF_p
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings