Factoring semi-primes with (quantum) SAT-solvers.

Area of Science:

• Cryptography
• Quantum Computing
• Computational Complexity

Background:

• The security of RSA public-key cryptography relies on the difficulty of factoring large integers.
• Classical factoring algorithms are sub-exponential, while Shor's quantum algorithm offers polynomial time factorization.
• Quantum computers capable of running Shor's algorithm are not yet available.

Purpose of the Study:

• To investigate the practicality of recent attempts to factor large integers using quantum reductions to NP-hard problems like Boolean Satisfiability (SAT).
• To assess the viability of these quantum approaches for practical integer factorization, even with advanced quantum hardware.

Main Methods:

• Analysis of quantum factoring algorithms reduced to NP-hard problems.
• Evaluation of the practicality of these reductions for large-scale integer factorization.
• Consideration of various quantum computing paradigms, including quantum annealing.

Main Results:

• No evidence found supporting the practicality of quantum reductions to NP-hard problems for factoring large integers.
• The studied quantum approaches are deemed unlikely to be viable paths for factoring, even for future fault-tolerant quantum computers.
• The findings question the efficacy of using SAT solvers or similar methods for quantum-based factorization.

Conclusions:

• The reduction of integer factorization to NP-hard problems for quantum computation is not a practical approach for breaking RSA cryptography.
• Further research is needed to explore alternative quantum algorithms or hardware for efficient integer factorization.
• Current quantum strategies targeting NP-hard problems do not offer a clear path to practical large-integer factorization.