Прот Прайм

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

Тестирование простоты

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

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

^[3]^[5]

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

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

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

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

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

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

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

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

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

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

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

Использует

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

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

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

Ссылки

^ аб Борсос, Берталан; Ковач, Аттила; Тиханьи, Норберт (2022), «Точные верхняя и нижняя границы обратной суммы простых чисел Прота», Ramanujan Journal , 59 , Springer: 181–198, doi : 10.1007/s11139-021-00536-2 , hdl : 10831/83020 , S2CID 246024152
^ abc Sze, Tsz-Wo (2008). «Детерминированное доказательство простоты чисел Прота». arXiv : 0812.2596 [math.NT].
^ ab Weisstein, Eric W. "Proth Prime". mathworld.wolfram.com . Получено 2019-12-06 .
^ Weisstein, Eric W. "Число Прота". mathworld.wolfram.com . Получено 2019-12-07 .
^ Вайсштейн, Эрик В. «Теорема Прота». MathWorld .
^ Конягин, Сергей; Померанс, Карл (2013), Грэм, Рональд Л.; Нешетржил, Ярослав; Батлер, Стив (ред.), «О простых числах, распознаваемых за детерминированное полиномиальное время», Математика Пола Эрдёша I , Springer New York, стр. 159–186, doi :10.1007/978-1-4614-7258-2_12, ISBN 978-1-4614-7258-2
^ Колдуэлл, Крис. «Двадцатка лучших: Прот». The Prime Pages .
^ Ван Циммерман (30 ноября 2016 г.) [9 ноября 2016 г.]. «Обнаружено мировое рекордное число Кольбера!». PrimeGrid .
^ Колдуэлл, Крис. «Двадцатка лучших: самые большие известные простые числа». The Prime Pages .
^ "The Prime Glossary: Fermat divisor". primes.utm.edu . Получено 14 ноября 2021 г. .
^ abcdefghijk Колдуэлл, Крис К. "The top twenty: Proth". The Top Twenty . Получено 6 декабря 2019 г. .
^ ab Goetz, Michael (27 февраля 2018 г.). «Seventeen or Bust». PrimeGrid . Получено 6 декабря 2019 г. .
^ "Расширенная задача Серпинского PrimeGrid: поиск простых чисел" (PDF) . primegrid.com . PrimeGrid . Получено 28 декабря 2021 г. .
^ abcdef "Новые факторы GFN". www.prothsearch.com . Получено 14 ноября 2021 г. .
^ "Официальное открытие простого числа 168451×219375200+1" (PDF) . PrimeGrid . Получено 6 декабря 2019 г. .
^ "Статус факторизации Ферма". www.prothsearch.com . Получено 14 ноября 2021 г. .
^ "Официальное открытие простого числа 99739×214019102+1" (PDF) . PrimeGrid . 24 декабря 2019 . Получено 14 ноября 2021 .
^ Хельфготт, HA; Платт, Дэвид Дж. (2013). «Численная проверка тернарной гипотезы Гольдбаха до 8,875e30». arXiv : 1305.3062 [math.NT].
^ Хельфготт, Харальд А. (2013). «Тернарная гипотеза Гольдбаха верна». arXiv : 1312.7748 [math.NT].
^ "Харальд Андрес Хелфготт". Александр фон Гумбольдт-Профессур . Проверено 8 декабря 2019 г.
^ Браун, Дэниел РЛ (24 февраля 2015 г.). "CM55: специальные эллиптические кривые простого поля, почти оптимизирующие сокращение Ден Бура между Диффи–Хеллманом и дискретными логарифмами" (PDF) . Международная ассоциация криптографических исследований : 1–3.
^ Акар, Толга; Шумов, Дэн (2010). «Модулярная редукция без предварительного вычисления для специальных модулей» (PDF) . Microsoft Research .