Here are details of the Miller-Rabin primality test, which is a probabilistic test that gives a high confidence that a number is prime in a fast computation which does not yield the factors. It is widely used in public key cryptographic systems to test prime factors used to create encryption keys. It can be made deterministic for integers as large as 64 bits by testing only 12 witness numbers.
Impressive. Learned something new today. Algorithms, yum!