# Quantum Algorithms

**- Shor's factoring algorithm**

Shor's algorithm is a quantum algorithm for factoring a number *N* in *O((log N)3)* time and *O(log N)* space, named after Peter Shor.

The algorithm is significant because it implies that public key cryptography might be easily broken, given a sufficiently large quantum computer. RSA, for example, uses a public key *N *which is the product of two large prime numbers. One way to crack RSA encryption is by factoring *N*, but with classical algorithms, factoring becomes increasingly time-consuming as *N *grows large; more specifically, no classical algorithm is known that can factor in time *O((log N)k)* for any *k*. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

**[More to come ...]**