SICP 练习 1.28：Miller-Rabin 检验中的假阴性
SICP exercise 1.28: false negatives in the Miller-Rabin test
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.
(define (fast-prime? n)
(define (fast-prime-iter n counter)
(cond ((= counter 1) #t) ; There is no need to check 1
((miller-rabin-test n counter)
(fast-prime-iter n (- counter 1)))
(else
(newline)
(display counter)
#f)))
(fast-prime-iter n (- n 2)))
(define (miller-rabin-test n a)
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(nontrivial-square-root?
(remainder (square (expmod base (/ exp 2) m))
m)))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(= (expmod a (- n 1) n) 1))
(define (nontrivial-square-root? val)
(if (= val 1)
0
val))
我的想法是用程序nontrivial-square-root?过滤掉那些所谓的"nontrivial square roots of 1 modulo n"。如果 (remainder (square (expmod base (/ exp 2) m)) m) 为 1，则返回 0，在这种情况下，(expmod base (/ exp 2) m) 的平方必须等于 1 模 n（这是因为 m 始终等于 n), 使其成为一个非平凡的平方根。
虽然 nontrivial-square-root? 确实过滤掉了 561、1105、1729、2465、2821 和 6601 等卡迈克尔数，但据报道 7 和 13 等素数也是合数。
是什么导致了这些假阴性？
引用中用粗体标出的重要部分：
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
因此，在平方和取余之前，您必须检查参数是否不是 1 或 n - 1。例如，如果您调用 (miller-rabin-test 5 3)，就会发生这种情况。执行递归后，您会注意到有一个调用 (nontrivial-square-root? (remainder (square 4) 5))，其计算结果为 (nontrivial-square-root? 1)。但是，5 仍然可以是素数，因为 4 是 5 - 1。
因此在平方部分，您可以调用以下函数：
(define (sqrmod-with-check val n)
(let ((sqrmod (remainder (square val) n)))
(cond ((or (= val (- n 1)) (= val 1)) sqrmod)
((= sqrmod 1) 0)
(else sqrmod))))
参数是 expmod 调用和 m。这将为您计算平方和余数，除非我们找到 1 模 n 的非平凡平方根，当它 returns 0 时。我将它分为三个条件，而不是两个，只是因为可读性。
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.
(define (fast-prime? n)
(define (fast-prime-iter n counter)
(cond ((= counter 1) #t) ; There is no need to check 1
((miller-rabin-test n counter)
(fast-prime-iter n (- counter 1)))
(else
(newline)
(display counter)
#f)))
(fast-prime-iter n (- n 2)))
(define (miller-rabin-test n a)
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(nontrivial-square-root?
(remainder (square (expmod base (/ exp 2) m))
m)))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(= (expmod a (- n 1) n) 1))
(define (nontrivial-square-root? val)
(if (= val 1)
0
val))
我的想法是用程序nontrivial-square-root?过滤掉那些所谓的"nontrivial square roots of 1 modulo n"。如果 (remainder (square (expmod base (/ exp 2) m)) m) 为 1，则返回 0，在这种情况下，(expmod base (/ exp 2) m) 的平方必须等于 1 模 n（这是因为 m 始终等于 n), 使其成为一个非平凡的平方根。
虽然 nontrivial-square-root? 确实过滤掉了 561、1105、1729、2465、2821 和 6601 等卡迈克尔数，但据报道 7 和 13 等素数也是合数。
是什么导致了这些假阴性？
引用中用粗体标出的重要部分：
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
因此，在平方和取余之前，您必须检查参数是否不是 1 或 n - 1。例如，如果您调用 (miller-rabin-test 5 3)，就会发生这种情况。执行递归后，您会注意到有一个调用 (nontrivial-square-root? (remainder (square 4) 5))，其计算结果为 (nontrivial-square-root? 1)。但是，5 仍然可以是素数，因为 4 是 5 - 1。
因此在平方部分，您可以调用以下函数：
(define (sqrmod-with-check val n)
(let ((sqrmod (remainder (square val) n)))
(cond ((or (= val (- n 1)) (= val 1)) sqrmod)
((= sqrmod 1) 0)
(else sqrmod))))
参数是 expmod 调用和 m。这将为您计算平方和余数，除非我们找到 1 模 n 的非平凡平方根，当它 returns 0 时。我将它分为三个条件，而不是两个，只是因为可读性。