プライバシーは素数が守る [応用] | 逆ポーランド電卓の実践ウェブ rpn hacks!

　キャッシュカードの暗証番号、携帯電話のロック番号、コンピュータのログインパスワード…。預金残高・メール・社内データなど、誰もが自分しかアクセスできない情報を持っています。

これらの暗証やパスワードといった認証とは別に、情報自体を守るための技術として暗号化があります。旧日本軍の真珠湾攻撃における「ニイタカヤマノボレ一二〇八」や「トラ・トラ・トラ」は有名ですが、ローマ時代のシーザー暗号に始まり、第二次世界大戦でのドイツ軍のエニグマなど、暗号技術は共通鍵方式を軸に進化を続けてきました(示した暗号は全て解読されてしまいましたが)。

「ニイタカヤマノボレ一二〇八」の意味は12月8日午前零時、戦闘を開始せよ。「トラ・トラ・トラ」は我奇襲に成功せりです。※新高山は台湾の玉山(3952m)で当時の日本領で最高峰の山。

戦争は暗号の解読合戦でもあります。第二次世界大戦時には日本もアメリカの重要暗号を解読しています。開戦当初は暗号書と乱数表(暗号を解くキー)を使う日本軍の暗号は破られていませんでしたが、戦闘でそれらが回収され、解読され始めました。それ以降、日本の暗号は筒抜け状態でした。一方、日本陸軍の暗号は強力で統制もあり、最後まで解読できなかったという話もあります。

共通鍵方式は暗号を解くキーを秘密裏に相手に渡さなければならないという欠点を持っていましたが、現在の暗号は公開鍵と秘密鍵のペアを持つ公開鍵方式が主流です。この方式の中核を担っているのが、なんとあの素数だというのですから驚きです。

素数(prime number)とは2以上の整数で、1と自分自身以外では割り切れない数字のことです。なお、素数が無限にあることは紀元前300年にユークリッドが証明済み。

そして、2つの大きな素数を掛け合わせた数から元の2つの素数を見つけることは、最新のコンピュータをもってしても時間が掛かるという性質を使って、暗号理論が構築されています。つまり、銀行間の通信、軍事情報、企業の機密データ、プライバシーなど、全ての社会基盤が素数の性質に掛かっているわけです。

素数は判定も発見も困難

　そんな素数の世界をちょっとだけ垣間見てみましょう。古来より、人類はある数字が素数かどうかを簡単に判別する方法を捜し求めてきましたが、未だに分かっていません。

エラトステネスのふるいという有名なアルゴリズムがありますが、数字が大きくなると処理時間が急速に増えてしまいます。改良版もたくさん発表されていますが、現在でもコンピュータパワーに任せた力ずくの探索であることに違いはありません。

加えて興味深いことに、2以上の整数は全て素数の掛け算で表すことができます。そのように掛け合わせて作られた数字を合成数といいます(合成数が素因数と同じときが素数)。

　合成数＝素因数｛×素因数｝　※{}は0回以上の繰り返し

これ自体、凄いことのように思えますが、肝心の素数(素因数)を求めるにはどうすればいいのでしょうか。そうです。あのやっかいな素因数分解が必要になります。例えば、2から10までの数字を素因数分解すると次のようになります。

素因数分解された数字を掛け合わせると元の数字になります。つまり、2、3、5、7が素数、4、6、8、9、10が合成数です(素因数分解した数字が1つしかないときが素数)。

さて、小さな数字を素因数分解するなら簡単ですが、大きい数字となると人間には難しいものがあります。例えば、2011は素数かと問われて即答できる人はまずいません。そこで、rpnプログラムを用意します。プログラム名はprimesです。

ちなみに2011は素数です(2000年から2030年の間では2003、2011、2017、2027、2029が該当)。また、任意の数が素数である確率は1/ln(n)です。2011の場合、rpn式では「2011 l n」(13%)。

素因数分解プログラムのダウンロード

• 素因数分解プログラムのZIPファイルをダウンロードしてください。
• ダウンロードしたZIPファイルをダブルクリックするとprimes.objが表示されます。
• primes.objを格納したいフォルダにドラッグすると以下のダイアログが出てきます。
• パスワードを入力してください。一致していれば、primes.objが解凍されます。

　※パスワードは講座サポートのpasteプログラムのダウンロードと同じです。

素因数分解プログラムの使い方

ここでは、c:\rpnディレクトリにobjファイルが保存してあるものとして説明します。DOSプロンプトを起動して、c:\rpnまで移動してください。以下のrpn式を入力すると素因数分解してくれます。

123は素因数が3と41の合成数であることが分かりますね。

primesプログラムは最大16桁の数値まで対応しています。

素因数分解≒素数判定(1000までの素数)

　結局、素因数分解ができるなら素数の判定ができていることになります。ところで一体、素数はどれくらいあるのでしょうか。素因数分解プログラムのprimesを使って、2から1000までの間の素数を探してみましょう。

一気に999個の数字(2～1000)までの素因数分解が終わりました。このうち、素因数が1つしかないものが素数です。

素数を表示するには元の数字をファイルの"num.txt"に格納して、素因数分解した数字をファイルの"tmp"に格納します。その後、ファイルを横結合して、素因数の数が1つのものだけピックアップすればOKです。

行数カウントを取ると素数の数が分かります。その数は168個です。

168個÷999個で0.168168の出現率になります(何故か小数点以下は見つけた素数の数である168の繰り返し)。2割弱が素数で8割強が合成数です(パレートの80対20ルールのようですね)。

2から10000までの場合はどうなるでしょう。大数学者のガウスは「nが十分に大きいとき、nを超えない素数の数はn÷ln(n)にほぼ等しい」ことを15歳のときに発見しています(素数定理)。この定理によると10000までなら約1085個ということになります(rpn式で「10000 . l /」)。

素数に規則性はあるのか？

　それでは、168個の素数を横15個で整列表示してみましょう。素数の数字に何かの規則性を感じることができるでしょうか。

ちなみに168個の素数を幹葉表示してみると次のようになります。

やはり、ランダムな感じがしますね。次に素数を1、合成数を0として横70個に整列表示してみましょう(npdを使って空白を詰めています)。素数の出現間隔に何か規則性を見出せるでしょうか。

　これら素数となる数字に規則性はありませんし、素数が発生する間隔にも規則性はありません。数学者も規則性を見つけていないし、証明もできていないので、少なくとも今日現在ではそう信じられています。

不思議なことに、1(素数)と0(素数でない)の列を中心から外側に向かって渦巻状に並べていくとパターンらしきものが浮かび上がってきます。

素数の出現規則や完全な生成方法が解明されれば、パスワードも暗号文も全て破られます。あなたのプライバシーの鍵は素数が握っていると言っても過言ではないのです。アメリカも国家安全保障の観点から、世界中の優秀な数学者を集めて、日々研究していることは確かなようです。

アメリカはリーマン予想をはじめ、既に素数の謎を解いているという噂があります(あくまで噂)。いずれにしても、仮に効率的な素因数分解のアルゴリズムが見つかってしまえば、公開鍵方式の暗号技術は崩壊します。

歴史上、素数の不思議さは多くの天才数学者を魅了しました。フェルマーは素数と平方数との関係を、オイラーは素数とπとの間に関連を見出しました。なかには没頭しすぎて統合失調症にまでなった人(ナッシュ均衡のジョン・ナッシュ)もいます。

素数を4で割って余りが1ならば、素数は二つの平方数の和になる(素数全体の半数が該当)。

素数とは神が授けた暗号なのでしょうか。それにπ、e…。果たして、これらに関連性はあるのでしょうか、それともないのでしょうか。

2の素数乗-1(メルセンヌ素数)は素数である確率が高く、素数判定が簡単です。例えば、2の31乗-1=2147483647は素数。この方法を使って2013年1月15日に最大素数の記録が更新されました(48番目のメルセンヌ素数)。その値は素数乗が57885161、素数は17425170桁に及ぶ長大なもの。なお、1000万桁以上の素数発見には賞金が掛けられているそうです。あなたも挑戦してみては。

2015年9月に49番目のメルセンヌ素数が発見され、最大素数の記録が更新されました。その桁数は22,338,618。48番目よりも500万桁大きいことになります。そして、2017年12月に50番目のメルセンヌ素数が、その一年後の12月に51番目が発見されています(2^82,589,933-1で桁数は24,862,048)。

応用コーナーに戻る