Wagstaff Prime - Wagstaff prime

Wagstaff Prime
Названный в честь	Сэмюэл С. Вагстафф-мл.
Год публикации	1989
Автор публикации	Бейтман, П. Т., Селфридж, Дж. Л., Вагстафф младший, С.С.
Нет. известных терминов	43
Первые триместры	3, 11, 43, 683
Самый большой известный термин	(213372531+1)/3
OEIS индекс	A000979; Простые числа Вагстаффа: простые числа формы (2 ^ p + 1) / 3;

В теория чисел, а Wagstaff Prime это простое число п формы

{ displaystyle p = {{2 ^ {q} +1} более 3}}

куда q является нечетное простое число. Простые числа Вагстаффа названы в честь математик Сэмюэл С. Вагстафф мл.; то основные страницы Благодарим Франсуа Морена за то, что он назвал их в лекции на конференции Eurocrypt 1990. Простые числа Вагстаффа появляются в Новая гипотеза Мерсенна и иметь приложения в криптография.

Примеры

Первые три простых числа Вагстаффа - 3, 11 и 43, потому что

{ displaystyle { begin {align} 3 & = {2 ^ {3} +1 over 3}, [5pt] 11 & = {2 ^ {5} +1 over 3}, [5pt] 43 & = {2 ^ {7} +1 более 3}. End {align}}}

Известные простые числа Вагстаффа

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

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651,… (последовательность A000979 в OEIS )

По состоянию на октябрь 2014 г.^{[Обновить]}, известные экспоненты, которые дают простые числа Вагстаффа или вероятные простые числа находятся:

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,^[2] (все известные простые числа Вагстаффа)

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399,…, 13347311, 13372531 (вероятные простые числа Вагстаффа) (последовательность A000978 в OEIS )

В феврале 2010 года Тони Рейкс обнаружил вероятный прайм Вагстаффа:

{ displaystyle { frac {2 ^ {4031399} +1} {3}}}

который состоит из 1 213 572 цифр и был третьим по величине вероятным простым числом, когда-либо найденным на эту дату.^[3]

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

{ displaystyle { frac {2 ^ {13347311} +1} {3}}}

и

{ displaystyle { frac {2 ^ {13372531} +1} {3}}}

Каждое из них является вероятным простым числом с чуть более чем 4 миллионами десятичных цифр. В настоящее время неизвестно, существуют ли какие-либо экспоненты между 4031399 и 13347311, которые дают вероятные простые числа Вагстаффа.

Обратите внимание, что когда p является простым числом Вагстаффа, ${ displaystyle { frac {2 ^ {p} +1} {3}}}$ не обязательно быть простым, первый контрпример p = 683, и предполагается, что если p является простым числом Вагстаффа и p> 43, то ${ displaystyle { frac {2 ^ {p} +1} {3}}}$ составной.

Проверка на первичность

Первобытность была доказана или опровергнута для ценностей q до 83339. Те, у кого q > 83339 - вероятные простые числа по состоянию на апрель 2015 г.^[ref]. Доказательство простоты для q = 42737 было выполнено Франсуа Мореном в 2007 г. с распределенным ECPP реализация запущена в нескольких сетях рабочих станций на 743 ГГц-дни на Opteron процессор.^[5] Это было третьим по величине доказательством примитивности ECPP с момента его открытия до марта 2009 года.^[6]

В настоящее время самым быстрым известным алгоритмом доказательства простоты чисел Вагстаффа является ECPP.

Инструмент LLR (Lucas-Lehmer-Riesel) Жана Пенне используется для нахождения вероятных простых чисел Вагстаффа с помощью теста Врба-Рейкса. Это тест PRP, основанный на свойствах цикла диграф под x ^ 2-2 по модулю числа Вагстаффа.

Обобщения

Естественно считать^[7] в более общем смысле числа в форме

{ Displaystyle Q (b, n) = { гидроразрыва {b ^ {n} +1} {b + 1}}}

где база ${ displaystyle b geq 2}$ . Поскольку для ${ displaystyle n}$ странно у нас есть

{ displaystyle { frac {b ^ {n} +1} {b + 1}} = { frac {(-b) ^ {n} -1} {(- b) -1}} = R_ {n } (- б)}

эти числа называются "База чисел Вагстаффа" ${ displaystyle b}$ ", и иногда считается^[8] случай объединить числа с отрицательным основанием ${ displaystyle -b}$ .

Для некоторых конкретных значений ${ displaystyle b}$ , все ${ Displaystyle Q (Ь, п)}$ (с возможным исключением для очень маленьких ${ displaystyle n}$ ) составны из-за «алгебраической» факторизации. В частности, если ${ displaystyle b}$ имеет форму совершенной степени с нечетным показателем (например, 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000 и т. д. (последовательность A070265 в OEIS )), то тот факт, что ${ displaystyle x ^ {m} +1}$ , с ${ displaystyle m}$ нечетное, делится на ${ displaystyle x + 1}$ показывает, что ${ Displaystyle Q (а ^ {м}, п)}$ делится на ${ displaystyle a ^ {n} +1}$ в этих особых случаях. Другой случай ${ displaystyle b = 4k ^ {4}}$ , с k положительное целое число (например, 4, 64, 324, 1024, 2500, 5184 и т. д. (последовательность A141046 в OEIS )), где аврифейлевая факторизация.

Однако когда ${ displaystyle b}$ не допускает алгебраической факторизации, предполагается, что бесконечное число ${ displaystyle n}$ ценности делают ${ Displaystyle Q (Ь, п)}$ премьер, обратите внимание на все ${ displaystyle n}$ - нечетные простые числа.

За ${ displaystyle b = 10}$ , сами простые числа имеют следующий вид: 9091, 909091, 909090909090909091, 909090909090909090909090909091,… (последовательность A097209 в OEIS ), и эти пs: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (последовательность A001562 в OEIS ).

Видеть объединить для списка базы обобщенных простых чисел Вагстаффа ${ displaystyle b}$ . (Обобщенная база простых чисел Вагстаффа ${ displaystyle b}$ являются обобщенной базой простых чисел ${ displaystyle -b}$ со странным ${ displaystyle n}$ )

Наименьшее число п такой, что ${ Displaystyle Q (п, р)}$ простое (начинается с п = 2, 0, если такого нет п существуют)

3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... (последовательность A084742 в OEIS )

Наименьшая база б такой, что ${ Displaystyle Q (Ь, простое число (п))}$ простое (начинается с п = 2)

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ... (последовательность A103795 в OEIS )

внешняя ссылка

[1] Бейтман, П. Т.; Селфридж, Дж. Л.; Вагстафф младший, С. С. (1989). «Новая гипотеза Мерсенна». Американский математический ежемесячный журнал. 96: 125–128. Дои:10.2307/2323195. JSTOR 2323195.

[2] ttp://primes.utm.edu/top20/page.php?id=67

[3] PRP отчеты

[4] Новые экспоненты Wagstaff PRP, mersenneforum.org

[5] Комментарий Франсуа Морена, Основная база данных: (2⁴²⁷³⁷ + 1)/3 в Prime Pages.

[6] Колдуэлл, Крис, "Двадцатка лучших: доказательство простоты эллиптической кривой", В Prime Pages

[7] Дубнер, Х. и Гранлунд, Т .: Простые числа формы (b^п + 1) / (b + 1), Журнал целочисленных последовательностей, Vol. 3 (2000)

[8] Repunit, Wolfram MathWorld (Эрик В. Вайсштейн)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

простое число классы
По формуле	Ферма ( $2 2 п + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Wagstaff $(2 п + 1)/3$ Proth ( $k \cdot2 п + 1$ ) Факториал ( $п! \pm 1$ ) Первобытный ( $п п # \pm 1$ ) Евклид ( $п п # + 1$ ) Пифагорейский ( $4 п + 1$ ) Pierpont ( $2 м \cdot3 п + 1$ ) Квартан ( $Икс 4 + у 4$ ) Солинас ( $2 м \pm 2 п \pm 1$ ) Каллен ( $п \cdot2 п + 1$ ) Вудалл ( $п \cdot2 п - 1$ ) Кубинский ( $Икс 3 - у 3)/(Икс - у$ ) Кэрол $(2 п - 1) 2 - 2$ Kynea $(2 п + 1) 2 - 2$ Лейланд ( $Икс у + у Икс$ ) Табит ( $3\cdot2 п - 1$ ) Уильямс ( $(б -1)\cdot б п - 1$ ) Миллс ( $⌊ А 3 п ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман – Шанкс – Уильямс Перрин Перегородки Колокол Моцкин
По собственности	Виферих (пара ) Стена – Солнце – Солнце Wolstenholme Уилсон Счастливчик Удачливый Рамануджан Пиллай Обычный Сильный Штерн Суперсингулярный (эллиптическая кривая) Суперсингулярный (теория самогона) Хороший супер Хиггс Очень cototient
Основание -зависимый	Палиндромный Эмирп Repunit $(10 п - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Слабо Первобытный Полное повторение Уникальный Счастливый Себя Смарандаче – Веллин Стробограмматический Двугранный Тетрадич
Узоры	Близнец ( $п, п + 2$ ) Двусторонняя цепь ( $п - 1, п + 1, 2 п - 1, 2 п + 1, \dots$ ) Триплет ( $п, п + 2 или п + 4, п + 6$ ) Четверной ( $п, п + 2, п + 6, п + 8$ ) k−Tuple Двоюродная сестра ( $п, п + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен / Сейф ( $п, 2 п + 1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $п + а \cdot п, п = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательный п - п, п, п + п$ )
По размеру	Титаник (Более 1000 цифр) Гигантский (10 000+ цифр) Мега (Более 1000000 цифр) Самый большой известный
Сложные числа	Эйзенштейн простое Гауссово простое число
Составные числа	Псевдопремия Каталонский Эллиптический Эйлер Эйлер – Якоби Ферма Фробениус Лукас Сомер – Лукас Сильный Число Кармайкла Почти премьер Полупростой Interprime Пагубный
похожие темы	Вероятное простое число Прайм промышленного класса Незаконный премьер Формула для простых чисел Главный разрыв
Первые 60 простых чисел	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
Список простых чисел