Miller-Rabin test (SICP 1.28)

Question

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 less than 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.

This is what I have so far.

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

(define (expmod-signal b n m)
  (define (check a)
    (and (not (= a 1))
         (not (= a (- n 1)))
         (= (square a) (remainder 1 n))))
  (cond ((= n 0) 1)
        ((check b) 0)
        ((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
        (else (remainder (* b (expmod-signal b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? n a)
    (or (= n 0) (not (= n a))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n) a) #f)
          (else (try (- a 1)))))
  (try (- n 1)))

I think I implemented miller-rabin correctly but I don't understand how the modified expmod is supposed to work. Do you check the number before the square or after the square? I don't know from reading the question.

Answer 1

I solved this by using the original definition of expmod inside of expmod-signal. Somewhere in my tests, expmod-signal was naturally returning zero and messing with the tests. I misunderstood the check function, "whose square is equal to 1 modulo n" means check if a^2 % m = 1. The way this check function works is to return 0 if the argument is a non-trivial square root of 1 mod n, and return the argument otherwise. If it returns zero, the zero propagates through the remainder of expmod-signal and is returned.

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

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

(define (expmod-signal b n m)
  (define (check a)
    (if (and (not (= a 1))
             (not (= a (- n 1)))
             (= (remainder (square a) n) 1))
        0
        a))
  (cond ((= n 0) 1)
        ((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
        (else (remainder (* b (expmod b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? a)
    (or (= a 0) (not (= a 1))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n)) #f)
          (else (try (- a 1)))))
  (try (- n 1)))