SICP 問題 1.27 （Carmichael数に騙されるの巻）

【問題】
脚注47のCarmichael数が本当にFermatテストを騙すことを示せ。
それには整数 n をとり、a < n なる全ての a で、a^n が n を法として a の合同になるかどうか見る手続きを書き、Carmichael 数でその手続きを使ってみる。

【解答】
まずはその脚注47をご紹介。

47

Fermat テストを騙す数は、Carmichael数（Carmichael numbers）といい、非常に稀だということ以外はよく分からない。100,000,000 以下の Carmichael数は 255 個あり、小さい方のいくつかは 561, 1105, 1729, 2465, 2821, 6601である。

ランダムに選んだ非常に大きい数の素数性のテストで、Fermatテストを騙す数に遭遇する確率は、宇宙線が計算機の「正しい」アルゴリズムに誤りを生じさせる確率より小さい。

アルゴリズムが前の理由から不適切であり、後の理由からとしないのは数学と工学の違いを見せる。

提示されている Charmichael数は、561, 1105, 1729, 2465, 2821, 6601 の6個。
こいつらに、今から作る総当たりFermatテスト関数を摘要してやる。

;Carmichaelテスト用関数。
;引数で渡されたnが素数かどうかを真理値で返す。
(define (realy-prime? n)
  (fast-prime? n (- n 1)))

;Fermatテスト関数を指定回数実行する関数
;nが評価対象の数で、iで回数を指定。
(define (fast-prime? n i)
  (cond ((= i 0) #t)
        ((carmichael-test i n) (fast-prime? n (- i 1)))
        (else #f)))

;新Fermatテスト関数。
;基数aをランダム抽出するのではなく外から引数で指定してやる
(define (carmichael-test a n)
  (= (expmod a n n) a))

;お馴染み、冪剰余を算出する関数
(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 (square x)
  (* x x))

上記を全て読み込ませてチェック！

gosh> (map realy-prime? '(561 1105 1729 2465 2821 6601))

(#t #t #t #t #t #t)

gosh> 

見事に全て素数判定！
んが、以前作ったsmallest-divisor関数を読み込んで、

;最小除数を求める関数
(define (smallest-divisor n)
  (find-divisor n 2))
　
;除数を求める処理
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

;除数かどうかの判別処理
(define (divides? a b)
  (= (remainder b a) 0))

これで判定してやると・・・

gosh> (map smallest-divisor '(561 1105 1729 2465 2821 6601))

(3 5 7 5 7 7)

gosh> 

素数ではない！だまされている！