Праймы Сейф и Софи Жермен
В теории чисел 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:
- и 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]
где
— константа простого числа-близнеца Харди-Литтлвуда . Для 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]
Ссылки
[ редактировать ]- ^ В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. подробности см. Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел , Тексты для аспирантов по математике, том. 50, Спрингер, стр. 61–65, ISBN. 9780387950020 .
- ↑ Перейти обратно: Перейти обратно: а б Далмедико, Эми (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 .
- ↑ Перейти обратно: Перейти обратно: а б с Шуп, Виктор (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), «Большие простые числа Софи Жермен», Математика вычислений , 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.