As mentioned in the problem we need to check in the squaring step if the number that we are squaring is a non-trivial square root of n. I will paste here again the corresponding part of the problem:
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.
I have made the corresponding changes while squaring in
expmode procedure. I have written a new procedure
check that checks for the
‘‘nontrivial square root of $1\;modulo \; n$,’’ as described in problem. It uses
let expression to avoid computing that expression twice.
Also note that if the number is prime than
expmod process will return 1 as per Miller-Rabin test. Thus for the other case I am returning 0
as also suggested in the book.
I have also modified the carmichael-test procedure and checked all the carmichael-numbers we were given and the procedure correctly returns false for all these numbers. Also I checked for all prime numbers discovered in previous exercises and test runs as expected.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #lang sicp (#%require (only racket/base random)) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (check (expmod base (/ exp 2) m) m) ) (else (remainder (* base (expmod base (- exp 1) m)) m)) ) ) (define (check n m) (let ( (rs (remainder (square n) m)) ) (if (and (not (or (= n 1) (= n (- m 1)) ) ) (= rs 1) ) 0 rs ) ) ) (define (square x) (* x x)) (define (miller-rabin-test n) (define (try-it a) (= (expmod a (- n 1) n) 1)) (try-it (+ 1 (random (- n 1))))) (define (carmichael-test num) (define (carmi-iter n a) (if (= n a) true (if (= (expmod a (- n 1) n) 1) (carmi-iter n (+ a 1)) false ) ) ) (carmi-iter num 1) )