Shor's Algorithm and RSA Encryption

 

INTRODUCTION

Every positive number can be factorized to the product of primes. But factoring a large number is computationally expensive and it takes more time to factorize as the number of digits increase. Finding whether a number is prime or composite can be easily done on classical computers. The problem arises when we have to factorize the composite number. Even the most efficient classical factoring algorithm (number-theoretic sieve algorithm) couldn’t factor a composite number in polynomial time. RSA encryption leverages this fact in cryptography. Peter Shor followed the path started by Benioff, Bennett, Deutsch, Feynman, Simon, and others great scientists in the field of quantum computing created an algorithm based on Quantum Fourier Transform and modular exponentiation that can factorize number leveraging one of the properties of factorization and that is its ability to reduce to a period finding the problem.

 

PERIOD-FINDING PROBLEM

A factoring problem can be converted to a period finding problem. A function that repeats itself at a regular interval is called periodic functions and that interval is called the period of a function (e.g. trigonometric functions). Finding the period of modular function plays an important role in factoring a number.

MODULAR ARITHMETIC (f(x) = a mod N)

If X and Y are two integers, then we know X/Y = P, where P = XQ+R. 
Here, X is dividend; Y is divisor; Q is quotient; R is remainder.
R can be represented as R = X mod Y (X modulo Y is equal to R)

Example: 7 mod 5 = 2

In terms of the clock, to find the result of X mod Y we can follow these steps ;

1.  Construct a clock for size Y.
2.  Start at 0 and move around the clock X steps. 
3.  Wherever we land, is remainder.

            If X is negative, we move anticlockwise and if X is positive, we move clockwise.

MODULAR EXPONENTIATION (f(x) = a^x mod N)

Let us take the sequence S(n) = 2ⁿ, where n is a natural number.

           S(n) = 2, 4, 8, 16, 32, 64, 128,...                                  --------------> (1)

So, if we take modulo 15 of S(n), we get :

           S(n) mod 15 =  2ⁿ mod 15 = 2, 4, 8, 1, 2, 4, 8,...        ---------------> (2)

One can notice that the function (2) repeats itself with a period 4. For smaller values of a, we can find period of f(x) = a^x mod N just by looking at it. For bigger values of a, we use something called Quantum Fourier Transform (QFT). These modular exponentiations and QFT consist the heart of Shor's algorithm.

SHOR’S ALGORITHM

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer or Shor’s Algorithm is a period finding algorithm that is used to factorize numbers. Basically, it involves 5 steps to factorize a number and the one that involves quantum computers is step 2.

CONVERTING PRIME FACTORIZATION PROBLEM TO PERIOD-FINDING PROBLEM 

Let N = p*q where p and q are two prime numbers (for simplicity let’s take only 2 prime numbers). Factors (or divisors) of N are 1, p, q and N. Now 1 and N are the trivial solution (i.e.) they are too obvious. We have to find non-trivial solutions. If N is even, then 2 is one of the factors since it is the only even prime number. The other factor will be. So let’s focus on odd numbers, factoring using Shor’s algorithm involves 5 steps.

1. Choose a random positive integer 1 < m < N. Find the greatest common divisor form of N i.e. gcd(m, N) using the polynomial-time Euclidian algorithm. There are two possible outcomes.

Outcome (I):  gcd(m, N) != 1

Here, m<N so the gcd(m, N) cannot be equal to N and according to outcome (I), gcd(m, N) != 1. So if m and N had a gcd it has to be either p or q. If one of them is known (say p), other (say q) can be obtained by dividing N with it (i.e. p).

Outcome (II):  gcd(m, N) = 1

GCD of two numbers will be 1 only if they both don’t have any common divisor (or factor). Proceed to step 2. 

2. Now that we have a number m, we define a function f(x) = MX mod N. Using QFT we find the period P of this function on a quantum computer. P is the period of the function if f(x) = f(x + P). If P is odd, move back to step 1. If even proceed to step 3.

3. If P is odd, move back to step 1. If even, proceed to step 3.

4. P is the period,

        =>  m^P = 1 mod N                                                    -------------------> (3)

        =>  m^P-1 = 0 mod N                                                 -------------------> (4)

Therefore, m^P-1 is a multiple of N. Again, m^P-1 = (m^P/2 - 1)(m^P/2 + 1).

If (m^P/2 + 1) = 0 mod N, then m^P/2  = (-1) mod N           -------------------> (5)

Then return back to step 1, else proceed to step 5.     (see Table 1 for reference)

5.  Therefore, d = gcd(m^P/2-1, N). Since equation (5) is not true i.e. (m^P/2 + 1) != 0 mod N (or m^P/2  != -1 mod N), it can be easily shown that d is non-trivial (i.e. neither 1 nor N) factor (or divisor) of N.     

                Table 1: finding factors of 15 using Shor’s algorithm

m	period P	gcd(15, ar/2-1)	gcd(15, ar/2+1)
2	4	3	5
4	2	3	5
7	4	3	5
8	4	3	5
11	2	5	3
13	4	3	5
14	2	1	15

Step 4 explanation: if m^p/2 = -1 mod N, then gcd(m^p/2-1,N)  would give either 1 or N which are trivial solutions. For example, look at m = 14 in Table 1 which has a period P = 2 and 14^2/2 = -1 mod 15. The factors obtained using m = 14 are 1 and 15 which are out of our scope. So we go back to step 1 and start the whole procedure with different m (< N).

 

APPLICATIONS OF SHOR’S ALGORITHM 

One of the popular applications of Shor’s algorithm is breaking RSA encryption but this can also be used to solve any problem involving period-finding. Though we have quantum computers that can run this algorithm and find factors of small numbers, we need more powerful quantum computers to actually break RSA encryption. Scientists are working to counter this application of Shor’s algorithm before it’s too late. Quantum Computing is an upcoming field and it’s not going to replace classical computers. Quantum computers are not efficient at doing every-day task that we do with our phones or laptops. They are built for a specific purpose like factorization, optimization, model simulations, etc.

(by Naveen V.)