• c is a common diviser of a and b if it divides a and b without a remainder.
• The modulo function x mod n, is the remainder of x divided by n.

To understand the procedure, you first need what is called the "Euler function," (n) associated with a number n. It is the number of integers smaller than n the greater common diviser of which is 1. So for example, for n=15, (15)=8 as only (1,2,4,7,8,11,13,14) have the number 1 as common greatest diviser with 15.

The Euler function has two neat properties:

1. If n is the product of two primes p and q, then (n)=(p-1)(q-1). Thus, if we know n, (=pq) and (n), we easily get the factors, and thus finding (n) is computationally equivalent to factor n.

2. If two numbers (say, k and m) have only one as their common greatest common diviser, then k exponentiated to the Euler function of m is equal to one modulo m; that is, k^(m)=1 mod m. For example, 3 and 8 have 1 as greatest common diviser, thus 3⁽⁸⁾= 3⁴=81, and 81 mod 8=1.

With all these ingredients we can see how to send secure information: Alice wants to send her credit-card number to Bob. Bob selects a "large" number, N=15, which is the product of two primes. (Today, the Netscape browser uses RSA with a 128-digit number. The largest factored number had 129 digits by 600 people working on 1600 workstations over 8 months.) He calculates (15)=(5-1) X (3-1)=8, by rule (A). He selects a number e such that the greater common diviser of e and (15)=8 is 1: e=3 works. He sends N and e to Alice. Alice encodes her credit-card number x, say 2, by the transformation x^e mod N=2³ mod 15=8, which she sends back to Bob. To decode this, Bob needs to find d such that ed=1 mod (N), d=3 will work (that is, 3 X 3=1 mod 8.) To find x, Bob uses the rule (B) to calculate x^ed=x^1+kN=x mod N; for instance, 2^{3 X 3} mod 15=2.

How to Break This Encryption?

To break the code, we need to know (N) or equivalent to factor N. Factoring large numbers on a classical computer is a difficult problem. To factor a number of N with log₁₀N digits takes roughly Exp[(log₁₀N)^1/3] number of steps -- a quantum computer would accomplish the same task in about (log₁₀N)3 steps; see Figure 5.

To factor N, a classical computer essentially tries all numbers, one by one, up to roughly N. That makes it a very inefficient process. Quantum computers excel for problems that search for a common property of a large set of numbers such as the periodicity. It turns out that factoring is equivalent to finding the period r of the function f(a)=y^a mod N, where y is, essentially, any number between 1 and N. The greatest common diviser of (y^r/2±1) mod N and N will be a factor of N. With the aforementioned example using N=15, we can choose y=7.

The periodicity of the function, as seen in the figure, is 4. (7^4/2±1) mod 15=5 or 3, which indeed are the right factors; see Figure 6. The quantum algorithm works in such a way that in a single computation, we evaluate the function f(a) for the superpostition of all numbers a from 1 to N. The periodicity is determined by a Fourier transform, a process that induces constructive interference for the correct value of the periodicity and destructive interference for the incorrect ones. To do the same task on a classical computer would require exponentially more steps.

D.C. and R.L.