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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править исходный текст]

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


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

Известные числа Вагстафа[править | править исходный текст]

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

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 года.[1] Оно имеет 1213572 знаков и на январь 2013 года является четвертым наибольшим известным PRP.

Проверка простоты[править | править исходный текст]

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

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

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]