Yahoo!ニュース

じつに6年ぶりの大発見！…なんと「桁数が4102万4320」の素数を叩き出した「1」の魔法

配信

現代ビジネス

巨大な数の場合は？

リュカ・レーマーテストは、数列Sₙを2ᵖ－1で割った余りを調べます。pが大きくなると,2ᵖ－1がとても大きな数になります。2ᵖ－1をどのように表すか,そして,どのように割り算をおこなうか,という問題が生じます。 この問題を解決する1つの方法が2進法です。

2進法で問題解決

メルセンヌ数2ᵖ－1は2進法で書くと 111… 11　(p桁) という特別な形の数になります。10進法で2ᵖ－1で割ることは、2進法ではp桁の111… 11で割ることです。そして,2進法で100… 00をp桁の111… 11で割った余りは、下位の0をp個とることを繰り返すと得られます。 たとえば、p=3のとき、2³－1=7を2進法で表すと 111 となります。2進法で 1000=111+1 だから、1000を111で割った余りが1になります。この余りの1は、1000の下位の0を3つとることで得られます。 このような計算で、2進法では 1, 10, 100, 1000, 10000, 100000, 1000000, … を111で割った余りは 1, 10, 100, 1, 10, 100, 1, … となります。 下位の0を3つとることを繰り返すことで得られます。

下位に0が並ばない数では？

また,2進法で1011のように下位に0が並ばない数を111で割る場合, 1011=1000+11 と変形します。右辺を111で割った余りは 1+11 です。2進法で 1+11=100 なので、1011を111で割った余りは100になることがわかります。 ところで、これと同様の原理を用いて手計算で発見された最大の素数が何桁におよぶか、想像がつきますか？

手計算で発見された最大の素数

リュカは1876年に、このような原理を使って 2¹²⁷－1=170141183460469231731687303715884105727 が素数であることを示しています。 リュカは上で紹介した数列ではなく,Sₙ=S²ₙ₋₁－2の式が同じで,初項がS₁=3の数列Sₙを使って,2進法のS₁₂₆が 111111111111111111111111111111111 111111111111111111111111111111111 111111111111111111111111111111111 1111111111111111111111111111(127桁) で割り切れることを示しました。 じつに、127桁におよぶ数字です。これができたときの感動には、計り知れないものがあります。 リュカの結果は、手計算で発見された最大のメルセンヌ素数です。

次ページは：巨大な素数は暗号に使われている

2/3ページ

【関連記事】