Applying Shor’s Algorithm

An interactive short story

Editor’s Intro: Generally, folks who have heard of quantum computers have also heard of Shor’s algorithm, the algorithm devised by Peter Shor to factor large numbers. This algorithm is the source of much interest in the quantum community — one day perhaps a few decades in the future, these devices would be able to use Shor’s algorithm to crack RSA, the encryption that safeguards much of our data. This past week on Coding With Qiskit, IBM Quantum’s Jin-Sung Kim walked us through how this algorithm works by coding it on a quantum computer using Qiskit. Check it out:

To give a better sense of how this algorithm might work in the real world, Qiskit Advocate Spencer Churchill imagined what might happen if you found RSA-encrypted code in the real world, and how Shor’s algorithm would be able to crack it. Of course in the real world, RSA-encrypted coprimes are thousands of digits long, which would require a fault-tolerant quantum computer…and again, that’s a long way’s off. If you want to learn more about the machinery that goes into Shor’s algorithm, namely Quantum Phase Estimation and the Quantum Fourier Transform, check out lectures 7 through 9 on our Introduction to Quantum Computing and Quantum Hardware course.

Introduction

“I have lucrative news to share before it goes public… don’t worry, I encrypted the listing. See you soon.”

You look up to see a man hastily exit the New York City subway, leaving behind a scrap of paper on the floor. Curious, you read the contents of the slip:

“Buy 213”

At the bottom, you see what you can only assume is the coprime of an RSA key, , 15).

You know three things:

1. A company is going to report high earnings.
2. That company’s encrypted stock listing is “213,”
3. and the coprime of that RSA key is 15.

RSA

The RSA (Rivest–Shamir–Adleman) cryptosystem is an algorithm which enables one group to encrypt and decrypt data while restricting another to only decrypting. This works because RSA is a special type of function referred to as an asymmetric algorithm — the mathematics required to encrypt the data is straightforward for a computer, but decrypting the data takes an unreasonably large amount of computing resources. Two distinct pieces of information are required to obtain the full range of the RSA function, a public and a private key.

RSA’s public key derives from the two product of two large prime numbers, which is available to anyone publicly for encrypting data. However, only people with the actual prime numbers themselves can decrypt the data; this is called the private key. This tutorial will use a basic form of RSA to highlight the capability of Shor’s algorithm. The functions below simply use the properties of asymmetric algorithms to encode and decode text using public and private keys.

The prospect of cracking an insider trade is too compelling to ignore, so you try to guess the private key.

Guesses:
	1. BBB
	2. EBJ
	3. BBG

Well, that didn’t work — RSA is too secure to simply be guessed. The asymmetric modular function is constructed in such a way as to only allow the private key to unlock the encryption. The scrap only has the coprime factor of the key, though.

Graphic credit: Jeronimo Garcia

The only way to read the listing would be to

1. factor the coprime number,
2. use those factors to generate the private key,
3. then decrypt the listing with the private key.

Luckily, you attended Abe’s lecture on Shor’s algorithm and know exactly where to begin!

Shor’s Algorithm

Shor’s algorithm is quantum algorithm used to find the period of cyclic or periodic functions. By representing a product of two prime numbers, called the coprime, as a periodic function using the modulo operator, and converting this equation into a form that a quantum computer can process, Shor’s algorithm can determine the period of that function. Interestingly, using the period of this function, a quantum computer could factor the coprime number. Using a quantum computer to factor the extremely large numbers used in RSA is decades away and will require an error-corrected device with many qubits— but today, we can at least use it to factor very small coprimes…like 15.

You review and write out each step from the notes:

Pick an integer, a, such that 1 < a < N and gcd(a, N) = 1.

1 < 7 < 15, True

Find the period of f(x) = a^x (mod N), where x is the function’s period

This is when you connect to your quantum computer and begin your period-finding circuit.

Graphic credit: Qiskit

First, you notice the measurement qubits, |0>, are all being initialized with Hadamard (H) gates and the target qubits are being initialized at |1>.

Second, you see U gates applying a unitary operator, U(x) = a^x (mod N), on the target qubits controlled by the measurement qubits, which in your case is

U(x) = a^x mod 15

Third, you perform an inverse quantum Fourier transform on the measurement qubits.

Fourth, you measure the measurement qubits to hopefully return an exponent, x, which satisfies f(x) = a^x (mod N).

Finally, you assemble the circuit,

run it,

and return possible exponents for period finding.

Measured periods:	0	4	8	12

Factoring N

Now, you sort through the possible exponents, finding those which satisfy two constraints:

1. the exponent, x, must be even and
2. a^(x/2) + 1 ≠ 0 (mod N)

Using an applicable period, x, you can find nontrivial factors, P and Q , of N with gcd(a^(x/2) ± 1, N) .

P = 3
Q = 5

 3 x 5 = 15, True

Decrypting 213

This is the moment you’ve been waiting for! Quickly, you use the factors P and Q to restore the incomplete private key.

Using RSA and Shor's Algorithm, you determine the private key to be:
	(23, 15)

Decrypting the listing is only one function away now… You hesitate but eventually run the cell below.

You learn that the decrypted listing is IBM!

Being the ethical quantum programmer you are, you decide not to buy the stock — insider trading isn’t your thing. Knowing you did the right thing, you enjoy the rest of your day.

I had the privilege of attending Abe Asfaw’s lectures on Shor’s Algorithm during the Qiskit Global Summer School. By the fourth day, we were assigned a lab factoring the coprime 15. This inspired me to demonstrate Shor’s algorithm applied to a “realistic” situation. I spent two weeks of my quarantine having fun and learning so much from the many lecturers, mentors, and peers contributing on Crowdcast and Discord. If you’d like to learn more about Shor’s algorithm (under the hood), check out the Qiskit Textbook.

Thank you again to everyone who made the Qiskit Global Summer School possible and those who enjoyed reading this blog.

Sources

How does RSA work?

Shor’s algorithm

Shor’s Algorithm

I’m currently writing a series of short stories teaching quantum algorithm applications and hope to share it with you all soon!