おおむね素数 概素数 工業レベルの素数とは

おおむね素数 概素数 工業レベルの素数とは

  • JBpress
  • 更新日:2016/10/21
No image

香港で公開された英数学者A・チューリングの手稿〔 AFPBB News 〕

素数は難しい

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に対してx^n+y^n=z^nは自然数の解をもたない」というもので1994年にワイルズによって証明されました。

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

素数p=3の場合
n=2 2^3=8 → 3で割ると商が2で、余りは2
n=3 3^3=27 → 3で割ると商を8として、余りは3
n=4 4^3=64 → 3で割ると商を20として、余りは4
n=5 5^3=125 → 3で割ると商を40として、余りは5

素数p=5の場合
n=2 2^5=32 → 5で割ると商が6で、余りは2
n=3 3^5=243 → 5で割ると商を48として、余りは3
n=4 4^5=1024 → 5で割ると商を204として、余りは4
n=5 5^5=3125 → 5で割ると商を624として、余りは5

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

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

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

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

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

さてフェルマーの小定理は次のように言い換えることができます。

「pとnは互いに素(公約数が1だけ)のとき、pが素数ならば、任意の整数nのp-1乗をpで割った余りは1である」

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

素数p=3の場合
pと互いに素であるn=2 2^2=4 → 3で割ると商が1で、余りは1
pと互いに素でないn=3 3^2=9 → 3で割ると商が3で、余りは0
pと互いに素であるn=4 4^2=16 → 3で割ると商が5で、余りは1
pと互いに素であるn=5 5^2=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 5^7=78125 → 8で割ると商が9765で、余りは5 → 余りは1でない → p=8は合成数

これに対して、「余りが1」となる場合はpは素数、合成数どちらにもなります。

p=23として
pと互いに素であるn=5 5^22=2384185791015625 → 23で割ると商が2384185791015624で、余りは1 → p=23は素数!

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

概素数

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

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

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

さて、正確な表現として、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番目メルセンヌ素数2^86243-1(25962桁)まで素数判定ができましたが、29番目はできませんでした。素数判定の喜びを味わうと同時に素数にアタックすることの困難さを実感しました。チャレンジするに値する数が素数だということです。

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

この記事をお届けした
グノシーの最新ニュース情報を、

でも最新ニュース情報をお届けしています。

外部リンク

コラム総合カテゴリの人気記事

グノシーで話題の記事を読もう!
1万4千円の婚約指輪を店員に笑われ......花嫁の返答が話題に
リーダーになってはいけない人の3つの特徴
【正答率1%だと!?】解けたらIQ167の問題が話題に!あなたは天才か、それとも凡人か?
【体の不思議】耳にできる「くさい穴」を知ってる? 衝撃の認知度とは......
ひとりエッチも卒業!「オマエしか見えない」カレシ独占エッチ2つ
  • このエントリーをはてなブックマークに追加