Analysis of RSA and Shor’s algorithm for cryptography: A quantum perspective
Abstract
The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
ML-KEM security relies on the Module Learning-with-Errors problem, for which there is no known polynomial-time quantum algorithm.
“its security relies on the Module Learningwith-Errors (M-LWE) problem, for which there is no known polynomial-time quantum algorithm [56,57].”
From A hybrid encryption algorithm based on AES and Kyber for secure image protection in the post-quantum era (2026) · cites this paper as [56]
Cites
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · see citing works
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738 · see citing works
Monte Carlo methods for index computation (𝑚𝑜𝑑𝑝)
Pollard, J. M. (1978) · Mathematics of Computation · doi:10.1090/s0025-5718-1978-0491431-9 · Cited by 825 · see citing works
Parallel Collision Search with Cryptanalytic Applications
van Oorschot, P. C., & Wiener, M. J. (1999) · Journal of Cryptology · doi:10.1007/pl00003816 · Cited by 639 · see citing works
The development of the number field sieve
Lenstra, A. K., Lenstra, H. W., Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993) · Lecture notes in mathematics · doi:10.1007/bfb0091534 · Cited by 575 · see citing works
Realization of a scalable Shor algorithm
Monz, T., Nigg, D., Martinez, E. A., Brandl, M. F., Schindler, P., Rines, R., Wang, S. X., Chuang, I. L., & Blatt, R. (2016) · Science · doi:10.1126/science.aad9480 · Cited by 486 · see citing works
The Quadratic Sieve Factoring Algorithm
Pomerance, C. B. (2007) · Springer eBooks · doi:10.1007/3-540-39757-4_17 · Cited by 204 · see citing works
The multiple polynomial quadratic sieve
Silverman, R. D. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866119-8 · Cited by 150 · see citing works
Kangaroos, Monopoly and Discrete Logarithms
Pollard, J. M. (2000) · Journal of Cryptology · doi:10.1007/s001450010010 · Cited by 143 · see citing works
Lenstra, A. K., & Manasse, M. S. (2007) · Springer eBooks · doi:10.1007/3-540-46885-4_35 · Cited by 108 · see citing works
The magic words are squeamish ossifrage
Atkins, D., Graff, M., Lenstra, A. K., & Leyland, P. C. (1995) · Lecture notes in computer science · doi:10.1007/bfb0000440 · Cited by 93 · see citing works
Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment
Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., & Zimmermann, P. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-56880-1_3 · Cited by 71 · see citing works
A Kilobit Special Number Field Sieve Factorization
Aoki, K., Frankē, J., Kleinjung, T., Lenstra, A. K., & Osvik, D. A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-76900-2_1 · Cited by 53 · see citing works
It's About the Gateway Courses: Defining and Contextualizing the Issue
Koch, A. K. (2017) · New Directions for Higher Education · doi:10.1002/he.20257 · Cited by 53 · see citing works
An overview of Quantum Cryptography and Shor’s Algorithm
(2020) · International Journal of Advanced Trends in Computer Science and Engineering · doi:10.30534/ijatcse/2020/214952020 · Cited by 51 · see citing works
Sihotang, H. T., Efendi, S., Zamzami, E. M., & Mawengkang, H. (2020) · Journal of Physics Conference Series · doi:10.1088/1742-6596/1641/1/012042 · Cited by 43 · see citing works
The Odyssey of Entropy: Cryptography
Zolfaghari, B., Bibak, K., & Koshiba, T. (2022) · Entropy · doi:10.3390/e24020266 · Cited by 41 · see citing works
A Kilobit Hidden SNFS Discrete Logarithm Computation
Fried, J., Gaudry, P., Heninger, N., & Thomé, E. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56620-7_8 · Cited by 37 · see citing works
New Cryptanalytic Attack on RSA Modulus N = pq Using Small Prime Difference Method
Ariffin, M. R. K., Abubakar, S. I., Yunos, F., & Asbullah, M. A. (2018) · Cryptography · doi:10.3390/cryptography3010002 · Cited by 26 · see citing works
Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computerPreprint
Dash, A., Sarmah, D., Behera, B. K., & Panigrahi, P. K. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10478 · Cited by 26 · see citing works
A formal proof of countermeasures against fault injection attacks on CRT-RSA
Rauzy, P., & Guilley, S. (2013) · Journal of Cryptographic Engineering · doi:10.1007/s13389-013-0065-3 · Cited by 24 · see citing works
Improved RSA cryptosystem based on the study of number theory and public key cryptosystems
Jahan, I., Asif, M., & Rozario, L. J. (2015) · Cited by 22 · see citing works
The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
Aono, Y., Liu, S., Tanaka, T., Uno, S., Meter, R. V., Shinohara, N., & Nojima, R. (2022) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2022.3183385 · Cited by 12 · see citing works
Small Private Exponent Attacks on RSA Using Continued Fractions and Multicore Systems
Bahig, H. M., Nassr, D. I., Mahdi, M. A., & Bahig, H. M. (2022) · Symmetry · doi:10.3390/sym14091897 · Cited by 10 · see citing works
Performance Analysis of Fermat Factorization Algorithms
Bahig, H. M., Mohammed, A., Khaled, A., AlGhadhban, A., & Hatem, M. (2020) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2020.0111242 · Cited by 10 · see citing works
The Improvement of Elliptic Curve Factorization Method to Recover RSA’s Prime Factors
Somsuk, K. (2021) · Symmetry · doi:10.3390/sym13081314 · Cited by 9 · see citing works
Research on the Security of Elliptic Curve Cryptography
Bao, J. (2022) · Advances in economics, business and management research/Advances in Economics, Business and Management Research · doi:10.2991/aebmr.k.220405.164 · Cited by 9 · see citing works
Pollard RHO Algorithm for Integer Factorization and Discrete Logarithm Problem
Hegde, N. P., & Deepthi, P. (2015) · International Journal of Computer Applications · doi:10.5120/21639-4969 · Cited by 9 · see citing works
Factoring RSA Moduli with Weak Prime Factors
Nitaj, A., & Rachidi, T. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-18681-8_29 · Cited by 7 · see citing works
Sarkar, S., & Maitra, S. (2009) · Bulletin of the Korean Mathematical Society · doi:10.4134/bkms.2009.46.4.721 · Cited by 7 · see citing works
Partial Key Attack Given MSBs of CRT-RSA Private Keys
Ghafar, A. H. A., Ariffin, M. R. K., Yasin, S. M., & Sapar, S. H. (2020) · Mathematics · doi:10.3390/math8122188 · Cited by 6 · see citing works
Baby-step giant-step algorithms for the symmetric group
Bach, E., & Sandlund, B. (2017) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2017.07.003 · Cited by 2 · see citing works
Cryptanalytic attacks on RSA algorithm and its variants
Savic, D. A. (2022) · PRZEGLĄD ELEKTROTECHNICZNY · doi:10.15199/48.2022.02.04 · Cited by 2 · see citing works
Overview of Improvements and Modifications in RSA Algorithm
Prajapati, K. S., & Buddhdev, B. V. (2014) · Journal of Emerging Technologies and Innovative Research · Cited by 1 · see citing works
Outsourcing decryption of KP-ABE using elliptic curve cryptography
Kumar, M., & Kumar, D. (2022) · International Journal of Information and Computer Security · doi:10.1504/ijics.2022.10046937 · Cited by 1 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Moccia, F. A. A., Domínguez, E. R., Gatica, G., Guerra-Tamara, B., Vidal, G. H., Rozo, J. M. K., Romero-Conrado, A. R., & Coronado-Hernández, J. R. (2025) · Procedia Computer Science · doi:10.1016/j.procs.2025.07.238 · Cited by 10 · see citing works
Singh, P., Hasija, T., Ramkumar, K. R., & Kanika (2026) · Discover Computing · doi:10.1007/s10791-026-10577-0
Kalinaki, K., Malik, O. A., Alfarisy, G. A. F., & Nassanga, J. (2025) · IGI Global eBooks · doi:10.4018/979-8-3693-8876-1.ch008
Coherence and decoherence in generalized Shor’s algorithm
叶, L. 琳. Y., Wu, Z., & 周, N. 南. Z. (2026) · Chinese Physics B · doi:10.1088/1674-1056/ae445e
Three party quantum key distribution using bilocality
Kumar, M., & Mondal, B. (2025) · Optical and Quantum Electronics · doi:10.1007/s11082-025-08612-3
- Authors
- Kute, S., Desai, C., & Jadhav, M.
- Affiliations
- Dr. Babasaheb Ambedkar Marathwada University (IN)
- National Defence Academy (IN)
- Shri Shivaji Science and Arts College, Chikhli (IN)
- Corresponding author
- Kute, Seema
- Venue
- AIP Conference Proceedings
- Publisher
- AIP Publishing
- Published
- 2024
- Volume
- 3222
- Pages
- 040004
- ISSN
- 0094-243X (ISSN-L)
- OpenAlex
- W4403295992
- Cited by
- 5
- References
- 35
- Citations by year
- 2026: 2 · 2025: 3
- FWCI
- 1.44
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- AIP conference proceedings (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- Shor's algorithm, quantum computing, cryptography, integer factorization, quantum algorithms, public-key encryption
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
