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
```