ワグスタッフ素数のソースを表示

<!--
{{Infobox integer sequence
| named_after           = [[Samuel S. Wagstaff, Jr.]]
| publication_year      = 1989<ref>{{Cite journal | last1 = Bateman | first1 = P. T. | author1-link = Paul T. Bateman | last2 = Selfridge | first2 = J. L. | author2-link = John Selfridge | last3 = Wagstaff, Jr. | first3 = S. S. | title = The New Mersenne Conjecture | journal = American Mathematical Monthly | year = 1989 | volume = 96 | pages = 125–128 | jstor = 2323195 }}</ref>
| author                = [[Paul T. Bateman|Bateman, P. T.]], [[John Selfridge|Selfridge, J. L.]], [[Samuel S. Wagstaff, Jr.|Wagstaff Jr., S. S.]]
| terms_number          = 43
| first_terms           = [[3 (number)|3]], [[11 (number)|11]], [[43 (number)|43]], [[683 (number)|683]]
| largest_known_term    = (2<sup>13372531</sup>+1)/3
| OEIS                  = A000979
}}
-->
[[数論]]において、'''ワグスタッフ素数'''（{{lang-en-short|Wagstaff prime}}）は、

:<math>p={{2^q+1}\over 3}</math>

の形をした素数 ''p'' である。ただし ''q'' は別の素数である。ワグスタッフ素数は、[[数学者]]の{{仮リンク|サミュエル S. ワグスタッフ・ジュニア|en|Samuel S. Wagstaff Jr.}}にあやかって名付けられた。[[Prime Pages]] では、{{仮リンク|フランソワ・モラン|de|François Morain}}が {{仮リンク|Eurocrypt|en|Eurocrypt}} の 1990年 の[[学会]]での講演において、この素数を名付けた事に言及している。<!--the [[prime pages]] credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference.-->ワグスタッフ素数は[[メルセンヌ予想#新メルセンヌ予想|新メルセンヌ予想]]と関連しており、[[暗号理論]]への応用を持っている。

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

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

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

2013年10月の時点で、ワグスタッフ素数か[[確率的素数]]（PRP)になるとわかっている[[冪乗|指数]]<math>q</math>を、小さい順に並べると以下のようになる。
: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 {{OEIS|id=A000978}}

2010年2月に、Tony Reix が次のワグスタッフ確率的素数を発見した。
: <math>\frac{2^{4031399}+1}3</math>
これは 1,213,572 桁の数であり、当時見つかっていた中で3番目に大きい確率的素数であった<ref>[http://www.primenumbers.net/prptop/prptop.php PRP Records]</ref>。

2013年9月、Ryan Propper はさらに2つのワグスタッフ確率的素数の発見を知らせた<ref>[http://mersenneforum.org/showthread.php?t=18569 New Wagstaff PRP exponents], mersenneforum.org</ref>。
: <math>\frac{2^{13347311}+1}3</math>
と
: <math>\frac{2^{13372531}+1}3</math>
である。いずれも400万桁よりわずかに多い桁数をもった確率的素数である。4031399 と 13347311 の間にワグスタッフ確率的素数を生み出す指数があるのかどうか、今のところ知られていない。

== 素数判定 ==
これらの数は ''q'' の値が 83339 までのときは素数であることが証明されている。{{as of|2020|12|lc=on|url=http://primes.utm.edu/top20/page.php?id=67}} ''q'' > 83339 のときは確率的素数である。 ''q'' = 42737 のときに素数であることの証明は François Morain によって、 [[Opteron]] processor上で 743 {{仮リンク|GHz-days|en|MIPS-year}} 間ワークステーションのいくつかのネットワーク上で動作している分散された {{仮リンク|ECPP|en|Elliptic curve primality proving}} を実行することによって、2007 年になされた<ref>François Morain の Prime Pages でのコメント。[http://primes.utm.edu/primes/page.php?id=82071#comments The Prime Database: (2<sup>42737</sup>&nbsp;+&nbsp;1)/3]</ref>。それはその発見から2009年3月まででは ECPP による素数の証明では3番目に大きい素数であった<ref>{{Citation |first=Chris |last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=27 |title=The Top Twenty: Elliptic Curve Primality Proof |work=The [[Prime Pages]] }}</ref>。

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

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

== 一般化 ==
より一般的な次の形の数を考えることが自然である<ref>[[Harvey Dubner|Dubner, H.]] and Granlund, T.: [https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.pdf Primes of the Form (b<sup>n</sup> + 1)/(b + 1)], ''Journal of Integer Sequences'', Vol. 3 (2000)</ref>
:<math>Q(b,n)=\frac{b^n+1}{b+1}</math>
ただし底は <math>b \ge 2</math> である。<math>n</math> が奇数のときには
:<math>\frac{b^n+1}{b+1}=\frac{(-b)^n-1}{(-b)-1}=R_n^{(-b)}</math>
であるので、これらの一般化されたワグスタッフ数は、負の底 <math>-b</math> をもった[[レピュニット]]数のケースと考えられることがある<ref>[http://mathworld.wolfram.com/Repunit.html Repunit], Wolfram MathWorld (Eric W. Weisstein)</ref>。

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

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

{{OEIS|id=A084742}}

{| class="wikitable"
|'''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
|&#62;10000
|19
|7
|3
|-
|'''100+'''
|7
|3
|&#62;10000
|673
|11
|3
|103
|13
|59
|23
|3
|3
|&#62;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
|&#62;10000
|5
|3
|61
|827
|5
|-
|'''180+'''
|449
|1487
|11
|19
|11
|&#62;10000
|&#62;10000
|&#62;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
|&#62;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
|&#62;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 は素数でない）

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

<math>b=10</math> に対して、素数は次のように現れる。9091, 909091, 909090909090909091, 909090909090909090909090909091, … {{OEIS|id=A097209}}。また、これらの ''n'' は次のようになる。5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... {{OEIS|id=A001562}}。

<math>Q(b, prime(n))</math> が素数になるような最小の底 ''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 で始まる) {{OEIS|id=A103795}}

== 脚注 ==
{{Reflist}}

== 外部リンク ==
*{{MathWorld|urlname=WagstaffPrime|title=Wagstaff prime|author=John Renze and [[Eric W. Weisstein]]}}
*Chris Caldwell, [http://primes.utm.edu/top20/page.php?id=67 ''The Top Twenty: Wagstaff''] at The [[Prime Pages]].
* Renaud Lifchitz, [http://primenumbers.net/Documents/TestNP.pdf "An efficient probable prime test for numbers of the form (2<sup>''p''</sup>&nbsp;+&nbsp;1)/3"].
* Tony Reix, [http://tony.reix.free.fr/Mersenne/SummaryOfThe3Conjectures.pdf "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under ''x''<sup>2</sup>&nbsp;&minus;&nbsp;2 modulo a prime"].
*[http://www.primenumbers.net/Henri/us/MersFermus.htm repunit in base -50 to 50]

{{素数の分類}}
{{Num-stub}}
{{デフォルトソート:わくすたつふそすう}}
[[Category:素数]]
[[Category:暗号技術]]
[[Category:数学に関する記事]]
[[Category:素数の類]]
[[Category:数学のエポニム]]