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

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

主な素数

編集

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

 

知られているワグスタッフ素数

編集

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

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

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

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 が次のワグスタッフ確率的素数を発見した。

 

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

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

 

 

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

素数判定

編集

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

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

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

一般化

編集

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

 

ただし底は   である。  が奇数のときには

 

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

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

しかしながら、  が代数的な分解をもたないときは、  が素数になる   が無数に存在するという予想を立てることができる。(  ≤ 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 は素数でない)

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

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

  が素数になるような最小の底 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)

外部リンク

編集
  • John Renze and Eric W. Weisstein. "Wagstaff prime". mathworld.wolfram.com (英語).
  • Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
  • Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2p + 1)/3".
  • Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x2 − 2 modulo a prime".
  • repunit in base -50 to 50