For a prime <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$p{\,>\,}3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mrow> <mspace width="0.166667em" /> <mo>></mo> <mspace width="0.166667em" /> </mrow> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and a supersingular elliptic curve E defined over <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathbb {F}_{p^2}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <msup> <mi>p</mi> <mn>2</mn> </msup> </msub> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${j(E)\notin \{0,1728\}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>j</mi> <mo stretchy="false">(</mo> <mi>E</mi> <mo stretchy="false">)</mo> <mo>∉</mo> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1728</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, consider an endomorphism <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> of E represented as a composition of L isogenies of degree at most d and assume <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$L\log d = O(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>log</mo> <mi>d</mi> <mo>=</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$n{\,=\,}\log (p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mrow> <mspace width="0.166667em" /> <mo>=</mo> <mspace width="0.166667em" /> </mrow> <mo>log</mo> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We prove that the trace of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> may be computed in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$O(n^4(\log n)^2 + dLn^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>4</mn> </msup> <msup> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>+</mo> <mi>d</mi> <mi>L</mi> <msup> <mi>n</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> bit operations, using a generalization of the SEA algorithm for computing the trace of the Frobenius endomorphism of an ordinary elliptic curve. When <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$L\in O(\log p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>∈</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$d\in O(1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>∈</mo> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> modulo p.

The SEA algorithm for endomorphisms of supersingular elliptic curves

期刊论文
出版模式：

开放获取
发表日期：

2026年6月17日

查看全文

Travis Morrison,
Lorenz Panny,
Jana Sotáková,
Michael Wills

摘要

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) \notin {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 \in O (log p)$ and $d\in O(1)$ $d \in 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.