Shor's Algorithm

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer, developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of a superpolynomial speedup over the best known classical factoring algorithms, since it could in principle break widely used public key cryptosystems that rely on factoring being hard. Running it on numbers large enough to threaten real cryptographic keys would require quantum computers far larger than any yet built, because of the overhead of quantum error correction.