SICP問題1.28 Miller-Rabinテスト

; 1.28
(use srfi-27)

(define (expmod base exp m)
  (cond [(= exp 0) 1]
	[(even? exp) (miller-rabin (expmod base (/ exp 2) m) m)]
	[else (remainder (* base (expmod base (- exp 1) m)) m)]))

(define (miller-rabin a m)
  (if (and (not (= a 1))
	   (not (= a (- m 1)))
	   (= (remainder (square a) m) 1))
      0
      (remainder (square a) m)))

(define (miller-rabin-test n)
  (let ((try-it (lambda (a)
                    (= (expmod a (- n 1) n) 1))))
    (try-it (random-integer n))))

(define (miller-rabin-prime? n times)
  (cond [(= times 0) #t]
	[(miller-rabin-test n) (miller-rabin-prime? n (- times 1))]
	[else #f]))