Простые числа Сейфа и Софи Жермен - Safe and Sophie Germain primes

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

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

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

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

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

Свойства

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

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

Если безопасный премьер q сравнимо с 7 по модулю 8, то он является делителем Число Мерсенна с соответствующим простым числом Софи Жермен в качестве экспоненты.

Если q > 7 - безопасное простое число, тогда q делит 3^(q−1)/2 - 1. (Это следует из того, что 3 является квадратичный вычет мод q.)

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

За исключением 7, безопасное простое число q имеет вид 6k - 1 или, что то же самое, q ≡ 5 (мод 6) - как есть п > 3. Точно так же, за исключением 5, безопасное простое число. q имеет вид 4k - 1 или, что то же самое, q ≡ 3 (mod 4) - тривиально верно, поскольку (q - 1) / 2 должно оцениваться как нечетное натуральное число. Объединение обеих форм с использованием lcm (6,4) определяем, что безопасное простое число q > 7 также должны иметь вид 12k−1 или, что то же самое, q ≡ 11 (мод. 12). Отсюда следует, что 3 (также 12) является квадратичный вычет мод q для любого безопасного прайма q > 7. (Таким образом, 12 не является первобытный корень любого безопасного прайма q > 7, и единственные безопасные простые числа, которые также простые числа с полным повторением в база 12 5 и 7)

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

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

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

Нерешенная проблема в математике: Есть ли бесконечно много простых чисел Софи Жермен? (больше нерешенных задач по математике)

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

А эвристический оценка количество Софи Жермен простые числа меньше, чем п является^[14]

${\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}$

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

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

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

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

Приложения

Криптография

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

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

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

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

Проверка на первичность

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

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

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

Точно так же простые числа Софи Жермен можно использовать при генерации псевдослучайные числа. Десятичное разложение 1 /q создаст ручей из q - 1 псевдослучайная цифра, если q безопасное простое число простого числа Софи Жермен п, с участием п соответствует 3, 9 или 11 (модификация 20).^[25] Таким образом, «подходящие» простые числа q 7, 23, 47, 59, 167, 179 и т. д. (OEIS: A000353) (соответствующий п = 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. Обратите внимание, что эти цифры не подходят для криптографических целей, поскольку значение каждой может быть получено из его предшественника в цифровом потоке.^{[нужна цитата ]}

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

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

использованная литература

1. В частности, Жермен доказала, что первый случай Великой теоремы Ферма, в котором показатель степени делит одно из оснований, верен для любого простого числа Софи Жермен, и она использовала аналогичные аргументы, чтобы доказать то же самое для всех других простых чисел до 100. Подробнее увидеть Эдвардс, Гарольд М. (2000), Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел, Тексты для выпускников по математике, 50, Springer, стр. 61–65, ISBN  9780387950020.
2. Двадцать лучших простых чисел Софи Жермен - от Prime Pages. Дата обращения 17 мая 2020.
3. База данных Prime: 2618163402417 × 2^1290000 - 1
4. "Софи Жермен Прайм из PrimeGrid" (PDF). PrimeGrid. Получено 18 апреля 2012.
5. База данных Prime: 183027 * 2 ^ 265440-1. От Prime Pages.
6. База данных Prime: 648621027630345 * 2 ^ 253824-1.
7. База данных Prime: 620366307356565 * 2 ^ 253824-1
8. База данных Prime: 1068669447 * 2 ^ 211088-1 От Prime Pages.
9. База данных Prime: 99064503957 * 2 ^ 200008-1 От Prime Pages.
10. База данных Prime: 607095 * 2 ^ 176311-1.
11. База данных Prime: 48047305725 * 2 ^ 172403-1.
12. База данных Prime: 137211941292195 * 2 ^ 171960-1.
13. Кранц, Стивен Г. (2010), Эпизодическая история математики: математическая культура через решение задач, Математическая ассоциация Америки, стр. 206, ISBN  9780883857663.
14. Шуп Виктор (2009), «5.5.5 Простые числа Софи Жермен», Вычислительное введение в теорию чисел и алгебру, Cambridge University Press, стр. 123–124, ISBN  9780521516440.
15. Рибенбойм, П. (1983), "1093", Математический интеллект, 5 (2): 28–34, Дои:10.1007 / BF03023623, Г-Н  0737682.
16. Дубнер, Харви (1996), "Большие простые числа Софи Жермен", Математика вычислений, 65: 393–396, CiteSeerX  10.1.1.106.2395, Дои:10.1090 / S0025-5718-96-00670-9, Г-Н  1320893.
17. Рибенбойм, Пауло (1999), Последняя теорема Ферма для любителей, Springer, стр. 141, ISBN  9780387985084.
18. Уэллс, Дэвид (2011), Простые числа: самые загадочные числа в математике, John Wiley & Sons, стр. 35, ISBN  9781118045718, Если сильный премьер k-гипотеза верна, то цепи Каннингема могут достигать любой длины.
19. Лё, Гюнтер (1989), "Длинные цепочки почти удвоенных простых чисел", Математика вычислений, 53 (188): 751–759, Дои:10.1090 / S0025-5718-1989-0979939-8, Г-Н  0979939.
20. Ривест, Рональд Л .; Сильверман, Роберт Д. (22 ноября 1999 г.), Нужны ли для RSA "сильные" простые числа? (PDF)
21. Чхон, Чон Хи (2006), "Анализ безопасности сильной проблемы Диффи – Хеллмана", 24-я ежегодная международная конференция по теории и применению криптографических методов (EUROCRYPT'06), Санкт-Петербург, Россия, 28 мая - 1 июня 2006 г., Труды (PDF), Конспект лекций по информатике, 4004, Springer-Verlag, стр. 1–11, Дои:10.1007/11761679_1.
22. Гордон, Джон А. (1985), «Сильные простые числа легко найти», Труды EUROCRYPT 84, Семинар по теории и применению криптографических методов, Париж, Франция, 9–11 апреля 1984 г., Конспект лекций по информатике, 209, Springer-Verlag, стр. 216–223, Дои:10.1007/3-540-39757-4_19.
23. Яп, Вун-Ше; Йео, Сзе Линг; Хенг, Суи-Хуай; Хенриксен, Мэтт (2013), «Анализ безопасности GCM для связи», Сети безопасности и связи, Дои:10.1002 / сек.798.
24. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004), "ПРИМЕР в П" (PDF), Анналы математики, 160 (2): 781–793, Дои:10.4007 / анналы.2004.160.781, JSTOR  3597229
25. Мэтьюз, Роберт А. Дж. (1992), "Максимально периодические взаимные значения", Вестник Института математики и его приложений, 28 (9–10): 147–148, Г-Н  1192408.
26. Петерсон, Иварс (21 декабря 2002 г.), «Драма в числах: воплощение страсти к математике», Новости науки, [Джин Э.] Тейлор указала, что в примере с простым числом Жермена, приведенном в предварительном тексте, отсутствует термин «+1». «Когда я впервые пошел смотреть« Доказательство »и этот момент наступил в пьесе, я был счастлив услышать, как четко сказано« плюс один », - говорит Тейлор.
27. Ульман, Даниэль (2006), «Обзор фильма: доказательство» (PDF), Уведомления AMS, 53 (3): 340–342, Есть пара отрывов от реализма в Доказательство где персонажи говорят так, чтобы приносить пользу аудитории, а не так, как математики говорят между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он говорит с Кэтрин в манере, которая будет покровительствовать другому математику.

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

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