pith. sign in

arxiv: 2006.08444 · v2 · pith:FFNPHQJUnew · submitted 2020-06-15 · 💻 cs.CR · math.NT

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

Anas A. Abudaqa , Nujud Alyami , Mostefa Kara , Farid Binbeshr , Muhammad Imam , Amjad Abuhassan This is my paper

Pith reviewed 2026-05-24 14:38 UTC · model grok-4.3

classification 💻 cs.CR math.NT
keywords factoring algorithmsprimality testingquantum algorithmsShor's algorithmRSA cryptosystemclassical algorithmsperformance comparisontime complexity
0
0 comments X

The pith

Quantum factoring algorithms outperform classical ones while quantum primality testing shows no such advantage.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reviews and compares classical and quantum algorithms for factoring large numbers and testing primality. It applies them practically and finds that quantum methods like Shor's algorithm bring major speedups to factoring, which underpins RSA security. However, for checking if a number is prime, quantum approaches do not outperform classical ones in the same way. This matters because modern encryption relies on both generating primes and the hardness of factoring composites. The comparison highlights speed and accuracy tradeoffs across methods.

Core claim

While quantum factoring algorithms, particularly Shor's algorithm and its refinements, have introduced significant advancements over their classical counterparts, quantum primality testing algorithms have not demonstrated comparable advantages.

What carries the argument

Comprehensive review, classification, and performance comparison of classical and quantum factorization and primality testing algorithms, including time complexities and practical implementations.

If this is right

  • Shor's algorithm and its refinements provide significant advancements in factoring over classical methods.
  • Quantum primality testing algorithms do not show comparable advantages to their classical counterparts.
  • The comparison reveals specific speed/accuracy tradeoffs and time complexities for both factoring and primality testing.
  • Insights apply directly to the security assumptions in systems like RSA that depend on factoring difficulty.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Efforts to create quantum primality tests with advantages comparable to Shor's in factoring could change the balance between the two tasks.
  • Classical primality tests may stay dominant even as quantum hardware improves for other cryptographic problems.
  • Extending the performance comparison to newer quantum hardware could test whether implementation details alter the observed lack of advantage.

Load-bearing premise

That the specific algorithms selected for implementation and the metrics used in the performance comparison fairly represent the current state of both classical and quantum approaches without selection bias or implementation artifacts.

What would settle it

A demonstration of a quantum primality testing algorithm that significantly outperforms the best classical methods in speed or accuracy on large numbers would falsify the claim of no comparable advantage.

Figures

Figures reproduced from arXiv: 2006.08444 by Amjad Abuhassan, Anas A. Abudaqa, Farid Binbeshr, Mostefa Kara, Muhammad Imam, Nujud Alyami.

Figure 1
Figure 1. Figure 1: Five Primality Tests Comparison Java and Python Performance. Pre “J” means Java implementation, and “P” [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Three Primality Tests Comparison Java and Python Performance. Pre “J” means Java implementation, and “P” [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of Monto-Carlo randomized primality tests [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of Las-Vegas randomized primality tests (proth numbers as the inputs) [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Proth vs. Miller tests for composite numbers [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Lucas vs Pocklington when a prime factor [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Deterministic primality tests comparison (Fermat numbers as inputs). [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Naïve primality test behaviors (small to large numbers). [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Pepin vs Proth for testing Fermat numbers. [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Comparison of 3 deterministic primality tests (Mersenne numbers as inputs). [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Baillie vs the most efficient Monto-Carlo primality test (Miller-Rabin). [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Baillie vs the most efficient Las-Vegas primality test (Proth). [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Baillie vs the most efficient primality test for Fermat numbers (Pepin). [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Baillie vs the most efficient test for Mersenne numbers (Lucas-Lehmer). [PITH_FULL_IMAGE:figures/full_fig_p016_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Comparison of 5 primality testing algorithms (Two large Mersenne numbers as inputs). [PITH_FULL_IMAGE:figures/full_fig_p019_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Comparison of 5 primality testing algorithms (Two large Proth numbers as inputs). [PITH_FULL_IMAGE:figures/full_fig_p020_16.png] view at source ↗
read the original abstract

Many modern asymmetric encryption methods rely on prime numbers, as they have distinctive properties. For instance, the security of RSA cryptosystem relies on the computational difficulty of factoring a large composite number in its prime factors, a problem that remains challenging for classical computers but potentially solvable using quantum algorithms. On the other hand, generating large prime numbers is also challenging due to their irregular distribution among integers, necessitating the use of primality testing algorithms to verify candidate primes. In this paper, we intensively review and classify various classical and quantum algorithms for factorization and primality testing, highlighting their advantages, limitations, speed/accuracy tradeoffs, time complexities, along with a brief summary. Furthermore, we apply and compare these algorithms to gain practical insights and conduct a comprehensive performance comparison. The insights from this paper show that while quantum factoring algorithms, particularly Shor's algorithm and its refinements, have introduced significant advancements over their classical counterparts, quantum primality testing algorithms have not demonstrated comparable advantages.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript reviews and classifies classical and quantum algorithms for integer factorization and primality testing. It discusses advantages, limitations, speed/accuracy tradeoffs, and time complexities, provides brief summaries, and reports a performance comparison of selected algorithms. From this comparison the authors conclude that quantum factoring algorithms (particularly Shor's and refinements) have introduced significant advancements over classical methods, whereas quantum primality testing algorithms have not demonstrated comparable advantages.

Significance. If the performance comparison is adequately documented and free of selection or implementation artifacts, the survey would usefully distinguish the asymmetric impact of quantum methods on the two problems that underpin RSA security. The classification of complexities and tradeoffs could serve as a reference for the cryptography community.

major comments (1)
  1. [Abstract] Abstract (performance comparison paragraph): the central claim that quantum primality testing algorithms have not demonstrated comparable advantages rests on an empirical comparison, yet the text supplies no dataset sizes, selection criteria, metrics, error bars, or exclusion rules for the runs. This absence directly undermines support for the comparative conclusion.
minor comments (1)
  1. Ensure every algorithm discussed is accompanied by its original reference citation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and the opportunity to address the concern regarding documentation of the performance comparison. We respond to the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (performance comparison paragraph): the central claim that quantum primality testing algorithms have not demonstrated comparable advantages rests on an empirical comparison, yet the text supplies no dataset sizes, selection criteria, metrics, error bars, or exclusion rules for the runs. This absence directly undermines support for the comparative conclusion.

    Authors: We agree that the manuscript does not supply the requested details on the empirical comparison (dataset sizes, selection criteria, metrics, error bars, or exclusion rules). This omission weakens support for the central claim in the abstract. We will revise both the abstract and the performance comparison section to document these elements explicitly, including the range of integer sizes tested, how test cases were generated, the precise metrics recorded, variability across runs, and any filtering applied. This revision will be made in the next version of the manuscript. revision: yes

Circularity Check

0 steps flagged

Review paper with no derivations or fitted parameters; no circularity present

full rationale

This is a survey paper that reviews, classifies, and compares existing classical and quantum algorithms for factoring and primality testing. The abstract and structure indicate no original mathematical derivations, equations, or parameter-fitting steps. The central claim (quantum factoring advances vs. limited quantum primality gains) rests on literature summary and performance comparisons of known algorithms, not on any self-referential construction, self-citation chain, or renaming of results. No load-bearing steps reduce to the paper's own inputs by definition or construction. This matches the default expectation for non-derivational review papers.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a review paper; it introduces no free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5716 in / 1040 out tokens · 23375 ms · 2026-05-24T14:38:47.843428+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 1 internal anchor

  1. [1]

    A lightweight password-based authentication protocol using smart card

    Chenyu Wang, Ding Wang, Guoai Xu, and Yanhui Guo. A lightweight password-based authentication protocol using smart card. International Journal of Communication Systems, 30(16):e3336, 2017

    work page 2017

  2. [2]

    New directions in cryptography.IEEE transactions on Information Theory, 22(6):644–654, 1976

    Whitfield Diffie and Martin Hellman. New directions in cryptography.IEEE transactions on Information Theory, 22(6):644–654, 1976

    work page 1976

  3. [3]

    Primality testing and integer factorization in public-key cryptography

    Song Y Yan. Primality testing and integer factorization in public-key cryptography. 2009

    work page 2009

  4. [4]

    Fermat’s little theorem

    Ulrich Daepp and Pamela Gorkin. Fermat’s little theorem. In Reading, Writing, and Proving, pages 315–323. Springer, 2011

    work page 2011

  5. [5]

    Great Internet Mersenne Prime Search

    George Woltman, Luke Welsh, and Ernst Mayer. Great Internet Mersenne Prime Search. https://www. mersenne.org/, 2018. [Online; accessed 17-April-2020]

    work page 2018

  6. [6]

    A method for obtaining digital signatures and public-key cryptosystems

    Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978

    work page 1978

  7. [7]

    Elementary number theory: primes, congruences, and secrets: a computational approach

    William Stein. Elementary number theory: primes, congruences, and secrets: a computational approach. Springer Science & Business Media, 2008

    work page 2008

  8. [8]

    Mersenne and fermat numbers

    Raphael M Robinson. Mersenne and fermat numbers. Proceedings of the American Mathematical Society , 5(5):842–846, 1954

    work page 1954

  9. [9]

    Numerical verification of the ternary goldbach conjecture up to 8.875· 1030

    Harald A Helfgott and David J Platt. Numerical verification of the ternary goldbach conjecture up to 8.875· 1030. Experimental Mathematics, 22(4):406–409, 2013

    work page 2013

  10. [10]

    Elementary number theory

    David M Burton. Elementary number theory. Tata McGraw-Hill Education, 2006

    work page 2006

  11. [11]

    The so-called sieve of eratosthenes

    GA Miller. The so-called sieve of eratosthenes. Science, 68(1760):273–274, 1928

    work page 1928

  12. [12]

    Evaluation and comparison of two efficient probabilistic primality testing algorithms

    Louis Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoretical Computer Science, 12(1):97–108, 1980

    work page 1980

  13. [13]

    Four primality testing algorithms

    René Schoof. Four primality testing algorithms. arXiv preprint arXiv:0801.3840, 2008

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  14. [14]

    Three primality tests and maple implementation

    Renee Marie Canfield. Three primality tests and maple implementation. PhD thesis, University of Georgia, 2008

    work page 2008

  15. [15]

    Primality tests using algebraic groups

    Masanari Kida. Primality tests using algebraic groups. Experimental Mathematics, 13(4):421–427, 2004

    work page 2004

  16. [16]

    Randomized and deterministic primality testing

    Monica Perrenoud. Randomized and deterministic primality testing. Technical report, 2009

    work page 2009

  17. [17]

    Framework for evaluation and comparison of primality testing algorithms

    Cristina-Loredana Duta, Laura Gheorghe, and Nicolae Tapus. Framework for evaluation and comparison of primality testing algorithms. In 2015 20th International Conference on Control Systems and Computer Science, pages 483–490. IEEE, 2015

    work page 2015

  18. [18]

    A Verilog description and efficient hardware implementation of the Baillie-PSW primality test

    Yasaswy Kasarabada. A Verilog description and efficient hardware implementation of the Baillie-PSW primality test. PhD thesis, University of Cincinnati, 2016

    work page 2016

  19. [19]

    Hardware implementation of the baillie-psw primality test

    Carla Purdy, Yasaswy Kasarabada, and George Purdy. Hardware implementation of the baillie-psw primality test. In 2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS), pages 651–654. IEEE, 2017

    work page 2017

  20. [20]

    Fermat’s theorem and its generalization by euler

    T Nagell. Fermat’s theorem and its generalization by euler. Introduction to Number Theory, Wiley, NY, pages 71–73, 1951

    work page 1951

  21. [21]

    Pseudoprime statistics to 1019

    Jens Kruse Andersen and Harvey Dubner. Pseudoprime statistics to 1019. Experimental Mathematics, 16(2):209– 213, 2007

    work page 2007

  22. [22]

    On composite numbers p which satisfy the fermat congruence ap−1≡ 1modp

    Robert D Carmichael. On composite numbers p which satisfy the fermat congruence ap−1≡ 1modp. The American Mathematical Monthly, 19(2):22–27, 1912

    work page 1912

  23. [23]

    There are infinitely many carmichael numbers.Annals of Mathematics, pages 703–722, 1994

    William R Alford, Andrew Granville, and Carl Pomerance. There are infinitely many carmichael numbers.Annals of Mathematics, pages 703–722, 1994

    work page 1994

  24. [24]

    A fast monte-carlo test for primality.SIAM journal on Computing, 6(1):84–85, 1977

    Robert Solovay and V olker Strassen. A fast monte-carlo test for primality.SIAM journal on Computing, 6(1):84–85, 1977

    work page 1977

  25. [25]

    Riemann’s hypothesis and tests for primality

    Gary L Miller. Riemann’s hypothesis and tests for primality. Journal of computer and system sciences, 13(3):300– 317, 1976

    work page 1976

  26. [26]

    Probabilistic algorithm for testing primality

    Michael O Rabin. Probabilistic algorithm for testing primality. Journal of number theory, 12(1):128–138, 1980

    work page 1980

  27. [27]

    Sur la série des nombres premiers

    François Proth. Sur la série des nombres premiers. Nouvelle Correspondance Mathématique, 4:236–240, 1878. 17 A PREPRINT - J UNE 16, 2020

    work page 2020

  28. [28]

    A primality test for k p n + 1 numbers

    José Grau, Antonio Oller-Marcén, and Daniel Sadornil. A primality test for k p n + 1 numbers. Mathematics of Computation, 84(291):505–512, 2015

    work page 2015

  29. [29]

    The top twenty Proth numbers

    Caldwell Chris K. The top twenty Proth numbers . https://primes.utm.edu/top20/page.php?id=66,

    work page

  30. [30]

    [Online; accessed 5-June-2020]

    work page 2020

  31. [31]

    Lucas pseudoprimes

    Robert Baillie and Samuel S Wagstaff. Lucas pseudoprimes. Mathematics of Computation, 35(152):1391–1417, 1980

    work page 1980

  32. [32]

    The determination of the prime or composite nature of large numbers by fermat’s theorem

    Henry C Pocklington. The determination of the prime or composite nature of large numbers by fermat’s theorem. Proc. Cambridge Philosophical Society, 1914, 18:29–30, 1914

    work page 1914

  33. [33]

    Sur la formule 22n + 1

    Pe Pepin. Sur la formule 22n + 1. des seances de l’Academie des sciences, 85:329–331, 1877

    work page

  34. [34]

    Fermat and mersenne numbers in pepin’s test

    Alena Šolcová and Michał Kˇrižek. Fermat and mersenne numbers in pepin’s test. Demonstratio Mathematica, 39(4):737–742, 2006

    work page 2006

  35. [35]

    Tests for primality by the converse of fermat’s theorem.Bulletin of the American Mathematical Society, 33(3):327–340, 1927

    Derrick H Lehmer. Tests for primality by the converse of fermat’s theorem.Bulletin of the American Mathematical Society, 33(3):327–340, 1927

    work page 1927

  36. [36]

    Primes is in p

    Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in p. Annals of mathematics, pages 781–793, 2004

    work page 2004

  37. [37]

    Primality tests in polynomial time

    Alberto Bedodi and Francesco Pappalardi. Primality tests in polynomial time . PhD thesis, Master’s thesis, Universitá Degli Studi Roma TRE, 2010

    work page 2010

  38. [38]

    Baillie-psw primality test

    Eric W Weisstein. Baillie-psw primality test. 2004

    work page 2004

  39. [39]

    The baillie-psw primality test

    TR Nicely. The baillie-psw primality test. 2005

    work page 2005

  40. [40]

    Are there counter-examples to the baillie-psw primality test

    Carl Pomerance. Are there counter-examples to the baillie-psw primality test. Dopo Le Parole aangeboden aan Dr. AK Lenstra. Privately published Amsterdam, 1984

    work page 1984

  41. [41]

    Fermat primes: primes of the form 22k + 1 , for some k > = 0

    Neil James Sloane and David Wilson. Fermat primes: primes of the form 22k + 1 , for some k > = 0 . . http://oeis.org/A019434, 2010. [Online; accessed 2-June-2020]. A Appendix A Table 6: Two big Mersenne numbers. Number Value #-digits Type (21279− 1) 1040793219466439908192524032736408553861526224726670 4805319112350403608059673360298012239441732324184842 4...

    work page 2010