Solution to SICP 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)))))

Share this:

Like this: