Advances in Factoring and Primality Testing: From Classical to Quantum Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909047784996864 |
|---|---|
| author | Abudaqa, Anas A. Alyami, Nujud Kara, Mostefa Binbeshr, Farid Imam, Muhammad Abuhassan, Amjad |
| author_facet | Abudaqa, Anas A. Alyami, Nujud Kara, Mostefa Binbeshr, Farid Imam, Muhammad Abuhassan, Amjad |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_08444 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Advances in Factoring and Primality Testing: From Classical to Quantum Algorithms Abudaqa, Anas A. Alyami, Nujud Kara, Mostefa Binbeshr, Farid Imam, Muhammad Abuhassan, Amjad Cryptography and Security Number Theory 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. |
| title | Advances in Factoring and Primality Testing: From Classical to Quantum Algorithms |
| topic | Cryptography and Security Number Theory |
| url | https://arxiv.org/abs/2006.08444 |