**Exercise 1.28:** One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat’s Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n – 1)st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number a

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
(define (miller-rabin-test n) (define (random n) (random-integer n)) (define (expmod base exp m) (define (square-mod x) (remainder (* x x) m)) (define (square-signal-root x) (if (and (not (or (= 1 x) (= x (- m 1)))) (= 1 (square-mod x))) 0 (square-mod x))) (cond ((= exp 0) 1) ((even? exp) (square-signal-root (expmod base (/ exp 2) m))) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (try-it a) (= (expmod a (- n 1) n) 1)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (cond ((= times 0) #t) ((miller-rabin-test n) (fast-prime? n (- times 1))) (else #f))) |

Carmichael Numbers: 561, 1105, 1729, 2465, 2821, 6601

Primes: 2, 3, 10169, 31337, 1000249, 382176531747930913347461352433

Non-primes: 6, 27, 49, 1024

> (fast-prime? 561 10)

*#f*

> (fast-prime? 1105 10)

*#f*

> (fast-prime? 1729 10)

*#f*

> (fast-prime? 2465 10)

*#f*

> (fast-prime? 2821 10)

*#f*

> (fast-prime? 6601 10)

*#f*

> (fast-prime? 2 10)

*#t*

> (fast-prime? 3 10)

*#t*

> (fast-prime? 10169 10)

*#t*

> (fast-prime? 31337 10)

*#t*

> (fast-prime? 1000249 10)

*#t*

> (fast-prime? 382176531747930913347461352433 10)

*#t*

> (fast-prime? 6 10)

*#f*

> (fast-prime? 27 10)

*#f*

> (fast-prime? 49 10)

*#f*

> (fast-prime? 1024 10)

*#f*