Jump to content

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

(Перенаправлено с Софи Жермен Прайм )

В теории чисел 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 или z. В противном случае, . Этот случай, когда 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. 600 необходимы.

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

Ценить Количество цифр Время открытия Первооткрыватель
2618163402417 × 2 1290000 − 1 388342 февраль 2016 г. Доктор Джеймс Скотт Браун в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR. [5]
18543637900515 × 2 666667 − 1 200701 апрель 2012 г. Филипп Блидунг в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR. [6]
183027 × 2 265440 − 1 79911 март 2010 г. Том Ву использует LLR [7]
648621027630345 × 2 253824 − 1 и 620366307356565 × 2 253824 − 1 76424 ноябрь 2009 г. Золтан Харай, Габор Фаркас, Тимеа Чайбок, Янош Каса и Антал Харай [8] [9]
1068669447 × 2 211088 − 1 63553 май 2020 г. Майкл Квок [10]
99064503957 × 2 200008 − 1 60220 апрель 2016 г. С. Урушихата [11]
607095 × 2 176311 − 1 53081 сентябрь 2009 г. Том Ву [12]
48047305725 × 2 172403 − 1 51910 январь 2007 г. Дэвид Андербакке использует TwinGen и LLR [13]
137211941292195 × 2 171960 − 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:

Если 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]

где

константа простого числа-близнеца Харди-Литтлвуда . Для n = 10 4 , эта оценка предсказывает 156 простых чисел Софи Жермен, что имеет ошибку 20% по сравнению с точным значением 190. Для n = 10 7 , оценка предсказывает 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. 128 + 12451, для устранения недостатков в режиме Галуа/Счетчика с использованием двоичного конечного поля GF(2 128 ). Однако было показано, что 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]

  1. ^ В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. подробности см. Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел , Тексты для аспирантов по математике, том. 50, Спрингер, стр. 61–65, ISBN.  9780387950020 .
  2. Перейти обратно: Перейти обратно: а б Далмедико, Эми (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 .
  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), «Большие простые числа Софи Жермен», Математика вычислений , 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 г., есть пара отрывается от реализма в «Доказательстве» , где персонажи говорят так, чтобы принести пользу аудитории, а не так, как математики на самом деле разговаривали бы между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он обращается к Кэтрин так, словно покровительственно обращается к другому математику.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9bb7e9425a5a6fbbe75dfa98f3548661__1721324460
URL1:https://arc.ask3.ru/arc/aa/9b/61/9bb7e9425a5a6fbbe75dfa98f3548661.html
Заголовок, (Title) документа по адресу, URL1:
Safe and Sophie Germain primes - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)