Code

#lang racket

(require "common.scm")

(define (next n) (if (= n 2) 3 (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (expmod1 base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (define x (expmod1 base (/ exp 2) m))
         (define x2 (remainder (square x) m))
         (if (and
              (= x2 1)
              (not (= x 1))
              (not (= x (- m 1))))
             0
             x2))
        (else
         (remainder (* base (expmod1 base (- exp 1) m))
                    m))))


(define (prime? n)
  (= n (smallest-divisor n)))

(define (mr-test n)
  (define (try-it a)
    (= (expmod1 a (- n 1) n) 1))
  (try-it (+ 1 (random (- (remainder n 4294967087) 1)))))

(define (mr-fast-prime? n times)
  (cond ((= times 0) true)
        ((mr-test n) (mr-fast-prime? n (- times 1)))
        (else false)))

; tests

(eq? (expmod 3 560 561) (expmod1 3 560 561))
(newline)
(mr-fast-prime? 561 100)
(mr-fast-prime? 1105 100)
(mr-fast-prime? 1729 100)
(mr-fast-prime? 2465 100)
(mr-fast-prime? 2821 100)
(newline)
(mr-fast-prime? 997 100)
(mr-fast-prime? 1999 100)

Output

#t

#f
#f
#f
#f
#f

#t
#t