Proth Prime

Номер Proth является натуральным числом N вида , где к и п имеют положительные целые числа , к является нечетным и . Proth премьер ряд Proth что премьер . Они названы в честь французского математика Франсуа Прота . ^[1] Первые несколько простых чисел Proth ${\ displaystyle N = k2 ^ {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, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 ( OEIS :  A080076 ).

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

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

Число Proth принимает форму, где k и n - натуральные числа, нечетное и . Простое число Proth - это простое число Proth. ^{[1] [2]}${\ displaystyle N = k2 ^ {n} +1}$${\ displaystyle k}$${\ displaystyle 2 ^ {n}> k}$

Без условия, что все нечетные целые числа больше 1 будут числами Proth. ^[3]${\ displaystyle 2 ^ {n}> k}$

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

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

${\ displaystyle a ^ {\ frac {p-1} {2}} \ Equiv -1 {\ pmod {p}}.}$^{[2] [4]}

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

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

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

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

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

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

• общий поиск Proth Prime
• 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, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

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

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

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

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

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

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