ワグスタッフ素数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数論において、ワグスタッフ素数: Wagstaff prime)は、

p={{2^q+1}\over 3}

の形をした素数 p である。ただし q は別の素数である。ワグスタッフ素数は、数学者サミュエル S. ワグスタッフ・ジュニア英語版にあやかって名付けられた。Prime Pages英語版 では、フランソワ・モランドイツ語版Eurocrypt英語版 の 1990年 の学会での講演において、この素数を名付けた事に言及している。ワグスタッフ素数は新メルセンヌ予想英語版と関連しており、暗号理論への応用を持っている。

主な素数[編集]

最初の3つのワグスタッフ素数は、3, 11, 43 である。なぜならば


\begin{align}
3 & = {2^3+1 \over 3}, \\[5pt]
11 & = {2^5+1 \over 3}, \\[5pt]
43 & = {2^7+1 \over 3}.
\end{align}

知られているワグスタッフ素数[編集]

最初のいくつかのワグスタッフ素数は以下のものである。

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, … オンライン整数列大辞典の数列 A000979

2013年10月の時点で、ワグスタッフ素数か確率的素数(PRP)になるとわかっている指数qを、小さい順に並べると以下のようになる。

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, …, 13347311, 13372531 オンライン整数列大辞典の数列 A000978

2010年2月に、Tony Reix が次のワグスタッフ確率的素数発見した。

\frac{2^{4031399}+1}3

これは 1,213,572 桁の数であり、当時見つかっていた中で3番目に大きい確率的素数であった[1]

2013年9月、Ryan Propper はさらに2つのワグスタッフ確率的素数の発見を知らせた[2]

\frac{2^{13347311}+1}3

\frac{2^{13372531}+1}3

である。いずれも400万桁よりわずかに多い桁数をもった確率的素数である。4031399 と 13347311 の間にワグスタッフ確率的素数を生み出す指数があるのかどうか、今のところ知られていない。

素数判定[編集]

これらの数は q の値が 42737 までのときは素数であることが証明されている。2010年2現在 q > 42737 のときは確率的素数である。 q = 42737 のときに素数であることの証明は François Morain によって、 Opteron processor上で 743 GHz-days英語版 間ワークステーションのいくつかのネットワーク上で動作している分散された ECCP英語版 を実行することによって、2007 年になされた[3]。それはその発見から2009年3月まででは ECPP による素数の証明では3番目に大きい素数であった[4]

今のところ知られているアルゴリズムで、ワグスタッフ数が素数であることを最も早く証明できるものは、ECPP である。

Jean Penné による LLR (Lucas-Lehmer-Riesel) ツールは、 Vrba-Reix test の手段でワグスタッフ確率的素数を見つけるために使われる。それはワグスタッフ数を法とした x^2-2 のもとでの digraph の周期性に基づいた PRP テストである

一般化[編集]

より一般的な次の形の数を考えることが自然である[5]

Q(b,n)=\frac{b^n+1}{b+1}

ただし底は b \ge 2 である。n が奇数のときには

\frac{b^n+1}{b+1}=\frac{(-b)^n-1}{(-b)-1}=R_n^{(-b)}

であるので、これらの一般化されたワグスタッフ数は、負の底 -b をもったレピュニット数のケースと考えられることがある[6]

いくつかの特定の b の値について、(非常に小さい n に対して例外があるかもしれないがそれを除いて)すべての Q(b,n) は、「代数的な」分解のために合成数である。具体的には、b が奇数の指数をもった完全冪の形(例えば 8, 27, 32, 64, 125, 128, 216, 243, etc. オンライン整数列大辞典の数列 A070265)であれば、m が奇数のとき x^m+1x+1 で割り切れるという事実によって、これらの特殊な場合には Q(a^m, n)a^n+1 で割り切れる。別のケースは k を正の整数として b=4k^4 のときである(例えば 4, 64, 324, 1024, 2500, 5184, etc. オンライン整数列大辞典の数列 A141046)。このとき aurifeuillean factorization英語版 がある。

しかしながら、b が代数的な分解をもたないときは、Q(b,n) が素数になる n が無数に存在するという予想を立てることができる。(b ≤ 300 に対しては、素数や PRP が知られていない 9 つの底 97, 103, 113, 175, 186, 187, 188, 220, and 284 が存在し、PRP は知られているが素数であることが証明されていないような 7 つの底 53, 124, 150, 182, 205, 222, and 296 が存在する。リストを見よ。すべての n が奇素数であることに注意せよ。)

オンライン整数列大辞典の数列 A084742

Base +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15 +16 +17 +18 +19 +20
0+ None 3 3 3 5 3 3 None 3 5 5 5 3 7 3 3 7 3 17 5
20+ 3 3 11 7 3 11 None 3 7 139 109 None 5 3 11 31 5 5 3 53
40+ 17 3 5 7 103 7 5 5 7 1153 3 7 21943 7 3 37 53 3 17 3
60+ 7 11 3 None 19 7 3 757 11 3 5 3 7 13 5 3 37 3 3 5
80+ 3 293 19 7 167 7 7 709 13 3 3 37 89 71 43 37 >10000 19 7 3
100+ 7 3 >10000 673 11 3 103 13 59 23 3 3 >10000 7 7 113 271 3 29 3
120+ 5 293 29 16427 None 5 317 7 17 467 5 3 5 13 5 5 101 103 3 59
140+ 5 3 7 3 7 17 11 3 17 6883 3 13 13 3 5 3 5 5 283 11
160+ 31 3 3 7 3 17 17 3 3 7 13 37 7 3 >10000 5 3 61 827 5
180+ 449 1487 11 19 11 >10000 >10000 >10000 3 3 479 109 3 19 3 43 31 37 313 7
200+ 43 229 5 3 5449 101 3 61 311 3 79 101 59 73 277 3 499 241 3 >10000
220+ 149 1657 5 7 383 7 89 7 11 13 7 3 11 7 223 11 3 23 59 7
240+ 19 5 None 71 5 3 3 7 19 857 5 43 5 569 7 5 5 5 19 397
260+ 109 7 13 19 5 31 3 5 11 17 401 103 3 61 7 5 59 167 3 3
280+ 7 7 37 >10000 29 5 137 3 3 5 3 19 47 3 29 1303 5 7 17 97

b = 53, 124, 150, 182, 205, 222, 296 に対しては確率的素数しか存在ない。

b = 97, 103, 113, 175, 186, 187, 188, 220, 284 に対しては素数も PRP も知られていない。

代数的な分解のために、b = 8, 27, 32, 64, 125, 243 に対しては素数が存在しない。(b = 1 の場合はすべて 1 だが 1 は素数でない)

すべての奇素数がリストにあることが期待される。

b=10 に対して、素数は次のように現れる。9091, 909091, 909090909090909091, 909090909090909090909090909091, … オンライン整数列大辞典の数列 A097209。また、これらの n は次のようになる。5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... オンライン整数列大辞典の数列 A001562

Q(b, prime(n)) が素数になるような最小の底 b

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (この列は n = 2 で始まる) オンライン整数列大辞典の数列 A103795

脚注[編集]

  1. ^ PRP Records
  2. ^ New Wagstaff PRP exponents, mersenneforum.org
  3. ^ François Morain の Prime Pages でのコメント。The Prime Database: (242737 + 1)/3
  4. ^ Caldwell, Chris, “The Top Twenty: Elliptic Curve Primality Proof”, The Prime Pages, http://primes.utm.edu/top20/page.php?id=27 
  5. ^ Dubner, H. and Granlund, T.: Primes of the Form (bn + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
  6. ^ Repunit, Wolfram MathWorld (Eric W. Weisstein)

外部リンク[編集]