上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
にほんブログ村 科学ブログ 数学へ
にほんブログ村
2015.02.09 多項式時間
ある数が素数かどうかはどうやったらわかるだろうか?

例えば2桁くらい、23とか49くらいなら一つづつ素数で割って調べていけばわかりますよね
でも385384596091なんて数になるともうお手上げですよね

1桁目が偶数でないから、2の倍数ではないとか
全ての数字を足して3で割り切れないから3の倍数ではない
そのくらいまでは解りますがそれ以上の素数(例えば11とか13)でわり切れるかどうかはすぐにはわかりません

しかし決定的多項式時間(なんじゃそりゃ?)というのを使うとその数が素数かどうかわかるそうです

それじゃあ、決定的多項式時間とはなんぞやということですが、コンピューターの暗号鍵と関連しているらしいところまではわかりましたが、なかなか難しそうなので、また今度調べたいと思います
関連記事
にほんブログ村 科学ブログ 数学へ
にほんブログ村
Secret

TrackBackURL
→http://recentreport.blog.fc2.com/tb.php/1236-007d9731
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。