暗号の数理 -素数の正体にせまる-
暗号の利用
暗号は、いろいろな取引やクレジットカードの利用などに多く用いられています。暗号の基本は素数にあります。極めて大きな数が、素数かどうかの判定をするときに、小さい素数で割っていって、割り切れなければその数は素数であることが分かります。
でも、与えられた数が大きければ大きいほど、割り算をする手順は幾何級数的に大きくなることになります。素数を小さい方から並べると、\(2,3,5,7,11,13、・・・\)となりますが、素数は無限に存在します。これは、2000年以上前のユークリッドによって証明もされています。素数そのものがどういう正体なのかは、今も分かっていませんが、無数に存在することは分かっています。
大きな数の素数判定は、スーパーコンピューターを使うわけですが、超高速のコンピューターを使っても高々、100年程度の時間では計算しきれないほどの計算量がかかります。素数かどうかは、明確に判断はできますが、人間の生活時間内に判定が困難である事を前提にしているわけです。
現在分かっている最大の素数は?
現在分かっている最大の素数は、\( 2^{57885161} − 1\) であり、1700万桁くらいの自然数になります。とてもではありませんが、この素数をここに書くことは不可能です。
以前触れましたが、リーマンのζ関数\(ζ(s)\)に関する予想が、解決されれば、素数の全貌が明確になり、暗号システム事態もさらにスマートなものにする必要があります。
リーマン予想がいつ解決されるのかは、誰にもわかりませんが、天才数学者が突然現れて、あっという間に解決してくれるかもしれません。
素数が無限に存在する事の証明 -ユークリッドの証明-
素数が無限に存在する事の証明は、易しいですからユークリッドの証明を書いておきましょう。
素数が、有限であると仮定します。有限ですから、素数は
\(p_1、p_2、・・・・・・・・・・・・、p_n \)と書くことができます。
ここで、数Nを、 \(N=p_1xp_2x・・・・・・・p_n + 1\) とすると \(N\)は、有限な全ての素数\(p_1、p_2、・・・・・・・・、p_n\) で割ったら、1余る事になりますから、\(N\)も素数と言う事になります。
これは、有限なn個の素数が1個増えたことになりますから、 最初の仮定に矛盾します。従って、背理法により、素数は無限であると結論できます。
幾何学を体系化したユークリッドは数論にも長けていた事は、ある意味で驚異でもあります。