modの世界

SICP

まず今もちゃんと理解出来てないコードから

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

これは素数性をテストするフェルマーテストのコードですが
はっきり言って何がしたいのかさっぱり・・・w
なのでgoshを使ってみました

gosh> (define ( expmod base exp m )
  ( cond (( = exp 0 ) 1 )
  (( even? exp )
 ( remainder ( square ( expmod bese ( / exp 2 ) m )) m ))
 ( else
  ( remainder ( * base ( expmod base ( - exp 1 ) m )) m ))))
 ( define ( square x ) ( * x x ))expmod

expmodについて定義してある部分はちゃんと分かったんですけど・・・
じゃあそもそもmodとかexpって・・・そもそも何か分からないのでした・・・

mod = (modularの略) 
2個の任意の整数a,bを自然数nで割った余りが等しいとき
a, b は n を法として合同であるといい
　　　　[tex:a \eq b ] (mod n) と表す
つまりnで割った整数a,bの余りが同じって事だよね？
exp = (exponentiationの略)冪乗（べきじょう）
ある一つの数同士を繰り返し掛け合わせるという操作のこと
つまり指数って事かな？

もう少し分かりやすく書いて下さいよー・・・
とかなんとか書いているうちになんかさっきのフェルマーテストの
コードwikipedeaのお陰で何となく分かって来た・・・かも？

フェルマーの小定理

a^n-1 \eq 1 (mod n)
a>n かつa,nが両方素数である整数a,nがあったとする
(aはnの倍数ではない整数である)
aをn-1乗した数字をnで割ると余りは1になる
この定理を踏まえた上で素数性のテストについて考えてみたいと思います
もし素数なら a^n-1 \eq 1 (mod n)が成立して
もし合成数ならその逆になります
(逆もまた真ってことですね☆)
合成数であるための条件は

1. a>n (aはnの倍数ではない整数である)かつa,nが共に素数ではない整数
2. aのn-1乗した数字をnで割った時の余りは1にならない

こんな条件のa,nがあったらそれは合成数という事になります
ただし[整数]という箇所に注目をして　かつ素数に1は含まないので
パラメーターは2以上n未満という条件でスタートします
ではもう一度コードを見てみます

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

やっぱ分かりそうで分からない・・・
後もう少しなのになぁ・・・
あとこのフェルマーテストは完璧な素数性のテストではありません
[確率的素数]が分かるテストなのです
カーマイケル数(絶対疑素数)なるものが存在するようです
カーマイケル数は、合成数なのにどんなaを使っても確率的に
素数だと判定されてしまいます
ちなみに10000 以下のカーマイケル数は
561, 1105, 1729, 2465, 2821, 6601, 8911 です
SICPによるとフェルマーテストを欺く数は稀なので
充分フェルマーテストは信用が出来るそうです
561で素数だと騙されちゃうのにフェルマーテストが信用出来ると言われても
少し微妙なんですけど・・・
ちなみにRSAアルゴリズムによる素数判定法は完全のようですw