# Miller-Rabin test

One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if `n` is a prime number and `a` is any positive integer less than `n` , then a raised to the ( `n − 1` )st power is congruent to 1 modulo `n` . To test the primality of a number `n` by the Miller-Rabin test, we pick a random number `a < n` and raise a to the ( `n − 1` )st power modulo `n` using the `expmod` procedure. However, whenever we perform the squaring step in `expmod` , we check to see if we have discovered a ``nontrivial square root of 1 modulo `n` ,'' that is, a number not equal to 1 or `n − 1` whose square is equal to 1 modulo `n` . It is possible to prove that if such a nontrivial square root of 1 exists, then `n` is not prime. It is also possible to prove that if `n` is an odd number that is not prime, then, for at least half the numbers `a < n` , computing `a^(n − 1)` in this way will reveal a nontrivial square root of 1 modulo `n` . (This is why the Miller-Rabin test cannot be fooled.) Modify the `expmod` procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure `miller-rabin-test` analogous to `fermat-test` . Check your procedure by testing various known primes and non-primes. Hint: One convenient way to make `expmod` signal is to have it return 0.