Computing Isomorphisms between Products of Supersingular Elliptic Curves
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915217447845888 |
|---|---|
| author | Gaudry, Pierrick Soumier, Julien Spaenlehauer, Pierre-Jean |
| author_facet | Gaudry, Pierrick Soumier, Julien Spaenlehauer, Pierre-Jean |
| contents | The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop $\ell$-adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. Under GRH, it is proved to run in expected polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21535 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing Isomorphisms between Products of Supersingular Elliptic Curves Gaudry, Pierrick Soumier, Julien Spaenlehauer, Pierre-Jean Number Theory Cryptography and Security Symbolic Computation The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop $\ell$-adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. Under GRH, it is proved to run in expected polynomial time. |
| title | Computing Isomorphisms between Products of Supersingular Elliptic Curves |
| topic | Number Theory Cryptography and Security Symbolic Computation |
| url | https://arxiv.org/abs/2503.21535 |