Great video on Shor's algorithm

Here is a great high-level explanation on Shor's algorithm by the channel minutephysics https://www.youtube.com/watch?v=lvTqbM5Dq4Q

As I mentioned in class, the reduction from factoring to order-finding that I presented in the lecture is oversimplistic and is only meant to give some intuition for the idea. In reality, the actual reduction used inside Shor's algorithm is a little bit more clever and is the one referred to in the video above.
Here is how the actual reduction works. Suppose you are able to find the order r of a mod N. Now we hope that the following two properties are satisfied:

1. r  is even;
2. a^r/2 +1 != 0 mod N and a^r/2 - 1 != 0 mod N (i.e., neither left-hand sides are divisible by N).

If this is the case, then we can factor a^r - 1 as (a^r/2 + 1)(a^r/2 - 1). Then, since N = pq, either (a^r/2 + 1) or (a^r/2 - 1) must be divisible by p (and the other by q). But that means we can find p (or q) simply by computing gcd(a^r/2 + 1, N) or gcd(a^r/2 - 1, N)!

The only remaining issue is to figure out how likely conditions 1. and 2. are to hold for a random choice of a. Fortunately, it turns out that the probability is at least 3/8 (see section 2 in this note for a proof).  So if either 1. or 2. doesn't hold, we simply pick a new a and try again. After a few tries we are very likely to find an a (with corresponding order r) for which both conditions hold.