Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2011.05355 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911760468934656 |
|---|---|
| author | Bastos, Daniel Chicayban Kowada, Luis Antonio |
| author_facet | Bastos, Daniel Chicayban Kowada, Luis Antonio |
| contents | Pollard's Rho is a method for solving the integer factorization problem. The strategy searches for a suitable pair of elements belonging to a sequence of natural numbers that given suitable conditions yields a nontrivial factor. In translating the algorithm to a quantum model of computation, we found its running time reduces to polynomial-time using a certain set of functions for generating the sequence. We also arrived at a new result that characterizes the availability of nontrivial factors in the sequence. The result has led us to the realization that Pollard's Rho is a generalization of Shor's algorithm, a fact easily seen in the light of the new result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_05355 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case Bastos, Daniel Chicayban Kowada, Luis Antonio Quantum Physics Pollard's Rho is a method for solving the integer factorization problem. The strategy searches for a suitable pair of elements belonging to a sequence of natural numbers that given suitable conditions yields a nontrivial factor. In translating the algorithm to a quantum model of computation, we found its running time reduces to polynomial-time using a certain set of functions for generating the sequence. We also arrived at a new result that characterizes the availability of nontrivial factors in the sequence. The result has led us to the realization that Pollard's Rho is a generalization of Shor's algorithm, a fact easily seen in the light of the new result. |
| title | A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2011.05355 |