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.