Shor’s Algorithm: Looking Beyond the Classical Limits
Classical supercomputers are the most powerful computers and yet, certain calculations are beyond their capabilities. For example, calculating prime factors of a very big number is very hard for a sequential computer. Even if hundreds of the most powerful supercomputers were used together, it could still take millions or even billions of years with no guarantee of obtaining the desired output. This is the primary reason why modern encryption algorithms that ensure our internet security like RSA use big numbers. They are very hard to break. But, there is always a bigger fish.
Soon, humankind will get fully functional quantum computers. Quantum computers will be capable of breaking RSA encryption much faster and more efficiently. One of the quantum algorithms that efficiently does this task by solving the problem at the quantum level is Shor’s Algorithm. The algorithm was formulated by the American mathematician, Peter Shor, in 1994. This algorithm demonstrated the ability of quantum computers to factor large numbers efficiently, a task that is considered classically intractable. Classical computers solve problems sequentially, which becomes impractical for large numbers. However, quantum computers can simultaneously consider multiple possibilities by utilizing the supposition of quantum bits or qubits. Thus, Shor’s algorithm takes advantage of quantum parallelism and entanglement to perform computation in parallel and can find the prime decomposition of very big numbers in O((logN)³) time and O(logN) space.
Physical Implementations: Past and Present
Algorithm
Shor’s algorithm is capable of factoring very large numbers in polynomial time.
The algorithm consist of two parts:
Classical Part: Factorization problem is converted into the problem of finding the period. This can be implemented classically in classical computers.
Quantum Part: Quantum computers are used to find the period using Quantum Parallelism and Quantum Fourier Transform(QFT).
The overall steps of Shor’s algorithm are as follows:
Step 1: Choose a random integer a such that 1<a<N, where N is the number to be factored.
Step 2: Find GCD(a,N). Greatest Common Divisor can be calculated using Euclid’s Division Algorithm.
IF, GCD(a,N)=1, then proceed to Step 3.
ELSE, GCD(a,N) is a factor of N and another factor is N/GCD(a,N), then exit.
Step 3: Quantum Subroutine: This step is a crucial step that uses quantum parallelism and utilizes the QFT to efficiently obtain the period of the periodic function. The function f(r)=a^r MOD N is a periodic function or modular exponentiation function, where a and N must be coprime.
Here, we know that,
f(0)=a⁰ mod N=1
For any period function with period r, we know that f(0)=f(0+r)=f(r), then
f(r)=a^r mod N=1
Or, a^r=1 mod N
Or, a^r-1=0 mod N
Or, (a^(r/2)+1)(a^(r/2)–1)=0 mod N…………….(i)
The quantum subroutine involves:
Quantum Superposition: Two Quantum registers are used, in which first is used to represent the input space which contains all possible values of r from 0 to N-1, and the second is used to represent function values which are initialized in a superposition of all the possible values of a^r mod N and given as:
Quantum Fourier Transform(QFT): For large numbers, it is very tedious to obtain the periodicity of the function. Hence, the superposition of the function is passed through QFT to obtain periodicity of the function.
Step 4: If obtained period r is odd, go to step 1. Else, obtained period r is even, proceed to step 5.
From equation (i), let say we obtain the even period at r=p, then
(a^(p/2)+1)(a^(p/2)–1)=0 mod N………(ii)
Step 5: From equation (ii),
IF (a^(p/2)+1)=0 mod N, go back to step 1
ELSE, (a^(p/2)+1)!=0 mod N, proceed to next step
Step 6: Compute f1=GCD(a^(p/2) -1,N) and f2=N/f1 are the factors of N.
Example
Let, N=21 to be factored.
- Let’s choose a=11.
- Compute GCD(11,21) and is equal to 1 for our guess . IF GCD(11,21) ! =1, then the non-trivial factor is known. Since, it is 1, we proceed to Quantum subroutine step.
- Quantum Superposition:
Create superposition of all possible values of r between 0 to N-1 using quantum parallelism. The superposition for N=21, a=11 and r is
=1/sqrt(21){|0,1⟩+|1,11⟩+|2,16⟩+|3,8⟩+|4,4⟩+|5,2⟩+|6,1⟩+|7,11⟩+|8,16⟩+….}
Quantum Fourier Transform: After passing Quantum superposition of the modular exponentiation function to QFT, we obtained a period of 6. We used a small number in this example but in a practical encryption algorithm, very large numbers were used and, for a large number, it is hard to find the period so quickly.
4. Luckily, the obtained period is even and 11^(⁶/2) mod 21 != 0.
Thus,
factor1=GCD(11^(⁶/2)–1,21)
=GCD(1330,21)
=7
And,
factor2=21/factor1
= 3
Hence, the prime factors of 21 are 7 and 3.
The Possible Threat to Internet Security
The graph above compares Shor’s algorithm with the best-known classical algorithm for a similar task. For the same number of digits, the classical algorithm exhibits exponential growth, while Shor’s algorithm shows logarithmic growth, implying that solutions for Shor’s algorithm can be obtained in finite time. The impact of Shor’s algorithm on internet security would become apparent once a fully functional quantum computer is developed, as many secure communications, including those used in e-commerce, online banking, and various secure messaging systems, depend on RSA and similar cryptographic algorithms. Currently, the development of quantum computers is an active area of research. However, once a fully developed quantum computer emerges, there is a concern that it might be misused to break modern encryption algorithms.
Research is ongoing to develop quantum cryptographic systems that are immune to quantum computers.
