按照要求，先在 expmod 中增加对非平凡方根的检测：
;;; 28-expmod.scm
(load "28-nontrivial-square-root.scm")
(define (expmod base exp m)
(cond ((= exp 0)
1)
((nontrivial-square-root? base m) ; 新增
0) ;
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
nontrivial-square-root 进行非平凡方根检查，看看是否有一个数 \(a\) ，它既不等于 \(1\) ，也不等于 \(n - 1\) ，但它的平方取模 \(n\) 等于 \(1\) ：
;;; 28-nontrivial-square-root.scm
(define (nontrivial-square-root? a n)
(and (not (= a 1))
(not (= a (- n 1)))
(= 1 (remainder (square a) n))))
我们还需要一个函数，它接受一个参数 \(n\) ，生成大于 \(0\) 小于 \(n\) 的随机数。
因为系统提供的 random 函数可以保证随机值小于 \(n\) ，因此我们自己的随机函数只要确保随机数不为 \(0\) 即可：
;;; 28-non-zero-random.scm
(define (non-zero-random n)
(let ((r (random n)))
(if (not (= r 0))
r
(non-zero-random n))))
接下来就该写 Miller-Rabin 测试的主体了：
;;; 28-miller-rabin-test.scm
(load "28-expmod.scm")
(load "28-non-zero-random.scm")
(define (Miller-Rabin-test n)
(let ((times (ceiling (/ n 2))))
(test-iter n times)))
(define (test-iter n times)
(cond ((= times 0)
#t)
((= (expmod (non-zero-random n) (- n 1) n)
1)
(test-iter n (- times 1)))
(else
#f)))
因为在计算 \(a^{n-1}\) 时只有一半的几率会遇到 \(1\) 取模 \(n\) 的非平凡方根，因此我们至少要执行测试 \(n/2\) 次才能保证测试结果的准确性（是的， Miller-Rabin 测试也是一个概率函数）。
另外，因为当 \(n\) 为奇数时， \(n/2\) 会计算出有理数，所以在 Miller-Rabin-test 过程中使用了 ceiling 函数对 \(n/2\) 的值进行向上取整。
使用书本 35 页注释 47 上的 Carmichael 数来进行 Miller-Rabin 测试，可以证实这些 Carmichael 数无法通过 Miller-Rabin 测试：
1 ]=> (load "28-miller-rabin-test.scm")
;Loading "28-miller-rabin-test.scm"...
; Loading "28-expmod.scm"...
; Loading "28-nontrivial-square-root.scm"... done
; ... done
; Loading "28-non-zero-random.scm"... done
;... done
;Value: test-iter
1 ]=> (Miller-Rabin-test 561)
;Value: #f
1 ]=> (Miller-Rabin-test 1105)
;Value: #f
1 ]=> (Miller-Rabin-test 1729)
;Value: #f
1 ]=> (Miller-Rabin-test 2465)
;Value: #f
1 ]=> (Miller-Rabin-test 2821)
;Value: #f
1 ]=> (Miller-Rabin-test 6601)
;Value: #f
只有真正的素数才会被识别出来：
1 ]=> (Miller-Rabin-test 7)
;Value: #t
1 ]=> (Miller-Rabin-test 17)
;Value: #t
1 ]=> (Miller-Rabin-test 19)
;Value: #t
See also