We are going to crack the RSA by finding the period of the ciphertext. Let m be the message, c the ciphertext, e the encoding number and N=pq such that

From Period Finding and the RSA post, the period of a ciphertext is defined as the smallest number r such that

First we prepare QBits at the state where is the number of bits of . The number of bits can be computed using the formula:

We also prepare QBits for the output register.

So initially we have the following setup:

The output register will contain the output of the operator:

where

We now apply the Hadarmard gate to the input register and apply the operator :

The Hadamard gates transform the state into a superposition of all possible values of the period while the operator transforms the output QBits as superposition of all possible values of .

Next we make a measurement of the output QBits. This will give us a number which corresponds to all states whose value of is of the form since

since by definition of a period.

Therefore, after the measurement, the input state is now

where m is the smallest integer such that .

We will then apply the quantum Fourier transform to state . The Quantum Fourier Transform is defined by its action on an arbitrary

Applying the Fourier Transform to the state ,

Now if we make a measurement of this new state, the probability of getting a value of y is the probability amplitude multiplied by it’s complex conjugate:

The factors in underbrace evaluates to 1 when multiplied and we’re left with

Using the formula

we can write the summation in underbrace as

We’d like to know at what value of y the expression above is maximum. We can use the following formula to simplify above summations:

If we let

this reduces the summations to:

Here is a plot of the function for m=4:

Notice that the graph attains its maximums when the values of f are integer values, that is when

Since y is an integer value, this means that the value of y must be close to . We can use a theorem in Number theory which states that if is a rational number that approximates a real number x and

we can approximate x using continued fraction expansion of p/q. In fact, if we find a y that is within 1/2 of one of the values, we have

and dividing both sides by , we get

which satisfies the theorem. We can therefore expand via continued fraction expansion and continue until we find a denominator that is less that . We then test whether r could be our period if it satisfies

If it satisfies the above, then r is the period. It’s just a matter of computing , the inverse of modulo r satisfying

Having computed , we can then decrypt the ciphertext using

In our example in period finding, let’s suppose that the quantum computer gave us the following number

We can expand the fraction as a continued fractions as follows:

or

We can stop until since . So we use the first expansion where and testing it

which confirms that is a period. Using in the equation

and solving for (which is the inverse of e modulo 58) we get

We can now get the original message using

which agrees with our original message.

We have just seen how a quantum computer can be used to crack the RSA. We have exploited the fact that the measurement will give us a value of y that is near with high probability. We then computed for the period using the continued fraction expansion of . With the period computed, it’s becomes straightforward to decrypt the ciphertext.