Miller-Rabin algorithm for testing for primes

miller-rabin.rkt

#lang racket

; modified expmod used in Miller-Rabin test that returns
; '(0 . #t) on discovering a non-trivial square root of
; 1 modulo n
(define (mr-expmod base exp m)
  (cond ((= exp 0) (cons 1 false))
        ((even? exp)
         (let ((res (mr-expmod base (/ exp 2) m)))
           (if (cdr res) res
               (let ((tmp (remainder (square (car res)) m)))
                 (if (and (= tmp 1)
                          (not (= (car res) (- m 1))) ; non-trivial: != m - 1
                          (not (= (car res) 1)))      ; non-trivial: != 1
                     (cons 0 true)
                     (cons tmp false))))))
        (else
         (let ((res (mr-expmod base (- exp 1) m)))
           (if (cdr res) res
               (cons (remainder (* base (car res)) m)
                     false))))))

; Miller-Rabin test for given n against a randomly-picked 
(define (mr-test n)
  (define (try-it a)
    (let ((res (mr-expmod a (- n 1) n)))
      (or (not (cdr res))
          (eq? (car res) 1))))
  (try-it (+ 1 (random (- n 1)))))

(define (mr-prime? n)
  (define max-tries 10)  ; try 10 times
  (define (worker times)
    (cond ((= 0 times) true)
          ((mr-test n) (worker (- times 1)))
          (else false)))
  (if (= n 1) false
      (worker max-tries)))