The SEA algorithm for endomorphisms of supersingular elliptic curves

Abstract For a prime $$p{\,&gt;\,}3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mrow> <mml:mspace/> <mml:mo>&gt;</mml:mo> <mml:mspace/> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> and a supersingular elliptic curve E defined over $$\mathbb {F}_{p^2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:msup> <mml:mi>p</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:msub> </mml:math> with $${j(E)\notin \{0,1728\}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> <mml:mo>∉</mml:mo> <mml:mo>{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1728</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> , consider an endomorphism $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> of E represented as a composition of L isogenies of degree at most d and assume $$L\log d = O(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>log</mml:mo> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where $$n{\,=\,}\log (p)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow> <mml:mspace/> <mml:mo>=</mml:mo> <mml:mspace/> </mml:mrow> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We prove that the trace of $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> may be computed in $$O(n^4(\log n)^2 + dLn^3)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>4</mml:mn> </mml:msup> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>d</mml:mi> <mml:mi>L</mml:mi> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$d\in O(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> modulo p .