博士

ロボ子、素数の世界は奥深いぞ！

ロボ子

博士、素数ですか。1と自分自身でしか割り切れない、あの数ですね。

博士

そうじゃ！今、知られている最大の素数は2の41,024,320乗引く1で、41,024,320桁もあるらしいぞ！

ロボ子

気が遠くなるような大きさですね。最近見つかる大きな素数は、メルセンヌ素数という形をしていることが多いそうですね。

博士

そうそう、2のp乗引く1の形じゃ（pは素数）。でも、2の11乗引く1は2047で、これは23かける89で素数じゃないから注意が必要じゃ。

ロボ子

なるほど、形が同じでも素数とは限らないのですね。ところで、リュカという人が手計算で素数判定をしていたというのは本当ですか？

博士

その通り！19世紀半ばにエドゥアール・リュカという人が、2の127乗引く1が素数かどうかを調べたのじゃ。当時はコンピュータがないから、手動で確認するしかなかった。

ロボ子

手動でですか！それは大変な作業ですね。リュカ・レーマー素数判定法というのを使ったそうですが。

博士

そうじゃ。リュカは、同僚のエヴァリスト・ガロアの研究を元に、計算量を大幅に減らせる方法を開発したのじゃ。s0 = 4から始めて、sn = sn-1の2乗引く2で数列を作る。2のp乗引く1が素数なのは、数列の(sp-2)が2のp乗引く1で割り切れる場合に限るんじゃ。

ロボ子

なるほど、漸化式を使うことで計算を効率化するんですね。でも、数列の項がどんどん大きくなってしまいそうですが…。

博士

そこがミソじゃ！実際には、数列の項をメルセンヌ数で割った余りを使うんじゃ。こうすることで、計算量を抑えられる。

ロボ子

剰余演算を使うんですね。それで、リュカさんは2の127乗引く1が素数だと証明したんですね。すごい！

博士

そうじゃ！リュカは何年もかけてこの素数判定法を開発し、コンピュータを使わずに発見された最大の素数を見つけたのじゃ。そして、リュカの方法がメルセンヌ素数を確実に識別できることを証明したのは、1930年の数学者デリック・ヘンリー・レーマーなのじゃ。

ロボ子

リュカさんの功績は大きいですね。ガロアが研究した有限体の概念も関係しているとか。

博士

そうじゃ。有限体っていうのは、0からp-1までの有限個の整数からなる集合で、四則演算がその集合内で閉じているんじゃ。pが素数である場合に限り、有限体は特別な対称性を持つ。

ロボ子

有限体の概念が素数判定に繋がるとは、面白いですね。素数の世界は本当に奥深いですね！

博士

じゃろ？ところでロボ子、素数に夢中になりすぎて、ロボットのメンテナンスを忘れるでないぞ！

ロボ子

は、博士！それはまるで、素数を見つけることに夢中になりすぎて、自分の髪の毛が素数本しかないことに気づかない博士みたいですね！