ハズレ日記

素数であるかを判定するFermatテストをお勉強。
ほぼ写経なんですが，コードはこんなかんじ。(gauche)

(use math.mt-random)

(define mt-m (make  :seed (sys-time)))                                                                                                                                        (define (square x) (* x x))


(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 (mt-random-integer mt-m  (- n 1)))))          

(define (fast-prime? n times)

  (cond ((= times 0) true)

             ((fermat-test n) (fast-prime? n (- times 1)))

             (else false))) 

(display (fermat-test 561))

(newline) 

で，これのおもしろいのは確率的に素数判定をおこなうということ。
さらにおもしろいのが，Carmichael numbersというFermatテストを騙すことができる数があることが明らかになっていること。しかも，1105とか明らかに素数でない数でFermatテストが騙される。なぜなぜ？
そのうえ，100,000,000以下のCarmichael numbersは255個ある，と。なんか意味ありげな数字だ。うーん，なにかありそう。

Carmichael numbersは完全疑似素数とよばれるのか。なんかかっこいい。

と，SICPの29Pのお話でした。
博士の愛した数式を読んだ直後ってこともあってめちゃくちゃ興味津々。こういう深追いは楽しいなぁ。