A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem

Grzegorz Herman, Michael Soltys

Although a deterministic polytime algorithm for primality testing is now known, the Rabin-Miller randomized test of primality continues being the most efficient and widely used alg…