Honestly, there were students in the course who could do a better job of explaining the relationship between period-finding and factoring than I could (one of our Math colleagues famously teaches a cryptology course which several of them had already taken), so I only did a real quick sketch of that. The two-registers trick to generate a periodic function in one of them is pretty ingenious, so I spent a good deal of time on that, and then a bunch of time on the idea of using a quantum FFT to get the period of that function. Then I just hand-waved past the continued fractions business, because it's too much.
I don't remotely think I fully covered it, but I think I was able to at least convey a sense of why this works as a quantum algorithm. I didn't even attempt to account for all the big-O classification to show that it's polynomial rather than exponential, because that's a big part of why I stopped taking CS courses back in the day...
I don't know how you do Shor. I've bounced off of it (or punted at some point midpoint) in each iteration of our "physics of qc/qi" course
Honestly, there were students in the course who could do a better job of explaining the relationship between period-finding and factoring than I could (one of our Math colleagues famously teaches a cryptology course which several of them had already taken), so I only did a real quick sketch of that. The two-registers trick to generate a periodic function in one of them is pretty ingenious, so I spent a good deal of time on that, and then a bunch of time on the idea of using a quantum FFT to get the period of that function. Then I just hand-waved past the continued fractions business, because it's too much.
I don't remotely think I fully covered it, but I think I was able to at least convey a sense of why this works as a quantum algorithm. I didn't even attempt to account for all the big-O classification to show that it's polynomial rather than exponential, because that's a big part of why I stopped taking CS courses back in the day...