This paper has been withdrawn by Anas Abudaqa

No PDF available, click to view other formats

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.

Submission history

From: Anas Abudaqa [view email]
[v1] Mon, 15 Jun 2020 14:40:50 UTC (403 KB)
[v2] Fri, 15 May 2026 21:46:19 UTC (92 KB)
[v3] Tue, 30 Jun 2026 15:16:33 UTC (1 KB) (withdrawn)