1 ;; 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 modulo 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 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. 
2 
3 ;; calculate base^exp modulo m but return 0 if nontrivial square root of 1 modulo n is discovered
4 (define (expmod base exp m)
5   (cond ((= exp 0) 1)
6 	((even? exp)
7 	 (let ((modulo-sqrt (expmod base (/ exp 2) m)))
8 	   (let ((modulo-sqr (remainder (square modulo-sqrt) m)))
9 	     (if (and (not (or (= modulo-sqrt 1) (= modulo-sqrt (- m 1))))
10 		      (= modulo-sqr 1))
11 		 0
12 		 modulo-sqr))))
13 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
14 
15 (define (miller-rabin-test n)
16   (define (try-it a)
17     (= (expmod a (- n 1) n) 1))
18   (try-it (+ 1 (random (- n 1)))))
19 
20 (define (miller-rabin-prime? n times)
21   (cond ((= times 0) #t)
22         ((miller-rabin-test n) (miller-rabin-prime? n (- times 1)))
23         (else #f)))
24 
25 (define (test-case actual expected)
26   (load-option 'format)
27   (newline)
28   (format #t "Actual: ~A Expected: ~A" actual expected))
29 
30 (define (quick-mr-prime? n)
31   (miller-rabin-prime? n 2500))
32 
33 ;;(test-case (quick-mr-prime? 2) #t)
34 (test-case (quick-mr-prime? 3) #t)
35 (test-case (quick-mr-prime? 4) #f)
36 (test-case (quick-mr-prime? 5) #t)
37 (test-case (quick-mr-prime? 6) #f)
38 (test-case (quick-mr-prime? 7) #t)
39 (test-case (quick-mr-prime? 8) #f)
40 (test-case (quick-mr-prime? 9) #f)
41 
42 ;; (list-primes 10000)
43 
44 ;; Carmichael Numbers
45 (test-case (quick-mr-prime? 561) #f)
46 (test-case (quick-mr-prime? 1105) #f)
47 (test-case (quick-mr-prime? 1729) #f)
48 (test-case (quick-mr-prime? 2465) #f)
49 (test-case (quick-mr-prime? 2821) #f)
50 (test-case (quick-mr-prime? 6601) #f)