Friday, February 14, 2014

Understanding Rabin-Miller

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.

Understanding Scope in Go

As per my New Year's resolution, I've been learning to program in Go and reading  The Go Programming Language .   On page 141 of the...