Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.16321 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913667095724032 |
|---|---|
| author | Morrison, Travis Panny, Lorenz Sotáková, Jana Wills, Michael |
| author_facet | Morrison, Travis Panny, Lorenz Sotáková, Jana Wills, Michael |
| contents | For a prime $p{\,>\,}3$ and a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ with ${j(E)\notin\{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^4(\log n)^2 + dLn^3)$ 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\in O(\log p)$ and $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 $α$ modulo $p$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16321 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The SEA algorithm for endomorphisms of supersingular elliptic curves Morrison, Travis Panny, Lorenz Sotáková, Jana Wills, Michael Number Theory For a prime $p{\,>\,}3$ and a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ with ${j(E)\notin\{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^4(\log n)^2 + dLn^3)$ 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\in O(\log p)$ and $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 $α$ modulo $p$. |
| title | The SEA algorithm for endomorphisms of supersingular elliptic curves |
| topic | Number Theory |
| url | https://arxiv.org/abs/2501.16321 |