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 prime numbers, and thus break RSA encryption much faster and more efficiently than in the classical case.