[archives] [homepage]

Problem 1.28
Friday, August 23, 2019; ago; Download .md

SICP Exercise 1.28

By Miller-Rabin test, we should check for: $$ a^{n-1} \equiv 1(mod n) $$

The procedures themselves were easy to build. The question has a big hint:

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.

(define (mr-expmod a n m)
  (cond ((= n 0) 1)
        ((even? n)
         (remainder (square (zero-if-ntsq (mr-expmod a (/ n 2) m) m)) m))
         (remainder (* a (zero-if-ntsq (mr-expmod a (- n 1) m) m)) m))))

(define (zero-if-ntsq x n)
  (if (non-trivial-sqrt? x n)
(define (non-trivial-sqrt?  num n)
  (and (not (= num 1))
       (not (= num (- n 1)))
       (= (remainder (square num) n) 1)))

(define (mr-test n)
  (define (runner a)
    (= (mr-expmod a (- n 1) n) a))
  (runner (+ 1 (random (- n 1)))))

Running the test on a few Carmichael numbers:

> (mr-test 561)
> (mr-test 1105)
> (mr-test 1729)
> (mr-test 2465)
> (mr-test 2821)