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:

Therefore, the probability of getting a specific y is

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.

How lucky do we need to get in order for the state to collapse to one of these y values close to ? Let’s evaluate the probability for

where is the distance of the closest y to . Since , we have

We can approximate the denominator using the small angle approximation of sine:

to get

Since m is the smallest integer such that , then

We can use this to approximate

to get

Since , we can see from the graph below that the line joining (0,0) and , whose equation is is less that the value of the sine function at that interval, that is,

Using this inequality, we can get a lower bound of the probability of getting a specific y value to be

Since there are r of these ‘s, the probability of getting any one of these ‘s is therefore:

which means that there is 40% probability of the state to collapse to a value of y that will give us the correct period.

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.