Proth Prime

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

(Перенаправлено с протого номера )

Proth Prime
Названный в честь	Франсуа Прот
Год публикации	1878 г.
Автор публикации	Прот, Франсуа
Количество известных терминов	Более 1,5 миллиарда Менее 2 ⁷⁰
Предполагаемый нет.условий	Бесконечный
подпоследовательности из	Простые числа, простые числа
Формула	к × 2 ^п + 1
Первые триместры	3, 5, 13, 17, 41, 97, 113
Самый большой известный термин	10223 × 2 ^31172165 + 1 (по состоянию на декабрь 2019 г.)
Индекс OEIS

Номер Proth представляет собой число N вида, где к и п имеют положительные целые числа, к нечетно и. Proth премьер ряд Proth что премьер. Они названы в честь французского математика Франсуа Прота. Первые несколько простых чисел Proth: ${\ displaystyle N = k2 ^ {n} +1}$ ${\ displaystyle N = k2 ^ {n} +1}$ ${\ displaystyle 2 ^ {n}gt; k}$ ${\ displaystyle 2 ^ {n}gt; 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 может быть проверена легче, чем многие другие числа подобной величины.

Содержание

1 Определение
2 Проверка первичности
3 большие простые числа
4 использования
5 ссылки

Определение

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

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

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

Смотрите также: Теорема Прота

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

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

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

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

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

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

По состоянию на 2019 год самый крупный из известных Proth Prime - это. Его длина составляет 9,383,761 цифра. Оно было обнаружено Сабольком Петером в проекте распределенных вычислений PrimeGrid, о котором было объявлено 6 ноября 2016 года. Это также крупнейшее известное простое число, не относящееся к Мерсенну. ${\ displaystyle 10223 \ cdot 2 ^ {31172165} +1}$ ${\ 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 \ раз 2 ^ {п} +1}$ ${\ Displaystyle 3 \ раз 2 ^ {п} +1}$
27121 Prime Search (поиск простых чисел формы и) ${\ displaystyle 27 \ times 2 ^ {n} +1}$ ${\ displaystyle 27 \ times 2 ^ {n} +1}$ ${\ displaystyle 121 \ times 2 ^ {n} +1}$ ${\ displaystyle 121 \ times 2 ^ {n} +1}$
Поиск простых чисел Каллена (поиск простых чисел формы) ${\ Displaystyle п \ раз 2 ^ {п} +1}$ ${\ Displaystyle п \ раз 2 ^ {п} +1}$
Задача Серпинского (и их простые и расширенные обобщения) - поиск простых чисел вида, где k находится в этом списке: ${\ Displaystyle к \ раз 2 ^ {п} +1}$ ${\ Displaystyle к \ раз 2 ^ {п} +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 являются:

ранг	премьер	цифры	когда	Каллен Прайм ?	Первооткрыватель (Проект)
1	10223 2 ^31172165 + 1	9383761	31 октября 2016 г.		Сабольч Петер (Проблема Серпинского)
2	168451 2 ^19375200 + 1	5832522	17 сен 2017		Бен Мэлони (простая задача Серпинского)
3	19249 2 ^13018586 + 1	3918990	26 марта 2007 г.		Константин Агафонов (Семнадцать или бюст)
4	193997 2 ^11452891 + 1	3447670	3 апреля 2018 г.		Том Грир (Расширенная проблема Серпинского)
5	3 2 ^10829346 + 1	3259959	14 янв 2014		Сай Ик Тан (321 Prime Search)
6	27653 2 ^9167433 + 1	2759677	8 июня 2005 г.		Дерек Гордон (семнадцать или бюст)
7	90527 2 ^9162167 + 1	2758093	30 июн 2010		Неизвестно (простая задача Серпинского)
8	28433 2 ^7830457 + 1	2357207	30 декабря 2004 г.		Team Prime Rib (семнадцать или бюст)
9	161041 2 ^7107964 + 1	2139716	6 янв 2015		Мартин Ванц (Расширенная проблема Серпинского)
10	27 2 ^7046834 + 1	2121310	11 октября 2018 г.		Эндрю М. Фэрроу (27121 Prime Search)
11	3 2 ^7033641 + 1	2117338	21 февраля 2011 г.		Майкл Хердер (321 Prime Search)
12	33661 2 ^7031232 + 1	2116617	17 октября 2007 г.		Стерле Сунде (Семнадцать или Бюст)
13	6679881 2 ^6679881 + 1	2010852	25 июл 2009	да	Магнус Бергман (Поиск Каллена Прайм)
14	1582137 2 ^6328550 + 1	1905090	20 апреля 2009 г.	да	Деннис Р. Гескер (Поиск Каллена Прайм)
15	7 2 ^5775996 + 1	1738749	2 ноя 2012		Мартин Элви (Поиск Прот Прайм)
16	9 2 ^5642513 + 1	1698567	29 ноя 2013		Серж Баталов
17	258317 2 ^5450519 + 1	1640776	28 июля 2008 г.		Скотт Гилви (Простая задача Серпинского)
18	27 2 ^5213635 + 1	1569462	9 марта 2015 г.		Хироюки Окадзаки (27121 Prime Search)
19	39 2 ^5119458 + 1	1541113	23 ноя 2019		Скотт Браун (Fermat Divisor Prime Search)
20	3 2 ^5082306 + 1	1529928	3 апреля 2009 г.		Энди Брэди (321 Prime Search)

Использует

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

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

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

Ссылки