Сейф и Софи Жермен праймс

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

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

Простые числа Софи Жермен названы в честь французского математика Софи Жермен , которая использовала их в своих исследованиях Великой теоремы Ферма . ^[1] Одна из попыток Жермен доказать Великую теорему Ферма состояла в том, чтобы позволить p быть простым числом вида 8k + 7 и позволить n = p – 1. В этом случае неразрешимо. Однако доказательство Жермен осталось незавершенным. ^{[2] [3]} Благодаря своим попыткам решить Великую теорему Ферма, Жермен разработала результат, теперь известный как теорема Жермен, который гласит, что если p является нечетным простым числом и 2p + 1 также является простым числом, то p должно делить x , y или z. В противном случае, . Этот случай, когда 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.

Для безопасного простого числа каждый квадратичный невычет , за исключением -1 (если невычет ^[a] ), является примитивным корнем . Из этого следует, что для безопасного простого числа наименьший положительный примитивный корень является простым числом. ^[15]

Модульные ограничения

За исключением 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
  • единственные безопасные простые числа, которые также являются полными обратными простыми числами в двенадцатеричной системе счисления, — это 5 и 7
  • q делит 3 ^{( q −1)/2} − 1 и 12 ^{( q −1)/2} − 1, то же самое, что 3 ^{( q −1)/2} ≡ 1 mod q и 12 ^{( q −1)/2} ≡ 1 mod q (согласно критерию Эйлера )
• q -3, q -4, q -9, q -12 являются квадратичными невычетами
  • q -3, q -4, q -9 и, для q > 11, q -12 являются примитивными корнями

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

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

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

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

Бесконечно ли много простых чисел Софи Жермен?

(еще нерешенные проблемы по математике)

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

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

${\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 ⁷ оценка предсказывает 50822, что все еще на 10% отличается от точного значения 56032. Форма этой оценки принадлежит GH Hardy и JE Littlewood , которые применили похожую оценку к простым числам-близнецам . ^[20]

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

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

Простое число 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. Однако при современной технологии факторизации преимущество использования безопасных и сильных простых чисел, по-видимому, незначительно. ^[23]

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

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

Тестирование простоты

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

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

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

Аналогично, простые числа Софи Жермен могут использоваться для генерации псевдослучайных чисел . Десятичное разложение 1/ q произведет поток из q  − 1 псевдослучайных цифр, если q является безопасным простым числом Софи Жермен p , где p сравнимо с 3, 9 или 11 по модулю 20. ^[28] Таким образом, «подходящие» простые числа 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. Обратите внимание, что эти цифры не подходят для криптографических целей, поскольку значение каждой из них может быть получено из ее предшественника в потоке цифр. ^{[ необходима цитата ]}

В популярной культуре

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

Примечания

1. -1 является квадратичным вычетом только тогда, когда безопасное простое число равно 5; для всех других безопасных простых чисел -1 является невычетом

Ссылки

1. В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для каждого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. Подробности см. в Edwards, Harold M. (2000), Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory , Graduate Texts in Mathematics, т. 50, Springer, стр. 61–65, ISBN 9780387950020.
2. Dalmedico, Amy (1991). «Sophie Germain». Scientific American . 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's Sophie Germain Prime Search" (PDF) . PrimeGrid. Архивировано (PDF) из оригинала 2022-10-09 . Получено 29 февраля 2016 .
6. "PrimeGrid's Sophie Germain Prime Search" (PDF) . PrimeGrid. Архивировано (PDF) из оригинала 2022-10-09 . Получено 18 апреля 2012 .
7. База данных Prime: 183027*2^265440-1. Со страниц Prime .
8. База данных Prime: 648621027630345*2^253824-1.
9. База данных Prime: 620366307356565*2^253824-1
10. База данных Prime: 1068669447*2^211088-1 Со страниц Prime .
11. База данных Prime: 99064503957*2^200008-1 Со страниц Prime .
12. База данных Prime: 607095*2^176311-1.
13. База данных Prime: 48047305725*2^172403-1.
14. База данных Prime: 137211941292195*2^171960-1.
15. Рамеш ВП, Макешвари М (16 сентября 2022 г.). «Наименьший примитивный корень любого безопасного простого числа является простым». The American Mathematical Monthly . 129 (10). doi :10.1080/00029890.2022.2115816.
16. Кранц, Стивен Г. (2010), Эпизодическая история математики: математическая культура через решение проблем, Математическая ассоциация Америки, стр. 206, ISBN 9780883857663.
17. Шоуп, Виктор (2009), «5.5.5 Простые числа Софи Жермен», Вычислительное введение в теорию чисел и алгебру, Cambridge University Press, стр. 123–124, ISBN 9780521516440.
18. Рибенбойм, П. (1983), «1093», The Mathematical Intelligencer , 5 (2): 28–34, doi :10.1007/BF03023623, MR  0737682.
19. Dubner, Harvey (1996), «Большие простые числа Софи Жермен», Mathematics of Computation , 65 (213): 393–396, CiteSeerX 10.1.1.106.2395 , doi :10.1090/S0025-5718-96-00670-9, MR  1320893 .
20. Рибенбойм, Пауло (1999), Последняя теорема Ферма для любителей, Springer, стр. 141, ISBN 9780387985084.
21. Уэллс, Дэвид (2011), Простые числа: самые загадочные цифры в математике, John Wiley & Sons, стр. 35, ISBN 9781118045718Если сильная гипотеза о простых k -кортежах верна, то цепи Каннингема могут достигать любой длины.
22. Лёх, Гюнтер (1989), «Длинные цепочки почти удвоенных простых чисел», Математика вычислений , 53 (188): 751–759, doi : 10.1090/S0025-5718-1989-0979939-8 , MR  0979939.
23. Ривест, Рональд Л.; Сильверман, Роберт Д. (22 ноября 1999 г.), Нужны ли «сильные» простые числа для RSA? (PDF) , заархивировано (PDF) из оригинала 2022-10-09
24. Чон, Чон Хи (2006), «Анализ безопасности сильной проблемы Диффи–Хеллмана», 24-я ежегодная международная конференция по теории и применению криптографических методов (EUROCRYPT'06), Санкт-Петербург, Россия, 28 мая – 1 июня 2006 г., Труды (PDF) , Lecture Notes in Computer Science , т. 4004, Springer-Verlag, стр. 1–11, doi : 10.1007/11761679_1.
25. Гордон, Джон А. (1985), «Сильные простые числа легко найти», Труды EUROCRYPT 84, Семинар по теории и применению криптографических методов, Париж, Франция, 9–11 апреля 1984 г. , Конспект лекций по информатике, т. 209, Springer-Verlag, стр. 216–223, doi : 10.1007/3-540-39757-4_19.
26. Яп, Вун-Ше; Йео, Сзе Лин; Хенг, Суи-Хуай; Хенриксен, Мэтт (2013), «Анализ безопасности GCM для связи», Безопасность и коммуникационные сети , 7 (5): 854–864, doi :10.1002/sec.798.
27. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004), «ПРАЙМЫ находятся в P» (PDF) , Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , JSTOR  3597229, в архиве (PDF) из оригинала 9 октября 2022 г.
28. Мэтьюз, Роберт А.Дж. (1992), «Максимально периодические обратные величины», Бюллетень Института математики и ее приложений , 28 (9–10): 147–148, MR  1192408.
29. Петерсон, Иварс (21 декабря 2002 г.), «Драма в числах: вынесение страсти к математике на сцену», Science News , doi :10.2307/4013968, JSTOR  4013968, [Жан Э.] Тейлор указал, что в примере с простым числом Жермен, приведенном в предварительном тексте, отсутствовал термин «+ 1». «Когда я впервые пошел смотреть «Доказательство» и этот момент появился в пьесе, я был рад услышать, как четко произнесено «плюс один», — говорит Тейлор.
30. Ульман, Дэниел (2006), "Обзор фильма: Доказательство" (PDF) , Notices of the AMS , 53 (3): 340–342, архивировано (PDF) из оригинала 2022-10-09, В Доказательстве есть несколько отступлений от реализма , когда персонажи говорят так, чтобы это было выгодно зрителям, а не так, как математики на самом деле говорили бы между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он говорит с Кэтрин так, как это было бы покровительственно по отношению к другому математику.

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

• Безопасное простое число в PlanetMath .
• M. Abramowitz , IA Stegun , ред. (1972). Справочник по математическим функциям. Серия прикладной математики. Т. 55 (Десятое печатное изд.). Национальное бюро стандартов. стр. 870.