How Peter Shor’s Algorithm Dooms RSA Encryption to Failure

Shor’s algorithm describes how to factor the product of pairs of very large prime numbers. The catch is that Shor’s algorithm requires a quantum computer to run on and while quantum computers do exist today, there aren’t any that are powerful enough to run Shor’s algorithm on the products of prime numbers which are big enough to be ‘interesting’.

Experts predict that there will be quantum computers sometime in the next couple of decades that should be able to run Shor’s algorithm on the products of very large (i.e. ‘interesting’) prime numbers.

Sidebar: If I have two very large prime numbers A and B then it is fairly easy to multiply them together to get a considerably larger number C. If I then give you C but don’t tell you the values of A and B that were multiplied together to get C then figuring out the values of A and B gets crazy difficult if A and B are large enough. Shor’s algorithm is able to figure out what the values of A and B are even if A and B are very large.

BTW, most modern encryption relies on the assumption that if A and B are prime and large enough and then it is extremely difficult to figure out the values of A and B if one only has the product of A and B.

https://interestingengineering.com/how-peter-shors-algorithm-dooms-rsa-encryption-to-failure