Простое число Вагстафа

В теории чисел простым числом Вагстафа (Wagstaff) называется простое число p вида

[math]\displaystyle{ p={{2^q+1}\over 3} }[/math]

где q – другое простое число. Числа названы в честь математика Самуэля Вагстафа (Samuel S. Wagstaff Jr.) Сайт prime pages приписывает наименование чисел Франсуазу Морану (François Morain), который назвал их так на конференции Eurocrypt 1990. Простые числа Вагстафа имеют отношение к новой гипотезе Мерсенна и имеют приложение в криптографии.

Примеры

Три первых числа Вагстафа – это 3, 11 и 43, поскольку

[math]\displaystyle{ \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, 768614336404564651, … (последовательность A000979 в OEIS)

Несколько первых показателей 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, 15135397, … (последовательность A000978 в OEIS)

В феврале 2010 года Тони Рейх (Tony Reix) обнаружил вероятно простое число Вагстафа:

[math]\displaystyle{ \frac{2^{4031399}+1}3 }[/math]

Оно состоит из 1 213 572 цифр и на тот момент являлось третьим наибольшим известным PRP.

В сентябре 2013 года Райан Проппер объявил о нахождении еще двух вероятно простых чисел Вагстафа:

[math]\displaystyle{ \frac{2^{13347311}+1}3 }[/math]

[math]\displaystyle{ \frac{2^{13372531}+1}3 }[/math]

Каждое из них является вероятно простым числом из чуть более чем 4 миллионов цифр. Они заняли 1-е и 2-е место в рейтинге наибольших известных PRP. При этом оставалось неизвестным, существуют ли еще какие-либо показатели степени между 4 031 399 и 13 347 311, которые являлись бы вероятно простыми числами Вагстафа.

В июне 2021 года Райан Проппер вновь объявил о рекорде:

[math]\displaystyle{ \frac{2^{15135397}+1}3 }[/math]

Это число состоит из более чем 4.5 миллионов цифр и является на текущий момент наибольшим известным простым числом Вагстафа и третьим по величине PRP.

Проверка простоты

Числа Вагстафа проверены на простоту для q вплоть до 83339. Числа с q > 83339 являются возможно простыми. Проверка простоты для q = 42737 была проведена Франсуа Мораном (François Morain) в 2007 году в проекте распределенных вычислений ECPP, реализованном на нескольких сетях станций, работающих на процессоре Opteron. Это было четвертое по величине значение, проверенное в ECPP к 2010-му году.

На текущий момент самым быстрым алгоритмом проверки простоты чисел Вагстафа является ECPP.

Ссылки

• John Renze and Eric W. Weisstein. Wagstaff prime (англ.) на сайте Wolfram MathWorld.
• Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
• Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2^p + 1)/3".
• Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x² − 2 modulo a prime".