Exercise 1.28: 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 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.
练习 1.28：费马检验有一个不会被愚弄的变体，称为 Miller-Rabin 检验（Miller 1976；Rabin 1980）。它从费马小定理的一个替代形式出发：若 n 是素数，a 是任意小于 n 的正整数，则 a 的 (n−1) 次幂模 n 同余于 1。用 Miller-Rabin 检验来检验数 n 的素性时，我们随机选取一个 a < n，利用 expmod 过程计算 a 的 (n−1) 次幂模 n 的结果。然而，每当在 expmod 中执行平方步骤时，我们检查是否发现了"1 模 n 的非平凡平方根 (nontrivial square root of 1 modulo n)"，即一个不等于 1 也不等于 n−1、其平方模 n 等于 1 的数。可以证明，若这样的非平凡平方根存在，则 n 不是素数；也可以证明，若 n 是奇合数，则对至少一半的 a < n，以此方式计算 a^(n−1) 会揭示出 1 模 n 的非平凡平方根。（这正是 Miller-Rabin 检验不会被愚弄的原因。）请修改 expmod 过程，使其在发现 1 的非平凡平方根时发出信号，并据此实现类似 fermat-test 的 Miller-Rabin 检验过程。用各种已知的素数和合数检验你的过程。提示：让 expmod 返回 0 是一种方便的发信号方式。