素数とは何かを解説。1と自分自身でしか割り切れない数の強みとは?【情報の安全を守る素数のチカラ】

 

素数とは「1より大きい自然数で、1とその数自身以外のどの自然数でも割り切れない数」のこと。

英語では Prime Number と言います。自然数:1以上の整数のこと。ここでの「割り切れる」は剰余が0の意味

 

例えば

「1」は「1より大きい自然数」ではないので、素数ではありません。

「2」は「1より大きい自然数」であり、「1と2」以外の自然数では割り切れないので、素数です。

「4」は「1より大きい自然数」ですが、「1と4」以外にも「2」で割り切れるので、素数ではありません。

「5」は「1より大きい自然数」であり、「1と5」以外の自然数では割り切れないので、素数です。

 

 

今回は、この素数の定義とその活用法について書いていきます。

 

素数の定義

素数の定義は、「正の約数が 1 とその数自身の2個だけである自然数」です。

 

 

注意点としては、「1」は素数ではないということ。

「1」の正の約数は「1」の1個だけですから、「素数とは、正の約数が2個の自然数」という定義で覚えておけば、間違えにくくなりますよ。

 

100までの素数一覧。その規則性は?

以下が、1から100までの素数の一覧です。

 

 

「2」以外の偶数は「1と2とその数自身」の3つ以上正の約数があるので、素数ではありません。

また、「5」以外の「一の位が5の数(15,25,35…)」も「1と5とその数自身」の3つ以上正の約数があるので、素数ではありません。

 

以上から、10以上の数については「一の位が1か3か7か9の数」の中に素数があることまでは分かるのですが、それ以上の規則性は分かりませんよね。

 

Tooda Yuuto
実際、素数が出現する規則性は、数多くの数学者たちがその解明に挑んだにも関わらず、いまだに解明することができていない「数学史上最大級の難問」とされています。

 

素因数分解とパスワード

実は、素数の「1とその数自身でしか割り切れない」という性質は、ある形でぼく達の生活と密接に関わっています。

 

それは、「情報の暗号化」です。

 

例えば、「1121893841」という数。

この数字、実は「2つの素数pとqの積(かけ算)」なのですが、pとqが何か分かりますか?

 

正解は、「21193」と「52937」。まず分かりませんよね…

 

答えが分かってしまえば、2つの数をかけ算して「1121893841」を求めること自体は簡単です。

しかし、答えを知らない人が「1121893841」という数字から2つの素数を導きだそうと(素因数分解)すると、とんでもなく難しくなってしまうんです。

 

 

この例では10桁なのでコンピュータならまだ何とかなりますが、桁数をある程度増やしてしまえば、コンピュータですら適わなくなってきます。

 

これは、「巨大な2つの素数の積」の素因数分解には効率よく答えを探す方法がないのが原因。

同じ10桁でも「1000000000」なら、「2で割る」「5で割る」を各9回行うことで 29×5だとすぐに分かりますが、「1121893841」は「2で割れない」「3で割れない」「5で割れない」「7で割れない」・・・を地道に繰り返すしかなく、とんでもない計算量になってしまうんです。

 

 

実際、2010年1月時点において、「RSA-768(出典)」と呼ばれる232桁の数字では、2つの素数を導き出す(素因数分解する)のに「高性能コンピュータ80台」を使っても半年もかかったことが実証されています。

 

「鍵があれば簡単に解けるけど、錠をどれだけ調べても解読するのは困難」

 

この「鍵に必要な条件」を高度に満たしているのが、巨大な素数だったんです。

 

あなたの大事な情報を守る「素数」の強み

この性質を利用したのが、「RSA暗号」と呼ばれる公開鍵暗号。

 

クレジットカードや銀行口座など、重要な個人情報・金融情報を管理する金融業界において、情報通信を安全に行う上で重要な存在となっています。

「巨大な2つの素数の積」を素因数分解する難度は、その桁数が増えるごとに天文学的な比率で跳ね上がっていきます。

それこそ、専用のコンピュータでも解読に数万年かかる暗号にすることだってできるんです。

 

そのため、将来的にコンピュータが圧倒的な進化を遂げたとしても、RSA暗号に使う数の桁数を増やしてしまえば、セキュリティ上問題ないとされています。

※裏を返せば、素因数分解を効率的に行う方法が見つかってしまうと暗号化システムの変更が必要になるかもしれません。

ただ、これを拡大解釈して「リーマン予想が証明されるとRSA暗号が危険に!?」という都市伝説もあるそうですが、リーマン予想は素因数分解の効率とは関係ありません。

 

Tooda Yuuto

ぼく達の重要な情報の安全性に貢献している素数。

その謎が解明されて欲しいような、欲しくないような、不思議な魅力のある数だと思います。

スポンサーリンク

ツイッターやブログ等でシェアしていただけると、非常に励みになります。

Tooda Yuuto
大阪大学を卒業後、数字とにらめっこする日々を送る社会人。当たり前なようでアタリマエじゃないことを日々探しています。