SICPの問題を解こう15

問題 1.28

Fermat-testの欠点を補うMiller-Rabinテストを実装せよという問題。
そこでここで書かれている素数の性質についてちょっと見てみる。

   ... ①
  かつ1 < x < n-1を満たす整数xが存在すればnは素数ではない。

　証明
  
　①は上位の式と同義であり、x-1, x+1はそれぞれ
  [tex:0

どうやら一般的なMiller-Rabinテストはもう少し面倒臭い事をしているが、これはどうも1 < x < n-1の条件により簡易化していると思う。
あと、「だまされないテスト」とあるけどこれは語弊がありそう。「だまされる確率を下げることが出来るテスト」が正しいと思う。
※FermatテストはCarmichael数の場合何度テストをしようがだまされてしまうけど、Miller-Rabinテストの場合はテスト回数を増やせばだまされる確率が減る。
※このテストでやっている「素数ではない」というテスト1回では「1/2以上の確率で素数ではない」と言っているだけなのでtimes回テストをすれば「1-1/2^times以上の確率で素数ではない」と言っているだけ。もちろんのテストもしているので正確な確率は「1-1/2^times」より精度はいい。

ではコード

(use srfi-27)
(define (mr-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random-integer (- n 1)))))
(define (expmod base exp m)
  (define ex 0)
  (define re 0)
  (cond ((= exp 0) 1)
        ((even? exp)
         (set! ex (expmod base (/ exp 2) m))
         (set! re (remainder (square ex) m))
         (if (or (= ex 1) (= ex (- m 1)))
             re
             (if (= re 1)
                 0
                 re)))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
(define (square n) (* n n))