Probablistic primality test based on SICP 1.2.6

prime.scm

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (carmichael-test n)
  (define (iter a n)
    (cond ((= a n) #t)
          ((= (expmod a n n) a) (iter (+ a 1) n))
          (else #f)))
  (iter 1 n))

(define (miller-rabin-test n)
  (define (miller-rabin-expmod base exp m)
    (define (squaremod-with-check x)
      (define (check-nontrivial-sqrt1 x square)
        (if (and (= square 1)
                 (not (= x 1))
                 (not (= x (- m 1))))
            0
            square))
      (check-nontrivial-sqrt1 x (remainder (square x) m)))
    (cond ((= exp 0) 1)
          ((even? exp) (squaremod-with-check (miller-rabin-expmod base
                                                                  (/ exp 2)
                                                                  m)))
          (else
           (remainder (* base (miller-rabin-expmod base
                                                   (- exp 1)
                                                   m))
                      m))))
  (define (try-it a)
    (=
      (miller-rabin-expmod a
                           (- n 1)
                           n)
      1))
  (try-it (+ 1 (random (- n 1)))))