1.28
练习 1.28： 费马检查的一种不会被欺骗的变形称为 Miller-Rabin 检查（Miller 1976；Rabin 1980），它来源于费马小定理的一个变形。这一变形断言，如果n是素数，a是任何小于n的整数，则a的（n-1）次幂与1模n同余。要用Miller-Rabin检查考察数n的素性，我们应随机地取一个数a < n并用过程 expmod 求a的(n-1)次幂对n的模。然而，在执行 expmod 中的平方步骤时，我们需要查看是否遇到了“1取模n的非平凡平方根”，也就是说，是不是存在不等于1或者n-1的数，其平方根取模n等于1。可以证明，如果1的这种非平凡平方根存在，那么n就不是素数。还可以证明，如果n是非素数的奇数，那么，至少有一半的数a < n，按照这种方式计算 an-1，将会遇到1取模n的非平凡平方根。这也是Miller-Rabin检查不会受骗的原因。请修改expmod过程，让它在发现1的非平凡平方根时报告失败，并利用它实现一个类似于fermat-test的过程，完成Miller-Rabin检查。通过检查一些已知素数和非素数的方式考验你的过程。提示：送出失败信号的一种简单方式就是让它返回 0。
修改后的expmod：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (xsquare (expmod base (/ exp 2) m) m)
m)
)
(else
(remainder (* base (expmod base (- exp 1) m))
m)
)
)
)
(define (xsquare x n) (if (non-trival-sqrt-exists? n) 0 (* x x)))
(define (non-trival-sqrt-exists? n) (non-trival-sqrt-test n 2))
(define (non-trival-sqrt-test n cur)
(if (>= cur (- n 1)) #f
(if (= (remainder (* cur cur) n) 1)
#t
(non-trival-sqrt-test n (+ cur 1))
)
)
)
(newline)
(expmod 2 3 7)
(newline)
(expmod 3 2 8)
(newline)
(expmod 3 8 8)
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)
)
)
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a)
)
(try-it (+ 1 (random (- n 1))))
)
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)
)
)
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a)
)
(try-it (+ 1 (random (- n 1))))
)
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (fast-prime? n 5)
(report-prime n (- (runtime) start-time)) #f))
(define (report-prime n elapsed-time)
(newline)
(display n)
(display " *** ")
(display elapsed-time)
(display ", 它的 \\log{n} 倍时间是 ")
(display (* elapsed-time (log elapsed-time)))
)
(define (timed-prime-test-between n1 n2 found)
(if (timed-prime-test n1)
(if (or (> found 1) (> n1 n2))
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 (+ found 1))
)
(if (> n1 n2)
(display " 测试结束！ ")
(timed-prime-test-between (+ n1 1) n2 found)
)
)
)
(newline)
(display "修改后的费马检查表现如下：")
(newline)
(display "大于 1000 的三个最小素数：")
(timed-prime-test-between 1001 9999 0)
(newline)
(newline)
(display "用carmichale数验证效果：")
(fermat-test 561)
(fast-prime? 561 200)
可以对比练习 1.27，那个版本的 expmod 会导致 561 被识别为素数，但是在这个版本里，它不会。