Quantum Prime Factorization: A Novel Approach Based on Fermat’s Method

Julien Mellaerts · 2025

Read Quantum Prime Factorization: A Novel Approach Based on Fermat’s Method by Julien Mellaerts (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10041.txt.

Introduction

Julien Mellaerts presents a quantum route to factoring large odd numbers, built on Fermat's classic method. He first sharpens that method on paper, cutting its work fourfold. He then recasts the search as an optimization task fit for quantum annealers. With that setup he factored 8,689,739, which he reports as the largest number yet factored on a quantum device. The 2025 note is brief and aimed at readers who track quantum factoring.

Catalog record

CREATORJulien Mellaerts
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-10041

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Prime Factorization: A Novel Approach Based on Fermat’s Method Julien Mellaerts Abstract In this paper, we introduce a novel quantum algorithm for the factorization of composite odd numbers. This work makes two significant contributions. First, we present a new improvement to the classical Fermat’s method, fourfold reducing the computational complexity of factoring. Second, we reformulate Fermat’s factorization method as an optimization problem suitable for Quantum Annealers which allowed us to factorize 8,689,739, the biggest number ever factorized using a quantum device to our knowledge. 1 Introduction The integer factorization problem, which involves finding the prime factors of a composite number, is a cornerstone of modern cryptography. This problem is particularly significant in the context of RSA encryption ( Rivest et al. 1978 ) , a widely used public-key cryptosystem that relies on the difficulty of factoring large integers into their prime components. In RSA, the security is predicated on the assumption that, given a large composite number N , which is the product of two large prime numbers p and q , it is computationally difficult to determine p and q using classical computing methods. This assumption underpins the security of countless secure communications and data transmissions worldwide. The advent of quantum computing has introduced new paradigms for solving complex computational problems, including integer factorization. Among the most notable quantum algorithms is Shor’s algorithm ( Shor 1997 ) , developed by Peter Shor in 1994. Shor’s algorithm leverages the principles of quantum mechanics to factor large integers in polynomial time, offering an exponential speedup over the best-known classical algorithms such as the General Number Field Sieve ( Lenstra et al. 1990 ) . This capability poses a significant threat to RSA encryption, as it could potentially render current cryptographic methods obsolete if large-scale, fault-tolerant quantum computers become a reality. In addition to Shor’s algorithm, other quantum approaches have been explored for integer factorization, including those based on quantum annealing ( Jiang et al. 2018 ; Ding et al. 2024 ) . Quantum annealing is a metaheuristic for finding the global minimum of an optimization problem and has been implemented in devices like the D-Wave quantum computer. Classically, Fermat’s factorization method is a well-known technique for factoring composite odd integers. It is based on the representation of an odd integer N as a difference of two squares. While Fermat’s method is elegant and straightforward, it is not efficient for very large numbers, which limits its practical application in modern cryptography. This paper first review classical Fermat’s method for factorization and propose an improvement fourfold reducing the number of iterations, secondly, it reformulates it as a combinatorial optimization problem suitable for quantum annealers. Instead of directly looking for p and q such that N=p\cdot q like in previous work, where the multiplication increases the number of variables because of carries encoding and degree reduction, the Fermat’s method reduces the problem as a difference of two squares, avoiding ancillary variables. By leveraging the capabilities of quantum annealing, this idea aims to shift the complexity from iteration count of the classical Fermat’s method to variable count to enhance the efficiency and scalability of Fermat’s method. 2 Fermat’s Method 2.1 Initial Fermat’s Formulation Fermat’s factorization method is based on the fact that any composite odd integer N can be represented as the difference of two squares: N=x^{2}-y^{2}=(x-y)(x+y) Where N=p\cdot q for two primes p and q , and x=\frac{p+q}{2},\quad y=\frac{p-q}{2} The purpose of the algorithm is to search for integers x and y such that x^{2}-N=y^{2} is a perfect square, it proceeds by starting with x=\lceil\sqrt{N}\rceil and incrementing x by one until x^{2}-N is a perfect square. Once x and y are known, p and q can be computed as p=x+y,\quad q=x-y From Fermat’s method, we know that the lower bound of x is x_{min}=\lceil\sqrt{N}\rceil , and the upper bound of x is x_{max}=\frac{N+\delta_{min}^{2}}{2\delta_{min}} where \delta_{min} is the minimal prime factor. Theoretically, we have \delta_{min}=3 , as 3 is the smallest possible prime, thus the theoretical upper bound of x is \frac{N+9}{6} . Considering the case of RSA prime factorization, it does not make sense to suppose the smallest possible prime to be 3, as recommendations are, given N a composite odd number of bitlength n , p and q should have n/2 bitlength. We can then consider without loss of generality that \delta_{min}=2^{n/2-1}+1 (as it must be odd). The lower bound of y is y_{min}=0 , the upper bound of y , y_{max} can be deducted from x_{max} : y_{max}=\sqrt{x_{max}^{2}-N} 2.2 Fermat’s Method Improvements Since its initial formulation by Fermat, in a letter to Mersenne around 1643, several improvements have been made, based on different concepts such that replacing the high-cost operation (the perfect square in Fermat’s method), with a low-cost operation, or reducing the search space to find the solution. The first most significant improvement used in this work is from Xiang ( Xiang 2004 ) , where he notices that we can deduce the parity of x^{2} depending on the form of the composite odd integer N . Indeed, if N is odd we have: N\equiv\pm 1\mod 4 (1) And for any integer n we know that: \forall n\in\mathbb{N}\left\{\begin{array}[]{ll}even\Leftrightarrow n^{2}\equiv 0\mod 4\\ odd\Leftrightarrow n^{2}\equiv 1\mod 4\end{array}\right. (2) Let N be an odd composite, from Fermat’s method we have: \exists x,y\in\mathbb{N}:N=x^{2}-y^{2} . Using (1) and by exhaustion: {unenumerate} [1.] If N\equiv 1\mod 4 , x^{2}-y^{2}\equiv 1\mod 4 , and by (2) \left\{\begin{array}[]{ll}\text{x is odd}\\ \text{y is even}\end{array}\right. If N\equiv-1\mod 4 , x^{2}-y^{2}\equiv-1\mod 4 , and by (2) \left\{\begin{array}[]{ll}\text{x is even}\\ \text{y is odd}\end{array}\right. Therefore, instead of increasing by one at each iteration, we can increase by two to look for either odd or even perfect square depending on the residue of N\mod 4 , halving the number of iterations. An other improvement used in this work is from Somsuk et al. ( Kasemvilas 2014 ) , considering that for any prime number p>3 , p\equiv\pm 1\mod 6 . Let N=p\cdot q , where p,q>3 both primes, we have: {unenumerate} [1.] If p\equiv\pm 1\mod 6 and q\equiv\pm 1\mod 6 , then N=p\cdot q\equiv 1\mod 6 , and p+q\equiv\pm 2\mod 6 If p\equiv\pm 1\mod 6 and q\equiv\mp 1\mod 6 , then N=p\cdot q\equiv-1\mod 6 , and p+q\equiv 0\mod 6 Therefore, the incrementing step of x can be conditioned by the residue of N\ mod6 . 3 Proposed Fermat’s Method Improvement We have previously seen that, given N an odd composite integer we have N\equiv\pm 1\mod 4 . The proposed improvement considers k\mod 2 as conditions to reduce the number of iterations, where: k\in\mathbb{N}\left\{\begin{array}[]{ll}k=\frac{N+1}{4}\text{ if }N\equiv-1\mod 4\\ k=\frac{N-1}{4}\text{ if }N\equiv 1\mod 4\end{array}\right. Case of N\equiv-1\mod 4 for any integer n we know that: \forall n\in\mathbb{N}\left\{\begin{array}[]{ll}\text{even}\Leftrightarrow n^{2}\mod 8\in\{0,4\}\\ \text{odd}\Leftrightarrow n^{2}\mod 8\in\{1\}\end{array}\right. (3) If N\equiv-1\mod 4 we have: N\mod 8\in\{3,7\} (4) From Fermat’s method, we know that \exists x,y\in\mathbb{N}:N=x^{2}-y^{2} , so we can write: (x^{2}\mod 8)-(y^{2}\mod 8)=(7-4\cdot(k\mod 2))\mod 8 Since x^{2} is even and y^{2} is odd, from (3) we know that y^{2}\equiv 1\mod 8 : (x^{2}\mod 8)-(1\mod 8)=(7-4\cdot(k\mod 2))\mod 8 (x^{2}\mod 8)=((7-4\cdot(k\mod 2))\mod 8)+(1\mod 8) We can see that we can consider only even perfect squares that comply with the residue of N\mod 8 conditioned by k\mod 2 , which fourfold reduces the overall number of

Read the complete text