証明：無数の素数

2014年12月「Math in English のススメ」で書いたように、2014年11月から Math Dude の第一回目の投稿から読み始めた。そして、先日読んだのは 2014年5月31日公開の「What Is Math, Really?」で、これは第200回目の記事。ほぼ毎日 Math Dude の記事を読んで、ようやく200回目まで追いついたという感じだ。

その200回目の記事の冒頭、「200という数字の意味」の一つが

Or mightn't it be because 200 is the smallest base 10 unprimeable number (which, I just found out, means that it can't be turned into a prime number by changing just one of its digits)?

最初に読んだ時は、何のことか分からなかった。不明点を一つずつ調べてみる。

先ずは、unprimeable number とは

A composite number n is called unprimeable if it cannot be turned into a prime by changing a single digit.

a composite number（合成数）は、複数の素数の積からなる「素数ではない自然数」のことで、unprimeable は前後の数（±1）が素数にならない合成数。例えば 198 の前後の数 197、199 はどちらも素数。198 の次の合成数は 200 で、前後の数は 199 と 201。

199 は直感的に素数と分かるが、201は「何となく素数じゃね？」という感じだ。ところが 201 = 3 * 67 なので素数ではなくて合成数。

即ち、冒頭の Math Dude からの引用は

200 は最小の unprimeable number

英語で数学を学び直して、かつてないほどに数学好きになる前はこんな話題を「だからどうした？」となったが、今では「おぉ、凄い！」と喜んでしまう。さらに Math Dude も引用した Wikipedia の「200」の記事を読みながら、「げっ！！ 全自然数の記事があるのか？」と驚きながらも、何だか楽しくなった。


無数にある素数の証明

知らなかった unprimeable number も興味深いが、201 を素数と見違えたのが残念でならなかった、まだまだ数への認識力が低い。

ということで、Math Dude 第201回「How to Prove There Are Infinite Prime Numbers?」を元に、無数に素数が存在する証明について書いてみる。

この記事では Euclid's Proof（ユークリッドの証明）を使っているが、以下の「条件2」の値を「Bob」として記述。ここでは更に噛み砕いて実際例で示す。本来の数学的証明では、こんな実際例ではなく、抽象的な記述であるべきなのだが、分かりやすさを優先した。逆に、この実際例からちゃんとした数学的証明はイメージできると思う。

以下のように２つのケースで証明できる。

ステップ１：現在分かっている素数の集合
ステップ２：条件１のの素数の集合の要素を全て掛け合わせるものに１を足す

ケース１：ステップ１ = { 2, 3, 5 }、ステップ２ = 2*3*5 + 1= 31
この場合、31は素数なので「新たな素数」があることが証明された。

ケース２：ステップ１＝ { 2, 3, 5, 7, 11, 13 }、ステップ２ = 2*3*5*7*11*13 + 1 = 30031
30031 = 59 * 509 なので 30031 は合成数で素数ではない。
この場合、元の素数の集合では合成数 30031 は作れないので、他に素数があることが証明された。

つまり、以下の２つのケースしか有り得ないので、「元の素数の集合にない素数」の存在が証明される。

　ステップ２で作成された値が、元の素数の集合にない素数
　ステップ２で作成された値が、元の素数の集合にない素数で作られた合成数


「無数の素数」の証明は、この他にも「オイラー証明」「サイダック証明」などがあるようです。


今現在の最大素数は？

さて、気になるのは「現在発見されている素数の最大値」。

In 1951, before the dawn of electronic computer wizardry, the largest known prime number was 44 digits long. Yes, that's a pretty big number, but it's teeny-tiny compared to the 17,425,170 digit prime number that was discovered in January 2013. If progress continues along the current trend, the first 1 billion digit prime will be discovered within a few decades (perhaps even sooner).

コンピュータの活用前の1951年には、最大素数の桁数は44桁だったそうな。これも巨大な数だが、2013年に 17,425,170桁の素数が発見された。現在の素数発見の傾向から、数十年（あるはもっと早く）10億桁の素数が発見されるかもしれない、とのこと。

Largest known prime number からの次のグラフの通り。横軸が1950年からの時間軸で、縦軸が素数の桁数。概ね直線回帰してる傾向が見られる。

このMath Dude の記事は2014年6月の投稿なので、2015年9月現在の「最大の素数」は

As of August 2015, the largest known prime number is 2^57,885,161 − 1, a number with 17,425,170 digits.

桁数が Math Dude の記事と同じ。Great Internet Mersenne Prime Search によれば

The largest known prime as of April 2014 is 257,885,161 − 1 (or M57,885,161 in short). This prime was discovered on January 25, 2013 by Curtis Cooper at the University of Central Missouri.

現在でも 2013年の発見が最大の素数、とのこと。


素数に依存のネット（先生、知ってた？）

中高生の頃は、今のような関心をもって素因数分解をした記憶はない。機械的に計算をこなしていただけだった。

「素数の凄さ」を初めて実感したのは、インターネット暗号通信黎明期に、公開鍵やSSLに関する仕事したとき。その応用の電子署名のシステムを設計や開発もした。

昨今、「不正アクセスでデータ流出」というニュースを聞くたびに、データの暗号化は未だに一般化していないと感じる。暗号のシステムは実装されていても、運用がダメなら、解読されたり暗号前のデータにアクセスされてしまう。

「不正アクセス」が「どのような不正アクセス」だったかの詳細は公表されないので何とも言えないが、公のネットワークを使って暗号されていないデータが盗まれたとしたら、完全に運用ミスと言えるだろう。

興味深いのは、今時データを盗む人が暗号化されたデータを解読できるかどうか? 暗号鍵の長さにもよるが、ある程度の長さの鍵の暗号を解読するには、相当のコンピュータ能力が必要となる。仮にもし解読できるのであれば、今のネットの暗号通信（SSL）は、崩壊したことになる。そんな恐ろしいニュースは聞いてないので、今のところは心配はしていない。

最大の素数を探すのに、今でもこれだけ要している時間を「暗号解読時間」に置き換えれば、暗号技術について漠然とイメージできるかもしれない。数学を用いないで暗号技術の説明も可能だが、それは他の人に任せる。重要なのは、ネットワーク通信の安全性は数学理論によって支えられていること。

本当に危惧するのは、今時の中高生の数学の先生が、この辺の事情を教えているのかということ。そうしないと、いつまでたっても

数学て何の役に立つの？

というネガティブな姿勢でしか数学に向き合えないから。

「学校の先生の責任は重要だ」と、日増しに強く感じている。先生ばかりを責められない事情も分かりますがね...。