Прот Прайм

Прот Прайм
Назван в честь	Франсуа Прот
Год публикации	1878
Автор публикации	Прот, Франсуа
Количество известных терминов	4304683178 ниже 2 72
Предполагаемый нет. терминов	бесконечный
Последовательность	Числа Прота, простые числа
Формула	к × 2 н + 1
Первые сроки	3, 5, 13, 17, 41, 97, 113
Самый большой известный термин	10223 × 2 31172165 + 1 (по состоянию на декабрь 2019 г.)
ОЭИС Индекс	А080076 ; Простые числа Прота: простые числа вида k *2^ m + 1 с нечетным k <2^ m , m ≥ 1. ;

Число Прота — это натуральное число N вида $N=k\times 2^{n}+1$ где k и n — положительные целые числа , k — нечетно и $2^{n}>k$ . Простое число Прота — это число Прота, которое является простым . Они названы в честь французского математика Франсуа Прота . ^[2] Первые несколько простых чисел Прота равны

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 7 , 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 ( OEIS : A080076 ).

Вопрос о том, существует ли бесконечное число простых чисел Прота, до сих пор остается открытым. В 2022 году было показано, что обратная сумма простых чисел Прота сходится к действительному числу около 0,747392479, что существенно меньше значения 1,093322456 для обратной суммы чисел Прота. ^[1]

Простоту чисел Прота проверить легче, чем многих других чисел аналогичной величины.

Определение [ править ]

Число Прота принимает вид $N=k2^{n}+1$ где k и n — положительные целые числа, $k$ это странно и $2^{n}>k$ . Простое число Прота — это число Прота, которое является простым. ^[2]^[3] Без того условия, что $2^{n}>k$ , все нечетные целые числа больше 1 будут числами Прота. ^[4]

Тестирование на примитивность [ править ]

Простоту числа Прота можно проверить с помощью теоремы Прота , которая утверждает, что число Прота $p$ является простым тогда и только тогда, когда существует целое число $a$ для чего

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.

^[3]^[5]

Эту теорему можно использовать как вероятностный тест на простоту, проверяя множество случайных вариантов выбора. $a$ ли $a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.$ Если это не выполняется в течение нескольких случайных $a$ , то весьма вероятно, что число $p$ является составным . ^{[ нужна ссылка ]}Этот тест представляет собой алгоритм Лас-Вегаса : он никогда не возвращает ложноположительный результат , но может возвращать ложноотрицательный результат ; другими словами, он никогда не сообщает составное число как « вероятно простое », но может сообщать простое число как «возможно составное».

В 2008 году Сзе создал детерминированный алгоритм , который работает не более ${\tilde {O}}((k\log k+\log N)(\log N)^{2})$ время, где Õ — обозначение soft-O . Для типичного поиска простых чисел Прота обычно $k$ либо фиксирован (например, 321 Prime Search или проблема Серпинского), либо имеет порядок $O(\log N)$ (например, поиск простых чисел Каллена ). В этих случаях алгоритм работает не более ${\tilde {O}}((\log N)^{3})$ , или $O((\log N)^{3+\epsilon })$ время для всех $\epsilon >0$ . Также существует алгоритм, который работает в ${\tilde {O}}((\log N)^{24/7})$ время. ^[2]^[6]

Числа Ферма представляют собой частный случай чисел Прота, где $k =1$ . В таком сценарии тест Пепена доказывает, что $только основание a = 3$ для детерминированной проверки или фальсификации простоты числа Ферма необходимо проверять .

Большие простые числа [ править ]

По состоянию на 2022 год ^[update], самое большое известное простое число Прота равно $10223\times 2^{31172165}+1$ . Его длина составляет 9 383 761 цифр. ^[7] Его нашел Петер Сабольч в волонтерском вычислительном проекте PrimeGrid , который объявил об этом 6 ноября 2016 года. ^[8] Это также второе по величине известное простое число, не являющееся простым числом Мерсенна . ^[9]

Проект Seventeen or Bust , поиск Прота простых чисел с определенным $t$ чтобы доказать, что 78557 - наименьшее число Серпинского ( проблема Серпинского ), к 2007 году нашел 11 больших простых чисел Прота. Подобные решения простой проблемы Серпинского и расширенной проблемы Серпинского дали еще несколько чисел.

Поскольку делители чисел Ферма $F_{n}=2^{2^{n}}+1$ всегда имеют форму $k\times 2^{n+2}+1$ , принято определять, делит ли новое простое число Прота число Ферма. ^[10]

По состоянию на июль 2023 года PrimeGrid является ведущим вычислительным проектом для поиска простых чисел Прота. Среди его основных проектов:

общий поиск простых чисел Прота
321 Prime Search (поиск простых чисел вида $3\times 2^{n}+1$ , также называемые простыми числами Табита второго рода )
27121 Prime Search (поиск простых чисел вида $27\times 2^{n}+1$ и $121\times 2^{n}+1$ )
Поиск простых чисел Каллена (поиск простых чисел вида $n\times 2^{n}+1$ )
Проблема Серпинского (и их простые и расширенные обобщения) – поиск простых чисел вида $k\times 2^{n}+1$ где k находится в этом списке:

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 2 25931, 227723, 229673, 237019, 238411}

По состоянию на июнь 2023 года крупнейшими обнаруженными простыми числами Прота являются: ^[11]

классифицировать	основной	цифры	когда	Комментарии	Первооткрыватель (Проект)	Ссылки
1	10223 × 2 ^31172165 + 1	9383761	31 октября 2016 г.		Петер Сабольч (Задача Серпинского)	^[12]
2	202705 × 2 ^21320516 + 1	6418121	1 декабря 2021 г.		Павел Атнашев (Расширенная задача Серпинского)	^[13]
3	81 × 2 ^20498148 + 1	6170560	13 июля 2023 г.	Обобщенный Ферма F ₂ (3 × 2 ^5124537)	Райан Проппер (LLR)	^[11]
4	7 × 2 ^20267500 + 1	6101127	21 июля 2022 г.	Разделяет F _20267499 (12)	Райан Проппер (LLR)	^[11]^[14]
5	168451 × 2 ^19375200 + 1	5832522	17 сентября 2017 г.		Бен Мэлони (Основная задача Серпинского)	^[15]
6	7 × 2 ^18233956 + 1	5488969	1 октября 2020 г.	Разделяет Ферма F _18233954 и F _18233952 (7)	Райан Проппер	^[16]^[14]
7	13 × 2 ^16828072 + 1	5065756	11 октября 2023 г.		Райан Проппер	^[11]
8	3 × 2 ^16408818 + 1	4939547	28 октября 2020 г.	Делит F _16408814 (3), F _16408817 (5) и F _16408815 (8)	Джеймс Браун (PrimeGrid)	^[14]
9	11 × 2 ^15502315 + 1	4666663	8 января 2023 г.	Разделяет F _15502313 (10)	Райан Проппер	^[14]
10	37 × 2 ^15474010 + 1	4658143	8 ноября 2022 г.		Райан Проппер	^[14]
11	(2 ^7658613 + 1) × 2 ^7658614 + 1	4610945	31 июля 2020 г.	Гауссова норма Мерсенна	Райан Проппер и Серж Баталов	^[11]
12	13 × 2 ^15294536 + 1	4604116	30 сентября 2023 г.		Райан Проппер	^[11]
13	37 × 2 ^14166940 + 1	4264676	24 июня 2022 г.		Райан Проппер	^[11]
14	99739 × 2 ^14019102 + 1	4220176	24 декабря 2019 г.		Брайан Нигоцки (Расширенная задача Серпинского)	^[17]
15	404849 × 2 ^13764867 + 1	4143644	10 марта 2021 г.	Обобщенный Каллен с основанием 131072	Райан Проппер и Серж Баталов	^[11]
16	25 × 2 ^13719266 + 1	4129912	21 сен 2022 г.	Ф ₁ (5 × 2 ^6859633)	Райан Проппер	^[11]
17	81 × 2 ^13708272 + 1	4126603	11 октября 2022 г.	Ф2 ₂ (3× ^3427068)	Райан Проппер	^[11]
18	81 × 2 ^13470584 + 1	4055052	9 октября 2022 г.	Ф2 ₂ (3× ^3367646)	Райан Проппер	^[11]
19	9 × 2 ^13334487 + 1	4014082	31 марта 2020 г.	Делит F _13334485 (3), F _13334486 (7) и F _13334484 (8)	Райан Проппер	^[14]
20	19249 × 2 ^13018586 + 1	3918990	26 марта 2007 г.		Константин Агафонов (Семнадцать или Бюст)	^[12]

Использует [ править ]

Маленькие простые числа Прота (менее 10 ²⁰⁰) использовались при построении лестниц простых чисел, последовательностей простых чисел, в которых каждый член «близок» (в пределах примерно 10 ¹¹) к предыдущему. Такие лестницы использовались для эмпирической проверки гипотез , связанных с простыми числами . Например, слабая гипотеза Гольдбаха была проверена в 2008 году до 8,875 × 10. ³⁰ используя лестницы простых чисел, построенные из простых чисел Прота. ^[18] (Эту гипотезу позже доказал Харальд Хелфготт . ^[19]^[20]^{[ нужен лучший источник ]})

Кроме того, простые числа Прота могут оптимизировать приведение ден-Бура между проблемой Диффи-Хеллмана и проблемой дискретного логарифма . Простое число 55 × 2 ²⁸⁶ + 1 использовался таким образом. ^[21]

Поскольку простые числа Прота имеют простое двоичное представление, они также использовались для быстрого модульного сокращения без необходимости предварительного вычисления, например, Microsoft . ^[22]

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

^ Jump up to: ^а ^б Борсос, Берталан; Ковач, Аттила; Тиханьи, Норберт (2022), «Точные верхняя и нижняя границы обратной суммы простых чисел Прота», Ramanujan Journal , 59 , Springer: 181–198, doi : 10.1007/s11139-021-00536-2 , hdl : 10831/83020 , S2CID 246024152
^ Jump up to: ^а ^б ^с Сзе, Цз-Во (2008). «Детерминированное доказательство простоты на числах Прота». arXiv : 0812.2596 [ math.NT ].
^ Jump up to: ^а ^б Вайсштейн, Эрик В. «Прот Прайм» . mathworld.wolfram.com . Проверено 6 декабря 2019 г.
^ Вайсштейн, Эрик В. «Число Прота» . mathworld.wolfram.com . Проверено 7 декабря 2019 г.
^ Вайсштейн, Эрик В. «Теорема Прота» . Математический мир .
^ Конягин, Сергей; Померанс, Карл (2013), Грэм, Рональд Л.; Нешетржил, Ярослав; Батлер, Стив (ред.), «О простых числах, распознаваемых в детерминированное полиномиальное время», Математика Пола Эрдеша I , Springer New York, стр. 159–186, doi : 10.1007/978-1-4614-7258-2_12 , ISBN 978-1-4614-7258-2
^ Колдуэлл, Крис. «Двадцатка лучших: Прот» . Главные страницы .
^ Ван Циммерман (30 ноября 2016 г.) [9 ноября 2016 г.]. «Обнаружен мировой рекорд числа Кольбера!» . ПраймГрид .
^ Колдуэлл, Крис. «Двадцать лучших: самые большие известные простые числа» . Главные страницы .
^ «Глоссарий: делитель Ферма» . primes.utm.edu . Проверено 14 ноября 2021 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Колдуэлл, Крис К. «Двадцатка лучших: Прот» . Двадцатка лучших . Проверено 6 декабря 2019 г.
^ Jump up to: ^а ^б Гетц, Майкл (27 февраля 2018 г.). «Семнадцать или бюст» . ПраймГрид . Проверено 6 декабря 2019 г.
^ «Расширенная задача Серпинского PrimeGrid: поиск простых чисел» (PDF) . primegrid.com . ПраймГрид . Проверено 28 декабря 2021 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж «Новые факторы GFN» . www.prothsearch.com . Проверено 14 ноября 2021 г.
^ «Официальное открытие простого числа 168451×2. ^19375200+1» (PDF) . PrimeGrid . Дата обращения 6 декабря 2019 г. .
^ «Факторинговый статус Ферма» . www.prothsearch.com . Проверено 14 ноября 2021 г.
^ «Официальное открытие простого числа 99739×2. ^14019102+1» (PDF) . PrimeGrid . 24 декабря 2019 г. Проверено 14 ноября 2021 г. .
^ Хелфготт, ХА; Платт, Дэвид Дж. (2013). «Численная проверка тройной гипотезы Гольдбаха до 8,875e30». arXiv : 1305.3062 [ math.NT ].
^ Хелфготт, Харальд А. (2013). «Тройная гипотеза Гольдбаха верна». arXiv : 1312.7748 [ math.NT ].
^ «Харальд Андрес Хелфготт» . Александр фон Гумбольдт-Профессур . Проверено 8 декабря 2019 г.
^ Браун, Дэниел Р.Л. (24 февраля 2015 г.). «CM55: специальные эллиптические кривые простого поля, почти оптимизирующие преобразование ден Бура между Диффи – Хеллманом и дискретными логарифмами» (PDF) . Международная ассоциация криптологических исследований : 1–3.
^ Ачар, Толга; Шумоу, Дэн (2010). «Модульная редукция без предварительного расчета для специальных модулей» (PDF) . Исследования Майкрософт .

[:proth-1] Jump up to: ^а ^б Борсос, Берталан; Ковач, Аттила; Тиханьи, Норберт (2022), «Точные верхняя и нижняя границы обратной суммы простых чисел Прота», Ramanujan Journal , 59 , Springer: 181–198, doi : 10.1007/s11139-021-00536-2 , hdl : 10831/83020 , S2CID 246024152

[:0-2] Jump up to: ^а ^б ^с Сзе, Цз-Во (2008). «Детерминированное доказательство простоты на числах Прота». arXiv : 0812.2596 [ math.NT ].

[:1-3] Jump up to: ^а ^б Вайсштейн, Эрик В. «Прот Прайм» . mathworld.wolfram.com . Проверено 6 декабря 2019 г.

[4] Вайсштейн, Эрик В. «Число Прота» . mathworld.wolfram.com . Проверено 7 декабря 2019 г.

[5] Вайсштейн, Эрик В. «Теорема Прота» . Математический мир .

[6] Конягин, Сергей; Померанс, Карл (2013), Грэм, Рональд Л.; Нешетржил, Ярослав; Батлер, Стив (ред.), «О простых числах, распознаваемых в детерминированное полиномиальное время», Математика Пола Эрдеша I , Springer New York, стр. 159–186, doi : 10.1007/978-1-4614-7258-2_12 , ISBN 978-1-4614-7258-2

[7] Колдуэлл, Крис. «Двадцатка лучших: Прот» . Главные страницы .

[8] Ван Циммерман (30 ноября 2016 г.) [9 ноября 2016 г.]. «Обнаружен мировой рекорд числа Кольбера!» . ПраймГрид .

[9] Колдуэлл, Крис. «Двадцать лучших: самые большие известные простые числа» . Главные страницы .

[10] «Глоссарий: делитель Ферма» . primes.utm.edu . Проверено 14 ноября 2021 г.

[top20-11] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Колдуэлл, Крис К. «Двадцатка лучших: Прот» . Двадцатка лучших . Проверено 6 декабря 2019 г.

[:2-12] Jump up to: ^а ^б Гетц, Майкл (27 февраля 2018 г.). «Семнадцать или бюст» . ПраймГрид . Проверено 6 декабря 2019 г.

[13] «Расширенная задача Серпинского PrimeGrid: поиск простых чисел» (PDF) . primegrid.com . ПраймГрид . Проверено 28 декабря 2021 г.

[gfermat-14] Jump up to: ^а ^б ^с ^д ^и ^ж «Новые факторы GFN» . www.prothsearch.com . Проверено 14 ноября 2021 г.

[15] «Официальное открытие простого числа 168451×2. ^19375200+1» (PDF) . PrimeGrid . Дата обращения 6 декабря 2019 г. .

[fermat-16] «Факторинговый статус Ферма» . www.prothsearch.com . Проверено 14 ноября 2021 г.

[17] «Официальное открытие простого числа 99739×2. ^14019102+1» (PDF) . PrimeGrid . 24 декабря 2019 г. Проверено 14 ноября 2021 г. .

[18] Хелфготт, ХА; Платт, Дэвид Дж. (2013). «Численная проверка тройной гипотезы Гольдбаха до 8,875e30». arXiv : 1305.3062 [ math.NT ].

[:02-19] Хелфготт, Харальд А. (2013). «Тройная гипотеза Гольдбаха верна». arXiv : 1312.7748 [ math.NT ].

[humboldt-professur.de-20] «Харальд Андрес Хелфготт» . Александр фон Гумбольдт-Профессур . Проверено 8 декабря 2019 г.

[21] Браун, Дэниел Р.Л. (24 февраля 2015 г.). «CM55: специальные эллиптические кривые простого поля, почти оптимизирующие преобразование ден Бура между Диффи – Хеллманом и дискретными логарифмами» (PDF) . Международная ассоциация криптологических исследований : 1–3.

[22] Ачар, Толга; Шумоу, Дэн (2010). «Модульная редукция без предварительного расчета для специальных модулей» (PDF) . Исследования Майкрософт .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

v т и Классы простых чисел
По формуле	Ферма ( $2 2 н + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Вагстафф $(2 п + 1)/3$ Прот ( $k \cdot2 н + 1$ ) Факториал ( $n! \pm 1$ ) Первобытный ( $p n # \pm 1$ ) Евклид ( $p n # + 1$ ) Пифагорейский ( $4 n + 1$ ) Пьерпон ( $2 м \cdot3 н + 1$ ) Квартан ( $х 4 + и 4$ ) Солинас ( $2 м \pm 2 н \pm 1$ ) Каллен ( $n \cdot2 н + 1$ ) Вудалл ( $n \cdot2 н - 1$ ) Кубинский ( $х 3 - и 3)/(Икс - у$ ) Лейланд ( $x и + и х$ ) Сабит ( $3\cdot2 н - 1$ ) Уильямс ( $(b -1)\cdot b н - 1$ ) Миллс ( $⌊ А 3 н ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман–Шэнкс–Уильямс Перрин
По свойству	Виферих ( пара ) Стена–Солнце–Солнце Вулстенхолм Уилсон Удачливый удачливый Рамануджан Пиллаи Обычный Сильный Стерн Суперсингулярная (эллиптическая кривая) Суперсингулярная (теория самогона) Хороший Супер Хиггс Высокий коэффициент Уникальный
Базово -зависимый	палиндромный Эмирп Репунит $(10 н - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Нежный Первобытный Полный отчет Уникальный Счастливый Себя Смарандаш-Веллин Стробограмматический двугранный тетрадный
Узоры	Твин ( $р, р + 2$ ) Двойная цепь ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Тройка ( $p, p +2 или p +4, p +6$ ) Четверка ( $р, р +2, р +6, р +8$ ) k -кортеж Двоюродный брат ( $п, р + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен/Сейф ( $п, 2п +1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательные p - n, p, p + n$ )
По размеру	Мега (1 000 000+ цифр) Самый крупный известный список
Комплексные числа	Айронстоун прайм Гауссово простое число
Составные числа	Псевдопростой каталанский Эллиптический Эйлер Эйлер – Якоби Ферма Фробениус Лукас Перрин Сомер-Лукас Сильный Число Кармайкла Почти премьер Полупервоклассный Сфеническое число Интерпрайм Пагубный
Связанные темы	Вероятное простое число Промышленный класс Prime Незаконный премьер Формула простых чисел Премьер-разрыв
Первые 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
Список простых чисел