Part 3: Shor’s Algorithm (classically)

References

Wikipedia article on Shor's algorithm.

There are various ways to factor classically, but they all require exponential time. The best current algorithm is the general number field sieve. Quantum computers, though, can factor in polynomial time using an algorithm called Shor’s algorithm.

Shor’s algorithm contains many steps, all of which run quickly on a classical computer except for the period finding step, which runs slowly and can only be efficiently evaluated by a quantum computer. In this section you will write a python script that implements Shor’s algorithm classically. The period running step will obviously run slowly. Later on you will replace the period finding piece with your quantum computing simulator (it will still run slowly because you're using a simulator, but you can imagine your code is a real quantum computer and then in your imagination it will run quickly).

Here are the steps of Shor’s algorithm:

Goal: Factor a number N

Make sure it's not already easy (or impossible) to factor. Do this by checking:
- your number isn't prime (this can be done quickly with primality testing...in your case ask python)
- your number isn't even (i.e $N=2x$)
- your number isn't of the form $N=x^a$. To check this, you can just check $\sqrt[a]{x}$ for any integer a up to $\log_2(N)$ Evaluating an $a$'th root is quick.
Choose a random number $x\in [1..\sqrt{N}]$
Check that $GCD(x,N)=1.$ This means that $x$ is co-prime with $N$. (If we are not co-prime with $N$ then we’ve already found a factor). Checking a GCD is quickly (Euclid invented the algorithm!)
Find the minimum $r$ such that $x^r\equiv 1( \textrm{mod } N)$. This is what a quantum computer will do for you. If $r$ is odd, then start over again with a new $x$. The probability this happens is low (you’ll check this soon). Do you understand why $r$ needs to be even?
Then $(x^{r/2}-1)(x^{r/2}+1)\equiv 1(\textrm{mod } N)$ and therefore $GCD[(x^{r/2}-1) (\textrm{mod } N),N]$ and $GCD[(x^{r/2}+1) (\textrm{mod } N),N]$ are both factors. If you are unlucky, it might be that $(x^{r/2}-1) (\textrm{mod } N)$ and $(x^{r/2}+1) (\textrm{mod } N)$ equal 1 and $N$. If that happens, start over. This also only happens with low probability (you’ll check that too).

Do you see why this works? If not, we should talk about it.

Write a python script that implements this algorithm with a separate function for period finding. Your algorithm should check for failure modes and simply start over with a new random $x$ in the case of a failure. Use your code to factor some numbers!

	Grading
	Show that your factoring code works by factoring a lot of numbers. Show that you can factor a number up to 10 bits. Paste into your document the $x$ and $r$ you find by factoring $N=30$ Put a list of ten N, x, r where N is less than 5 bits and x and r are not trivial. You will use these later on for testing.

Show that your factoring code works by factoring a lot of numbers. Show that you can factor a number up to 10 bits.

Paste into your document the $x$ and $r$ you find by factoring $N=30$ Put a list of ten N, x, r where N is less than 5 bits and x and r are not trivial. You will use these later on for testing.

Congrats! You now have an algorithm that factors. Shor's algorithm will involve replacing period finding with a quantum computer