💻 computer science

Advances in Factoring and Primality Testing: From Classical to Quantum Algorithms

This paper provides a comprehensive review and comparative performance analysis of classical and quantum algorithms for factoring and primality testing, concluding that while quantum methods like Shor's algorithm offer significant advantages for factoring, they do not provide comparable benefits for primality testing.

Original authors: Anas A. Abudaqa, Nujud Alyami, Mostefa Kara, Farid Binbeshr, Muhammad Imam

Published 2026-07-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anas A. Abudaqa, Nujud Alyami, Mostefa Kara, Farid Binbeshr, Muhammad Imam

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the digital world as a massive, bustling city where every secret message, bank transfer, and private photo is locked inside a steel vault. The keys to these vaults are made of numbers, specifically huge prime numbers—numbers that can only be divided evenly by 1 and themselves. For decades, the security of our entire internet has relied on a simple mathematical trick: it's incredibly easy to multiply two giant prime numbers together to make a huge, messy number, but it is nearly impossible to take that messy number apart and figure out which two primes created it. This "mathematical lock" is what keeps your online life safe.

However, a new kind of machine is being built: the quantum computer. Think of a classical computer as a detective who checks one clue at a time, walking down a long hallway of possibilities one by one. A quantum computer, on the other hand, is like a magical detective who can walk down every hallway in the building simultaneously. For a long time, scientists wondered if this super-detective could crack the prime number locks instantly. This paper is a deep dive into that question, exploring whether these new machines can break the locks (factoring) and how good they are at finding the right keys (primality testing) compared to our old, reliable tools.

The Great Lock-Picking Race: Classical vs. Quantum

This paper acts like a massive scoreboard and a rulebook for a race between old-school math methods and new-fangled quantum magic. The authors, a team of researchers from universities in Saudi Arabia and Algeria, gathered every known method for two specific tasks: Factoring (taking a big number apart into its prime pieces) and Primality Testing (checking if a number is a prime to begin with).

When it comes to Factoring, the paper confirms that the quantum side is winning the race by a landslide. The star player here is Shor's Algorithm, a method discovered in 1994 that uses the quantum detective's ability to see all paths at once. The paper explains that while our best classical computers take thousands of years to break a large code, Shor's algorithm could theoretically do it in a matter of hours or days. But the story doesn't stop there. The authors highlight that scientists are constantly tweaking Shor's algorithm to make it more efficient. They are trying to shrink the size of the "quantum machine" needed, reducing the number of tiny components (called qubits) required. For instance, recent improvements suggest that with clever tricks like "multimode memory," we might be able to break a 2048-bit RSA key (a standard internet lock) using only about 13,436 physical qubits, a number much smaller than earlier estimates. The paper also introduces newer contenders like Regev's algorithm, which uses a different mathematical approach to potentially use even fewer resources, though it relies on some mathematical assumptions that are still being tested.

However, the plot takes a twist when we switch to Primality Testing. You might think that if quantum computers are so good at breaking numbers apart, they would also be amazing at checking if a number is prime. But the paper finds the opposite to be true. In the world of checking for primes, the classical methods are still the champions. The authors review various quantum methods designed to test primality, such as the Chau and Lo algorithm or the Dos Santos and Maziero algorithm, and they conclude that these quantum approaches haven't shown any real advantage over the classical ones we already use. In fact, the classical methods are often faster, simpler, and just as accurate. The paper notes that even the discovery of the world's largest known prime number in 2024 was done using classical methods on a network of regular computers, not a quantum one.

The Verdict: A Tale of Two Worlds

So, what is the final score? The paper draws a clear line in the sand. If you are trying to break a code (factoring), quantum computers are the future, and they are getting closer to being able to crack the codes that protect our banks and emails today. The authors suggest that we are approaching a "break-even point" where a quantum machine could outperform the best supercomputers, potentially threatening the security of current internet encryption within the next decade or so.

But if you are trying to build a code (finding a prime number to make a new key), you don't need to worry about quantum computers just yet. The classical tools are still the best in the business. The paper explicitly rules out the idea that quantum computers offer a speed boost for finding primes; in this specific job, the old ways are still the most efficient.

The authors wrap up by saying that while the quantum revolution in breaking codes is real and exciting, it's not a magic wand that solves everything. We are in a transition period where we need to prepare for the day when quantum machines can break our locks, but for now, the classical methods for checking if a number is prime remain the gold standard. The future of cryptography, they suggest, will likely involve a mix of new quantum-resistant locks and a continued reliance on the proven, classical methods for generating the keys.

Technical Summary: Advances in Factoring and Primality Testing: From Classical to Quantum Algorithms

Problem Statement
The paper addresses two fundamental problems in computational number theory with critical implications for modern cryptography: integer factorization and primality testing. The security of widely used asymmetric encryption systems, such as RSA, relies on the computational asymmetry between the ease of multiplying large primes and the extreme difficulty of factoring the resulting composite numbers. While classical algorithms for factoring operate in sub-exponential time, rendering large integers (e.g., RSA-2048) secure against current classical supercomputers, the advent of quantum computing threatens this security model. Conversely, generating large primes for key generation requires efficient primality testing. The paper investigates the current state of both classical and quantum approaches to these problems, aiming to classify algorithms, analyze their trade-offs, and determine the extent of quantum advantage in each domain.

Methodology
The authors conducted a systematic review and classification of existing literature, categorizing algorithms into distinct taxonomies based on their operational principles (deterministic vs. randomized) and computational models (classical vs. quantum).

Classification: The study classifies 11 classical and 4 quantum primality testing algorithms, and 5 classical and multiple quantum factoring algorithms.
Theoretical Analysis: The authors analyze the time complexity, resource requirements (qubit counts, gate depth), and error probabilities of each algorithm. Special attention is paid to the transition from Shor's original framework to newer theoretical variants (e.g., Regev's algorithm) and alternative approaches (e.g., adiabatic computation, hidden subgroup generalizations).
Experimental Evaluation: To provide practical insights, the authors implemented 11 representative classical primality testing algorithms on a standard personal computer (Intel Core i7-2430M, 16 GB RAM). The experiments utilized integers up to 20 decimal digits, including general integers, Fermat numbers, Mersenne numbers, and Proth numbers, to measure execution times and compare scalability across deterministic, probabilistic, and heuristic methods.

Key Contributions

Novel Taxonomy: The paper presents a structured classification of primality testing algorithms into five categories: Randomized Monte-Carlo, Randomized Las-Vegas, Deterministic, Heuristic, and specialized tests for numbers with specific forms (Mersenne, Fermat, Proth).
Comprehensive Quantum Survey: It provides a detailed overview of quantum factoring beyond Shor's original algorithm, including theoretical refinements by Regev, Ragavan, Vaikuntanathan, and Ekerå, as well as alternative methods like Bernstein's sublinear qubit approach and Li's square-free decomposition.
Empirical Comparison: The paper offers a direct performance comparison of classical primality tests, highlighting that while probabilistic tests (Miller-Rabin, Baillie-PSW) are highly efficient for general use, specialized deterministic tests (Lucas-Lehmer, Pepin) remain superior for specific number forms.
Resource Estimation Analysis: The authors synthesize recent literature to estimate the physical resources (qubits and time) required to break RSA-2048, noting that hybrid architectures with multimode memory could potentially achieve this with approximately 13,436 physical qubits in 177 days.

Results

Primality Testing: The experimental results and theoretical analysis confirm that quantum primality testing algorithms have not demonstrated comparable advantages over classical counterparts. Classical algorithms, particularly the Baillie-PSW heuristic and the AKS deterministic test, remain computationally competitive and are sufficient for verifying large primes. The paper notes that the largest known prime (a Mersenne prime discovered in 2024) was found using classical methods (Lucas-Lehmer test) on distributed GPU networks.
Integer Factoring: In contrast, quantum factoring algorithms show significant advancement. Shor's algorithm reduces factoring complexity from sub-exponential to polynomial time $O((\log N)^3)$ . Recent theoretical variants, such as Regev's algorithm, further optimize gate counts to $\tilde{O}(n^{3/2})$ and reduce qubit requirements through space-time trade-offs.
Performance Trade-offs: The study highlights that while quantum factoring offers exponential speedup, it currently faces hardware limitations (NISQ era noise, coherence times). Conversely, classical factoring (GNFS) remains the state-of-the-art for large integers but is vulnerable to future large-scale quantum computers.
Break-even Points: The paper estimates that the "break-even" point for practical quantum cryptanalysis of RSA-2048 is approaching the $10^4$ qubit range, suggesting that RSA security margins may vanish as hardware scales.

Significance and Claims
The paper claims to fill a gap in the literature by providing a holistic review that bridges the theoretical advancements in quantum factoring with practical classical implementations. Its primary significance lies in the asymmetric conclusion regarding the two problems:

For Factoring: The transition to quantum computing poses an existential threat to current public-key cryptography. The paper emphasizes that while Shor's algorithm is the foundation, recent refinements (Regev, Ekerå, Gidney) are making the resource requirements for breaking RSA more concrete and potentially achievable sooner than previously estimated.
For Primality Testing: The paper asserts that the quantum advantage is not present in this domain. Classical methods remain the standard for generating and verifying primes, and quantum algorithms for primality testing (e.g., Chau-Lo, Donis-Vela) have not surpassed the efficiency of classical probabilistic or deterministic tests.

The authors conclude that while the field of quantum factoring is rapidly evolving toward practical deployment, the field of primality testing remains dominated by classical efficiency. Consequently, the immediate cryptographic imperative is the migration to Post-Quantum Cryptography (PQC) resistant to the Hidden Subgroup Problem, while the generation of keys can continue to rely on robust classical primality testing.

More like this