1.27
练习 1.27： 证明脚注47中列出的Carmichael数确实能骗过费马检查。也就是说，写一个过程，它以整数n为参数，对每个a < n检查an是否与a模n同余。用你的过程去检查前面给出的那些Carmichael数。
角注47：能够骗过费马检查的数称为Carmichael数，我们对他们知之甚少，只知其非常罕见。在100 000 000之内有255个Carmichael数，其中最小的几个是561、1105、1729、2465、2821和6601.在检查很大的数是否为素数时，所用选择是随机的。撞上能欺骗费马检查的值的机会比宇宙射线导致计算机在执行“正确”算法中出错的机会还要小。对算法只考虑第一个因素而不考虑第二个因素恰好表现出数学与工程的不同。
(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 (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m)
)
(else
(remainder (* base (expmod base (- exp 1) m))
m)
)
)
)
(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 (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
m)
)
(else
(remainder (* base (expmod base (- exp 1) m))
m)
)
)
)
(define (test-carmichale n)
(start-carmichale-test n 1))
(define (start-carmichale-test n start)
(display start)
(display "^")
(display n)
(display " mod ")
(display n)
(display "=")
(display (expmod start n n))
(display " === ")
(display start)
(display " *** ")
(display start)
(display "^2 = ")
(display (* start start))
(display " mod ")
(display n)
(display " = ")
(display (remainder (* start start) n))
(newline)
(if (< start (- n 1))
(start-carmichale-test n (+ start 1))
(display "测试结束！")
)
)
(newline)
(display "检查 561 是否为 Carmichale 数 ：")
(newline)
(test-carmichale 561)
(newline)
(display "检查 1105 是否为 Carmichale 数 ：")
(newline)
(test-carmichale 1105)
(newline)
(display "检查 1729 是否为 Carmichale 数 ：")
(test-carmichale 1729)
(newline)
(display "检查 2465 是否为 Carmichale 数 ：")
(test-carmichale 2465)
(newline)
(display "检查 2821 是否为 Carmichale 数 ：")
(newline)
(display "检查 6601 是否为 Carmichale 数 ：")
(newline)