.svg)
Quantum Algorithms: Shor's Algorithm
What it Is
Shor’s Algorithm is an algorithm for finding the prime factors of large numbers in polynomial time. In cybersecurity, a common encryption technique is RSA (Rivest–Shamir–Adleman). RSA is based on a public key that is the product of two large prime numbers that are kept secret. RSA is based on the assumption that a computer won’t be able to factor a very large number into its prime components, as factoring is a very different kind of problem-solving compared to addition or multiplication. Shor’s algorithm takes advantage of quantum mechanical properties of superposition and interference to quickly search through possible solutions, though the method could potentially be performed on a classical computer, over a much larger time frame.
For example, according to Thorsten Kleinjung of the University of Bonn, it would take 1 or 2 years to factor N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 on a 2.2 GHz Athlon 64 CPU PC with ≤ 2 GB memory.
Shor’s Algorithm is a powerful tool with the potential to factor any prime number, granting its wielder the ability to break many current encryptions. While today’s NISQ quantum computers are not yet sufficient to break the RSA encryption, experts estimate that within a few years, this could be possible. Indeed, Shor’s algorithm sparked significant interest in quantum computers.
While some predict that Shor’s Algorithm will be able to run on quantum annealing devices - non-universal quantum computers with only specialized optimization applications - within 10 years, there are many factors that go into this calculation. This is assuming that every other year the number of annealing qubits will double, as has happened in the past, but we mustn't fully rely on this calculation. Annealing qubit advancements could be hindered by various roadblocks slowing this timeframe, or ongoing research in annealing or universal quantum computing could result in breakthroughs revealing better algorithms or technologies to speed this process up.
This uncertainty in the time frame, as well as the intensity of RSA encryption being rendered useless, has gained attention from adjacent fields and governments alike. A recent United States Executive Order establishing a timeline for creating standards and frameworks for post-quantum cryptography (PQC) and developing quantum-resistant algorithms demonstrates how serious this security breach could be. Where there is data, there is a need for security. CIOs/CTOs from enterprises all over the world are investing in quantum after learning of the impact of Shor’s Algorithm, oftentimes strengthening quantum competencies with other applications and gaining an advantage over those who wait to begin their quantum journey. For example, UnitedHealth Group has quantum teams on three continents, and they’ve begun investigating artificial intelligence applications with quantum machine learning after their start in quantum cryptography.
How it Works
The essence of Shor’s Algorithm is in transforming a bad guess of a factor into a much better one by finding the period of a function containing the RSA key.
We start with the large number we are factoring, $N$, and an initial guess, $g.$ There are two cases for this starting guess. In case one, either $g$ is a factor of $N$ or it shares a common factor with $N$. In this case, we are done thanks to Euclid’s Algorithm, or the faster Euclidean Algorithm, a method of checking or finding common factors using subtraction or modulo, respectively. To find a factor of $N$, we don’t have to strictly guess a factor, but one that shares factors with $N$ works, too.
If $g$ is neither a factor of $N$ nor shares a common factor, then we move on to transforming this guess into a better one. For any two whole numbers, $A$ and $B$, there exists a power $p$ and multiple $m$, such that $A^p = m*B +1$. We can demonstrate this with some primes, say 3 and 7.
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
This relationship helps us look at the problem differently.
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
This is where quantum computers take over. We can cleverly construct a superposition of possible powers, where all of the incorrect guesses destructively interfere with one another.
To reiterate, we are searching for a power to which we raise our initial bad guess. When subtracting the large number term, $m*N$, from this exponentiated term, $g^p$, we need a remainder of 1, or $g^p - m*N = 1$. So our system is as follows.
Input superposition of powers into exponentiation:
$$|x\rangle \rightarrow [g^x] \rightarrow |x, g^x\rangle .$$
Input superposition of exponentiations into difference of the large number term to find remainder:
$$|x, g^x\rangle \rightarrow [>m*N] \rightarrow |x, +r\rangle .$$
And we want this remainder to equal 1.
We now take advantage of a structural relationship between exponentiation and modular arithmetic.
$$g^x = m*N + r \rightarrow g^{x+p} = m_1*N + r \rightarrow g^{x+2p} = m_2*N + r$$
The remainder stays the same regardless of linear changes to the exponent, meaning there is a repeating property with some period. Take this example with different powers creating different remainders combining to have the same remainder.
$$g^{p+10} = g^pg^{10}$$
$$ = (mN + 2)(m_1N + 4)$$
$$ = mm_1N^2+4mN+2m_1N+8$$
$$ = (mm_1\frac{N}{2}+2m+m_1)N + 4\Rightarrow\text{something} N + 4 $$
$$ = (mm_1\frac{N}{4}+m+\frac{m_1}{2})N + 2\Rightarrow\text{something} N + 2.$$
When we input a superposition through our system and measure the remainder, we get a superposition of all possible powers that result in only that remainder. And this remaining superposition repeats with a period of the power $p$ or has a frequency of $f=\frac{1}{p}$.
Just as a classical Fourier Transform translates a wave as a function of time into a function of frequency, so too does a Quantum Fourier Transform (QFT), with a superposition as an output with a frequency of the input.
So, if we input a single state into a QFT, the output will be a superposition of states with varying weights or probabilities that form a wave with the input state as the frequency. And if we input multiple states into a QFT, the output will be a superposition of superpositions - with destructive and constructive interference combining superpositions into one wave. And if our input to the QFT is a superposition with period $p$, destructive interference leaves only $\frac{1}{p}$.
From here, we simply calculate our better guess, $g^{\frac{p}{2}} ± 1$, and iterate as needed.
Today’s quantum computers are only able to factor small numbers like 15 and 21, with the more sophisticated techniques like Adiabatic Quantum Computing (AQC) requiring 5900 qubits to factor some of the smallest numbers used for RSA.
What it Is
Shor’s Algorithm is an algorithm for finding the prime factors of large numbers in polynomial time. In cybersecurity, a common encryption technique is RSA (Rivest–Shamir–Adleman). RSA is based on a public key that is the product of two large prime numbers that are kept secret. RSA is based on the assumption that a computer won’t be able to factor a very large number into its prime components, as factoring is a very different kind of problem-solving compared to addition or multiplication. Shor’s algorithm takes advantage of quantum mechanical properties of superposition and interference to quickly search through possible solutions, though the method could potentially be performed on a classical computer, over a much larger time frame.
For example, according to Thorsten Kleinjung of the University of Bonn, it would take 1 or 2 years to factor N = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396491743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 on a 2.2 GHz Athlon 64 CPU PC with ≤ 2 GB memory.
Shor’s Algorithm is a powerful tool with the potential to factor any prime number, granting its wielder the ability to break many current encryptions. While today’s NISQ quantum computers are not yet sufficient to break the RSA encryption, experts estimate that within a few years, this could be possible. Indeed, Shor’s algorithm sparked significant interest in quantum computers.
While some predict that Shor’s Algorithm will be able to run on quantum annealing devices - non-universal quantum computers with only specialized optimization applications - within 10 years, there are many factors that go into this calculation. This is assuming that every other year the number of annealing qubits will double, as has happened in the past, but we mustn't fully rely on this calculation. Annealing qubit advancements could be hindered by various roadblocks slowing this timeframe, or ongoing research in annealing or universal quantum computing could result in breakthroughs revealing better algorithms or technologies to speed this process up.
This uncertainty in the time frame, as well as the intensity of RSA encryption being rendered useless, has gained attention from adjacent fields and governments alike. A recent United States Executive Order establishing a timeline for creating standards and frameworks for post-quantum cryptography (PQC) and developing quantum-resistant algorithms demonstrates how serious this security breach could be. Where there is data, there is a need for security. CIOs/CTOs from enterprises all over the world are investing in quantum after learning of the impact of Shor’s Algorithm, oftentimes strengthening quantum competencies with other applications and gaining an advantage over those who wait to begin their quantum journey. For example, UnitedHealth Group has quantum teams on three continents, and they’ve begun investigating artificial intelligence applications with quantum machine learning after their start in quantum cryptography.
How it Works
The essence of Shor’s Algorithm is in transforming a bad guess of a factor into a much better one by finding the period of a function containing the RSA key.
We start with the large number we are factoring, $N$, and an initial guess, $g.$ There are two cases for this starting guess. In case one, either $g$ is a factor of $N$ or it shares a common factor with $N$. In this case, we are done thanks to Euclid’s Algorithm, or the faster Euclidean Algorithm, a method of checking or finding common factors using subtraction or modulo, respectively. To find a factor of $N$, we don’t have to strictly guess a factor, but one that shares factors with $N$ works, too.
If $g$ is neither a factor of $N$ nor shares a common factor, then we move on to transforming this guess into a better one. For any two whole numbers, $A$ and $B$, there exists a power $p$ and multiple $m$, such that $A^p = m*B +1$. We can demonstrate this with some primes, say 3 and 7.
$3^2 = 9 = 1*7 + 2$
$3^3 = 27 = 3*7 + 6$
$3^4 = 81 = 11*7 + 4$
$3^5 = 243 = 34*7 + 5$
$3^6 = 729 = 104*7 + 1$
This relationship helps us look at the problem differently.
We can write our relationship with our terms: $g^p = m*N +1$. Once we subtract 1 from both sides, getting $g^p-1 = m*N$, we can rewrite this as $(g^{\frac{p}{2}} + 1)(g^{\frac{p}{2}} - 1) = m*N$, as this is a difference of two squares. This looks more like two factors of $N$, for which we are searching, so instead of searching for a better guess $g$, we will now search for a power $p$.
This is where quantum computers take over. We can cleverly construct a superposition of possible powers, where all of the incorrect guesses destructively interfere with one another.
To reiterate, we are searching for a power to which we raise our initial bad guess. When subtracting the large number term, $m*N$, from this exponentiated term, $g^p$, we need a remainder of 1, or $g^p - m*N = 1$. So our system is as follows.
Input superposition of powers into exponentiation:
$$|x\rangle \rightarrow [g^x] \rightarrow |x, g^x\rangle .$$
Input superposition of exponentiations into difference of the large number term to find remainder:
$$|x, g^x\rangle \rightarrow [>m*N] \rightarrow |x, +r\rangle .$$
And we want this remainder to equal 1.
We now take advantage of a structural relationship between exponentiation and modular arithmetic.
$$g^x = m*N + r \rightarrow g^{x+p} = m_1*N + r \rightarrow g^{x+2p} = m_2*N + r$$
The remainder stays the same regardless of linear changes to the exponent, meaning there is a repeating property with some period. Take this example with different powers creating different remainders combining to have the same remainder.
$$g^{p+10} = g^pg^{10}$$
$$ = (mN + 2)(m_1N + 4)$$
$$ = mm_1N^2+4mN+2m_1N+8$$
$$ = (mm_1\frac{N}{2}+2m+m_1)N + 4\Rightarrow\text{something} N + 4 $$
$$ = (mm_1\frac{N}{4}+m+\frac{m_1}{2})N + 2\Rightarrow\text{something} N + 2.$$
When we input a superposition through our system and measure the remainder, we get a superposition of all possible powers that result in only that remainder. And this remaining superposition repeats with a period of the power $p$ or has a frequency of $f=\frac{1}{p}$.
Just as a classical Fourier Transform translates a wave as a function of time into a function of frequency, so too does a Quantum Fourier Transform (QFT), with a superposition as an output with a frequency of the input.
So, if we input a single state into a QFT, the output will be a superposition of states with varying weights or probabilities that form a wave with the input state as the frequency. And if we input multiple states into a QFT, the output will be a superposition of superpositions - with destructive and constructive interference combining superpositions into one wave. And if our input to the QFT is a superposition with period $p$, destructive interference leaves only $\frac{1}{p}$.
From here, we simply calculate our better guess, $g^{\frac{p}{2}} ± 1$, and iterate as needed.
Today’s quantum computers are only able to factor small numbers like 15 and 21, with the more sophisticated techniques like Adiabatic Quantum Computing (AQC) requiring 5900 qubits to factor some of the smallest numbers used for RSA.
About "The Qubit Guy's Podcast"
Hosted by The Qubit Guy (Yuval Boger, our Chief Marketing Officer), the podcast hosts thought leaders in quantum computing to discuss business and technical questions that impact the quantum computing ecosystem. Our guests provide interesting insights about quantum computer software and algorithm, quantum computer hardware, key applications for quantum computing, market studies of the quantum industry and more.
If you would like to suggest a guest for the podcast, please contact us.
