Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
##(link2sicp "book-Z-H-11.html#%_thm_1.28" "Exercise 1.28")
解答例
Miller-Rabinテスト
(define (expmod2 base exp m)
(cond ((= exp 0) 1)
((even? exp)
(let* ((n1 (expmod2 base (/ exp 2) m))
(n2 (remainder (square n1) m)))
(if (and (= n2 1)
(not (or (= n1 1) (= n1 (- m 1)))))
0
n2)))
(else
(remainder (* base (expmod2 base (- exp 1) m)) m))))
(define (miller-rabin-test n)
(define (try-it a)
(= (expmod2 a (- n 1) n) 0))
(try-it (+ 1 (random-integer (- n 1)))))
(define (miller-rabin-test2 n)
(define (try-it a)
(= (expmod2 a (- n 1) n) 0))
(define (iter a)
(if (= a 1)
#f
(or (try-it a)
(iter (- a 1)))))
(iter (- n 1)))
miller-rabin-test はランダムに選んだ a < n なる a でテストする miller-rabin-test2 は a < n なるすべての自然数でテストする
実行結果(miller-rabin-test2 は引数が合成数であれば、#tを返す)
gosh> (miller-rabin-test2 561) #t gosh> (miller-rabin-test2 1105) #t gosh> (miller-rabin-test2 1729) #t gosh> (miller-rabin-test2 2465) #t gosh> (miller-rabin-test2 2821) #t gosh> (miller-rabin-test2 6601) #t
コード
##(sicp-answer-code "ex-1.28.scm")
