Friday, July 9, 2010

ミラー・ラビン素数判定(修正)

昨日のプログラムの修正。
こっちの方が多分だいぶマシ。

(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)
        (or (= (expmod a b n) (- n 1)) (= (expmod a b n) 1))
        (or (test-iter a (/ b 2))
            (= (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: