Upper bounding the quantum space complexity for computing class group and principal ideal problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909207729537024 |
|---|---|
| author | Ng, Iu-Iong |
| author_facet | Ng, Iu-Iong |
| contents | In this paper, we calculate the upper bound on quantum space complexity of the quantum algorithms proposed by Biasse and Song (SODA'16) for solving class group computation and the principal ideal problem using the reductions to $S$-unit group computation. We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23) and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisenträger, Hallgren, Kitaev, and Song (STOC'14). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12508 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Upper bounding the quantum space complexity for computing class group and principal ideal problem Ng, Iu-Iong Quantum Physics In this paper, we calculate the upper bound on quantum space complexity of the quantum algorithms proposed by Biasse and Song (SODA'16) for solving class group computation and the principal ideal problem using the reductions to $S$-unit group computation. We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23) and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisenträger, Hallgren, Kitaev, and Song (STOC'14). |
| title | Upper bounding the quantum space complexity for computing class group and principal ideal problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2405.12508 |