Прот Прайм

Простое число вида k*(2^n)+1

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

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]

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

Определение

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

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

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

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$^{[3] [5]}

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

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

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

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

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

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

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

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

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

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]

Использование

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

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

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

Рекомендации

1. Борсос, Берталан; Ковач, Аттила; Тиханьи, Норберт (2022), «Точные верхняя и нижняя границы обратной суммы простых чисел Прота», Ramanujan Journal , 59 , Springer: 181–198, doi : 10.1007/s11139-021-00536-2 , hdl : 10831/83020 , S2CID  246024152
2. Sze, Цз-Во (2008). «Детерминированное доказательство простоты на числах Прота». arXiv : 0812.2596 [math.NT].
3. Вайсштейн, Эрик В. «Прот Прайм». 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 г.
11. Колдуэлл, Крис К. «Двадцатка лучших: Прот». Двадцатка лучших . Проверено 6 декабря 2019 г.
12. Гетц, Майкл (27 февраля 2018 г.). «Семнадцать или бюст». ПраймГрид . Проверено 6 декабря 2019 г.
13. «Расширенная задача Серпинского PrimeGrid: поиск простых чисел» (PDF) . primegrid.com . ПраймГрид . Проверено 28 декабря 2021 г.
14. «Новые факторы GFN». www.prothsearch.com . Проверено 14 ноября 2021 г.
15. «Официальное открытие простого числа 168451×219375200+1» (PDF) . ПраймГрид . Проверено 6 декабря 2019 г.
16. «Статус факторинга Ферма» . www.prothsearch.com . Проверено 14 ноября 2021 г.
17. «Официальное открытие простого числа 99739×214019102+1» (PDF) . ПраймГрид . 24 декабря 2019 года . Проверено 14 ноября 2021 г.
18. Хелфготт, ХА; Платт, Дэвид Дж. (2013). «Численная проверка тройной гипотезы Гольдбаха до 8,875e30». arXiv : 1305.3062 [math.NT].
19. Хелфготт, Харальд А. (2013). «Тройная гипотеза Гольдбаха верна». arXiv : 1312,7748 [math.NT].
20. "Харальд Андрес Хелфготт". Александр фон Гумбольдт-Профессур . Проверено 8 декабря 2019 г.
21. Браун, Дэниел Р.Л. (24 февраля 2015 г.). «CM55: специальные эллиптические кривые простого поля, почти оптимизирующие преобразование ден Бура между Диффи – Хеллманом и дискретными логарифмами» (PDF) . Международная ассоциация криптологических исследований : 1–3.
22. Ачар, Толга; Шумоу, Дэн (2010). «Модульная редукция без предварительного расчета для специальных модулей» (PDF) . Исследования Майкрософт .