素数の話

今日はネタもないので読み物風に。夏の夜長にどうぞ。(?)

まずは参照リンク

これは、まぁ昔からの難問である素数判別の話です。ある数が素数であるかどうかを調べる、というもの──あるいは逆をいえば、素数を次々にいっていくことができる公式の作成──その類の研究は、それこそ紀元前から始まっていたといっても過言ではないのです。

このサイトを見ている方で、素数を知らない方はまずいないだろうから、その辺は割愛させていただきましょう。素数なんか知らないという方は、こちらをどうぞ。

例えば、99703は素数かどうか? 答えは、179×557なので素数ではない。こういう素数判別については、人間はともかく、あの計算をスイスイこなすコンピューターでも苦手な分野なのです。

コンピューターは地道な計算をすることしかできないのです。99073を2で割って、3で割って、5で割って……とひたすら割り算をしていって、割れるか割れないかを確かめる、コンピューターではその程度しかできないのです。

先ほど例に挙げた数ならまだコンピューターでも1秒以下で計算できる事でしょう。しかし、たとえば、162259276829213363391578010288127*注ではどうでしょう? こんなの割り算していたら日が暮れます。大きい数になってしまえば、コンピューターでも本当に日が暮れるのです。

素数かどうか。これを利用したのが、暗号などといった、セキュリティシステムに利用されているのです。簡単にいってしまえば、つまり計算機を使っても100年かかる計算をさせるセキュリティで守っていれば、銀行口座のお金は生きてる間は大丈夫だ、ということです(ナニカチガウ)。

ただし、これには問題があります。コンピューターとアルゴリズムの発展。今回発表された素数判定技術……どのようなシステムなのかしらないですが、長年の問題だった事を考えれば、数学屋の目から見ても凄い事だと思います。といっても、私はその研究の論文を読んだわけでもないので、実際にどのようなアルゴリズムなのか知る由もないのですが。その辺はまた勉強したいと思います。

*注:実はこれはメルセンヌが素数について予想した「メルセンヌ数」の中で、メルセンヌが見逃した数です。上の値は、2107-1のはず。

☆★☆今日のぺけぺけ☆★☆
今日の『素数の話題』
 その1。素数は無数にあるか。これは紀元前から知られていて答えは「無数にある」。そしてその証明はとても鮮やかなのです。証明はまたいつか。

 その2。この前小学生の時に親に買ってもらった「算数大事典」みたいなのをみていたら、正5角形の作図方法が書いてあった。これには深い意味があってですね。定規とコンパスで作図できる正素数角形は、フェルマー数という数、3・5・17・257・65537の5つの正多角形のみということをガウスが1796年に発見しています。それを示唆するような算数大事典恐るべし。フェルマー数ってのは、フェルマーが「これは素数を次々に作る公式だ!」と予測して間違っていた悲しい式で、Fn=22n+1。これはnが0~4の時のみ素数なのです。ちなみに正17角形の作図については、高校で複素数か何かを学ぶとできるはずです。そのフェルマー数は、Fn乗根を求められるってことなんです。だから作図もできるという。ムズカシイ話はこれぐらい。参照リンク

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください