3
\$\begingroup\$

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 < 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 < 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)
             (> 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?

\$\endgroup\$
1
\$\begingroup\$

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)
             (> 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 (> 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.