**Exercise 1.27:** Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether an is congruent to a modulo n for every a

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
(define (square n) (* n n)) (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 a) (define (try-it a) (= (expmod a n n) a)) (try-it a)) (define (fermat-prime? n times) (cond ((= times n) #t) ((fermat-test n times) (fermat-prime? n (+ times 1))) (else #f))) (define (test-prime? n) (fermat-prime? n 1)) |

Carmichael Numbers:
561: 3 11 17
1105: 5 13 17
1729: 7 13 19
2465: 5 17 29
2821: 7 13 31
6601: 7 23 41
> (test-prime? 561)
*#t*

> (test-prime? 1105)

*#t*

> (test-prime? 1729)

*#t*

> (test-prime? 2465)

*#t*

> (test-prime? 2821)

*#t*

> (test-prime? 6601)

*#t*

These number indeed fool the test. I will trace through a case where a=10 and n=561. I will leave the **remainder **procedure out to save text space but I will apply it as if it is there. I don’t think much is left out by applying **remainder **implicitly.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
(expmod 10 561 561) (* 10 (expmod 10 560 561) (* 10 (square (expmod 10 280 561))) (* 10 (square (square (expmod 10 140 561)))) (* 10 (square (square (square (expmod 10 70 561))))) (* 10 (square (square (square (square (expmod 10 35 561)))))) (* 10 (square (square (square (square (* 10 (expmod 10 34 561))))))) (* 10 (square (square (square (square (* 10 (square (expmod 10 17 561)))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (expmod 10 16 561))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (expmod 10 8 561)))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (expmod 10 4 561))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square (expmod 10 2 561)))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square (square (expmod 10 1 561))))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square (square (* 10 (expmod 10 0 561)))))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square (square (* 10 1))))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square (square 10)))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square (square 100))))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square (square 463)))))))))) (* 10 (square (square (square (square (* 10 (square (* 10 (square <strong>67</strong>))))))))) ; Nontrivial square root (* 10 (square (square (square (square (* 10 (square (* 10 1)))))))) (* 10 (square (square (square (square (* 10 (square 100))))))) (* 10 (square (square (square (square (* 10 463)))))) (* 10 (square (square (square (square 529))))) (* 10 (square (square (square 463)))) (* 10 (square (square <strong>67</strong>))) ; Nontrivial square root (* 10 (square 1)) (* 10 1)) 10 |

This exercise and the Miller-Rabin test are getting me to think about Discrete Logarithms.