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

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

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

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

Примеры

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

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

Известные числа Вагстафа

Первые несколько чисел Вагстафа:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, … (последовательность 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, … (последовательность A000978 в OEIS)

Наибольшее известное (вероятно) простое число Вагстафа

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

было найдено Тони Рейхом (Tony Reix) в феврале 2010 года. Оно имеет 1213572 знаков и на январь 2013 года является четвертым наибольшим известным 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".