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<n, and try your procedure on the given Carmichael numbers
(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.
(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 **67**))))))))) ; 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 **67**))) ; Nontrivial square root
(* 10 (square 1))
(* 10 1))
10
This exercise and the Miller-Rabin test are getting me to think about Discrete Logarithms.