« ■コマネチ大学数学科99講:自然数 | トップページ | ■コマネチ大学数学科100講:白銀比 »

2008年7月27日 (日)

■素因数分解にうっとり^^;

所長「なぜなのら~、私が『素因数分解』などと口にすれば、女の子は皆、逃げていくのに、「ジョンフン」が「素因数分解」と言っただけで、あの戸部アナもうっとりだ。なぜなのら~」
助手「あの、なにを言ったかは、カンケーないかと……誰が言ったかが問題かと」

(※初期値「2000」をダブルクリックして数値を入力。ボタンを押す)

所長「そこで、私は考えた。ジョンフンならば、日本の『数学』離れを救ってくれると! すくなくとも、ジョンフンのファンならば『素因数分解』に興味を持ってくれたはずじゃ!」
助手「たんに、素因数分解だけじゃ、誰も見てくれないので、ジョンフンをダシに使っただけじゃないですか!」

 というわけで、ここからは「素因数分解って何なの?」という人だけ読んでほしい。

 素数とは、その数自身と「1」でしか割り切れない数のこと。「3」や「5」や「7」は素数だけれど、「9」は「3」で割り切れる数なので、素数ではない。「9=3^2」と表すことができる。「15」なら「15=3*5」というように、ある数を素数の積の形で表すことを「素因数分解」と言う。素数でない自然数は、すべて「合成数」なので、素因数分解ができることになる(ただし、「1」の素因数分解は「1」とする)。

 実際に「12345」を素因数分解してみよう。1の位が「5」なので、「2」で割ると余りが出てしまう。そこで「3」で割ってみる。「12345÷3=4115」で割りきることができた。続けて、その商を割る「4115÷3=1371.666…」とすると、割り切れないので、次の素数「5」で割ってみる。「4115÷5=823」となった。

 ここまでで「12345=3*5*823」と表すことができた。ところが「823」を「7」で割っても「11」で割っても余りが出てしまう。いったい、どこまで素数で割り続けなければならないのか。「12345」の平方根を求め、小数点以下を切り捨て、自然数にすると「111」。「111」は合成数だが、111以下の最大の素数まで調べればよい。

 どういうことかと言うと、「111」以下の素数では「109」が最大。109×109=11881、次の素数「113」だと、「113×113=12769」と「12345」より大きな数になってしまう。

 で、結局「109」まで調べたとしても「823」を割り切れる数は存在しない。なぜなら「823」は素数だからだ。つまり「12345=3*5*823」で素因数分解は完了していたわけ。素因数分解は、互いに素な数の積の形で表せられる。積の交換法則は成り立つが、その一意性が担保されている。つまり、ある数を素因数分解すると、たったひと通りに定まり、これ以外の素因数分解の形は、存在しないということになる。

 上の冗長な文章の手順説明を、もう少し簡潔に表したのが下のスクリプトだ。

 コンピュータは計算が速く、疲れ知らずなので、こうした、しらみつぶし的な愚直な方法でも、この程度なら、なんとかなってしまうが、これよりさらに大きな数を素因数分解するには、この方法は使えなくなる。爺の理解の範囲を超えてしまうけれど、ポラード・ロー素因数分解法や、連分数法、楕円曲線法など、もっと効率的なアルゴリズムもあるようだ。興味のある人は調べてみてほしい。また、素因数分解の一意性は、RSA暗号の公開鍵の生成などにも使われているんだよね。けっこう奥が深いぞ「素因数分解」。

※今回、制作したFlashのダウンロード
factorize.zip(Flash8)

「たけしのコマ大数学科」7~9月限定のエンディング曲「floating ~漂流~」は、John-Hoonの新曲「君を守りたい」にカップリングされている。

John_hoon01 John_hoon02


|

« ■コマネチ大学数学科99講:自然数 | トップページ | ■コマネチ大学数学科100講:白銀比 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/22590885

この記事へのトラックバック一覧です: ■素因数分解にうっとり^^;:

» ジョンフン:「日本」の数学離れを救ってくれる?? [ジョンフンJohn-Hoonが好き!JH Forever! 2πR]
ジョンフンが「コマ大数学科」に出演した際に、普段数学になじみのない ファンが、皆、ジョンフンの「素因数分解」にシビレましたよね~♪ ★ランキング参加応援のぽちっ!コマウォ~☆⇒芸能ブログ ... [続きを読む]

受信: 2008年8月 8日 (金) 12時22分

« ■コマネチ大学数学科99講:自然数 | トップページ | ■コマネチ大学数学科100講:白銀比 »