Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the European Association for Theoretical Computer Science

Quantum Computing and the Hunt for Hidden Symmetry.

Gorjan Alagic, Alexander C. Russell

Published Jan 1, 2007• 1 citation
OpenAlex

Abstract

In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. 1

Related papers

Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem

JozsaRichard

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. In...

IEEE Multimedia•Mar 1, 1996•0 citations

Quantum factoring, discrete logarithms, and the hidden subgroup problem

Richard Jozsa

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.

arXiv:quant-ph/0012084•Computing in Science & Engineering•Jan 1, 2001•148 citations

An Exposition on Peter Shor's Polynomial-Time Factoring Algorithm and Its Effects on Post-Quantum Cryptography

Kristopher Lonnie Watkins

When building cryptosystems, cryptographers focus on finding problems that are not believed to be solvable in polynomial-time. Some of the most popular problems they have found are the Discrete Logarithm Problem and Integer Factoring. The former is used in Diffie-Hellman Key Exachange (DHK) and El Gamal encryption, while the latter is used in RSA. El Gamal and DHK are both very popular, but RSA is more prevalent due to its efficiency.\n Nevertheless, it is plausible that in the next few decades, all three of these systems will likely be useless due to the advances made by Peter Shor in quantum computing. This paper will explain the details of how Shor’s algorithm works and how it accomplishes the above. It will also feature a redesign of the proof of Jeffrey Miller (1975) that efficiently reduces from order finding in a group of order N to factoring N. Hopefully, doing so will aid future students in their studies of quantum algorithms and Post-Quantum Cryptography.

•Oct 30, 2019•0 citations

Quantum Computational Number Theory

Song Yuan Yan

This chapter gives an account of ef?cient algorithms for solving the three important infeasible problems in computational number theory, including the Integer Factorization Problem (IFP), the Discrete Logarithm Problems (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP). The quantum algorithms for order ?nding and factoring can be used, with some small modi?cations, to solve the Discrete Logarithm Problem (DLP) ef?ciently in polynomial time. Quantum factoring is reportedly in its very earliest stages and will not threaten the security of RSA at least at present, as the current quantum computer can only factor a number with just 2 digits, such as 15, which is essentially hopeless. The Elliptic Curve Method (ECM) factoring algorithm is very well suited to parallel implementation. The Number Field Sieve (NFS) factoring algorithm is also very well suited to parallel implementation.

Wiley eBooks•Nov 27, 2012•5 citations

3 Factorization with Quantum Computers: Shor’s Algorithm

Daniel Neuenschwander

Lecture notes in computer science•Jan 1, 2004•0 citations

量子計算と量子アルゴリズム

哲朗 西野

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.

•Jul 31, 2003•0 citations
When building cryptosystems, cryptographers focus on finding problems that are not believed to be solvable in polynomial-time. Some of the most popular problems they have found are the Discrete Logarithm Problem and Integer Factoring. The former is used in Diffie-Hellman Key Exachange (DHK) and El Gamal encryption, while the latter is used in RSA. El Gamal and DHK are both very popular, but RSA is more prevalent due to its efficiency.\n Nevertheless, it is plausible that in the next few decades, all three of these systems will likely be useless due to the advances made by Peter Shor in quantum computing. This paper will explain the details of how Shor’s algorithm works and how it accomplishes the above. It will also feature a redesign of the proof of Jeffrey Miller (1975) that efficiently reduces from order finding in a group of order N to factoring N. Hopefully, doing so will aid future students in their studies of quantum algorithms and Post-Quantum Cryptography.
This chapter gives an account of ef?cient algorithms for solving the three important infeasible problems in computational number theory, including the Integer Factorization Problem (IFP), the Discrete Logarithm Problems (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP). The quantum algorithms for order ?nding and factoring can be used, with some small modi?cations, to solve the Discrete Logarithm Problem (DLP) ef?ciently in polynomial time. Quantum factoring is reportedly in its very earliest stages and will not threaten the security of RSA at least at present, as the current quantum computer can only factor a number with just 2 digits, such as 15, which is essentially hopeless. The Elliptic Curve Method (ECM) factoring algorithm is very well suited to parallel implementation. The Number Field Sieve (NFS) factoring algorithm is also very well suited to parallel implementation.
In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.