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))