How Shor’s Algorithm Quashed a Revolution RSA and the internet have ushered in a revolution in encryption; allowing millions of people to exchange information over great distances in a relatively secure manner without the need for a trusted intermediary to deliver a lengthy cipher. Fortunately for the NSA/CSS in 1994 ATT scientist Peter Shor was able to harness the superposition property of quantum mechanics to drive an algorithm capable of factoring integers greater or equal to 15. Quantum systems consist of all possible states until they are measured thus collapsing the superpositions of conflicting realities into something more mundane such spin up or spin down. Shor outlined a series of operations that acted upon an entangled quantum system as opposed to a classical computer which has gate operations that act upon discrete bits of data contained in registers. Shor’s algorithm required only two qubit registers. Basically a qubit register is an array/grouping of quantum systems interacting with each other in a fashion that makes the outcome of measuring one element of the register the same as measuring every element of the register; Much like a game of a poker where all the participants agree to reveal their cards simultaneously. The elements of these qubit registers can be a string of subatomic particles or custom designed molecules. Each possible state can be mapped to “1” or a “0” just like a digital register and the register as a whole represents an integer in binary. Therefore one of the qubit registers must have at a minimum the same number of elements as the binary exponent of the integer being factored. After using a regular computer to run a well known and very fast algorithm to find an arbitrary integer “a”, which is both a prime number and relatively prime to our given integer “n” such that “a” is less than “n”, we are able to assign our first qubit register with the unkown superpostition of possible integer values a mod q, where q is an integer multiple of our factor of n. At this point if we were to measure the first qubit register we would collapse it into a meaningless value. Therefore we need to use a second qubit register populated with a value derived from “n” and “a”. Using this second register allows us to perform a quantum fourier transform on the first the first register without collapsing either one. Then we perform a unitary matrix operation on the first register. Now these two operations have greatly restricted the possible string values of the first register. There exist a high probability that when we measure our first register the integer value a mod q will indeed yield a q such that there exist an integer r where r*p = q. And this “p” will be a prime factor of “n”. All that remains is to collapse the first register by measuring it and doing a little post processing on the resultant value to arrive at a factor “p”. Running Shor’s algorithm a statistically valid number of times will yield a spread of answers which can be graphed into a double peak distribution. The two peaks are the prime factors of “n”. Of course only one peak would arise if “n” was the square of an integer. The privately held RSA company has issued a slew of challenges to the scientific computing community to factor specific integers of various sizes. The answers are sealed and the only known way to discover the integers is thru labourious calculations. The reward for factoring RSA-2048, a 2048 bit integer, is 200,000 USD. Using IBM’s Bluegene rated at 100 teraflops(100 trillion floating operations per second) to crack this number using the most efficient classical algorithm known to the general public would take longer than the current lifetime of our species. Because the work function of Shor’s algorithm is a polynomial log function as opposed to the exponential log function of the general sieve method and the fact that quantum gates run faster than their digital counterparts to avoid the discoherence associated with Heisenberg’s uncertainty principle a quantum computer using Shor’s algorithm and Bluegene(L) rated at 2 teraflops for post and preprocessing should be able to crack RSA-2048 in roughly the time it takes to boil a pot of tea. Before you think ‘easy money’ and start fantasying about ebay spending sprees you might consider that the largest integer to be factored so far on a quantum computer is the number 15. This was accomplished by IBM and Stanford University’s and underwritten by public funds courtesy of the Central Security Service. Never heard of it, good, you were never meant to. But even the diminutive 15, a far cry from the 617 decimal place RSA-2048, was still hailed as a milestone. It put to rest arguments from a large group of scientist who thought Heisenberg’s uncertainty principle would doom Shor’s algorithm to the textbooks as a purely theoretical thought experiment. And now that we know it can be done all that is required is the money and time to develop a mature implementation of the technology. On the money side, Uncle Sam is looking to fund anything that will tame a destabilizing technology such as RSA, and on the time side one or two decades seems a reasonable span to expect significant progress. At first blush there seems to be no point in worrying; who’ll care what we wrote each other decades ago. Apparently, the government cares. As shown by the Venona project, governments have the institutional memories to spend the resources necessary to decipher codes from an interwar period generations old. All that is necessary is to copy everyone's public keys and use any one of a number of means to filter out and copy encrypted emails stored on public pop-mail servers. Remember emails tend to travel thru a number of mail servers before they arrive at their intended destination. After the emails and their associated public keys are stored in inexpensive bulk media storage all that is left to be done is to wait for the appropriate breakthroughs in quantum computing to open a treasure trove of information.