On completely factoring any integer efficiently in a single run of an order finding algorithm
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909217720369152 |
|---|---|
| author | Ekerå, Martin |
| author_facet | Ekerå, Martin |
| contents | We show that given the order of a single element selected uniformly at random from $\mathbb Z_N^*$, we can with very high probability, and for any integer $N$, efficiently find the complete factorization of $N$ in polynomial time. This implies that a single run of the quantum part of Shor's factoring algorithm is usually sufficient. All prime factors of $N$ can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_10044 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | On completely factoring any integer efficiently in a single run of an order finding algorithm Ekerå, Martin Quantum Physics Cryptography and Security Discrete Mathematics We show that given the order of a single element selected uniformly at random from $\mathbb Z_N^*$, we can with very high probability, and for any integer $N$, efficiently find the complete factorization of $N$ in polynomial time. This implies that a single run of the quantum part of Shor's factoring algorithm is usually sufficient. All prime factors of $N$ can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller. |
| title | On completely factoring any integer efficiently in a single run of an order finding algorithm |
| topic | Quantum Physics Cryptography and Security Discrete Mathematics |
| url | https://arxiv.org/abs/2007.10044 |