Please note: This PhD seminar will be given online.
Sebastian
Verschoor, PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
The assumed computationally difficulty of factoring large integers forms the basis of security for RSA public-key cryptography, which specifically relies on products of two large primes or semi-primes. The best-known factoring algorithm for classical computers, the Number Field Sieve, runs in sub-exponential time. Since integer factorization is in NP, one can reduce this problem to any NP-hard problem, such as Boolean Satisfiability (SAT). While reducing factoring to SAT has proved to be useful for studying SAT solvers, attempting to factor large integers via such a reduction has not been found to be successful.
Shor’s quantum factoring algorithm factors any integer in polynomial time, although large-scale fault-tolerant quantum computers capable of implementing Shor’s algorithm are not yet available, so relevant benchmarking experiments for factoring via Shor’s algorithm are not yet possible. In recent years, however, several authors have attempted factorizations with the help of quantum processors via reductions to NP-hard problems. While this approach may shed some light on some algorithmic approaches for quantum solutions to NP-hard problems, in the first work we study and question the practical effectiveness of this approach for factoring large numbers. 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.
In the second work the use of SAT solvers is restricted to a smaller task related to factoring: finding smooth numbers, which is an essential step of the Number Field Sieve. We present a SAT circuit that can be given to quantum SAT solvers such as annealers in order to perform this step of factoring. If quantum SAT solvers achieve any asymptotic speedup over classical brute-force search, then our factoring algorithm is faster than the classical NFS.
To join this PhD seminar on Webex, please go to https://uwaterloo.webex.com/uwaterloo/j.php?MTID=mf9bac2e3feefac4f017eaee07809c8c2
Meeting
number
(access
code):
160
556
5877
Password:
yvGZePdM387