#
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.