RTFA: http://en.wikipedia.org/wiki/Shor’s_algorithm
Shor’s algorithm is a quantum algorithm for factoring an integer N in O((log N)3) time and O(log N) space, named after Peter Shor.
A common public-key cryptography method known as RSA is based on the assumption that it is computationally infeasible to factor a large integer. For this reason a quantum computer with sufficiently many quantum bits could “break” RSA. RSA 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 which is polynomial in log N.
Like many quantum computer algorithms, Shor’s algorithm is probabilistic. Furthermore, it gives the correct answer with constant bounded probability. A proposed answer can be easily verified by dividing the RSA key by the alleged factor and looking for a remainder. By running the algorithm multiple times a correct answer can be obtained with exponentially small error.
Shor’s algorithm was discovered in 1994 by Peter Shor, but the classical part was known before; it is credited to G. L. Miller. Seven years later, in 2001, it was demonstrated by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits. [1]
Well, at least there aren’t too many groups who can implement this in the next decade…
older post
Add New Comment
Thanks. Your comment is awaiting approval by a moderator.
Do you already have an account? Log in and claim this comment.
Add New Comment
Trackbacks
(Trackback URL)