ワグスタッフ素数

数論において、ワグスタッフ素数（）は、

の形をした素数 p である。ただし q は別の素数である。ワグスタッフ素数は、数学者のにあやかって名付けられた。Prime Pages では、が  の 1990年 の学会での講演において、この素数を名付けた事に言及している。ワグスタッフ素数は新メルセンヌ予想と関連しており、暗号理論への応用を持っている。

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

知られているワグスタッフ素数 
最初のいくつかのワグスタッフ素数は以下のものである。
3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, … 

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 

2010年2月に、Tony Reix が次のワグスタッフ確率的素数を発見した。
 
これは 1,213,572 桁の数であり、当時見つかっていた中で3番目に大きい確率的素数であった。

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

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

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

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

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

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

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

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

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

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, … 。また、これらの n は次のようになる。5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... 。

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

脚注

外部リンク 

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

素数
暗号技術
数学に関する記事
素数の類
数学のエポニム