src/sicp/ex1_28.clj

   1 (ns sicp.ex1_28
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5
   6 ;;; exercise 1.28
   7 (defn expmod2 [base exp m]
   8   (cond (= exp 0) 1
   9         (even? exp) (square-test (expmod2 base (/ exp 2) m) m)
  10         :else (rem (* base (expmod2 base (dec exp) m))
  11                    m)))
  12
  13 (defn square-test [x m]
  14   (if (and (not (or (= x 1) (= x (- m 1))))
  15            (= (rem (square x) m) 1))
  16     0
  17     (rem (square x) m)))
  18
  19 (defn miller-rabin-test [n]
  20   (try-it (+ 2 (rand-int (- n 2)))
  21           n))
  22
  23 (defn try-it [a n]
  24   (= (expmod2 a (- n 1) n) 1))
  25
  26 (comment
  27   "If the random number generated (a) is 1, then this returns false
  28    positives. So generate random numbers between 2 and n-1. (is this
  29    assumption correct?) "
  30 )