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

Простое число Вагстафа — простое число вида:

$\frac{2^q+1}{3}$,

где $q$ — другое простое число.

Названы в честь Шаблон:Нп2, при этом считается, что это наименование им дал Франсуа Морен (Шаблон:Lang-fr2 в 1990 году в выступлении на конференции Eurocrypt-1990.

Простые числа Вагстафа имеют отношение к Шаблон:Нп5 и имеют приложение в криптографии.

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

$3=\frac{2^3+1}{3}$, $11=\frac{2^5+1}{3}$, $43=\frac{2^7+1}{3}$.

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

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, …

Несколько первых показателей $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, …

В феврале 2010 года Тони Райкс (Шаблон:Lang-de2) обнаружил вероятно простое число Вагстафа:

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

оно состоит из Шаблон:Num цифр и на тот момент являлось третьим наибольшим известным PRP.

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

$\frac{2^{13347311}+1}{3}$,

$\frac{2^{13372531}+1}{3}$.

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

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

$\frac{2^{15135397}+1}{3}$,

число состоит из более чем 4,5 млн цифр и является Шаблон:На наибольшим известным простым числом Вагстафа и третьим по величине PRP.

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

По состоянию Шаблон:На самым быстрым алгоритмом проверки простоты чисел Вагстафа является ECPP.

Ссылки

• Шаблон: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».