Meadow から Emacs for Windows への移行はちょっと大変そうなので、とりあえずは置いておくことにしました(問題の先送り….)。
それにあわせて DrRacket 導入も見送りで、結局当分は Meadow+Gauche という元鞘に戻りそうな予感。時が満ちたら再チャレンジします。

SICP 本体は、どうも Fermat テストに関する理解ができていないせいでこのあたりの問題に着手すると手が止まってしまいます。
飛ばすのは簡単なんですが、Fermat テストに関係ない本質的なところまで飛ばしてしまうことになるので悩みどころです。
完璧に理解するのは無理として、一度 Fermat テスト周りのコードは全て写経して完全に動くソースコードを作ってみます。

本文

Fermat テスト再考

Fermat テストの理解もざっくりしすぎなので、一度整理。

法として合同 :
二つの数を n で割った時、同じ徐余を持てば、 n を法として合同という。

例 : 8 と 11
それぞれ 3 で割ると余りは 2 なので、8 と 11 は 3 を法として合同である。
また、この時の余り 2 は、3 を法とした 8(11) の徐余もしくは 3 を法とした 8(11) である。

Fermat の小定理 :
n を素数、a を n より小さい正の任意の整数とすると、a の n 乗は n を法として a と合同である。

例 : n=11, a=3
3^11 = 177147
177147 mod 11 = 3
3 mod 11 = 3 → 11 を法として合同

n = 12, a=3
3^12 = 531441
531441 mod 12 = 9 → 12 を法として合同でない

Fermat テストコード

(define (random num)
  (use srfi-27)
  (* (random-integer num) 1.0))


(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)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

問題解答

問1.27
Carmichael 数の確認

 (checkCarmichael n)
  (define (check-iter a n)
    (cond ((= a (- n 1)) #t)
          ((= (expmod a n n) a)
           (check-iter (+ a 1) n))
          (else #f)))

  (check-iter 1 n)

gosh> (checkCarmichael 561)
#t
gosh> (checkCarmichael 1105)
#t
gosh> (checkCarmichael 1729)
#t
gosh> (checkCarmichael 2465)
#t
gosh> (checkCarmichael 2821)
#t
gosh> (checkCarmichael 6601)
#t

例えば 2821 = 7 * 13 * 31。
たしかにだまされている。