1.7 KiB
We have presented Shor’s algorithm as a Las Vegas algorithm, which means that the output is always correct and the expected runtime is finite. With a small modification, it can be presented as a Monte Carlo algorithm, which means that the output may be incorrect with a certain probability.
- Shor's algorithm is a quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer, find its prime factors. It was invented in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer, Shor's algorithm runs in polynomial time. -search unordered list in square root n time rather than searching every element which leads to O(n)
- The algorithm that quantum computers can effectively use to solve various problems that we have set up in society today. Essentially, our entire system is set up on mathematics; therefore, with this algorithm, a quantum computer can solve issues of factorization, discrete log, elliptical curve and more which means all RSA encrypted cryptosystems could easily be broken.
Shor’s Algorithm for Discrete Logarithm
The full paper on Shor’s algorithms was published in 1997 and has described not only an algorithm for integer factoring but also an exponentially faster algorithm for discrete logarithm.
It is a remarkable and celebrated scientific contribution to quantum computing, but the algo- rithm for discrete logarithm has not been described in many books. Some papers apply this algorithm to cryptography.
Code implementations of Shor's Algorithm
The full description of the code can be found here in the qisket textbook.