ホーム
吉田 安紀彦はじめに
素数と聞いて、「2,3,5,7,11…のことだよね」と分かった人も多いと思いますが、では、現在までに見つかっている最も大きな素数はご存知ですか？じつは、その素数は2千万桁以上にもなります。どうやってその数が素数であることがわかったのか、考えてみるとふしぎではありませんか？2千万桁の数を2からひとつずつ割っていくわけにもいかないし。ということで、ここでは素数の判定方法などをまとめてみました。なお、この文章での「現在」とは2018年7月14日のことです。
素数とは
\(2,3,5,7,11,13,17,19,23,29,31\cdots\)というような数のことです。 素数の定義は色々ありますが、簡単に言うと「その個数のおはじきを長方形に並べることができない数。ただし1列に並べるのは除く」と言えると思います。
素数の記録
2017年12月26日、現在までに見つかっている素数の中で一番大きな素数の\(2^{77232917}-1\)が発見されました。これは23249425桁の素数で、１ページびっしりに印刷しても719ページの本になります。（実際にAmazonで売られていたり…） このような素数の記録は「The Prime Pages」(http://primes.utm.edu/)で管理されています。
素数の種類
素数と言っても、ただのランダムな素数や、きれいな数式で表される素数、ある数列の中に出てくる素数など様々な種類があります。といっても整数の種類はたくさんあるのでここで紹介するのはほんの一部です。
メルセンヌ素数 (Mersenne Prime) \(2^n-1\)
先ほどの\(2^{77232917}-1\)がその例です。現在50個のメルセンヌ素数が発見されています。また、現在発見されている素数の大きい方から10個のうち、9個がメルセンヌ素数です。n=2,3,5,7,13,17,19,31,61,89の時などがメルセンヌ素数です。フェルマー素数 (Fermat Prime) \(2^{2^n}+1\)
nが少し大きくなるだけで\(2^{2^n}+1\) は大きくなってしまうので、探すのが大変な素数の一つです。 nが32のとき（1292913986桁）までは素数かどうかが分かっていて、そのうちnが0,1,2,3,4のときのみが素数です。nが4よりも大きいとき素数になるかどうかはわかっていないのですが、初めの5個だけ素数で、そのあとには素数がまだ見つかっていないっていうのはちょっと不思議な感じがします。プロス素数 (Proth Prime) \(k\cdot2^n+1(2^n>k)\)
メルセンヌ素数のところで、現在発見されている素数の大きい方から10個のうち9個がメルセンヌ素数だと書きましたが、その残りの1個がこのプロス素数の \(10223\cdot 2^{31172165}+1\)です。双子素数 (Twin Primes)
隣り合っている2つの奇数（pとp+2）の両方が素数である数です。 現在見つかっている中で最大の双子素数は、2016年9月に発見された \(2996863034895\cdot 21290000 \pm 1\)（388342桁）です。階乗素数 (Factorial Primes) \(n!+1,n!-1\)
一瞬、この数はnまでは割れないので、全てが素数なように見えますが実は少なく、 \(n!-1\) は27個、 \(n!+1\) は22個しか見つかっていません。現在見つかっている最大の階乗素数は、2016年7月に発見された\(208003!-1\)（1015843桁）です。 2018/7/14現在 \(n=250823\) まで探索が終了しています。 (http://prpnet.primegrid.com:12002/server_stats.html)素数階乗素数 (Primorial Primes) \(n\#+1,n\#-1\)
2から順にnまでの素数をすべてかけた数を \(n\#\) と表します。 この数も、見た目よりはるかに素数になりにくく、 \(n\#-1\) は20個、 \(n!+1\) は22個しか見つかっていません。現在見つかっている最大の素数階乗素数は、2012年3月に発見された \(1098133\#-1\) （476311桁）です。 2018/7/14現在 \(n=2550167\) まで探索が終了しています。 (http://prpnet.primegrid.com:12008/server_stats.html)レピュニット素数 (Repunit Prime) \((10^n-1)/9=11111111....11\)
1だけでできた数、Repeated unit（反復単位数）を縮めてレピュニット(Repunit)と呼び、この数が素数の時、レピュニット素数といいます。 現在見つかっている最大の素数（確率的素数）は、2007年7月に発見された \((10^{270343}-1)/9\) です。 現在、\(n=2500000\)までの素数の探索が完了しています。 (http://www.elektrosoft.it/matematica/repunit/status.htm)ニアレピュニット素数 (Near Repunit Prime)
レピュニット数の数字をひとつだけ別の数に置き換えた数です。 現在見つかっている（たぶん）最大のニアレプディジット素数（確率的素数）は2014年12月に発見された \((64 \cdot 10^{762811}-1)/9=711111...111\) です。ニアレプディジット素数 (Near Repdigit Prime)
すべての位が同じ数のことをレプディジット数とよびます。そのレプディジット数の数字をひとつだけ別の数に置き換えた素数です。現在見つかっている最大のニアレプディジット素数は、2013年9月に発見された\(2\cdot 10^{1059002}-1=199999...99\)です。回文素数 (Palindrome Prime)
上から読んでも下から読んでも同じ素数です。 現在の最大は2014年11月に発見された\(10^{474500}+999\cdot 10^{237249}+1=100000\cdots 00000999000\cdots00001\) です。フィボナッチ素数 (Fibonacchi Prime)
フィボナッチ数列とは、\(1,1,2,3,5,8,13,21,34,55,89,144\cdots\)のことで、このうち素数のフィボナッチ数のことです。現在51個の確率的素数が見つかっていて、その最大は3340367番目の698096桁の数です。また、この51個のうち34個は素数であることが証明されています。Smarandache素数 (Smarandache Prime)
1234567891011121314151617…というふうに１から順に自然数を並べた素数です。（1,112,123,1234,12345,123456,1234567,12345678,123456789,12345678910,1234567891011…）この形の素数はすぐに見つかりそうですが、現在、少なくとも344869まで探索され、まだ一つも見つかっていません。 ちなみに、\(12345678901234567890123456789012\cdots\)が素数なのは、\(n=171,277,367,561,567,18881\)です。（これ以降は380000まで探索しましたが、まだ見つけていません）Wall-Sun-Sun素数（Fibonacci-Wieferich素数）
同じ素数に2つも名前がついていますが、現在まだ見つかっていません。Wilson素数 (Wilson Prime)
pを素数として、\(p^2\)が\((p-1)!+1\)を割り切るとき、その素数pをWilson素数といいます。 現在、20,000,000,000,000までの素数675,895,909,271個が調べられましたが、\(p=5,13,563\) しか見つかっていません。 (https://arxiv.org/abs/1209.3436)Wieferich素数 (Wieferich Prime)
pを素数として、\(p^2\)が\(2^{p-1}-1\) を割り切るとき、その素数pをWieferich素数といます。現在、607,131,900,000,000,000までの素数15,208,298,813,191,373個を調べられましたが、p=1093,3511しか見 つかっていません。 (http://u-g-f.de/PRPNet/wrange_stats.php?proj=WFS)素数探索の歴史
1588年、イタリアの数学者Pietro Cataldiが \(2^{17}-1=131071\)と \(2^{19}-1=524287\)を発見しました。なんと手計算で、しかもローマ数字で743までの素数表をつくり、それで１つ１つ割って発見しました。 1772年、１８世紀を代表する数学者のオイラーが、\(2^{31}-1=2147483647\)を発見しました。\(2^{31}-1\)の約数は \(248\cdot n+1\) か\(248 \cdot n+63\) の形でなければならないことを見つけ、実際に割ってみて発見したといわれています。 1867年、Landryが (259-1)/179951が素数であることを見つけました。この素数はメルセンヌ数以外の素数として、長く記録に残りました。 1876年、リュカ(Lucas)が\(2^{127}-1=170141183460469231731687303715884105727\) を発見しました。リュカ数列を使って15歳のときから手計算で素数判定を始め、19年後ついに素数であることを確かめました。これが、手計算で見つけられた最大の素数です。 1951年、Ferrierが \((2^{148}+1)/17=20988936657440586486151264256610222593863921\) を、機械式電卓を使って発見しました。これでコンピューター以前の時代は終了し、その年のうちにMillerとWheelerがイギリスのコンピューターEDSACで79桁の素数\(180\cdot (2^{127}-1)^2+1=5210644015679228794060694325390955853335898483908056458352183851018372555735221\) を見つけました。 その翌年の1952年には、Raphael RobinsonがアメリカのコンピューターSWACを使って \(2^{521}-1,2^{607}-1,2^{1279}-1,2^{2203}-1,2^{2281}-1\) を見つけました。このうち最初の２つの素数はプログラムを走らせ始めたその日のうちに見つかりました。 その後、1957年には \(2^{3217}-1\)、1961年には \(2^{4423}-1,2^{4253}-1\)、1963年には \(2^{9689}-1,2^{9941}-1,2^{11213}-1\) というように順調に記録を伸ばし続けています。 上の \(2^{4423}-1,2^{4253}-1\) の2つの素数について、面白いエピソードが残っています。この素数を発見したHurwitzは、2つのうち大きい方の素数 \(2^{4423}-1\) を \(2^{4253}-1\) より数秒前に知りました。出力用紙が重なっていたからです。素数が「発見された」と言うためには人間がその結果を見る必要があるのか、それともコンピューターが知っていればいいのか微妙なところですが、出力結果を人間が見たときに発見したと言うとすると \(2^{4253}-1\) が最大の既知素数になることはありませんでした。
素数判定法
素数の判定方法は、大きく分けて決定的素数判定法と確率的素数判定法の2つがあります。 決定的素数判定法とは絶対に素数であると証明できる判定方法で、確率的素数判定法は素数である確率が非常に高いと言えるが、100%素数であるとは言えない判定方法のことです。 他にも、特殊な数に対して判定できる方法などがあります。
試し割り（決定的素数判定法）
\(\sqrt N\) までのすべての素数で割ってみて、そのどれでも割り切れなかったら\(N\)が素数ではないと示すことができます。 この方法は最も手軽にできる方法ですが、\(N\)が20桁を超えるくらいになると、2から10000000000くらいの素数の全てで割らなければならず、現実的な時間で終わらないので、試し割りができるのはせいぜい15桁くらいまでだと思います。
フェルマーテスト（確率的素数判定法）
大きな数の素数判定をするのに最も一般的に使われる方法が、フェルマーの小定理を使ったフェルマーテストです。 フェルマーの小定理とは、 \(p\)を素数、\(a\)を\(p\)の倍数でない任意の整数とすると、\(a^{p-1}\equiv 1\ (mod\ p)\) が成り立つ。 という定理です。 この定理を逆に使って、\(n\)が素数かどうか判定することができます。\(a\)を適当に選んで\(a^{n-1}\ mod\ n\) を計算してみて、\(1\)ではなかったら絶対に素数ではなく、\(1\)だったらおそらく素数だろうと言えます。その\(1\)のときの\(n\)を、\(a\)を底とする概素数(probable prime)と呼び、a-PRPと書きます。 例えば、77が素数かどうか調べてみます。 \(2^{77-1}=2^{76}=75557863725914323419136=77×981270957479406797651+9\) 余りは9なので、77が素数ではないことが分かりました。 しかし、この方法は100%素数とは言えません。例えば、341は2-PRP （つまり\(2^{341-1}\ mod\ 341=1\)）ですが、341=11×31は素数ではありません。ほかにも、1,000,000,000,000以下に2-PRPだけれども素数ではない数は101,629個あります。それでも、1,000,000,000,000以下の素数は37,607,912,018個あるので、それと比べると成功率は非常に高いのが分かります。また、複数の底\(a\)に対してテストをすればもっと正確に判定できます。 ただし、\(n\)の約数以外の底に対してはすべてフェルマーテストを通ってしまう、Carmichael数と呼ばれる数があります。このような数は1,000,000,000,000までに8241個と少ししかありませんが、無限個存在することが示されています。
ミラー・ラビン判定法（確率的素数判定法）
Gary Miller氏が発表したMillerテストをベースにして、1976年にMichael Rabin氏が発明した素数判定法です。 細かい説明は省略しますが、\(n\)がミラー・ラビン判定法を通った時、\(n\)は\(a\)を底とする強概素数(strong probable prime)と呼び、a-SPRPと書きます。 この方法でもおそらく素数だと間違えて判定してしまう可能性はありますが、1,000,000,000,000以下の合成数（素数ではない数のこと）のうち2-SPRPは22407個（2-PRPは101629個）、1,000,000,000,000以下の合成数のうち2, 3, 5, 7, 11-SPRPは0個（2, 3, 5, 7, 11-PRPは5718個）というように、フェルマーテストよりも優れています。さらに、フェルマーテストの時のCarmichael数のような数が無いことがわかっています。
リュカ擬素数テスト（確率的素数判定法）
リュカ擬素数テスト、Lucas-Lehmer 法、Lucas擬素数判定法、Lucas pseudoprime test、Lucas-Selfridgeとも呼ばれています。 ここで、擬素数(Pseudoprime)とは素数ではないのにおそらく素数だと判定されてしまった数のことを言います。 リュカ擬素数テストの中でも、複数の判定法があります。大きく分けてⅠとⅡの2段階があり、３以上の合成数\(n\)に対してⅠを満たす\(n\)をリュカ擬素数(Lucas Pseudoprime)、Ⅱを満たす\(n\)を 強リュカ擬素数(Strong Lucas Pseudoprime)といいます。さらに、\(Q=-1\)のときⅢが成立する合成数\(n\)を超強リュカ擬素数(Extra Strong Lucas Pseudoprime) といいます。このとき、\(U_t\)を無視すると、ほとんど超強リュカ擬素数(Almost Extra Strong Lucas Pseudoprime)といいます。 それぞれの1,000,000,000,000以下の合成数のうちの擬素数の個数は、リュカ擬素数は116928個、強リュカ擬素数は25542個、ほとんど超強リュカ擬素数は17245個、超強リュカ擬素数は16231個です。 また、Bruckman-Lucas擬素数は43039個、フィボナッチ擬素数は77188個、ペル擬素数は89714個あります。
Baillie-PSW法（確率的素数判定法）
BPSW法とも呼ばれています。この方法は、上２つのミラー・ラビン判定法と強リュカ擬素数テストを組み合わせた判定法です。ミラー・ラビン擬素数で、かつ強リュカ擬素数であるような合成数しか失敗しませんが、このような数はまだ見つかっていません。
ペラン擬素数判定法（確率的素数判定法）
ペラン数列（Perrin Sequence）の性質の一つの、\(q\)が素数のとき\(p_q\)が\(q\)の倍数になることを逆に使い、\(p_q\)が\(q\)の倍数のとき\(q\)はペラン概素数(Perrin Probable Prime)といい、特に合成数のペラン概素数をペラン擬素数(Perrin pseudoprime)といいます。これは非常に少なく、1,000,000,000,000以下の合成数のうちペラン擬素数は285個しかありません。
Frobeniusテスト（確率的素数判定法）
Grantham’s Frobenius test、Quadratic Frobenius test、Frobenius-Grantham 法などとも呼ばれています。 この判定法の中でも複数あり、1,000,000,000,000以下の合成数のうち、(1,-1)のFrobenius擬素数は37527個、(3,-5)のFrobenius擬素数は1532個、(P, 2)のFrobenius擬素数は０個、Frobenius-Underwood擬素数は0個で、この中で(P, 2)のFrobenius擬素数とFrobenius-Underwood擬素数はまだ発見されていません。
Kraitchik-Lehmer法（決定的素数判定法）
ここからは100%素数だと言える決定的素数判定法を紹介していきます。 Kraitchik-Lehmer法は、Lucasの判定法、Lucas primality test、ｎ-1判定法とも呼ばれています。素数判定をしたい数\(n\)に対して、\(n-1\)の素因数分解ができていれば、確定的に素数かどうか判定できる、つまり素数であることの証明ができるという判定法です。しかし、これは\(n-1\)の素因数分解が完全にできていることが条件です。\(150209!+1\)のようにもともと素因数分解されている数に１を足した数についてはこの方法が使えますが、そうではなくてランダムに選んだ大きな数は素因数分解するのが大変なので、そのような数に使うのは厳しいです。
ポクリントンの判定法（決定的素数判定法）
ポクリントンの判定法は、一般Pocklington法、Pocklingtonの判定法、ｎ-1判定法、Pocklington-Lehmer testとも呼ばれている方法です。 これは、\(n-1\)の素因数分解が５０％以上できている、つまり\(n-1=a\times b\times c \times\ \cdots\ \times R\)（\(a,b,c,\cdots\)は素数、\(R\)は合成数）というふうに素因数分解できているとき、\(R\)が\(\sqrt {n-1}\)以下のときに使える方法です。その他にも33.3%以上素因数分解できている、つまり\(R\)が\(\sqrt{R/F}\)以下の素因数を持たないときに使える方法もあります。
モリソンの判定法（決定的素数判定法）
Morrison’s testとも呼ばれています。これは、ポクリントンの判定法とは逆に\(n+1\)の素因数分解が33.3%以上出来ているときに使える方法です。
PPLS法（決定的素数判定法）
PPLS法は、Proth-Pocklington-Lehmer-Selfridge法、n-1/n+1法、複合判定法、combined method、combined \(n^2-1\) testとも呼ばれている判定法です。 これは、ポクリントンの判定法とモリソンの判定法を組み合わせたような判定法で、\(n-1\)と\(n+1\)の素因数分解されている部分の積が\(n\)の立方根より大きい場合に使える方法です。
ECPP法（決定的素数判定法）
これは楕円曲線素数判定法、Elliptic Curve Primality Proving法、ECPP法とも呼ばれています。この方法は、\(n-1\)と\(n+1\)の素因数分解が十分にできていない数\(n\)が素数である証明をするときに最も一般的に使われている判定法で、Goldwasser-Kilian の素数判定法、Atkin-Morain の素数判定法、高速楕円曲線素数判定法などがあります。
AKS素数判定法（決定的素数判定法）
AKS素数判定法（Agrawal-Kayal-Saxena素数判定法）は、Manindra Agrawal、Neeraj Kayal、Nitin Saxenaの三人が2002年に発表した判定法で、与えられた自然数が素数かどうかを決定性多項式時間でできるという衝撃的な方法でした。ただし発表された当初は、この方法では６桁の素数判定に10秒くらいかかるようなとてつもなく遅い方法でした。現在ではそれが改良されて100桁の素数判定に１秒くらいでできるようになりましたが、まだ楕円曲線素数判定法に比べると遅いです。
ヤコビ和法（決定的素数判定法）
ヤコビ和法は、Cohen-Lenstra法、Jacobi sums test、APR判定法とも呼ばれています。Leonard Adleman、Carl Pomerance、Robert Rumelyが発表した決定的素数判定法で、後にHenri CohenとHendrik Willem Lenstraが改良したものはAPR-CL判定法と呼ばれています。 それをもとに円分判定法（円分環素数判定法、cyclotomic primality testsとも呼ばれている）も作られました。
Lucas-Lehmer判定法（特殊な数に対する判定法）
ここからは、特殊な数に対する判定法を紹介していきます。 Lucas-Lehmer判定法は、L-L法、リュカ・レーマーテスト、Lucas-Lehmer testとも呼ばれている、メルセンヌ素数に対する判定法です。1930年に、D. H. Lehmerがエドゥアール・リュカの判定法を改良して作ったため、こう呼ばれています。\(2^{521}-1\)以降のメルセンヌ素数はすべてこの方法で見つけられました。最初の\(2^{77232917}-1\)もこの方法で素数だとわかりました。この判定法はコンピューターで計算しやすいため、巨大なメルセンヌ素数がいくつも発見されています。
Pepinの判定法（特殊な数に対する判定法）
フェルマー数\(F_n=2^{2^n}+1\)に対する判定法です。しかし、フェルマー数は\(n\)が少し大きくなるだけでとてつもない大きさになるので、この判定法に当てはめて計算することは難しいです。例えば、まだ素数かどうかわかっていない\(F_{33}\)は2,585,827,973桁の数です。これは今見つかっている中で一番大きな素数\(2^{77232917}-1\)の23,249,425桁の100倍以上の桁数です。
Prothの判定法（特殊な数に対する判定法）
プロス数 \(h×2^k+1\) （ただし \(2^k>h\)） に対する判定法です。プロス数という名前は、フランスの独学の数学者で農家のFrancois Prothに由来します。
LLRテスト（特殊な数に対する判定法）
Lucas-Lehmer-Rieselテストは、\(h×2^k-1\)（ただし \(2^k>h\)）に対する判定法です。メルセンヌ素数の判定法のLucas-LehmerテストをベースにしてHans Rieselが発展させました。
素数判定法の速度比較
実際に複数の素数判定法の速度を調べてみました。最近のCPUでシングルスレッドでの実行時間です。
10桁から100桁
全てmpirというライブラリを使用。試し割りは素数に対する判定。 L-LとはLucas-Lehmer判定法のことです。
| 桁 | 試し割り(秒) | 2-PRP(秒) | 2-SPRP(秒) | ECPP(秒) | L-L(秒) |
|---|---|---|---|---|---|
| 10 | 0.0003162 | 0.00000207 | 0.00002015 | 0.00156 | 0.0000423 |
| 15 | 0.1001246 | 0.00000241 | 0.00001970 | 0.01515 | 0.0000423 |
| 20 | 202.321935 | 0.00000345 | 0.00002327 | 0.03909 | 0.0000457 |
| 30 | 0.00000531 | 0.00002534 | 0.26259 | 0.0000395 | |
| 40 | 0.00000914 | 0.00003315 | 0.78847 | 0.0000323 | |
| 50 | 0.00001044 | 0.00003722 | 1.47968 | 0.0000504 | |
| 60 | 0.00001672 | 0.00005238 | 3.37809 | 0.0000575 | |
| 70 | 0.00001966 | 0.00007992 | 7.95976 | 0.0000236 | |
| 80 | 0.00002969 | 0.00008309 | 7.75192 | 0.0000308 | |
| 90 | 0.00003428 | 0.00008861 | 9.15327 | 0.0000659 | |
| 100 | 0.00004711 | 0.00012416 | 17.60249 | 0.0000806 |
100桁から1000桁
ECPPの300桁以降はPRIMOを使用した結果を利用。
| 桁 | 2-PRP(秒) | 2-SPRP(秒) | ECPP(秒) | L-L(秒) |
|---|---|---|---|---|
| 100 | 0.0000471 | 0.0001242 | 17.6 | 0.0000806 |
| 200 | 0.0003169 | 0.0003149 | 111.3 | 0.0001596 |
| 300 | 0.0008869 | 0.0008142 | 8.5 | 0.0003368 |
| 400 | 0.0018953 | 0.0017754 | 10.2 | 0.0005779 |
| 500 | 0.0036472 | 0.0041140 | 20.7 | 0.0000323 |
| 600 | 0.0061181 | 0.0072429 | 52.8 | 0.0000248 |
| 700 | 0.0093117 | 0.0108036 | 107.1 | 0.0000286 |
| 800 | 0.0131810 | 0.0163689 | 139.1 | 0.0000246 |
| 900 | 0.0181532 | 0.0232536 | 293.4 | 0.0000358 |
| 1000 | 0.0244537 | 0.0286438 | 388.8 | 0.0000429 |
1000桁から10000桁
2-PRPはPFGWを使用して計測、ECPPはPRIMOを使用した結果を利用。
| 2-PRP | ECPP | L-L | |
|---|---|---|---|
| 1000桁 | 0.0130秒 | 6.5分 | 0.007秒 |
| 2000桁 | 0.0432秒 | 74.3分 | 0.042秒 |
| 3000桁 | 0.1031秒 | 499.7分 | 0.108秒 |
| 4000桁 | 0.1585秒 | 27.5時間 | 0.238秒 |
| 5000桁 | 0.2715秒 | 89.5時間 | 0.430秒 |
| 6000桁 | 0.3864秒 | 183時間 | 0.656秒 |
| 7000桁 | 0.5845秒 | 13.6日 | 1.021秒 |
| 8000桁 | 0.6637秒 | 21.0日 | 1.487秒 |
| 9000桁 | 0.9299秒 | 60.1日 | 1.731秒 |
| 10000桁 | 1.2008秒 | 31.6日 | 2.175秒 |
0000桁から100000桁
2-PRPはPFGWを使用して計測、ECPPはPRIMOを使用した結果を利用。 ECPPの30000桁の結果は、30950桁の数の素数証明をした結果。
| 2-PRP | ECPP | L-L | |
|---|---|---|---|
| 10000桁 | 1.20秒 | 31.6日 | 2.182秒 |
| 20000桁 | 6.48秒 | 242.4日 | 11.321秒 |
| 30000桁 | 12.71秒 | 1409.4日 | 31.687秒 |
| 40000桁 | 26.77秒 | 67.202秒 | |
| 50000桁 | 35.46秒 | 126.009秒 | |
| 60000桁 | 53.08秒 | 216.691秒 | |
| 70000桁 | 76.20秒 | 285.263秒 | |
| 80000桁 | 99.18秒 | 420.646秒 | |
| 90000桁 | 129.23秒 | 447.456秒 | |
| 100000桁 | 155.39秒 | 573.296秒 |
100000桁から1000000桁
2-PRPはPFGWを使用して計測、L-LはPrime95を使用した時の推定値。
| 2-PRP | L-L | |
|---|---|---|
| 100000桁 | 2.59分 | 0.4分 |
| 200000桁 | 12.57分 | 1.3分 |
| 300000桁 | 32.90分 | 3.2分 |
| 400000桁 | 65.45分 | 7.3分 |
| 500000桁 | 122.65分 | 11.2分 |
| 600000桁 | 187.86分 | 18.9分 |
| 700000桁 | 281.54分 | 22.6分 |
| 800000桁 | 384.21分 | 29.5分 |
| 900000桁 | 498.08分 | 36.6分 |
| 1000000桁 | 688.06分 | 50.3分 |
1000000桁から10000000桁
2-PRPはPFGWを使用して計測、L-LはPrime95を使用した時の推定値。
| 2-PRP | L-L | |
|---|---|---|
| 1000000桁 | 11.5時間 | 0.8時間 |
| 2000000桁 | 3.0時間 | |
| 3000000桁 | 7.0時間 | |
| 4000000桁 | 14.1時間 | |
| 5000000桁 | 21.8時間 | |
| 6000000桁 | 31.0時間 | |
| 7000000桁 | 42.4時間 | |
| 8000000桁 | 59.0時間 | |
| 9000000桁 | 74.7時間 | |
| 10000000桁 | 90.6時間 |
素数判定法の比較
試し割り
素数判定をするのには向いていませんが、大きな数の素数判定をする時、はじめに小さめの素数で割ってみて割り切れないかどうか確認するのにつかえます。
フェルマーテスト
100%素数だとは言えませんが、間違って素数だと判定してしまう擬素数は意外に少なく、大きな数ほど擬素数は少なくなるので、±1をしても素因数分解できない大きな数についてはこの方法を使うのが一般的です。ミラーラビンテストは比較的小さい数には有効ですが、大きな数についてはフェルマーテストで十分だと思います。
ECPP
±1をしても素因数分解ができない大きな数の素数の証明をするならこの方法です。しかし、特別な理由がない限り2万桁以上の素数をこの方法で証明するのは現実的とは言えず、これまでに3万桁以上の素数は4個しかこの方法で証明されていません。
Lucas-Lehmerテスト
とりあえず大きな素数を見つけたいならこの方法です。確率的素数判定法のフェルマーテストよりもけた違いに早い上に素数だと証明ができる判定法ですが、メルセンヌ数に対してのみにしか判定できません。
n+1法、n-1法
素数であることの証明が、フェルマーテストの１倍から数十倍くらいの計算時間でできますが、±1が素因数分解できないとこの方法は使えません。
どの素数判定法を使えばいいのか
素数であることの証明をしなくてもいいときは、15桁以下くらいなら試し割りをして、それ以上でもある程度まで試し割りをし、その後フェルマーテストを何回かするのがいいと思います。 素数であることの証明が必要なときも、まずは上の方法を試して素数である可能性が高いことを確認してから、±1をすると素因数分解できる数は n±1法で、できないなら最終手段としてECPPをするのがいいと思います。
おすすめのフリーソフト
OpenPFGW（Prime Form/GW）
どんな形の数でも高速にフェルマーテストやn+1法、n-1法ができます。
LLR
(K×b^n±1)の形の素数判定が高速にできます。
NewPGen
何種類かの形の素数について、一度にたくさんの数を高速に篩（試し割り）ができます。
Prime95
Lucas-Lehmerテストが高速にできます。1997年以降に見つかっているメルセンヌ素数はすべてこのソフトによって発見されました。
Yafu
素因数分解などができます。さいごに
実生活で直接は関係しないように思われるこのような素数判定法は、実はインターネットで通信する時の暗号化でも使われていたり、意外と身の回りで使われています。 今回、これをまとめるにあたって色々とネット上を調べましたが、日本語の情報がすごく少なく、さらに英語の情報も少ししかないことがよくあったり、ひとつの判定法にいろいろな名前がつけられていたりしました。できるだけ正しい情報をまとめたつもりですが、間違っていることもあるかもしれません。その内容も、大学レベルの数学ばかりで正直ぜんぜん理解できていなかったので、細かい説明や証明を書かずに大雑把にまとめてしまいました。わかりにくいところも多々あったと思いますが、この文章を読んでいただいてありがとうございました。
参考サイト・文献など
- http://primes.utm.edu/prove/merged.html
- https://www.ipa.go.jp/security/fy14/crypto/prime_num/invest.pdf
- http://factordb.com/
- http://oeis.org/
- http://stdkmd.com/nrr/
- http://mathworld.wolfram.com/
- http://www.primenumbers.net/prptop/prptop.php
- https://books.google.co.jp/books?id=8KZ4RQufxhYC
- http://stdkmd.com/blog/2003/04/0301.html
- https://www16.atwiki.jp/projectpn/pages/42.html
- その他多数。