Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.28


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 and raise a to the st power modulo 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 ,’’ that is, a number not equal to or whose square is equal to . It is possible to prove that if such a nontrivial square root of 1 exists, then 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 ,’’ 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)
)