Праймы Сейф и Софи Жермен

В теории чисел p простое число является простым числом Софи Жермен , если 2 p + 1 также является простым. Число 2 p + 1, связанное с простым числом Софи Жермен, называется безопасным простым числом . Например, 11 — простое число Софи Жермен, а 2 × 11 + 1 = 23 — соответствующее ему безопасное простое число. Простые числа Софи Жермен и безопасные простые числа находят применение в криптографии с открытым ключом и тестировании на простоту . Было высказано предположение , что существует бесконечно много простых чисел Софи Жермен, но это остается недоказанным.

Простые числа Софи Жермен названы в честь французского математика Софи Жермен , которая использовала их в своих исследованиях Великой теоремы Ферма . ^[1] Одна из попыток Жермена доказать Великую теорему Ферма заключалась в том, чтобы позволить p быть простым числом вида 8 k + 7 и положить n = p – 1. В этом случае $x^{n}+y^{n}=z^{n}$ неразрешима. Однако доказательство Жермена осталось незавершенным. ^[2]^[3] Благодаря своим попыткам решить Великую теорему Ферма Жермен разработала результат, ныне известный как Теорема Жермена, которая утверждает, что если p — нечетное простое число и 2 p + 1 также является простым, то p должно делить x , y или z. В противном случае, ${\textstyle x^{n}+y^{n}\neq z^{n}}$ . Этот случай, когда p не делит x , y или z, называется первым случаем. Работа Софи Жермен была наибольшим прогрессом, достигнутым в то время по последней теореме Ферма. ^[2] Более поздние работы Куммера и других всегда делили проблему на первый и второй случаи.

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

Первые несколько простых чисел Софи Жермен (меньше 1000) равны

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, ... OEIS : A005384

Следовательно, первые несколько безопасных простых чисел равны

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, ... OEIS : A005385

В криптографии гораздо большие простые числа Софи Жермен, например 1 846 389 521 368 + 11. ⁶⁰⁰ необходимы.

Два проекта распределенных вычислений, PrimeGrid и Twin Prime Search , включают поиск больших простых чисел Софи Жермен. Некоторые из крупнейших известных простых чисел Софи Жермен приведены в следующей таблице. ^[4]

Ценить	Количество цифр	Время открытия	Первооткрыватель
2618163402417 × 2 ^1290000 − 1	388342	февраль 2016 г.	Доктор Джеймс Скотт Браун в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR. ^[5]
18543637900515 × 2 ⁶⁶⁶⁶⁶⁷ − 1	200701	апрель 2012 г.	Филипп Блидунг в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR. ^[6]
183027 × 2 ²⁶⁵⁴⁴⁰ − 1	79911	март 2010 г.	Том Ву использует LLR ^[7]
648621027630345 × 2 ²⁵³⁸²⁴ − 1 и 620366307356565 × 2 ²⁵³⁸²⁴ − 1	76424	ноябрь 2009 г.	Золтан Харай, Габор Фаркас, Тимеа Чайбок, Янош Каса и Антал Харай ^[8]^[9]
1068669447 × 2 ²¹¹⁰⁸⁸ − 1	63553	май 2020 г.	Майкл Квок ^[10]
99064503957 × 2 ²⁰⁰⁰⁰⁸ − 1	60220	апрель 2016 г.	С. Урушихата ^[11]
607095 × 2 ¹⁷⁶³¹¹ − 1	53081	сентябрь 2009 г.	Том Ву ^[12]
48047305725 × 2 ¹⁷²⁴⁰³ − 1	51910	январь 2007 г.	Дэвид Андербакке использует TwinGen и LLR ^[13]
137211941292195 × 2 ¹⁷¹⁹⁶⁰ − 1	51780	май 2006 г.	Джарай и др. ^[14]

2 декабря 2019 года Фабрис Будо, Пьеррик Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Поль Циммерманн объявили о вычислении дискретного логарифма по модулю 240-значного (795 бит) простого числа RSA-240 + 49204 (первое безопасное простое число). выше RSA-240) с использованием алгоритма сита числового поля ; см. записи дискретных логарифмов .

Свойства [ править ]

Для безопасных простых чисел не существует специального теста на простоту, как для простых чисел Ферма и простых чисел Мерсенна . Однако критерий Поклингтона можно использовать для доказательства простоты числа 2 p + 1, как только будет доказана простота числа p .

Подобно тому, как каждый член цепи Каннингема первого рода, кроме последнего, является простым числом Софи Жермен, так и каждый член такой цепочки, кроме первого, является безопасным простым числом. Безопасные простые числа, оканчивающиеся на 7, то есть вида 10 n + 7, являются последними членами таких цепочек, когда они встречаются, поскольку 2(10 n + 7) + 1 = 20 n + 15 делится на 5.

Модульные ограничения [ править ]

За исключением 7, безопасное простое число q имеет вид 6 k − 1 или, что то же самое, q ≡ 5 ( mod 6) – как и p > 3. Аналогично, за исключением 5, безопасное простое число q имеет вид форма 4 k − 1 или, что то же самое, q ≡ 3 (mod 4) — тривиально верно, поскольку ( q − 1)/2 должно иметь нечетное натуральное число . Комбинируя обе формы с помощью lcm (6, 4), мы определяем, что безопасное простое число q > 7 также должно иметь вид 12 k − 1 или, что то же самое, q ≡ 11 (mod 12).

Отсюда следует, что для любого безопасного простого числа q > 7:

и 3, и 12 являются квадратичными вычетами по модулю q (по закону квадратичной взаимности )
ни 12 не являются примитивными корнями q ни 3 ,
единственные безопасные простые числа, которые также являются полными повторяющимися простыми числами по основанию 12, - это 5 и 7.
q делит 3 ^{( q −1)/2} − 1

Если p — простое число Софи Жермен, большее 3, то p должно быть конгруэнтно 2 по модулю 3. В противном случае оно было бы конгруэнтно 1 по модулю 3, а 2 p + 1 было бы конгруэнтно 3 по модулю 3, что невозможно для простое число. ^[15] Аналогичные ограничения справедливы для больших простых модулей и являются основой для выбора «поправочного коэффициента» 2 C в оценке Харди – Литтлвуда плотности простых чисел Софи Жермен. ^[16]

Если простое число Софи Жермен p конгруэнтно OEIS 3 (по модулю 4) ( : A002515 , простые числа Люка ), то соответствующее ему безопасное простое число 2 p + 1 ( соответствующее 7 по модулю 8) будет делителем числа Мерсенна 2. ^п − 1. Исторически этот результат Леонарда Эйлера числа Мерсенна с простым индексом был первым известным критерием составного . ^[17] Его можно использовать для генерации самых больших чисел Мерсенна (с простыми индексами), которые, как известно, являются составными. ^[18]

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

Нерешенная задача по математике :

Существует ли бесконечно много простых чисел Софи Жермен?

(еще нерешенные задачи по математике)

Предполагается , что существует бесконечно много простых чисел Софи Жермен, но это не доказано . ^[16] Несколько других известных гипотез в теории чисел обобщают эту гипотезу и гипотезу о простых числах-близнецах ; они включают гипотезу Диксона , гипотезу Шинцеля H и гипотезу Бейтмана-Хорна .

Эвристическая чисел оценка количества простых Софи Жермен меньше n равна ^[16]

2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}

где

C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161

— константа простого числа-близнеца Харди-Литтлвуда . Для n = 10 ⁴, эта оценка предсказывает 156 простых чисел Софи Жермен, что имеет ошибку 20% по сравнению с точным значением 190. Для n = 10 ⁷, оценка предсказывает 50822, что все еще на 10% меньше точного значения 56032. Форма этой оценки принадлежит Г.Х. Харди и Дж. Э. Литтлвуду , которые применили аналогичную оценку к простым числам-близнецам . ^[19]

Последовательность + 1) + 1, ...) , ( p , 2 p + 1, 2(2 p в которой все числа простые, называется цепочкой Каннингема первого рода. Каждый член такой последовательности, кроме последнего, является простым числом Софи Жермен, а каждый член, кроме первого, является безопасным простым числом. Развивая гипотезу о том, что существует бесконечно много простых чисел Софи Жермен, было также высказано предположение, что существуют сколь угодно длинные цепи Каннингема: ^[20] хотя известно, что бесконечные цепи невозможны. ^[21]

Сильные простые числа [ править ]

Простое число q является сильным простым числом, если q + 1 и q − 1 имеют несколько больших (около 500 цифр) простых делителей. Для безопасного простого числа q = 2 p + 1 число q − 1 , естественно, имеет большой простой делитель, а именно p , и поэтому безопасное простое число q соответствует части критериев сильного простого числа. Время работы некоторых методов факторизации числа с q в качестве простого множителя частично зависит от размера простых множителей q - 1 . Это справедливо, например, для метода p −1 .

Приложения [ править ]

Криптография [ править ]

Безопасные простые числа также важны в криптографии из-за их использования в дискретном логарифме методах, основанных на , таких как обмен ключами Диффи-Хеллмана . Если 2 p + 1 — безопасное простое число, мультипликативная группа целых чисел по модулю 2 p + 1 имеет подгруппу большого простого порядка . Обычно желательна именно эта подгруппа простого порядка, и причина использования безопасных простых чисел заключается в том, чтобы модуль был как можно меньшим по отношению к p .

Простое число p = 2 q + 1 называется безопасным простым числом, если q простое. Таким образом, p = 2 q + 1 является безопасным простым числом тогда и только тогда, когда q является простым числом Софи Жермен, поэтому поиск безопасных простых чисел и поиск простых чисел Софи Жермен эквивалентны по вычислительной сложности. Понятие безопасного простого числа можно усилить до сильного простого числа, для которого и p − 1, и p + 1 имеют большие простые множители. Безопасные и сильные простые числа были полезны в качестве факторов секретных ключей в криптосистеме RSA , поскольку они предотвращают взлом системы некоторыми алгоритмами факторизации , такими как алгоритм Полларда p - 1 . Однако при нынешней технологии факторизации преимущество использования безопасных и сильных простых чисел кажется незначительным. ^[22]

Подобные проблемы возникают и в других криптосистемах, включая обмен ключами Диффи-Хеллмана и подобные системы, которые зависят от безопасности задачи дискретного логарифма, а не от факторизации целых чисел. ^[23] По этой причине протоколы генерации ключей для этих методов часто основаны на эффективных алгоритмах генерации сильных простых чисел, которые, в свою очередь, основаны на гипотезе о том, что эти простые числа имеют достаточно высокую плотность. ^[24]

В Sophie Germain Counter Mode было предложено использовать арифметику в конечном поле порядка, равного безопасному простому числу 2. ¹²⁸ + 12451, для устранения недостатков в режиме Галуа/Счетчика с использованием двоичного конечного поля GF(2 ¹²⁸). Однако было показано, что SGCM уязвим для многих из тех же криптографических атак, что и GCM. ^[25]

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

В первой версии теста на простоту AKS гипотеза о простых числах Софи Жермен используется для снижения сложности наихудшего случая с $O(log 12 n)$ равно $O(log 6 н)$ . Показано, что более поздняя версия статьи имеет временную сложность $O(log 7.5 n),$ которое также можно снизить до $O(log 6 n)$ используя гипотезу. ^[26] Было доказано, что более поздние варианты AKS имеют сложность $O(log 6 n)$ без каких-либо догадок и использования простых чисел Софи Жермен.

Генерация псевдослучайных чисел [ править ]

Безопасные простые числа, подчиняющиеся определенным сравнениям, можно использовать для генерации псевдослучайных чисел, используемых в моделировании Монте-Карло .

Точно так же простые числа Софи Жермен могут использоваться для генерации псевдослучайных чисел . Десятичное разложение 1/ q создаст поток из q - 1 псевдослучайных цифр, если q - безопасное простое число простого числа Софи Жермен p , где p соответствует 3, 9 или 11 по модулю 20. ^[27] Таким образом, «подходящими» простыми числами q являются 7, 23, 47, 59, 167, 179 и т. д. ( OEIS : A000353 ) (соответствует p = 3, 11, 23, 29, 83, 89 и т. д.) ( OEIS : А000355 ). Результатом является поток длиной q − 1 цифр (включая ведущие нули). Так, например, использование q = 23 генерирует псевдослучайные цифры 0, 4, 3, 4, 7, 8, 2, 6, 0, 8, 6, 9, 5, 6, 5, 2, 1, 7. , 3, 9, 1, 3. Обратите внимание, что эти цифры не подходят для криптографических целей, поскольку значение каждой может быть получено из ее предшественника в цифровом потоке. ^{[ нужна ссылка ]}

В популярной культуре [ править ]

Простые числа Софи Жермен упоминаются в спектакле « Доказательство». ^[28] и последующий фильм . ^[29]

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

^ В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. подробности см. Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел , Тексты для аспирантов по математике, том. 50, Спрингер, стр. 61–65, ISBN. 9780387950020 .
^ Jump up to: Перейти обратно: ^а ^б Далмедико, Эми (1991). «Софи Жермен» . Научный американец . 265 (6): 116–123. дои : 10.1038/scientificamerican1291-116 . JSTOR 24938838 – через JSTOR.
^ Лаубенбахер, Рейнхард; Пенгелли, Дэвид (1 ноября 2010 г.). Вот что я нашел: «Грандиозный план Софи Жермен по доказательству Великой теоремы Ферма» . История Математики . 37 (4): 641–692. arXiv : 0801.1809 . дои : 10.1016/j.hm.2009.12.002 . ISSN 0315-0860 .
^ Двадцать лучших простых чисел Софи Жермен — с сайта Prime Pages . Проверено 17 мая 2020 г.
^ «Поиск простых чисел Софи Жермен от PrimeGrid» (PDF) . ПраймГрид. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 29 февраля 2016 г.
^ «Поиск простых чисел Софи Жермен от PrimeGrid» (PDF) . ПраймГрид. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 18 апреля 2012 г.
^ База данных Prime: 183027*2^265440-1 . С сайта Prime Pages .
^ База данных Prime: 648621027630345*2^253824-1 .
^ База данных Prime: 620366307356565*2^253824-1.
^ База данных Prime: 1068669447*2^211088-1 с сайта Prime Pages .
^ База данных Prime: 99064503957*2^200008-1 с сайта Prime Pages .
^ База данных Прайм: 607095*2^176311-1 .
^ База данных Prime: 48047305725*2^172403-1 .
^ База данных Prime: 137211941292195*2^171960-1 .
^ Кранц, Стивен Г. (2010), Эпизодическая история математики: математическая культура через решение проблем , Математическая ассоциация Америки, стр. 206, ISBN 9780883857663 .
^ Jump up to: Перейти обратно: ^а ^б ^с Шуп, Виктор (2009), «5.5.5 Простые числа Софи Жермен», Вычислительное введение в теорию чисел и алгебру , Cambridge University Press, стр. 123–124, ISBN 9780521516440 .
^ Рибенбойм, П. (1983), «1093», The Mathematical Intelligencer , 5 (2): 28–34, doi : 10.1007/BF03023623 , MR 0737682 .
^ Дубнер, Харви (1996), «Большие простые числа Софи Жермен», Mathematics of Computing , 65 (213): 393–396, CiteSeerX 10.1.1.106.2395 , doi : 10.1090/S0025-5718-96-00670-9 , MR 1320893 .
^ Рибенбойм, Пауло (1999), Последняя теорема Ферма для любителей , Springer, стр. 141, ISBN 9780387985084 .
^ Уэллс, Дэвид (2011), Простые числа: самые загадочные цифры в математике , John Wiley & Sons, стр. 35, ISBN 9781118045718 , Если гипотеза о сильных простых k -кортежах верна, то цепи Каннингема могут достигать любой длины.
^ Лё, Гюнтер (1989), «Длинные цепочки почти удвоенных простых чисел», Mathematics of Computation , 53 (188): 751–759, doi : 10.1090/S0025-5718-1989-0979939-8 , MR 0979939 .
^ Ривест, Рональд Л.; Сильверман, Роберт Д. (22 ноября 1999 г.), Нужны ли «сильные» простые числа для RSA? (PDF) , заархивировано (PDF) из оригинала 9 октября 2022 г.
^ Чон, Юнг Хи (2006), «Анализ безопасности сильной проблемы Диффи – Хеллмана», 24-я ежегодная международная конференция по теории и приложениям криптографических методов (EUROCRYPT'06), Санкт-Петербург, Россия, 28 мая – 1 июня, 2006, Материалы (PDF) , Конспекты лекций по информатике , том. 4004, Springer-Verlag, стр. 1–11, номер документа : 10.1007/11761679_1 .
^ Гордон, Джон А. (1985), «Сильные простые числа легко найти», Труды EUROCRYPT 84, Семинар по теории и применению криптографических методов, Париж, Франция, 9–11 апреля 1984 г. , Конспекты лекций по информатике , том. 209, Springer-Verlag, стр. 216–223, номер документа : 10.1007/3-540-39757-4_19 .
^ Да, Вун-Ше; Йео, Сзе Лин; Хенг, Суи-Хуай; Хенриксен, Мэтт (2013), «Анализ безопасности GCM для связи», Сети безопасности и связи , 7 (5): 854–864, doi : 10.1002/sec.798 .
^ Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR 3597229 , в архиве (PDF) из оригинала 9 октября 2022 г.
^ Мэтьюз, Роберт А.Дж. (1992), «Максимально периодические обратные величины», Бюллетень Института математики и его приложений , 28 (9–10): 147–148, MR 1192408 .
^ Петерсон, Иварс (21 декабря 2002 г.), «Драма в цифрах: воплощение страсти к математике на сцене» , Science News , doi : 10.2307/4013968 , JSTOR 4013968 , [Жан Э.] Тейлор отметил, что пример Жермена В штрихе, указанном в предварительном тексте, отсутствовал термин «+1». «Когда я впервые пошел посмотреть «Доказательство» и этот момент появился в спектакле, я был рад услышать четко произнесенное слово «плюс один», - говорит Тейлор.
^ Уллман, Дэниел (2006), «Обзор фильма: Доказательство» (PDF) , Уведомления AMS , 53 (3): 340–342, заархивировано (PDF) из оригинала 09 октября 2022 г., есть пара отрывается от реализма в «Доказательстве» , где персонажи говорят так, чтобы принести пользу аудитории, а не так, как математики на самом деле разговаривали бы между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он обращается к Кэтрин так, словно покровительственно обращается к другому математику.

Внешние ссылки [ править ]

Безопасное простое число в PlanetMath .
М. Абрамовиц , И. А. Стегун , изд. (1972). Справочник по математическим функциям . Прикладная математика. Ряд. Том. 55 (Десятое издание). Национальное бюро стандартов. п. 870.

[1] В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. подробности см. Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел , Тексты для аспирантов по математике, том. 50, Спрингер, стр. 61–65, ISBN. 9780387950020 .

[:0-2] Jump up to: Перейти обратно: ^а ^б Далмедико, Эми (1991). «Софи Жермен» . Научный американец . 265 (6): 116–123. дои : 10.1038/scientificamerican1291-116 . JSTOR 24938838 – через JSTOR.

[3] Лаубенбахер, Рейнхард; Пенгелли, Дэвид (1 ноября 2010 г.). Вот что я нашел: «Грандиозный план Софи Жермен по доказательству Великой теоремы Ферма» . История Математики . 37 (4): 641–692. arXiv : 0801.1809 . дои : 10.1016/j.hm.2009.12.002 . ISSN 0315-0860 .

[4] Двадцать лучших простых чисел Софи Жермен — с сайта Prime Pages . Проверено 17 мая 2020 г.

[5] «Поиск простых чисел Софи Жермен от PrimeGrid» (PDF) . ПраймГрид. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 29 февраля 2016 г.

[6] «Поиск простых чисел Софи Жермен от PrimeGrid» (PDF) . ПраймГрид. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 18 апреля 2012 г.

[7] База данных Prime: 183027*2^265440-1 . С сайта Prime Pages .

[8] База данных Prime: 648621027630345*2^253824-1 .

[9] База данных Prime: 620366307356565*2^253824-1.

[10] База данных Prime: 1068669447*2^211088-1 с сайта Prime Pages .

[11] База данных Prime: 99064503957*2^200008-1 с сайта Prime Pages .

[12] База данных Прайм: 607095*2^176311-1 .

[13] База данных Prime: 48047305725*2^172403-1 .

[14] База данных Prime: 137211941292195*2^171960-1 .

[15] Кранц, Стивен Г. (2010), Эпизодическая история математики: математическая культура через решение проблем , Математическая ассоциация Америки, стр. 206, ISBN 9780883857663 .

[shoup-16] Jump up to: Перейти обратно: ^а ^б ^с Шуп, Виктор (2009), «5.5.5 Простые числа Софи Жермен», Вычислительное введение в теорию чисел и алгебру , Cambridge University Press, стр. 123–124, ISBN 9780521516440 .

[17] Рибенбойм, П. (1983), «1093», The Mathematical Intelligencer , 5 (2): 28–34, doi : 10.1007/BF03023623 , MR 0737682 .

[18] Дубнер, Харви (1996), «Большие простые числа Софи Жермен», Mathematics of Computing , 65 (213): 393–396, CiteSeerX 10.1.1.106.2395 , doi : 10.1090/S0025-5718-96-00670-9 , MR 1320893 .

[19] Рибенбойм, Пауло (1999), Последняя теорема Ферма для любителей , Springer, стр. 141, ISBN 9780387985084 .

[20] Уэллс, Дэвид (2011), Простые числа: самые загадочные цифры в математике , John Wiley & Sons, стр. 35, ISBN 9781118045718 , Если гипотеза о сильных простых k -кортежах верна, то цепи Каннингема могут достигать любой длины.

[21] Лё, Гюнтер (1989), «Длинные цепочки почти удвоенных простых чисел», Mathematics of Computation , 53 (188): 751–759, doi : 10.1090/S0025-5718-1989-0979939-8 , MR 0979939 .

[22] Ривест, Рональд Л.; Сильверман, Роберт Д. (22 ноября 1999 г.), Нужны ли «сильные» простые числа для RSA? (PDF) , заархивировано (PDF) из оригинала 9 октября 2022 г.

[23] Чон, Юнг Хи (2006), «Анализ безопасности сильной проблемы Диффи – Хеллмана», 24-я ежегодная международная конференция по теории и приложениям криптографических методов (EUROCRYPT'06), Санкт-Петербург, Россия, 28 мая – 1 июня, 2006, Материалы (PDF) , Конспекты лекций по информатике , том. 4004, Springer-Verlag, стр. 1–11, номер документа : 10.1007/11761679_1 .

[24] Гордон, Джон А. (1985), «Сильные простые числа легко найти», Труды EUROCRYPT 84, Семинар по теории и применению криптографических методов, Париж, Франция, 9–11 апреля 1984 г. , Конспекты лекций по информатике , том. 209, Springer-Verlag, стр. 216–223, номер документа : 10.1007/3-540-39757-4_19 .

[25] Да, Вун-Ше; Йео, Сзе Лин; Хенг, Суи-Хуай; Хенриксен, Мэтт (2013), «Анализ безопасности GCM для связи», Сети безопасности и связи , 7 (5): 854–864, doi : 10.1002/sec.798 .

[26] Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR 3597229 , в архиве (PDF) из оригинала 9 октября 2022 г.

[27] Мэтьюз, Роберт А.Дж. (1992), «Максимально периодические обратные величины», Бюллетень Института математики и его приложений , 28 (9–10): 147–148, MR 1192408 .

[28] Петерсон, Иварс (21 декабря 2002 г.), «Драма в цифрах: воплощение страсти к математике на сцене» , Science News , doi : 10.2307/4013968 , JSTOR 4013968 , [Жан Э.] Тейлор отметил, что пример Жермена В штрихе, указанном в предварительном тексте, отсутствовал термин «+1». «Когда я впервые пошел посмотреть «Доказательство» и этот момент появился в спектакле, я был рад услышать четко произнесенное слово «плюс один», - говорит Тейлор.

[29] Уллман, Дэниел (2006), «Обзор фильма: Доказательство» (PDF) , Уведомления AMS , 53 (3): 340–342, заархивировано (PDF) из оригинала 09 октября 2022 г., есть пара отрывается от реализма в «Доказательстве» , где персонажи говорят так, чтобы принести пользу аудитории, а не так, как математики на самом деле разговаривали бы между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он обращается к Кэтрин так, словно покровительственно обращается к другому математику.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

v т и Классы простых чисел
По формуле	Ферма ( $2 2 н + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Вагстафф $(2 п + 1)/3$ Прот ( $k \cdot2 н + 1$ ) Факториал ( $n! \pm 1$ ) Первобытный ( $p n # \pm 1$ ) Евклид ( $p n # + 1$ ) Пифагорейский ( $4 n + 1$ ) Пьерпон ( $2 м \cdot3 н + 1$ ) Квартан ( $х 4 + и 4$ ) Солинас ( $2 м \pm 2 н \pm 1$ ) Каллен ( $n \cdot2 н + 1$ ) Вудалл ( $n \cdot2 н - 1$ ) Кубинский ( $х 3 - и 3)/(Икс - у$ ) Лейланд ( $x и + и х$ ) Сабит ( $3\cdot2 н - 1$ ) Уильямс ( $(b -1)\cdot b н - 1$ ) Миллс ( $⌊ А 3 н ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман–Шэнкс–Уильямс Перрин
По свойству	Виферих ( пара ) Стена–Солнце–Солнце Вулстенхолм Уилсон Удачливый удачливый Рамануджан Пиллаи Обычный Сильный Стерн Суперсингулярная (эллиптическая кривая) Суперсингулярная (теория самогона) Хороший Супер Хиггс Высокий коэффициент Уникальный
Базово -зависимый	палиндромный Эмирп Репунит $(10 н - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Нежный Первобытный Полный отчет Уникальный Счастливый Себя Смарандаш-Веллин Стробограмматический двугранный тетрадный
Узоры	Твин ( $р, р + 2$ ) Двойная цепь ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Тройка ( $p, p +2 или p +4, p +6$ ) Четверка ( $р, р +2, р +6, р +8$ ) k -кортеж Двоюродный брат ( $п, р + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен/Сейф ( $п, 2п +1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательные p - n, p, p + n$ )
По размеру	Мега (1 000 000+ цифр) Самый крупный известный список
Комплексные числа	Айронстоун прайм Гауссово простое число
Составные числа	Псевдопростой каталанский Эллиптический Эйлер Эйлер – Якоби Ферма Фробениус Лукас Перрин Сомер-Лукас Сильный Число Кармайкла Почти премьер Полупервоклассный Сфеническое число Интерпрайм Пагубный
Связанные темы	Вероятное простое число Промышленный класс Prime Незаконный премьер Формула простых чисел Премьер-разрыв
Первые 60 простых чисел	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
Список простых чисел