こんな感じかな。
(define (square x)
(* x x))
(define (expmod base ex m)
(cond ((= ex 0) 1)
((and (not (= base 1))
(not (= base (- m 1)))
(= (remainder (square base) m) 1)) 0)
((even? ex) (remainder (square (expmod base (/ ex 2) m)) m))
(else (remainder (* base (expmod base (- ex 1) m)) m))))
(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) #t)
((miller-rabin-test n) (fast-prime? n (- times 1)))
(else #f)))これからは行けそうにないので"独"書会に。
aがnより小さい任意の正の整数で、aが1でもn-1でもなくa^2 ≡ 1 (mod n)であるときnが素数でないことの証明はこれでいいのかな。
1 < a < n - 1としていい。
a^2 ≡ 1 (mod n) なので、 a^2 = mn + 1 とできる。 (m: 整数)
∴ n = (a^2 - 1)/m = (a + 1)(a - 1)/m.
ここでnが素数であると仮定すると、m = k(a+1) または m = k(a-1). (k: 自然数)
なら n = (a + 1)/k または n = (a - 1)/k. これはaの範囲と矛盾しているので仮定は誤り。
nは素数でない。
