We prove a lower bound on the probability of Shor’s order-finding algorithm successfully recovering the order r in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any r , without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as r tends to infinity, the probability of successfully recovering r in a single run tends to one. Already for moderate r , a high success probability exceeding e.g. 1 - 10 -4 can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer N in a single run of the order-finding algorithm.
Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.
Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number
nin a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number
a,a∈Zn. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we mention about the fundamentals of Shor's quantum algorithm illustrating a concrete example.
In this article we develop an algorithm which computes a divisor of an integer
N, which is assumed to be neither prime nor the power of a prime. The algorithm uses discrete time heat diffusion on a finite graph. If
N has
m distinct prime factors, then the probability that our algorithm runs successfully is at least
p(m)=1−(m+1)/2m. We compute the computational complexity of the algorithm in terms of classical, or digital, steps and in terms of diffusion steps, which is a concept that we define here. As we will discuss below, we assert that a diffusion step can and should be considered as being comparable to a quantum step for an algorithm which runs on a quantum computer. With this, we prove that our factorization algorithm uses at most
O((logN)2) deterministic steps and at most
O((logN)2) diffusion steps with an implied constant which is effective. By comparison, Shor's algorithm is known to use at most
O((logN)2log(logN)log(loglogN)) quantum steps on a quantum computer. As an example of our algorithm, we simulate the diffusion computer algorithm on a desktop computer and obtain factorizations of
N=33 and
N=1363.
We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \emph{iterated diffusion process} on a finite graph. Concretely, a \emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an
ℓ1--normalized state vector, followed by an optional readout of selected coordinates. Let
N≥3 be an odd integer which is neither prime nor a prime power, and let
b∈(Z/NZ)∗ have odd multiplicative order
r=ordN(b). We construct, without knowing
r in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup
⟨b⟩ and whose edges correspond to the powers
b±2t for
t≤⌊log2N⌋+1. Using an explicit spectral decomposition together with an elementary doubling lemma, we show that
r can be recovered from a single heat-kernel value after at most
O((log2N)2) diffusion steps, with an effective bound. We then combine this order-finding model with the standard reduction from factoring to order finding (in the spirit of Shor's framework) to obtain a randomized factorization procedure whose success probability depends only on the number
m of distinct prime factors of
N. Our comparison with Shor's algorithm is \emph{conceptual and model-based}. We replace unitary
ℓ2 evolution by Markovian
ℓ1 evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.