SICP Exercise 1.28

Question

One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test. 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.

Answer

(define (square x) (* x x))

(define (ntsqrt? a n)
  (cond ((or (= a 1) (= a (- n 1))) false)
        ((= (remainder (square a) n) 1) true)
        (else false)))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (cond ((ntsqrt? exp m) 0)
           (else (remainder (square (expmod base (/ exp 2) m))
                      m))))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (try-it a n)
  (cond ((= 1 (expmod a (- n 1) n)) true)
        (else false)))

(define (millerrabin? n)
  (define (try-millerrabin n counter)
    (cond ((= counter 0) true)
          ((try-it counter n) (try-millerrabin n (- counter 1)))
          (else false)))
  (try-millerrabin n (- n 1)))

(display "These are non-primes and should be false:") (newline)
(millerrabin? 100)
(millerrabin? 34)
(millerrabin? 2001)
(millerrabin? 777)

(display "These are Carmichael numbers and should be false:") (newline)
(millerrabin? 561)
(millerrabin? 1105)
(millerrabin? 1729)
(millerrabin? 2465)
(millerrabin? 2821)
(millerrabin? 6601)

(display "These are primes and should be true:") (newline)
(millerrabin? 17)
(millerrabin? 1999)
(millerrabin? 97)
(millerrabin? 3)

Results:

These are non-primes and should be false:
#f
#f
#f
#f
These are Carmichael numbers and should be false:
#f
#f
#f
#f
#f
#f
These are primes and should be true:
#t
#t
#t
#t