計算機プログラムの構造と解釈 第二版 P29 問題1.27
ここで出ている、charmichael数っていうのは、
561、1105、1729、2465、2821
っていう数で、
Felmatテストはパスするけど、素数ではない数。
教科書に書いてあった
nを法として合同
とかいうことば。
先々週ぐらいに、教えてもらったのに、そもそも意味がわからない。
再度調べてみる。
wikipedia先生
http://ja.wikipedia.org/wiki/%E5%90%88%E5%90%8C%E5%BC%8F
定義
二つの整数 a, b は、a − b が自然数 n で割り切れるとき、n を法として合同（n をほうとしてごうどう、congruent modulo n ）であるといい、a ≡ b (modulo n), a ≡ b (mod n) あるいは a ≡n b などと表す。このように、合同関係をあらわす演算子で結ばれた式を合同式と総称する。a ≡ b (mod n) は、a, b それぞれを自然数 n で割ったときの剰余が等しいことと同値である。また同じことだが、整数 k の n を法とする剰余はしばしば k mod n で表されるので、この記法に従えば、合同式 a ≡ b (mod n) は等式 a mod n = b mod n に書き直すことができる（この等式で k mod n を後述のように剰余類の意味にとっても同じことである）。
整数の合同式
http://homepage3.nifty.com/sugaku/mod.htm
2数 a, b が ｐを法として合同
⇔
a-b がｐで割り切れる。つまり整数ｋを用いて、a-b=pkとかける。
（あるいは、pで割った余りが等しい）これを a≡ｂ （mod p）で表す。
なので、教科書にある
整数nをとり、a < n なるすべてのaでa^nがnを法として合同になるかどうか見る手続きを書き、
っつーのは、
（あるいは、pで割った余りが等しい）
って書いてある通りに考えて
aを、n-1から始めてを1ずつ引いていって1になるまで、
(イテレータ的？には、aを1から1ずつたしていって、n-1まで)
((a)^n) % n = a % n
が成り立てばいいということだ。
(まー a < n の関係から、a % n = a だけど、定義だしここのコードには残しておく)
なりたっていれば、素数である確率が高い。
そうでなければ、素数ではない。
なので、素数でないかどうか1-21で使った関数を使ってチェックしてからfelmatテストを行ってみる。
1 #!/usr/local/bin/gosh 2 ;; -*- coding: utf-8 -*- 3 4 5 ;;;1-21;;;;;;;;;;;;;;;;;;;;;;;;; 6 (define (square n) 7 (* n n)) 8 9 10 (define (smallest-divisor n) 11 (find-divisor n 2)) 12 13 (define (find-divisor n test-divisor) 14 (cond ((> (square test-divisor) n) n) 15 ((divides? test-divisor n) test-divisor) 16 (else (find-divisor n (cond ((= test-divisor 2) 3 ) 17 (else (+ test-divisor 2))))))) 18 19 (define (divides? a b) 20 (= (remainder b a) 0)) 21 22 (define (prime? n) 23 (cond ((= n (smallest-divisor n)) #t) 24 (else #f))) 25 ;;;;;;;;;;;;;;;;;;;; 26 27 ;;expmod実装 28 (define (expmod base exp m) ; a n n 29 (cond ((= exp 0) 1) 30 ((even? exp) 31 (remainder (square (expmod base (/ exp 2) m)) 32 m)) 33 (else 34 (remainder (* base (expmod base (- exp 1) m)) 35 m)))) 36 37 (define (test_for_charmichael_i a n) 38 (cond ((= a n) #t) 39 ((= (expmod a n n) (remainder a n)) (test_for_charmichael_i (+ a 1) n)) 40 (else #f))) 41 42 (define (test_for_charmichael? n) 43 (test_for_charmichael_i 1 n)) 44 45 46 (define (main args) 47 (display "charmichaelナンバーが、素数かチェック、素数なら#t")(newline) 48 (display "561:") 49 (display (prime? 561))(newline) 50 (display "1105:") 51 (display (prime? 1105))(newline) 52 (display "1729:") 53 (display (prime? 1729))(newline) 54 (display "2465:") 55 (display (prime? 2465))(newline) 56 (display "2821:") 57 (display (prime? 2821))(newline) 58 59 60 (newline) 61 (display "felmatテストを行う。素数性が確認されれば#t")(newline) 62 (display "561:")(print (test_for_charmichael? 561)) 63 (display "1105:")(print (test_for_charmichael? 1105)) 64 (display "1729:")(print (test_for_charmichael? 1729)) 65 (display "2465:")(print (test_for_charmichael? 2465)) 66 (display "2821:")(print (test_for_charmichael? 2821)) 67 0)
どうかな？
思惑通り、charmichael数は素数ではないが、素数性のテストはパスしている。
