Wagstaff prime

редактировать

Wagstaff prime
Назван в честь	Сэмюэля С. Вагстаффа, младшего
Год публикации	1989
Автор публикация	Ba Teman, PT, Selfridge, JL, Wagstaff Jr., SS
№ известных терминов	43
Первые термины	3, 11, 43, 683
Наибольший известный термин	(2 + 1) / 3
OEIS индекс	A000979 Простые числа Вагстаффа: простые числа формы (2 ^ p + 1) / 3

In теория чисел, простое число Вагстаффа - это простое число p в форме

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

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

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

Содержание

1 Примеры
2 Известные простые числа Вагстаффа
3 Проверка на простоту
4 Обобщения
5 Ссылки
6 Внешние ссылки

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примитивность была доказана или опровергнута для значений q до 83339. Те, у которых q>83339, являются вероятными простыми числами по состоянию на апрель 2015 года. выполненный Франсуа Мореном в 2007 году с распределенной реализацией ECPP, работающей в нескольких сетях рабочих станций для 743 на процессоре Opteron. Это было третьим по величине доказательством простоты ECPP с момента его открытия до марта 2009 года.

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

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

Обобщения

Естественно рассматривать более общие числа в форме

Q (b, n) = bn + 1 b + 1 {\ displaystyle Q (b, n) = {\ frac {b ^ {n} +1} {b + 1}}}

Q (b, n) = {\ frac {b ^ { n} +1} {b + 1}}

, где основание $b ≥ 2 {\ displaystyle b \ geq 2}$ $b \ geq 2$ . Поскольку для $n {\ displaystyle n}$ $n$ нечетное, мы имеем

bn + 1 b + 1 = (- b) n - 1 (- b) - 1 = R n (- b) {\ displaystyle {\ frac {b ^ {n} +1} {b + 1}} = {\ frac {(-b) ^ {n} -1} {(- b) -1}} = R_ {n } (- b)}

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

эти числа называются «основание чисел Вагстаффа $b {\ displaystyle b}$ $b$ » и иногда рассматриваются как случай перегруппировать числа с отрицательное основание $- b {\ displaystyle -b}$ $-b$ .

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

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

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

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

Наименьшее простое число p такое, что $Q (n, p) {\ displaystyle Q (n, p)}$ ${\ displaystyle Q (n, p)}$ является простым числом (начинается с n = 2, 0, если таких нет p существует)

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 )

Наименьшее основание b такое, что $Q (b, простое число (n)) {\ displaystyle Q (b, prime (n))}$ $Q (b, простое число (n))$ простое число (начинается с n = 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 )

Ссылки

Внешние ссылки

Джон Ренце и Эрик В. Вайстейн. "Прайм Вагстафф". MathWorld.
Крис Колдуэлл, The Top Twenty: Wagstaff at Prime Pages.
Рено Лифшиц, «Эффективный вероятный простой тест для чисел формы (2 + 1) / 3 ".
Тони Рейкс, " Три гипотезы о проверке простоты чисел Мерсенна, Вагстаффа и Ферма, основанные на циклах диграфа под x - 2 по модулю простого ".
Список повторных единиц в базе От -50 до 50
Список простых чисел Вагстаффа с основанием 2 до 160