Русская Википедия:Простое число Вагстафа
В теории чисел простым числом Вагстафа (Wagstaff) называется простое число p вида
- <math>p={{2^q+1}\over 3}</math>
где q – другое простое число. Числа названы в честь математика Шаблон:Нп5 (Samuel S. Wagstaff Jr.) Сайт prime pages приписывает наименование чисел Франсуазу Морану (François Morain), который назвал их так на конференции Eurocrypt 1990. Простые числа Вагстафа имеют отношение к Шаблон:Нп5 и имеют приложение в криптографии.
Примеры
Три первых числа Вагстафа – это 3, 11 и 43, поскольку
- <math>
\begin{align} 3 & = {2^3+1 \over 3}, \\[5pt] 11 & = {2^5+1 \over 3}, \\[5pt] 43 & = {2^7+1 \over 3}. \end{align} </math>
Известные числа Вагстафа
Первые несколько чисел Вагстафа:
- 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, … (Шаблон: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, …, 13347311, 13372531, 15135397, … (Шаблон:OEIS)
В феврале 2010 года Тони Рейх (Tony Reix) обнаружил вероятно простое число Вагстафа:
- <math>\frac{2^{4031399}+1}3</math>
Оно состоит из 1 213 572 цифр и на тот момент являлось третьим наибольшим известным PRP[1].
В сентябре 2013 года Райан Проппер объявил о нахождении еще двух вероятно простых чисел Вагстафа:[2]
- <math>\frac{2^{13347311}+1}3</math>
- <math>\frac{2^{13372531}+1}3</math>
Каждое из них является вероятно простым числом из чуть более чем 4 миллионов цифр. Они заняли 1-е и 2-е место в рейтинге наибольших известных PRP[3]. При этом оставалось неизвестным, существуют ли еще какие-либо показатели степени между 4 031 399 и 13 347 311, которые являлись бы вероятно простыми числами Вагстафа.
В июне 2021 года Райан Проппер вновь объявил о рекорде:[4]
- <math>\frac{2^{15135397}+1}3</math>
Это число состоит из более чем 4.5 миллионов цифр и является на текущий момент наибольшим известным простым числом Вагстафа и третьим по величине PRP[5].
Проверка простоты
Числа Вагстафа проверены на простоту для q вплоть до 83339. Числа с q > 83339 являются возможно простыми. Проверка простоты для q = 42737 была проведена Франсуа Мораном (François Morain) в 2007 году в проекте распределенных вычислений ECPP, реализованном на нескольких сетях станций, работающих на процессоре Opteron[6]. Это было четвертое по величине значение, проверенное в ECPP к 2010-му году[7].
На текущий момент самым быстрым алгоритмом проверки простоты чисел Вагстафа является ECPP.
Примечания
Ссылки
- Шаблон:MathWorld
- Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
- Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2p + 1)/3".
- Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x2 − 2 modulo a prime".
- ↑ Шаблон:Cite web
- ↑ New Wagstaff PRP exponents, mersenneforum.org
- ↑ Шаблон:Cite web
- ↑ Announcing a new Wagstaff PRP, mersenneforum.org
- ↑ Шаблон:Cite web
- ↑ Comment by François Morain, The Prime Database: (242737 + 1)/3 Шаблон:Wayback at The Prime Pages.
- ↑ Шаблон:Citation Шаблон:Wayback
