The SEA algorithm for endomorphisms of supersingular elliptic curves

Abstract For a prime $$p{\,>\,}3$$ p > 3 and a supersingular elliptic curve E defined over $$\mathbb {F}_{p^2}$$ F p 2 with $${j(E)\notin \{0,1728\}}$$ j ( E ) ∉ { 0 , 1728 } , consider an endomorphism $$\alpha $$ α of E represented as a composition of L isogenies of degree at most d and assume $$L\log d = O(n)$$ L log d = O ( n ) , where $$n{\,=\,}\log (p)$$ n = log ( p ) . We prove that the trace of $$\alpha $$ α may be computed in $$O(n^4(\log n)^2 + dLn^3)$$ O ( n 4 ( log n ) 2 + d L n 3 ) bit operations, using a generalization of the SEA algorithm for computing the trace of the Frobenius endomorphism of an ordinary elliptic curve. When $$L\in O(\log p)$$ L ∈ O ( log p ) and $$d\in O(1)$$ 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 $$\alpha $$ α modulo p .