The availability of working quantum computers has led to several proposals and claims of quantum advantage. In 2023, this has included claims that quantum computers can successfully factor large integers, by optimizing the search for nearby integers whose prime factors are all small. This paper demonstrates that the hope of factoring numbers of commercial significance using these methods is unfounded. Mathematically, this is because the density of smooth numbers (numbers all of whose prime factors are small) decays exponentially as n grows. Our experimental reproductions and analysis show that lattice-based factoring does not scale successfully to larger numbers, that the proposed quantum enhancements do not alter this conclusion, and that other simpler classical optimization heuristics perform much better for lattice-based factoring. However, many topics in this area have interesting applications and mathematical challenges, independently of factoring itself. We consider particular cases of the CVP, and opportunities for applying quantum techniques to other parts of the factorization pipeline, including the solution of linear equations modulo 2. Though the goal of factoring 1000-bit numbers is still out-of-reach, the combinatoric landscape is promising, and warrants further research with more circumspect objectives.
The availability of working quantum computers has led to several proposals and claims of quantum advantage. In 2023, this has included claims that quantum computers can successfully factor large integers, by optimizing the search for nearby integers whose prime factors are all small. This paper demonstrates that the hope of factoring numbers of commercial significance using these methods is unfounded. Mathematically, this is because the density of smooth numbers (numbers all of whose prime factors are small) decays exponentially as n grows. Our experimental reproductions and analysis show that lattice-based factoring does not scale successfully to larger numbers, that the proposed quantum enhancements do not alter this conclusion, and that other simpler classical optimization heuristics perform much better for lattice-based factoring. However, many topics in this area have interesting applications and mathematical challenges, independently of factoring itself. We consider particular cases of the CVP, and opportunities for applying quantum techniques to other parts of the factorization pipeline, including the solution of linear equations modulo 2. Though the goal of factoring 1000-bit numbers is still out-of-reach, the combinatoric landscape is promising, and warrants further research with more circumspect objectives.
Quantum computing has the potential to revolutionize cryptography by breaking classical public-key cryptography schemes, such as RSA and Diffie-Hellman. However, breaking the widely used 2048-bit RSA using Shor's quantum factoring algorithm is expected to require millions of noisy physical qubits and is well beyond the capabilities of present day quantum computers. A recent proposal by Yan et. al. tries to improve the widely debated Schnorr's lattice-based integer factorization algorithm using a quantum optimizer (QAOA), and further claim that one can break RSA 2048 using only 372 qubits. In this work, we present an open-source implementation of the algorithm proposed by Yan et. al. and show that, even if we had a perfect quantum optimizer (instead of a heuristic like QAOA), the proposed claims don't hold true. Specifically, our implementation shows that the claimed sublinear lattice dimension for the Hybrid quantum+classical version of Schnorr's algorithm successfully factors integers only up to 70 bits and fails to find enough factoring relations for random 80 bit integers and beyond. We further hope that our implementation serves as a playground for the community to easily test other hybrid quantum + classical integer factorization algorithm ideas using lattice based reductions.
Integer factorization is a significant problem, with implications for the security of widely-used cryptographic schemes. No efficient classical algorithm for polynomial-time integer factorization has been found despite extensive research. Although Peter Shor's breakthrough quantum algorithm offers a viable solution, current limitations of noisy intermediate-scale quantum (NISQ) computers hinder its practical implementation. To address this, researchers have explored alternative methods for factorization suitable for NISQ devices. One such method is the Quantum Approximate Optimization Algorithm, which treats factoring as an optimization problem defined over binary bits, resulting in various problematic aspects. In this paper, we explore the Func-QAOA approach for factorization, which premises overcoming some of the limitations of previous approaches and allows the incorporation of more advanced factorization techniques. After reviewing the most promising quantum implementations for integer arithmetics, we present a few illustrative examples to demonstrate the efficacy of the Func-QAOA approach and discuss methods to reduce the search space to speed up the optimization process.
The twenty-first century has been the era of data. Algorithms are crucial in tasks ranging from simple document searches to complex batching and scheduling jobs. Optimization techniques are often applied to enhance algorithms and achieve better results. As Moore rightly predicted, the exponential increase in transistors has led to a point where classical computers can no longer solve specific problems within a human timeframe. This paved the way for the development of quantum computers, which utilize quantum phenomena to solve problems. Quantum optimization techniques and algorithms have been designed to leverage the quantum advantage for improved optimization. This research compares and presents the results of quantum optimization techniques applied to classic combinatorial algorithms.
There have been several efforts to apply quantum SAT solving methods to factor large integers. While these methods may provide insight into quantum SAT solving, to date they have not led to a convincing path to integer factorization that is competitive with the best known classical method, the Number Field Sieve. Many of the techniques tried involved directly encoding multiplication to SAT or an equivalent NP-hard problem and looking for satisfying assignments of the variables representing the prime factors. The main challenge in these cases is that, to compete with the Number Field Sieve, the quantum SAT solver would need to be superpolynomially faster than classical SAT solvers. In this paper 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 for smooth numbers, then our factoring algorithm is faster than the classical NFS.
The landscape of modern cryptography, traditionally anchored in the computational hardness of number-theoretic problems such as integer factorization and the discrete logarithm problem, faces an existential threat from the advent of quantum computing. Shor's algorithm, discovered in 1994, demonstrates the theoretical capability of a sufficiently powerful quantum computer to efficiently solve these problems, rendering widely used cryptographic schemes like RSA and Elliptic Curve Cryptography (ECC) insecure. This imminent threat necessitates a paradigm shift towards post-quantum cryptography (PQC), which aims to develop cryptographic algorithms resistant to both classical and quantum attacks. Among the various candidates for PQC, lattice-based cryptography has emerged as a particularly promising area. This paper provides a comprehensive overview of the transition from classical number theory-based cryptography to lattice-based schemes. We explore the fundamental mathematical principles underlying lattices, introduce key lattice problems such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE), and discuss their application in constructing quantum-resistant cryptographic primitives. Furthermore, we analyze the security, efficiency, and practical considerations of prominent lattice-based cryptosystems, highlighting their role in the ongoing NIST post-quantum cryptography standardization process. The paper concludes by discussing the challenges and future directions in the deployment and research of lattice-based cryptographic solutions.
The advent of large-scale quantum computers poses an existential threat to the security of current public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), which rely on the computational intractability of integer factorization and discrete logarithms. This paper explores lattice-based cryptography as a promising candidate for post-quantum security. We delve into the mathematical foundations of lattices, specifically focusing on hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE) problems, which are believed to remain intractable even for quantum computers. We provide a comprehensive review of prominent lattice-based constructions, including NTRU, Kyber, and Dilithium, highlighting their security proofs, efficiency considerations, and suitability for various cryptographic primitives such as public-key encryption, key-exchange mechanisms, and digital signatures. Furthermore, we discuss the challenges and opportunities associated with their deployment, including parameter selection, resistance to side-channel attacks, and integration into existing cryptographic infrastructures. By examining the theoretical underpinnings and practical implications, this work aims to solidify understanding of lattice-based methods as a robust and essential component of the cryptographic landscape in the quantum era, moving beyond the traditional RSA frontier.