Computing modular polynomials by deformation
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911986693963776 |
|---|---|
| author | Kunzweiler, Sabrina Robert, Damien |
| author_facet | Kunzweiler, Sabrina Robert, Damien |
| contents | We present an unconditional CRT algorithm to compute the modular polynomial $Φ_\ell(X,Y)$ in quasi-linear time. The main ingredients of our algorithm are: the embedding of $\ell$-isogenies in smooth-degree isogenies in higher dimension, and the computation of $m$-th order deformations of isogenies. We provide a proof-of-concept implementation of a heuristic version of the algorithm demonstrating the practicality of our approach.
Our algorithm can also be used to compute the reduction of $Φ_{\ell}$ modulo $p$ in quasi-linear time (with respect to $\ell$) $\tilde{O}(\ell^2(\log p + \log \ell)^{\mathfrak{O}})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06990 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing modular polynomials by deformation Kunzweiler, Sabrina Robert, Damien Number Theory 11Y16 (Primary), 11G07, 11G10, 14B12 (Secondary) We present an unconditional CRT algorithm to compute the modular polynomial $Φ_\ell(X,Y)$ in quasi-linear time. The main ingredients of our algorithm are: the embedding of $\ell$-isogenies in smooth-degree isogenies in higher dimension, and the computation of $m$-th order deformations of isogenies. We provide a proof-of-concept implementation of a heuristic version of the algorithm demonstrating the practicality of our approach. Our algorithm can also be used to compute the reduction of $Φ_{\ell}$ modulo $p$ in quasi-linear time (with respect to $\ell$) $\tilde{O}(\ell^2(\log p + \log \ell)^{\mathfrak{O}})$. |
| title | Computing modular polynomials by deformation |
| topic | Number Theory 11Y16 (Primary), 11G07, 11G10, 14B12 (Secondary) |
| url | https://arxiv.org/abs/2408.06990 |