Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории чисел , А простое число р является простым Sophie Germain , если 2 р  +-также простой. Число 2 p  + 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 600 .

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

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

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 по модулю 8, то делитель числа Mersenne с его соответствием Софи Жермен штрихом в качестве показателя степени.

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

Модульные ограничения [ править ]

За исключением 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). Отсюда следует, что 3 (также 12) являетсяквадратичный вычет по модулю q для любого безопасного простого числа q > 7. (Таким образом, 12 не является примитивным корнем любого безопасного простого числа q > 7, и единственными безопасными простыми числами, которые также являются простыми числами с полным повторением в базе 12, являются 5 и 7.)

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

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

Бесконечность и плотность [ править ]

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

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

(больше нерешенных задач по математике)

Он высказал предположение , что существует бесконечно много Sophie Germain простых чисел, но это не было доказано . [14] Несколько других известных гипотез теории чисел обобщают эту гипотезу и гипотезу о простых близнецах ; Они включают в себя предположение Диксона , Шинцель Гипотеза H , и гипотеза Bateman-Хорн .

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

где

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

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

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

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

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

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

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

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

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

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

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

В популярной культуре [ править ]

Простые числа Софи Жермен упоминаются в постановке « Доказательство» [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. ^ a b c Шуп, Виктор (2009), «5.5.5 Простые числа Софи Жермен», Вычислительное введение в теорию чисел и алгебру , Cambridge University Press, стр. 123–124, ISBN 9780521516440.
  15. ^ Ribenboim, P. (1983), "1093", Математическая Интеллидженсер , 5 (2): 28-34, DOI : 10.1007 / BF03023623 , MR 0737682 .
  16. ^ Дабнер, Харви (1996), "Большие простые числа Софи Жермен", Математика вычислений , 65 : 393-396, CiteSeerX 10.1.1.106.2395 , DOI : 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, DOI : 10,1090 / S0025-5718-1989-0979939-8 , MR 0979939 .
  20. ^ Ривест, Рональд Л .; Сильверман, Роберт Д. (22 ноября 1999 г.), Нужны ли «сильные» простые числа для RSA? (PDF)
  21. ^ Cheon, Jung Hee (2006), "Анализ безопасности сильной проблемы Диффи – Хеллмана", 24-я ежегодная международная конференция по теории и приложениям криптографических методов (EUROCRYPT'06), Санкт-Петербург, Россия, 28 мая - 1 июня , 2006, Proceedings (PDF) , Lecture Notes in Computer Science , 4004 , Springer-Verlag, pp. 1–11, doi : 10.1007 / 11761679_1 .
  22. ^ Гордон, Джон А. (1985), «Сильные простые числа легко найти», Труды EUROCRYPT 84, Семинар по теории и применению криптографических методов, Париж, Франция, 9–11 апреля 1984 г. , Лекционные заметки на компьютере Наука, 209 ., Springer-Verlag, стр 216-223, DOI : 10.1007 / 3-540-39757-4_19.
  23. ^ Яп, Вун-Ше; Йео, Сзе Линг; Хенг, Суи-Хуай; Henricksen, Matt (2013), "Анализ безопасности GCM для общения", безопасности и сетей связи , DOI : 10.1002 / sec.798.
  24. ^ Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004), "PRIMES в Р" (PDF) , Анналы математики , 160 (2): 781-793, DOI : 10,4007 / annals.2004.160.781 , JSTOR 3597229  
  25. ^ Мэтьюз, Роберт AJ (1992), «Максимально периодические обратные», Бюллетень Института математики и его приложений , 28 (9–10): 147–148, MR 1192408 .
  26. ↑ Петерсон, Иварс (21 декабря 2002 г.), «Драма в числах: проявление страсти к математике на сцене» , Science News , [Джин Э.] Тейлор указала, что пример простого числа Жермена, приведенный в предварительном тексте, отсутствует. термин «+1». «Когда я впервые пошел смотреть« Доказательство »и этот момент наступил в пьесе, я был счастлив услышать, как четко сказано« плюс один », - говорит Тейлор.
  27. ^ Ульман, Дэниел (2006), «Обзор фильма: Доказательство» (PDF) , Уведомления AMS , 53 (3): 340–342, В « Доказательстве» есть пара отрывов от реализма, когда персонажи говорят таким образом для пользы аудитории, а не для того, чтобы математики разговаривали между собой. Когда Хэл (Гарольд) вспоминает, что такое простое число Жермена, он говорит с Кэтрин в манере, которая будет покровительствовать другому математику.

Внешние ссылки [ править ]

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