SICP 問題1.28

(define (miller-rabin-test n)
  (define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (let* ((tmp (expmod base (/ exp 2) m))
                  (tmp2 (remainder (square tmp) m)))
             (if (and (< 1 tmp (- n 1)) ;; 1でも(n-1)でもなく，かつ
                      (= 1 tmp2)) ;; nを法として１の自明でない平方根の時は０を返す
                 0
                 tmp2)))
          (else (remainder (* base (expmod base (- exp 1) m)) m))))
  (define (try-it a)
    (= 1 (expmod a (- n 1) n)))
  (try-it (+ 1 (random-integer (- n 1)))))

gosh> (miller-rabin-test 561)
#f
gosh> (miller-rabin-test 1105)
#t
gosh> (miller-rabin-test 1105)
#f
gosh> (miller-rabin-test 1729)
#f
gosh> (miller-rabin-test 2465)
#f
gosh> (miller-rabin-test 2821)
#f
gosh> (miller-rabin-test 6601)
#f