This borrows a LOT from https://code.google.com/p/primality-testing/source/browse/?r=1ac41d0fa8b661ccbea8d2d82bb1b93e0c334e49#hg%2FMiller-Rabin%2Fsrc

Sadly, it seems a bit slow.