Factoring semi-primes with (quantum) SAT-solvers
Abstract The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability probl...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2022-05-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-022-11687-7 |
| _version_ | 1811253217330200576 |
|---|---|
| author | Michele Mosca Sebastian R. Verschoor |
| author_facet | Michele Mosca Sebastian R. Verschoor |
| author_sort | Michele Mosca |
| collection | DOAJ |
| description | Abstract The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor’s quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor’s algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware. |
| first_indexed | 2024-04-12T16:47:32Z |
| format | Article |
| id | doaj.art-e8bccdc72c08431bba0b43d8d0091ba1 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-04-12T16:47:32Z |
| publishDate | 2022-05-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-e8bccdc72c08431bba0b43d8d0091ba12022-12-22T03:24:32ZengNature PortfolioScientific Reports2045-23222022-05-0112111210.1038/s41598-022-11687-7Factoring semi-primes with (quantum) SAT-solversMichele Mosca0Sebastian R. Verschoor1Institute for Quantum Computing, University of WaterlooInstitute for Quantum Computing, University of WaterlooAbstract The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor’s quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor’s algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.https://doi.org/10.1038/s41598-022-11687-7 |
| spellingShingle | Michele Mosca Sebastian R. Verschoor Factoring semi-primes with (quantum) SAT-solvers Scientific Reports |
| title | Factoring semi-primes with (quantum) SAT-solvers |
| title_full | Factoring semi-primes with (quantum) SAT-solvers |
| title_fullStr | Factoring semi-primes with (quantum) SAT-solvers |
| title_full_unstemmed | Factoring semi-primes with (quantum) SAT-solvers |
| title_short | Factoring semi-primes with (quantum) SAT-solvers |
| title_sort | factoring semi primes with quantum sat solvers |
| url | https://doi.org/10.1038/s41598-022-11687-7 |
| work_keys_str_mv | AT michelemosca factoringsemiprimeswithquantumsatsolvers AT sebastianrverschoor factoringsemiprimeswithquantumsatsolvers |