素数とは「1より大きい整数で、1と自分自身でしか割り切れない数」のこと。
英語では Prime Number と言います。※ここでの「割り切れる」は自然数で割ったときの「あまり」が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の数」の中に素数があることまでは分かるのですが、それ以上の規則性は分かりませんよね。
素因数分解とパスワード
実は、素数の「1とその数自身でしか割り切れない」という性質は、ある形でぼく達の生活と密接に関わっています。
それは、「情報の暗号化」です。
例えば、「1121893841」という数。
この数字、実は「2つの素数pとqをかけ算した値」なのですが、pとqが何か分かりますか？
正解は、「21193」×「52937」。まず分かりませんよね…
答えが分かってしまえば、2つの数をかけ算して「1121893841」を求めること自体は簡単です。
しかし、答えを知らない人が「1121893841」という数字から2つの素数を導きだそうとすると、とんでもなく難しくなってしまうのです。
この例では10桁なのでコンピューターならまだ何とかなりますが、桁数をある程度増やしてしまえば、コンピューターですら適わなくなってきます。
これは、「巨大な2つの素数の積」の素因数分解には効率よく答えを探す方法がないのが原因。
同じ10桁でも「1000000000」なら、「2で割る」「5で割る」を各9回行うことで 29×59 だとすぐに分かりますが、「1121893841」は「2で割れない」「3で割れない」「5で割れない」「7で割れない」・・・を地道に繰り返すしかなく、とんでもない計算量になってしまうんです。
実際、2010年1月時点において、「RSA-768（出典）」と呼ばれる232桁の数字では、素因数分解で2つの素数を導き出すのに「高性能コンピューター80台」を使っても半年もかかったことが実証されています。
「鍵があればカンタンに解けるけど、錠をどれだけ調べても解読するのは困難」
この「鍵に必要な条件」を高度に満たしているのが、巨大な素数のかけ算だったのです。
あなたの大事な情報を守る「素数」の強み
この性質を利用したのが、「RSA暗号」と呼ばれる公開鍵暗号。
クレジットカードや銀行口座など、重要な個人情報・金融情報を管理する金融業界において、情報通信を安全に行う上で重要な存在となっています。
「巨大な2つの素数の積」を素因数分解する難度は、その桁数が増えるごとに天文学的な比率で跳ね上がっていきます。
それこそ、専用のコンピューターでも解読に数万年かかる暗号にすることだってできるんです。
そのため、将来的にコンピューターが圧倒的な進化を遂げたとしても、RSA暗号に使う数の桁数を増やしてしまえば、セキュリティ上問題ないとされています。
※裏を返せば、素因数分解を効率的に行う方法が見つかってしまうと暗号化システムの変更が必要になるかもしれません。
ただ、これを拡大解釈して「リーマン予想が証明されるとRSA暗号が危険に！？」という話もあるそうですが、リーマン予想は素因数分解の効率とは関係ありません。
ぼく達の重要な情報の安全性に貢献している素数。
その謎が解明されて欲しいような、欲しくないような、不思議な魅力のある数だと思います。
次のページでは、いま紹介した素因数分解のカンタンなやり方を見ていきましょう。
