Dan's Thoughts Thinking somewhat carefully

Exercise 1.27 of SICP

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

(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.