人と星とともにある数学 第19回

標準

2017年7月31日


おおむね素数 概素数

工業レベルの素数とは

素数は難しい

1と自分自身のみを約数に持つ自然数が素数です。2、3、5、7、11、13、17、19、23、29、31、37、41、…。約数さえ理解できれば素数自体は容易です。

87は素数でしょうか。87=3×29なので87は素数ではありません。1より大きい自然数で素数でない数を合成数と呼びます。では、1729はどうでしょう。少し時間をかければ、1729=7×13×19とわかり1729は素数ではないことが判明します。

与えられた数が大きくなると、素数か合成数の判定は途端に容易ではなくなります。ここに数学が必要になります。その意味で素数は難しいと言えます。連載「サラリーマンのための超入門・リーマン予想」でも紹介したリーマンによるリーマン予想(1859年)の発見は、素数を探究した末にたどり着いた深い闇です。

ところで、1より大きい自然数は素数か合成数のどちらかでしたから、素数判定とともに合成数判定も考えられます。合成数とは2つ以上の素数の積で表すことができる自然数のことです。例えば6や30はそれぞれ2×3、2×3×5と素数の積で表される合成数です。

「フェルマーの小定理」を確かめる

フェルマーの小定理といわれる定理があります。「pが素数ならば、任意の整数nのp乗をpで割った余りはnである」というものです。ちなみに同じフェルマーによるフェルマーの大定理は、「3以上の自然数nに対してxn+yn=znは自然数の解をもたない」というもので、1994年にワイルズによって証明されました。

ではフェルマーの小定理を具体的に計算して確かめてみましょう。

素数p=3の場合
n=2 23=8 → 3で割ると商が2、余りは2
n=3 33=27 → 3で割ると商が8、余りは3
n=4 43=64 → 3で割ると商が20、余りは4
n=5 53=125 → 3で割ると商が40、余りは5

素数p=5の場合
n=2 25=32 → 5で割ると商が6、余りは2
n=3 35=243 → 5で割ると商が48、余りは3
n=4 45=1024 → 5で割ると商が204、余りは4
n=5 55=3125 → 5で割ると商が624、余りは5

このように余りはnと等しいことがわかります。もっと大きな数で確かめてみましょう。

素数p=17の場合
n=2 217=131072 → 17で割ると商が7710、余りは2
n=3 317=129140163 → 17で割ると商が7596480、余りは3
n=4 417=17179869184 → 17で割ると商が1010580540、余りは4
n=5 517=762939453125 → 17で割ると商が44878791360、余りは5

やはり最後の余りはnと等しくなります。「任意の整数nのp乗」の指数部分pが素数でないと、こうはなりません。例えば、指数部分を6とすれば、

素数でないp=6の場合
n=2 26=64 → 6で割ると商が10、余りは4
n=3 36=729 → 6で割ると商が121、余りは3
n=4 46=4096 → 6で割ると商が682、余りは4
n=5 56=15625 → 6で割ると商が2604、余りは1

となり、余りがnと等しくない場合が出てきます。

さてフェルマーの小定理は次のように言い換えることができます。
「pとnは互いに素(公約数が1だけ)のとき、pが素数ならば、任意の整数nのp-1乗をpで割った余りは1である」

先の計算例で再びこのことが成り立つかを確かめてみましょう。

素数p=3の場合
n=2 22=4 → 3で割ると商が1、余りは1
n=3 pとnは互いに素でない。公約数が1以外の3がある。
n=4 42=16 → 3で割ると商が5、余りは1
n=5 52=25 → 3で割ると商が8、余りは1

「フェルマーの小定理」は合成数の判定法には使える

フェルマーの小定理を次のように言い換えることができます(対偶をとる)。
「pとnは互いに素(公約数が1だけ)のとき、任意の整数nのp-1乗をpで割った余りが1でないならば、pは素数ではない」
すなわち、
「pとnは互いに素(公約数が1だけ)のとき、任意の整数nのp-1乗をpで割った余りが1でないならば、pは合成数である」
ということです。フェルマーの小定理は合成数の判定法となり得ることがわかります。

例えば、p=8として
pと互いに素であるn=5 57=78125 → 8で割ると商が9765、余りは5 → 余りは1でない → p=8は合成数

これに対して、「余りが1」となる場合はpは素数、合成数どちらにもなります。
p=23として
pと互いに素であるn=5 522=2384185791015625 → 23で割ると商が2384185791015624、余りは1 → p=23は素数!

p=25として
pと互いに素であるn=7 724=191581231380566414401 → 25で割ると商が7663249255222656576、余りは1 → p=25=5×5 は合成数!

概素数

残念ながらフェルマーの小定理は素数判定法にはなり得ません。しかし、興味深いことに「余りが1」となる場合、pは素数である確率が大きいことがわかっています。

そこで、フェルマーの小定理の計算で最後の「余りが1」となる場合、pはprobable primeと呼ばれています。おおむね素数という意味で、日本語では概素数と呼ばれます。「概算」からわかるように、概(おおむね)は「大体のところ。あらまし」という意味です。

フェルマーの小定理を用いることで、probably(おそらく)素数であることが判定できます。それゆえ、このような素数判定法を確率的素数判定法と呼びます。フェルマーの小定理を用いた確率的素数判定法はフェルマーテストと呼ばれます。

さて、正確な表現として、pとnは互いに素(公約数が1だけ)のとき、整数nのp-1乗をpで割った余りが1である場合のpのことをnを底とした概素数と呼び、n-PRPと書きます。そして、素数でない(合成数である)概素数を擬素数(ぎそすう、pseudoprimes)と呼びます。素数擬き(もどき)という意味です。

工業レベルの素数

25,000,000,000(250億)以下には、素数は1,091,987,405(約10億)個存在します。同じ範囲に2を底とする擬素数(合成数の概素数)は21,853個(0.0000874%)しかありません。事実、擬素数は素数に比べて珍しいことがエルデシュによって1950年に証明されています。

このことからHenri Cohen(コーエン)は2-RPRを「工業レベルの素数」と呼んでいます。確率的素数判定法によって見つかる素数のように、実用上問題ない精度で判定できる素数をこう呼びます。インターネット上で用いられるRSA暗号には2つの巨大な素数が必要ですが、確率的素数判定法であるミラーラビン法によって見つかる工業レベルの素数が用いられています。

驚異のカーマイケル数

高速な素数判定のために、フェルマーの小定理を用いた確率的素数判定法「フェルマーテスト」を様々な底nについて(底2を試し、次に底3、次に底5、…)行うことで厳しい素数判定ができるようになります。

ところが、すべての底nに対してフェルマーテストで「余りが1」になる擬素数が存在するという衝撃的な事実が明らかになりました。1910年、Carmichael(カーマイケル)によって発見されました。このカーマイケル数は、自身と互いに素である任意の底でフェルマーテストをすり抜ける合成数で、絶対擬素数(absolute pseudoprimes)とも呼ばれます。

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361

100,000以下のカーマイケル数

素数は面白い

素数は難しい。私自身、28番目メルセンヌ素数286243-1(25962桁)の素数判定を実際に行ってみてそのことを実感しました。しかし、同時に「チャレンジするに値する数が素数である」ことを強く感じました。

概素数、擬素数、工業レベルの素数、カーマイケル数、絶対擬素数、これらの言葉たちが、私たちが素数にチャレンジしてきた軌跡を物語ります。


関連記事
・人と星とともにある数学 第1回
・人と星とともにある数学 第2回
・人と星とともにある数学 第3回
・人と星とともにある数学 第4回
・人と星とともにある数学 第5回
・人と星とともにある数学 第6回
・人と星とともにある数学 第7回
・人と星とともにある数学 第8回
・人と星とともにある数学 第9回
・人と星とともにある数学 第10回
・人と星とともにある数学 第11回
・人と星とともにある数学 第12回
・人と星とともにある数学 第13回
・人と星とともにある数学 第14回
・人と星とともにある数学 第15回
・人と星とともにある数学 第16回
・人と星とともにある数学 第17回
・人と星とともにある数学 第18回


執筆者ご紹介  桜井進(さくらいすすむ)様
1968年山形県生まれ。
サイエンスナビゲーター®。株式会社sakurAi Science Factory 代表取締役。
(略歴)
東京工業大学理学部数学科卒、同大学大学院院社会理工学研究科博士課程中退。東京理科大学大学院、日本大学芸術学部非常勤講師。
理数教育研究所Rimse「算数・数学の自由研究」中央審査委員。高校数学教科書「数学活用」(啓林館)著者。
2000年、日本初のサイエンスナビゲーターとして数学の驚きと感動を伝える講演活動をスタート。
東京工業大学世界文明センターフェローを経て現在に至る。