Proth Prime - Proth prime

Proth Prime

Названный в честь	Франсуа Прот
Год публикации	1878
Автор публикации	Прот, Франсуа
Нет. известных терминов	Более 1,5 миллиарда ниже 2^70
Предполагаемый нет. условий	Бесконечный
Подпоследовательность из	Proth числа, простые числа
Формула	k × 2п + 1
Первые триместры	3, 5, 13, 17, 41, 97, 113
Самый большой известный термин	10223 × 2^31172165 + 1 (по состоянию на декабрь 2019 г.)
OEIS индекс	A080076 Простые числа: простые числа вида k * 2 ^ m + 1 с нечетным k <2 ^ m, m> = 1

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

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 принимает форму ${\displaystyle N=k2^{n}+1}$ куда k и п положительные целые числа, ${\displaystyle k}$ это странно и ${\displaystyle 2^{n}>k}$. Простое число Proth - это простое число Proth.^[1][2]

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

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

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

Простота числа 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 году Сзе создал детерминированный алгоритм что работает самое большее ${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$ время, где Õ - soft-O обозначение. Для типичного поиска простых чисел Proth обычно ${\displaystyle k}$ либо фиксировано (например, 321 Prime Search или проблема Серпинского), либо имеет порядок ${\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})}$ время.^[1][5]

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

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

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

По состоянию на декабрь 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}$)
• Задача Серпинского (и их простые и расширенные обобщения) - поиск простых чисел вида ${\displaystyle k\times 2^{n}+1}$ где k находится в этом списке:

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]

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

1. Остается неясным, к какому проекту присоединился Баталов, чтобы найти премьер; однако мы можем быть уверены, что он не используйте PrimeGrid.

Использует

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

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

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

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

1. Сзе, Цз-Во (2008). «Доказательство детерминированной примитивности на числах Proth». arXiv:0812.2596 [math.NT ].
2. Вайсштейн, Эрик В. «Прот Прайм». mathworld.wolfram.com. Получено 2019-12-06.
3. Вайсштейн, Эрик В. "Proth Number". mathworld.wolfram.com. Получено 2019-12-07.
4. Вайсштейн, Эрик В. «Теорема Прота». MathWorld.
5. Конягин Сергей; Померанс, Карл (2013), Грэм, Рональд Л .; Нешетржил, Ярослав; Батлер, Стив (ред.), "О простых числах, распознаваемых в детерминированном полиномиальном времени", Математика Пола Эрдёша I, Springer New York, стр. 159–186, Дои:10.1007/978-1-4614-7258-2_12, ISBN  978-1-4614-7258-2
6. Колдуэлл, Крис. «Двадцатка лучших: Proth». В Prime Pages.
7. Ван Циммерман (30 ноября 2016 г.) [9 ноября 2016 г.]. "Обнаружен мировой рекорд числа Колберта!". PrimeGrid.
8. Колдуэлл, Крис. «Двадцать лучших: наибольшие известные простые числа». В Prime Pages.
9. Колдуэлл, Крис К. «Двадцатка лучших: Прот». Двадцать лучших. Получено 6 декабря 2019.
10. Гетц, Майкл (27 февраля 2018 г.). «Семнадцать или бюст». PrimeGrid. Получено 6 декабря 2019.
11. "Официальное открытие простого числа 168451 × 2^19375200+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
12. "Официальное открытие простого числа 193997 × 2^11452891+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
13. "Официальное открытие простого числа 3 × 2^10829346+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
14. "Проблема Прайма Серпинского". mersenneforum.org. 18 июня 2004 г.. Получено 7 декабря 2019.
15. Колдуэлл, Крис К. "Патрис Салах". Прайм Страницы. Получено 9 декабря 2019.
16. "Официальное открытие простого числа 161041 × 2^7107964+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
17. «Официальное открытие простого числа 27 × 2^7046834+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
18. "Официальное открытие простого числа 3 × 2^7033641+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
19. "Официальное открытие простого числа 6679881 × 2^6679881+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
20. "Официальное открытие простого числа 6328548 × 2^6328548+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
21. "Официальное открытие простого числа 7 × 2^5775996+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
22. «Предложение: проект 5-7-9 Proth». PrimeGrid. 25 июл 2019. Получено 8 декабря 2019.
23. "9·2^5642513+1 (еще один ресурс Prime Pages) ". База данных Prime. 1 апреля 2014 г.. Получено 9 декабря 2019.
24. Колдуэлл, Крис К. "Скотт Гилви". Прайм Страницы. Получено 9 декабря 2019.
25. «Официальное открытие простого числа 27 × 2^5213635+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
26. «PrimeGrid Primes». PrimeGrid. Получено 7 декабря 2019.
27. "Официальное открытие простого числа 3 × 2^5082306+1" (PDF). PrimeGrid. Получено 6 декабря 2019.
28. Helfgott, H.A .; Платт, Дэвид Дж. (2013). «Численное подтверждение троичной гипотезы Гольдбаха до 8.875e30». arXiv:1305.3062 [math.NT ].
29. Хельфготт, Харальд А. (2013). «Тройная гипотеза Гольдбаха верна». arXiv:1312.7748 [math.NT ].
30. "Харальд Андрес Хельфготт". Александр фон Гумбольдт-Профессур. Получено 2019-12-08.
31. Браун, Дэниел Р. Л. (24 февраля 2015 г.). «CM55: специальные эллиптические кривые с простым полем, почти оптимизирующие редукцию ден Бура между диаграммами Диффи – Хеллмана и дискретными каротажами» (PDF). Международная ассоциация криптологических исследований: 1–3.
32. Акар, Толга; Шумов, Дэн (2010). «Модульная редукция без предварительного вычисления специальных модулей» (PDF). Microsoft Research.