Solution to Exercise 1.28:

`(define (square x)`

(* x x))

```
```(define (expmod-with-trivial-sqrt-check base exp m)

(cond ((= exp 0) 1)

((even? exp)

(let* ((intermediate (expmod-with-trivial-sqrt-check base (/ exp 2) m))

(squared-mod (remainder (square intermediate) m)))

(if (and (not (or (= intermediate 1) (= intermediate (- m 1))))

(= squared-mod 1))

0

squared-mod)))

(else

(remainder (* base (expmod-with-trivial-sqrt-check base (- exp 1) m))

m))))

`(define (miller-rabin-test n)`

(define (try-it a )

(= (expmod-with-trivial-sqrt-check a (- n 1) n) 1))

(try-it (+ 1 (random (- n 1)))))

Advertisements