\$ cd ~

# 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))
(else
(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)
0
x))

(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)
#f
> (mr-test 1105)
#f
> (mr-test 1729)
#f
> (mr-test 2465)
#f
> (mr-test 2821)
#f