Thursday, July 8, 2010

ミラー・ラビン素数判定

SICPの例題1.28のミラー・ラビン素数判定。
・・・一応カーマイケル数の判定にも成功するけど、コレでいいのかどうか・・・
(追記:修正しました)

同じ計算を繰り返しているところがあって、効率はあまりよくない。
一番底で-1かどうかチェックするだけでいいのか。

(define (square x) (* x x))

(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 (miller-rabin-test n)
  (define (test-iter a b)
    (if (odd? b)
        (= (expmod a b n) 1)
        (or (test-iter a (/ b 2))
            (and (= (expmod a b n) 1)
                 (= (expmod a (/ b 2) n) (- n 1))))))
  (test-iter (+ 1 (random (- n 1))) (- n 1)))

(define (good-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (good-prime? n (- times 1)))
        (else false)))

No comments: