I'm posting this to provide some
clarification on the Rabin-Miller primality test as requested on Twitter. My favorite reference on the test is the
notes by Diane Hoffoss located here. If you're not familiar with primality testing and/or Rabin-Miller; read the notes first then come back to this post if you need any clarification.
My purpose here is to restate a few key points
from Hoffoss's notes, provide a little more exposition on the
examples and to compare her description of the algorithm with the description given in the Handbook of Applied Cryptography. This is a derivative work and
I do not claim to have originated any of the ideas here. Of course, any mistakes are my own.
This test is discussed in many books
including Practical Cryptography, Understanding Cryptography and the Handbook of Applied Cryptography.
Note: For the examples below, I group digits using commas as is the convention in the U.S. All of the numbers are integers.
