# Exercise 1.28 of SICP

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