Exercise 1.28: One variant of the Fermat test that cannot be fooled is called the Miller-Rabin
test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat’s Little Theorem,
which states that if n is a prime number and a is any positive integer less than n,
then a raised to the (n - 1)st power is congruent to 1 modulo n. To test the primality
of a number n by the Miller-Rabin test, we pick a random number an-1 in this way will
reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be
fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1,
and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check
your procedure by testing various known primes and non-primes.
Hint: One convenient way to make expmod signal is to have it return 0.
(define (miller-rabin-test n)
(define (random n) (random-integer n))
(define (expmod base exp m)
(define (square-mod x) (remainder (* x x) m))
(define (square-signal-root x)
(if (and
(not (or (= 1 x) (= x (- m 1))))
(= 1 (square-mod x)))
0
(square-mod x)))
(cond ((= exp 0) 1)
((even? exp) (square-signal-root (expmod base (/ exp 2) m)))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(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)))
Carmichael Numbers: 561, 1105, 1729, 2465, 2821, 6601
Primes: 2, 3, 10169, 31337, 1000249, 382176531747930913347461352433
Non-primes: 6, 27, 49, 1024
> (fast-prime? 561 10)
#f
> (fast-prime? 1105 10)
#f
> (fast-prime? 1729 10)
#f
> (fast-prime? 2465 10)
#f
> (fast-prime? 2821 10)
#f
> (fast-prime? 6601 10)
#f
> (fast-prime? 2 10)
#t
> (fast-prime? 3 10)
#t
> (fast-prime? 10169 10)
#t
> (fast-prime? 31337 10)
#t
> (fast-prime? 1000249 10)
#t
> (fast-prime? 382176531747930913347461352433 10)
#t
> (fast-prime? 6 10)
#f
> (fast-prime? 27 10)
#f
> (fast-prime? 49 10)
#f
> (fast-prime? 1024 10)
#f