[btilly]

There is a mistake in the description of the Rabin-Miller test.

The test itself is deterministic. If you try it for more than half of the numbers in the range, it gives you an exact answer.

In practice we run it as a probabilistic test because we don't want to test all of those numbers. :-)

[animeshk]

Wow. didn't know that! Will add it to the section on Rabin-Miller. Thanks :)