Pythonでフェルマーテスト
今日、仲良くさせてもらっている一つ上の先輩から、オイラーの定理についての話を聞いた。
オイラーは僕の知っている数学の話でもよく出てくる人物だ。例えば、先日読んだ「博士の愛した数式」でもオイラーの公式が出てきたし、グラフ理論に関する本「複雑ネットワークとは何か」においても真っ先にオイラーグラフが紹介されている。
オイラーの定理はフェルマーの小定理から
先輩はオイラーの定理をRSA暗号方式の話の中で聞いたようだ。オイラーの定理についてよく知らなかったので、お得意のWikipediaで調べてみた。そうすると、フェルマーの小定理の一般形だということがわかった。フェルマーの小定理は1年生の時に勉強しているはずだったので、なんとなく理解はできた。証明は理解できなったんだけど・・・。
フェルマーの小定理の公式
Wikipediaからの引用ではあるが、フェルマーの小定理は以下のように定義される。
nを素数とし、aはnと互いに素である整数とするとき
これを噛み砕いて言うならば、aのn-1乗をnで割ったときの余りは1に等しいということである。
フェルマー小定理の対偶を考えると、素数判定ができる。
でもまあ、数式だけ知ったところであんまりうれしくないわけです。そこで出てくるのがフェルマーの小定理の対偶をとることで生まれるフェルマーテストと呼ばれる素数判定アルゴリズムです。
対偶って言葉は僕は使い慣れないので、これから言うことは正しいかどうかわからないですが、p⇒qという命題があったとき、¬q⇒¬pは対偶です。で、本を見ると、p⇒q≡¬q⇒¬pとなっており、これはフェルマーテストの存在は肯定しているのかなーなんて勝手に思っています。
フェルマーテストの概要
さて、数学チックな話は僕は苦手なので、もっと身近なところに話を持ってきます。フェルマーテストは以下のようなプロセスのアルゴリズムです。
確率的素数というのが曲者で、必ずしも素数であるとは限らないということを言っています。詳しくは本を見てください。ちなみに、フェルマーテストで確率的素数と判定された合成数のことを疑似素数なんて呼びます。
Pythonで実装
さっそくPythonで実装です。
#ファイル名：fermattest.py #フェルマーテストでnが合成数かどうかを判定 def fermattest(n,a=2): #aとnが互いに素でないなら、nは合成数 if gcdis1(n,a)!=1: print u'%dは合成数' % n; return; #a^(n-1)をnで割ったあまりが1でないなら、nは合成数 if a**(n-1)%n != 1: print str(n)+u'は合成数'; else: print str(n)+u'は確率的素数'; #aとnの最大公約数を求める（ユークリッドの互除法） def gcd(n,a): if(n>a): big=n; small=a; if(n<a): big=a; small=n; while(1): x=big%small; big=small; if(x==0): break; small=x; return small; #aとnが互いに素かどうかの判定 def gcdis1(n,a): if(gcd(n,a)==1): return 1; #素だったら1 else: return 0; #素じゃなかったら0
これで必要な機能はそろったので、コマンドラインから実行です。
>>> import fermattest >>> fermattest.fermattest(3) 3は確率的素数 >>> fermattest.fermattest(250) 250は合成数 >>> fermattest.fermattest(3571) ← 500番目の素数 3571は確率的素数
なんとなく、結果はよさそうです。
自力で一から考えるアルゴリズムも好きですが、数学的に正しい式に基づいてアルゴリズムを作ることも楽しいですね。
もっと数学ができるようになりたいなー。
