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


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

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

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

Примеры

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

3 = 2 3 + 1 3 , 11 = 2 5 + 1 3 , 43 = 2 7 + 1 3 . {displaystyle {egin{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)

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

2 4031399 + 1 3 {displaystyle {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.


  • Люка, Франсуа Эдуард Анатоль
  • Вторая гипотеза Харди — Литлвуда
  • Натуральное число
  • Жадный алгоритм для египетских дробей
  • Число Коксетера

  •  

    • Яндекс.Метрика
    • Индекс цитирования