Shor's algorithm

Among the first quantum algorithms that demonstrated advantage over classical ones we find Shor's algorithm. In general terms, Shor's algorithm allows us to find prime decomposition of very big numbers in O((logN)^3) time and O(logN) space.

Currently, our internet's security relies mainly on the RSA encryption scheme, which involves encryption using a large number made of two large prime numbers. Finding large prime numbers is thus very useful in order to decrypt messages. Shor's algorithm uses quantum mechanics to find such pirme numbers, and thus break RSA encryption much faster and more efficiently than in the classical case.

Prerequisite knowledge

The following videos contain an explanation of Shor's algorithm given by Elsie Loukiantchenko and Maria Flors Mor Ruiz, Applied Physics MSc students at TU Delft.

Find first a general view of the algorithm:

The role of quantum mechanics is covered in the second part:

Further Thinking

Euclid's algorithm is a way to find common divisors. Use this algorithm to find the greatest common divisor of 210 and 45.

Now, let's say that we have a number N=91, whose factors are 7 and 13. If we choose as a random guess g=64, which power p gives us the following expression?

g^p= m*N → (g^p/2+ 1)*(g^p/2 - 1) = m*N

Solution

Filter courses

Quantum Algorithms

Shor's algorithm

Prerequisite knowledge

Further Thinking

Further Reading