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

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

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

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

Примеры[править | править вики-текст]

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

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

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

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)

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

было найдено Тони Рейхом (Tony Reix) в феврале 2010 года[1]. Оно имеет 1213572 знаков и на январь 2013 года является четвертым наибольшим известным PRP.

Проверка простоты[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]