脚注47のCarmichael数が本当にFermatテストをだますことを示せ.
それには整数nをとり, a < nなるすべてのaで, anがnを法としてaの合同になるかどうか見る手続きを書き,
Carmichael数でその手続きを使ってみる.
a < nを満たす正の整数aについて, expmodを用いてanがnを法としてaと合同になるか調べます.
手続きは次のとおりです.
(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 (pass-fermat-test? n) (define (loop a) (or (= a n) (and (= (expmod a n n) a) (loop (+ a 1))))) (loop 1))
評価してみます.
ようこそ DrRacket, バージョン 6.1 [3m]. 言語: Pretty Big; memory limit: 2048 MB. > (pass-fermat-test? 561) #t > (pass-fermat-test? 1105) #t > (pass-fermat-test? 1729) #t > (pass-fermat-test? 2465) #t > (pass-fermat-test? 2821) #t > (pass-fermat-test? 6601) #t > (pass-fermat-test? 6605) #f > (pass-fermat-test? 6607) #t >
脚注のカーマイケル数は, フェルマー・テストをパスしています.
間違えて, 必ず#tを返す手続きを実装していては困りますので, 合成数6605では#fが返ってくることを確認しています.
0 件のコメント:
コメントを投稿