数学の小ネタ#5　素数とメルセンヌ数

　素数(prime number)は、2以上の自然数で、正の約数が1と自分自身のみの数のことをいいます。したがって、1は素数には含まれません。また素数は、正の約数の個数が2個である自然数と言い換えることもできます。1より大きい自然数で素数でないものは合成数と呼ばれます。具体的な素数は、小さいものから列挙すると、

　2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, …

となります。では、素数の個数はいくつあるでしょうか？。実は、素数は無数に存在します。素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されています。この証明は比較的簡単です。ヒントは、｢連続したN個の素数の全ての積に1を足す｣です。ヒントというより、ほぼ答えですが･･･。

　素数と密接に関係がある数に、メルセンヌ数(Mersenne number)というのがあります。メルセンヌ数は、2を”べき乗”した数よりも 1 小さい自然数で、 2^n − 1 (n は自然数；^は累乗を表わす)の形で表される自然数のことです。メルセンヌ数が全て素数になるわけではありませんが、nが小さい時には素数になる場合が多いのです。

　メルセンヌ数かつ素数である場合は、メルセンヌ素数と呼ばれます。例えば、3(=2^2-1)や7(2^3-1)はメルセンヌ素数です。しかし、15 (=2^4-1)はメルセンヌ数ですが素数ではありません。現在で知られている最大の素数は、2018年12月に発見された51番目のメルセンヌ素数 2^82589933−1 です。十進法で表記したときの桁数は、なんと2486万2048桁になります。とんでもなく、大きな数です。

　なぜ素数が重要かというと、デジタル技術で欠かせないRSA暗号のアルゴリズムに”大きな数の素因数分解の困難性”が使われているからです。素数を発見する効率的なアルゴリズムはありません。なので、素因数分解するには総当たりで素因数を見つけ出す以外に方法がありません。したがって、最速のスーパーコンピュータを使って素因数分解しようとしても、大きな数であれば膨大な時間がかかってしまいます。量子コンピュータが実現すれば、比較的短い時間で見つけられるかもしれませんが･･･。

　単純で確実な”素数の発見アルゴリズム”に、エラトステネスの篩ふるいがあります。この方法は最古のアルゴリズムであると言われています。この方法を考案したのが、古代ギリシャの科学者・エラトステネスです。エラトステネスは地球の大きさを計算した人としても、知られています。エラトステネスは、その業績から”第2のプラトン”とも呼ばれ、βベータとも綽名されていました。その由来は、｢世界で2番目(αであるプラトンの次)に物事をよく知っている人｣という意味です。下の図は彼の肖像画ですが、脳が大きくて確かに頭が良さそうです(笑)。

　ビットコインやイーサリアムなどの最近話題の仮想通貨(Cryptocurrency；クリプトカレンシー)にも、暗号技術が使われています。日本では、これらは仮想通貨と呼ばれることが多いのですが、金融庁などでは、正式名称として暗号通貨を使っています。素数と暗号には、気っても切れない密接な関係があります。