Yes. The naive algorithm for factorization runs in O(2^N) (where N is the number of bits in the number you want to factorize), which is impractical for any sufficiently large N (2^64 > 10^19, 2^1024 > 10^328 which is BIG). There are better known algorithms, but none of them are polynomial, so a bruteforce is highly impractical.
Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000.
So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
Ok, thanks. But when I start hearing conspiracy theories that the NSA (or anyone) has already developed one, I should basically look for an encryption algorithm that isn't based on prime factorization?
Encryption algorithms exist and are being developed which are not based on prime factorization and for which no known quantum algorithm exists which can break them in polynomial time.
There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.
Comments
Yes. The naive algorithm for factorization runs in O(2^N) (where N is the number of bits in the number you want to factorize), which is impractical for any sufficiently large N (2^64 > 10^19, 2^1024 > 10^328 which is BIG). There are better known algorithms, but none of them are polynomial, so a bruteforce is highly impractical.
Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000.
So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
Ok, thanks. But when I start hearing conspiracy theories that the NSA (or anyone) has already developed one, I should basically look for an encryption algorithm that isn't based on prime factorization?
Encryption algorithms exist and are being developed which are not based on prime factorization and for which no known quantum algorithm exists which can break them in polynomial time.
There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.