; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/28/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.28
;; 修改expmod中remaider和square为带有额外检查的remainder-check
(define (expmod base exp m)
(define (remainder-check x)
(define result (remainder (square x) m))
(if (and (= result 1)
(not (or (= x 1) (= x (- m 1)))))
0
result))
(cond ((= exp 0) 1)
((even? exp) (remainder-check (expmod base (/ exp 2) m)))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
;; miller-rabin测试主函数，使用题1.27中的测试模式，即测试所有可能的a
(define (miller-rabin-test n)
(define (try-it a)
(cond ((= a 0) #t)
((= (expmod a (- n 1) n) 1) (try-it (- a 1)))
(else #f)))
(try-it (- n 1)))
;; Test-it
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (miller-rabin-test 17)
;; #t
;; > (miller-rabin-test 1013)
;; #t
;; > (miller-rabin-test 1017)
;; #f
;; > (miller-rabin-test 6691)
;; #t
;; > (miller-rabin-test 561) ;; 以下为Carmichael数的测试，符合预期
;; #f
;; > (miller-rabin-test 1105)
;; #f
;; > (miller-rabin-test 1729)
;; #f
;; > (miller-rabin-test 2465)
;; #f
;; > (miller-rabin-test 2821)
;; #f
;; > (miller-rabin-test 6601)
;; #f
;; >