SICP exercise 1.28 - miller-rabin primality test part II This is a follow-up to SICP exercise 1.28 - miller-rabin primality test.


  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 \mod n\$. 
  
  To test the
  primality of a number \$n\$ by the Miller-Rabin test, we pick a random
  number \$a &lt; n\$ and raise \$a\$ to the \$n-1\$-st power \$\mod 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
\mod n\$,” that is, a number not equal to \$1\$ or \$n-1\$ whose square is
  equal to \$1 \mod 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 &lt; n\$, computing \$a^{n-1}\$ in this way will reveal a
  nontrivial square root of \$1 \mod 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\$.


Changes:


Avoid redundant modulo computations
Corrected use of base modulo n in expmod to avoid computing extremely large numbers
for any number greater than 2, prevent use of 1 as random base in the expmod because I think it will always return true when the random chosen number is 1. Is this needed?


While fixing my previous code, I already saw a procedure with recursive process that fixed all my problems above. I can't really call it my own, so to keep the spirit of the exercise, I rewrote my horrible recursive process code and turned it into a procedure that generates an iterative process.

Please review my code.

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

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

(define (miller-rabin-test n)
  (define (try-it a)
    (if (and (= a 1)
             (&gt; n 2))
        (miller-rabin-test n)
        (= (expmod a (- n 1) n) 1)))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n)
         (fast-prime? n (- times 1)))
        (else false)))


Did I improve on my previous code? Did I follow all the requirements in the exercise this time? How can I improve this code and make it faster?
Stylistically, I'd write it this way:

;; expmode b e m = b^e modulo m
(define (expmod b e m)
  (define (expmod-iter acc b e)      ; iterative accumulation
    (define bsq (remainder (* b b) m))
    (cond ((= e 0) acc)
          ((and (not (= b (- m 1)))
                (not (= b 1))
                (= bsq 1))
           0)
          ((even? exp)
           (expmod-iter acc bsq (/ e 2)))
          (else
           (expmod-iter (remainder (* acc b) m)
                        b
                        (- e 1)))))
  (expmod-iter 1 b e))               ; initial accumulator = 1

(define (miller-rabin-test n)
  (define (try-it b)
    (if (and (= b 1)
             (&gt; n 2))
        (miller-rabin-test n)
        (= (expmod b (- n 1) n) 
           1)))
  (try-it (random 1 n)))     

(define (fast-prime? n times)
  (or (= times 0)
      (and (&gt; times 0)
           (miller-rabin-test n)
           (fast-prime? n (- times 1)))))


You've corrected the error of not taking the remainder of the square.

There's no need to define a function square just to save one call to *.

You've converted your recursive expmod into iterative code; although I wouldn't call the former "horrible" since its complexity is only logarithmic, so recursion depth is kept in check.

Assuming you're using Racket, (+ 1 (random (- n 1))) can be written simply (random 1 n).

You've kept the awkward encoding for fast-prime? which is more naturally coded directly with the logical connectives.

Will think over some more with regards to its correctness, that you ask about.