Hybrid Number Field Sieve (NFS): Classical and Quantum approaches

Abstract or Introduction

The Number Field Sieve (NFS) is currently the best integer factoring algorithm for general RSA moduli on classical computers. While we know that Shor’s quantum algorithm solves the problem in quantum polynomial-time, the size of the fault-tolerant quantum computers needed for its concrete application seems currently beyond reach for the next decades. There are several bottlenecks in the NFS algorithm which are almost “combinatorial in nature” (for example the core of the sieving part). Several approaches have been proposed in order to mix quantum computing and classical computing for NFS. Among them, the work of Bernstein, Biasse and Mosca, implementing the quantum Grover’s search algorithm as a subroutine of classical NFS and more recently the work of Mosca et al. using speedup with a quantum SAT solver (and not requiring a fault-tolerant quantum computer). On the other hand, Jiang, Britt, Humble and Kais present an alternative way to solve the factorization problem using quantum annealers, a method which has a simplistic formalism and which uses laws of physics to express the factorization problem as an executable Ising model. In this work we have implemented a factorization example using quantum annealing formalism and the D-Wave annealing tools by introducing variable simplifications in order to reduce the number of qubits needed to perform the factorization. We compare at the low-level, combining number theory, quantum computing and algorithmic optimizations the aforementioned approaches.