## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.28

## Problem

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 *a* < *n* and
raise *a* to the (*n* - 1)st power modulo *n* using the `expmod` procedure. However, whenever we perform the squaring step in `expmod`, we check to see if we have discovered a "nontrivial square root of 1 modulo n,"
that is, a number not equal to 1 or *n* - 1 whose square is equal to 1 modulo *n*. It is possible to prove that if
such a nontrivial square root of 1 exists, then *n* is not prime. It is also possible to prove that if *n* is an odd
number that is not prime, then, for at least half the numbers *a* < *n*, computing *a*^{n − 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.

## Solution

Here's the `expmod` procedure modified for the Miller-Rabin test.
Note that 1 modulo *n* is 1 for all *n*>1.

(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (check-nontrivial-sqrt (expmod base (/ exp 2) m) m)) (else (remainder (* base (expmod base (- exp 1) m)) m))))

This helper procedure returns 0 if *n* is a non-trival square root of
1 modulo *m*, otherwise it returns the square of *n* modulo *m*. This
procedure is a lot easier to write efficiently if we cheat a bit and
use the `let` special form, which isn't introduced until section
1.3.2 of the text.

(define (check-nontrivial-sqrt n m) (let ((x (remainder (square n) m))) (if (and (not (= n 1)) (not (= n (- m 1))) (= x 1)) 0 x)))

Here's a procedure which tests a number for primality via the Miller-Rabin test. Note that the text states that one of the proofs only applies to odd numbers, so the prime test checks for even numbers (excepting 2, which is prime) before employing the Miller-Rabin test.

(define true #t) (define false #f) (define (miller-rabin-test n a) (= (expmod a (- n 1) n) 1)) (define (prime? n) (cond ((= n 2) #t) ((even? n) #f) (else (prime-helper n (- n 1))))) (define (prime-helper n a) (cond ((= a 0) #t) ((miller-rabin-test n a) (miller-rabin-test n (- a 1))) (else #f)))

Tests:

(prime? 1)

*Output:*

`
`

#t

(prime? 2)

*Output:*

`
`

#t

(prime? 3)

*Output:*

`
`

#t

(prime? 4)

*Output:*

`
`

#f

(prime? 5)

*Output:*

`
`

#t

(prime? 7)

*Output:*

`
`

#t

(prime? 9)

*Output:*

`
`

#f

(prime? 11)

*Output:*

`
`

#t

(prime? 13)

*Output:*

`
`

#t

(prime? 15)

*Output:*

`
`

#f

(prime? 109)

*Output:*

`
`

#t

(prime? 111)

*Output:*

`
`

#f

Now check some Carmichael numbers. All of these tests should return `#f`.

(prime? 561)

*Output:*

`
`

#f

(prime? 1105)

*Output:*

`
`

#f

(prime? 1729)

*Output:*

`
`

#f

(prime? 2465)

*Output:*

`
`

#f

(prime? 2821)

*Output:*

`
`

#f

(prime? 6601)

*Output:*

`
`

#f