Solution to SICP Exercise 1.28

Structure and Interpretation of Computer Programs

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