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

Простая пара (p, 2p+1)

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

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

Индивидуальные номера

Первые несколько простых чисел Софи Жермен (меньше 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 ^{600 .}

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

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 (по закону квадратичной взаимности )
• ни 3, ни 12 не являются примитивными корнями q
• единственные безопасные простые числа, которые также являются полными повторяющимися простыми числами по основанию 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 конгруэнтно 3 (по модулю 4) ( OEIS : A002515 , простые числа Люкаса ), то соответствующее ему безопасное простое число 2 p  + 1 ( соответствующее 7 по модулю 8) будет делителем числа Мерсенна  2 ^p  — 1. Исторически этот результат Леонарда Эйлера был первым известным критерием составного числа Мерсенна с простым индексом . ^[17] Его можно использовать для генерации самых больших чисел Мерсенна (с простыми индексами), которые, как известно, являются составными. ^[18]

Бесконечность и плотность

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

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

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

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

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

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

где

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

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

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

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

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

В первой версии статьи по проверке простоты AKS гипотеза о простых числах Софи Жермен используется для снижения сложности наихудшего случая с O(log ¹² n ) до O(log ⁶ n ) . Показано, что более поздняя версия статьи имеет временную сложность O(log ^7,5 n ) , которую также можно снизить до O(log ⁶ n ), используя гипотезу. ^[26] Было доказано, что более поздние варианты AKS имеют сложность O(log ⁶ 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 : A000355 ). Результатом является поток длиной 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]

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

1. В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. подробности см. Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел , Тексты для аспирантов по математике, том. 50, Спрингер, стр. 61–65, ISBN. 9780387950020.
2. Далмедико, Эми (1991). «Софи Жермен». Научный американец . 265 (6): 116–123. doi : 10.1038/scientificamerican1291-116. JSTOR  24938838 – через JSTOR.
3. Лаубенбахер, Рейнхард; Пенгелли, Дэвид (1 ноября 2010 г.). «Voici ce que j'ai trouvé:» Грандиозный план Софи Жермен по доказательству Великой теоремы Ферма». История Математики . 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. База данных Прайм: 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. База данных Прайм: 48047305725*2^172403-1.
14. База данных Prime: 137211941292195*2^171960-1.
15. Кранц, Стивен Г. (2010), Эпизодическая история математики: математическая культура через решение проблем, Математическая ассоциация Америки, стр. 206, ISBN 9780883857663.
16. Шуп, Виктор (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 Computation , 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 для связи», Security and Communication Networks , 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. Мэтьюз, Роберт AJ (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 г., Есть пара отказов от реализма в «Доказательстве» , где персонажи говорят так, чтобы принести пользу аудитории, а не так, как математики на самом деле разговаривали бы между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он обращается к Кэтрин так, словно покровительственно обращается к другому математику.

Внешние ссылки

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