Shor’s algorithm in c++

Try to factor the number 300000000. Haven’t found the answer? That’s actually a good thing. RSA encryption depends on this.

RSA what?

RSA encryption is a type of encryption that is used to make your emails, credit cards, and many other things secure.

Let’s use the number above as an example. Bob wants to send a private message to Alice. Bob doesn’t want any intruders or attackers to view the message, or else it wouldn’t be private. To prevent an intrusion, using the number 300000000, Bob and Alice can get the factors of that number, and only they would know the factors, because it’s a really big number(They’re usually 1024–4096 bit, numbers that have still not been mathematically factored yet). This ensures that Bob and Alice are the only people that are going to be viewing this message, because if an attacker tried to view those messages, he would have to factor this incredibly large number using his computer which would take thousands of years.

So how does this relate to quantum computing or Shor’s algorithm?

Well, Shor’s algorithm is an algorithm created to factor very large numbers. On classical computers, even with this algorithm, it would take a very, very long time to factor a number to crack RSA encryption(Like thousands of years). Using a quantum computer however, theoretically, these incredibly large numbers could be factored in minutes. This would crack RSA encryption, and revolutionize cybersecurity!

So how does Shor algorithm work?

Here are some steps on how to implement/how the algorithm works:

Step 1: Pick a random number less than N.

Step 2: Find r, the period of x^r mod n, where x is coprime to N(they both have only one factor: 1) R is the smallest positive number that x^r%N=1. % is modulus, which is the remainder of division.

In an actual quantum computer, this is where the quantum part would happen. Using the quantum Fourier transform, the period that satisfies the equation will be amplified and be used for the calculation. The quantum Fourier transform is used to amplify certain outputs that satisfy a function.

Step 3: Check that r is even and x^r/2+1 does not equal to 0.

Step 4: Let q=gcd(x^r/2–1,N)and let o =gcd(x^r/2+1,N)

gcd=greatest common denominator.

q and o are the factors of your number

I have implemented Shor’s algorithm in c++ here.

To watch a video on how the algorithm looks like, click here.