Scheme - 手続きとその生成するプロセス(例: 素数性のテスト(Carmichael数とFermatテスト、Miller-Rabin test))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.6(例: 素数性のテスト)の問1.28を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.28.

コード

sample.scm

(define (expmod base exp m)
  (cond ((= exp 0 ) 1)
        ((even? exp) (expmod-inner (expmod base (/ exp 2) m) m))
        (else (remainder (* base (expmod base (- exp 1) m))
                         m))))

(define (expmod-inner a m)
  (if (and (not (or (= a 1)
                    (= a (- m 1))))
           (= (remainder (square a) m) 1))
      0
      (remainder (square a) m)))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (miller-rabin-test 2)

;Value: #t

1 ]=> (miller-rabin-test 3)

;Value: #t

1 ]=> (miller-rabin-test 4)

;Value: #f

1 ]=> (miller-rabin-test 5)

;Value: #t

1 ]=> (miller-rabin-test 6)

;Value: #f

1 ]=> (miller-rabin-test 7)

;Value: #t

1 ]=> (miller-rabin-test 8)

;Value: #f

1 ]=> (miller-rabin-test 9)

;Value: #f

1 ]=> (miller-rabin-test 10)

;Value: #f

1 ]=> (miller-rabin-test 11)

;Value: #t

1 ]=> (miller-rabin-test 10000000000051)

;Value: #t

1 ]=> (miller-rabin-test 10000000000053)

;Value: #f

1 ]=> (miller-rabin-test 10000000000098)

;Value: #f

1 ]=> (miller-rabin-test 10000000000099)

;Value: #t

1 ]=> ; Carmichael数をテスト
(miller-rabin-test 561)

;Value: #f

1 ]=> (miller-rabin-test 1105)

;Value: #f

1 ]=> (miller-rabin-test 1729)

;Value: #f

1 ]=> (miller-rabin-test 2465)

;Value: #f

1 ]=> (miller-rabin-test 2821)

;Value: #f

1 ]=> (miller-rabin-test 6601)

;Value: #f

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.

ということで、Miller-RabinテストはFermatテストと違い、Carmichael数にだまされてない。