Quantum Prime Factorization: A Novel Approach Based on Fermat Method

2025/08/11 by Mellaerts, Julien
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2508.10041

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 method, fourfold reducing the computational complexity of factoring. Second, we reformulate Fermat 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.

Citations

• Effective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding
• Quantum Annealing for Prime Factorization
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A method for obtaining digital signatures and public-key cryptosystems

Related

• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Quantum Annealing for Prime Factorization
• Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization
• Factoring semi-primes with (quantum) SAT-solvers
• Factorization of large tetra and penta prime numbers on IBM quantum processor