Whew, this is developing into one of the longest post series I’ve ever written (with quite a few tangents and detours along the way). I thought it would be worth taking a step back for a minute to recap what we’ve covered and where this is going.
We started with Fermat’s Little Theorem and Euler’s Theorem, which form the basis for a lot of primality testing algorithms, with three different proofs of FlT and a proof of Euler’s Theorem.
We then detoured a bit to talk about some hypothetical machines and how fast they are.
Finally I got around to presenting the Fermat primality test, which is directly based on FlT.
For the Fermat test to make sense I realized we had to talk about modular exponentiation and how to do it by repeated squaring, which led to a Post Without Words and a whole tangent on its efficiency.
Next up: first of all, there’s still quite a bit more to say about the Fermat primality test. After that I plan to present some better/more efficient tests as well (at least Miller-Rabin and Baille-PSW, possibly others). And knowing me there will be at least three more tangents along the way!
Thanks a lot for your work.
Pingback: Primality testing: recap « Mathematics Hothouse