Cryptomathic

Miller-Rabin Primality Test

Did you ever wonder how we test gigantic odd numbers that we think may be prime?

Did you ever stop to wonder if 473155932665450549 was prime?

In modern cryptography we normally use special mathematical tools for generating prime numbers. Naturally we want to convince ourselves that the generated number is prime. Proving this is somewhat difficult, however, so we turn the question up-side down and convince ourselves probabilistically that we are dealing with a prime. If the test succeeds you are dealing with a prime (with extremely high probability). If the test fails, you can be certain that you are not dealing with a prime.

Go ahead - test any odd number!