In this sub-part you want to convince yourself of two things:
The current algorithm isn't fast (i.e. it takes exponential time) because period finding is slow
This algorithm would be fast if period finding was fast.
Q: Fast in what? We don't want to be polynomial time in $N$ (convince yourself of this by thinking up a simple algorithm which factors in time $N$)
Instead we want to factor quickly in time $\log N$ or the number of bits used to write down $N$.
The first test is easy to do. Factor 100 numbers between $2^k$ and $2^{k+1}$ for each $k \in (5,20)$. Compute how many multiplications you have to do to in period finding to find the period.
Grading: Graph the time as a function of $k.$ Expensive here means that it scales exponentially in $k$. Show that it is expnsive Put this in your document.
This has showed you that the algorithm is not fast on a classical computer.
Now, let's convince ourself that the algorithm is fast if your quantum computer does period-finding quickly.
The first thing to notice is that all the individual steps are quick (gcd, testing for easy cases, multiplication, etc.)
This means that running through the entire loop is fairly quick.
Then what we need to know is how many times things fail because each time we hit a failure mode we essentially have to do it all again.
Let’s measure how often the two failures happen and graph them as a function of $\log N$ (if the number of times we have to do something is exponential in $\log N$ that’s bad news).
Again factor 100 numbers between $2^k$ and $2^{k+1}$ for each $k \in (5,20)$.
[ ] Graded: Graph the two failure modes as a function of $k$ and show that they don't scale linearly wiht $k$.
This tells us that if we have a quantum computer that does period finding fast, then we can factor.