24 lines
634 B
Scheme
24 lines
634 B
Scheme
#lang sicp
|
|
|
|
(define (square n) (* n n))
|
|
|
|
(define (expmod-aux base exp n acc)
|
|
(define sqr (remainder (square base) n))
|
|
(cond ((= 0 exp) acc)
|
|
((even? exp)
|
|
(if (and (= sqr 1)
|
|
(not (= base 1))
|
|
(not (= base (- n 1))))
|
|
0
|
|
(expmod-aux sqr (/ exp 2) n acc)))
|
|
(else (expmod-aux base (- exp 1) n (remainder (* acc base) n)))))
|
|
|
|
(define (expmod base exp n)
|
|
(expmod-aux base exp n 1))
|
|
|
|
(define (miller-rabin-test n)
|
|
(define (try-it a)
|
|
(= (expmod a (- n 1) n) 1))
|
|
(if (and (even? n) (not (= 2 n)))
|
|
#f
|
|
(try-it (+ 1 (random (- n 1))))))
|