Extending Regev's factoring algorithm to compute discrete logarithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916280664064000 |
|---|---|
| author | Ekerå, Martin Gärtner, Joel |
| author_facet | Ekerå, Martin Gärtner, Joel |
| contents | Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way. Furthermore, we discuss natural extensions of Regev's factoring algorithm to order finding, and to factoring completely via order finding. For all of these algorithms, we discuss various practical implementation considerations, including in particular the robustness of the post-processing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05545 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extending Regev's factoring algorithm to compute discrete logarithms Ekerå, Martin Gärtner, Joel Cryptography and Security Quantum Physics Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way. Furthermore, we discuss natural extensions of Regev's factoring algorithm to order finding, and to factoring completely via order finding. For all of these algorithms, we discuss various practical implementation considerations, including in particular the robustness of the post-processing. |
| title | Extending Regev's factoring algorithm to compute discrete logarithms |
| topic | Cryptography and Security Quantum Physics |
| url | https://arxiv.org/abs/2311.05545 |