Algorithms for Quantum Computers
The security of modern encryption algorithms like RSA is based on the fact, that ordinary computers are by far too slow to break these algorithms. William Crowell, the Deputy Director of the NSA once said, that if all the computers in the world would be put together to break a PGP encrypted message, this would take 12 million times the age of the universe.
But what if computers would be introduced that would be millions of times faster than the computers nowadays ?
One of the first Algorithms designed for quantum computers was an algorithm for factoring a number N in O((log N)3) time and O(log N) space, invented by Peter Shor.
|
 |
Peter Shor |
A message encrypted with RSA can be deciphered by factoring the public key N, which is the product of two prime numbers. Classical algorithms are only capable of doing this task in exponential time, so they are not fast enough as N is increasing.
Shor's algorithm (published 1994) can break RSA in polynomial time, but only if it can be processed on a quantum computer.
Links:
A detailed description of Shor’s algorithm can be found at:
en.wikipedia.org/wiki/Shor%27s_algorithm
Illustration of Shor's Alogrithm:
www.doc.ic.ac.uk/~nd/surprise_97/journal/vol4/spb3/
Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor, 1996