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

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

${\displaystyle {{2^{q}+1} \over 3}}$,

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

Названы в честь Самуэля Вагстафа (англ. Samuel S. Wagstaff, Jr.), при этом считается, что это наименование им дал Франсуа Морен (François Morain в 1990 году в выступлении на конференции Eurocrypt-1990.

Простые числа Вагстафа имеют отношение к новой гипотезе Мерсенна^[англ.] и имеют приложение в криптографии.

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

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

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

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

Несколько первых показателей ${\displaystyle q}$, которые порождают простые Вагстафа или вероятно простые^[2]:

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 года Тони Райкс (Tony Reix) обнаружил вероятно простое число Вагстафа:

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

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

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

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

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

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

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

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

число состоит из более чем 4,5 млн цифр и является на 2024 год наибольшим известным простым числом Вагстафа и третьим по величине PRP^[7].

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

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

Примечания

1. последовательность A000979 в OEIS
2. последовательность A000978 в OEIS
3. PRP Records  (неопр.). Дата обращения: 24 марта 2010. Архивировано 24 марта 2010 года.
4. New Wagstaff PRP exponents Архивная копия от 28 сентября 2022 на Wayback Machine, mersenneforum.org
5. PRP Records  (неопр.). Дата обращения: 5 октября 2013. Архивировано 5 октября 2013 года.
6. Announcing a new Wagstaff PRP Архивная копия от 24 сентября 2022 на Wayback Machine, mersenneforum.org
7. PRP Records  (неопр.). Дата обращения: 29 июня 2021. Архивировано 29 июня 2021 года.
8. Comment by François Morain, The Prime Database: (2⁴²⁷³⁷ + 1)/3 Архивная копия от 2 мая 2013 на Wayback Machine at The Prime Pages.
9. Caldwell, Chris, "The Top Twenty: Elliptic Curve Primality Proof", The Prime Pages, Архивировано из оригинала 10 декабря 2008, Дата обращения: 24 января 2013

Ссылки

• 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^{${\displaystyle p}$} + 1)/3».
• Tony Reix, «Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under ${\displaystyle x}$² − 2 modulo a prime».