Войти
В теории чисел простое число p равно Простое число Софи Жермен, если 2p + 1 также простое число. Число 2p + 1, связанное с простым числом Софи Жермен, называется безопасным простым числом . Например, 11 - простое число Софи Жермен, а 2 × 11 + 1 = 23 - соответствующее ему безопасное простое число. Простые числа Софи Жермен названы в честь французского математика Софи Жермен, которая использовала их в своих исследованиях Великой теоремы Ферма. Простые числа Софи Жермен и безопасные простые числа применяются в криптографии с открытым ключом и тестировании на простоту. Было высказано предположение, что существует бесконечно много простых чисел Софи Жермен, но это остается недоказанным.
Первые несколько простых чисел Софи Жермен (меньше 1000):
Следовательно, первые несколько безопасных простых чисел:
В криптографии требуются гораздо более крупные простые числа Софи Жермен, например 1846,389,521,368 + 11.
Два проекта распределенных вычислений, PrimeGrid и Twin Prime Search, включают поиск больших простых чисел Софи Жермен. Наибольшие известные простые числа Софи Жермен по состоянию на май 2020 года приведены в следующей таблице.
| Значение | Количество цифр | Время обнаружения | Discoverer |
|---|---|---|---|
| 2618163402417 × 2 - 1 | 388342 | Февраль 2016 г. | PrimeGrid |
| 18543637900515 × 2 - 1 | 200701 | апрель 2012 г. | Филипп Блидунг в распределенном поиске PrimeGrid с использованием программ TwinGen и LLR |
| 183027 × 2-1 | 79911 | март 2010 | Том Ву использует LLR |
| 648621027630345 × 2 - 1 и 620366307356565 × 2 - 1 | 76424 | ноябрь 2009 г. | Золтан Ярай, Габор Фаркас, Тимеа Чайбок, Янош Каса и Антал Джараи |
| 1068669447 × 2 - 1 | 63553 | Май 2020 г. | Майкл Квок |
| 99064503957 × 2 - 1 | 60220 | апрель 2016 | С. Урушихата |
| 607095 × 2 - 1 | 53081 | сентябрь 2009 г. | Том Ву |
| 48047305725 × 2 - 1 | 51910 | Январь 2007 г. | Дэвид Андербакке с использованием TwinGen и LLR |
| 137211941292195 × 2-1 | 51780 | Май 2006 г. | Járai et al. |
2 декабря 2019 г. Фабрис Будо, Пьерк Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пол Циммерманн объявили о вычислении дискретного логарифма по модулю 240-значного (795-битного) простого числа RSA-240 + 49204 ( первое безопасное простое число выше RSA-240) с использованием алгоритма сита числового поля ; см. Записи дискретного логарифма.
Не существует специального теста на простоту для безопасных простых чисел, как для простых чисел Ферма и простых чисел Мерсенна. Однако критерий Поклингтона можно использовать для доказательства простоты 2p + 1, если доказана простота p.
Так же, как каждый член, кроме последнего в цепочке Каннингема первого вида, является простым числом Софи Жермен, поэтому каждый член такой цепочки, кроме первого, является безопасным простым числом. Безопасные простые числа, оканчивающиеся на 7, т.е. имеющие форму 10n + 7, являются последними членами в таких цепочках, когда они встречаются, поскольку 2 (10n + 7) + 1 = 20n + 15 делится на 5.
Если безопасное простое число q сравнимо с 7 по модулю 8, то оно является делителем числа Мерсенна с соответствующим ему простым числом Софи Жермен в качестве экспоненты.
Если q>7 - безопасное простое число, то q делит 3 - 1. (Это следует из того факта, что 3 является квадратичным остатком mod q.)
За исключением 7, безопасное простое число q имеет форму 6k - 1 или, что то же самое, q ≡ 5 (mod 6) - как и p>3. Точно так же, за исключением 5, безопасное простое число q имеет вид 4k - 1 или, что то же самое, q ≡ 3 (mod 4) - тривиально верно, поскольку (q - 1) / 2 должно вычисляться как нечетное натуральное число. номер. Комбинируя обе формы с помощью lcm (6,4), мы определяем, что безопасное простое число q>7 также должно иметь форму 12k − 1 или, что то же самое, q ≡ 11 (mod 12). Отсюда следует, что 3 (также 12) является квадратичным вычетом по модулю q для любого безопасного простого числа q>7. (Таким образом, 12 не является примитивным корнем любого безопасного простого числа q>7, и единственными безопасными простыми числами, которые также являются простыми числами с полным повторением в основании 12, являются 5 и 7)
Если p - простое число Софи Жермен больше 3, то p должно быть конгруэнтно 2 по модулю 3. В противном случае оно было бы конгруэнтно 1 по модулю 3 и 2p + 1 было бы конгруэнтно 3 по модулю 3, что невозможно для простого числа. Подобные ограничения сохраняются для больших модулей простых чисел и являются основой для выбора «поправочного коэффициента» 2C в оценке Харди – Литтлвуда плотности простых чисел Софи Жермен.
Если простое число Софи Жермен p равно конгруэнтно к 3 (mod 4) (OEIS : A002515, простые числа Люкаса), то соответствующее ему безопасное простое число 2p + 1 будет делителем Число Мерсенна 2 - 1. Исторически этот результат Леонарда Эйлера был первым известным критерием составного числа Мерсенна с простым индексом. Его можно использовать для генерации наибольших чисел Мерсенна (с простыми индексами), которые известны как составные.
 | Нерешенная математическая проблема :. Существует ли бесконечно много простых чисел Софи Жермен? (больше нерешенных задач в математике) |
высказано предположение, что существует бесконечно простых чисел Софи Жермен, но это не было доказано. Несколько других известных гипотез в теории чисел обобщают это и гипотезу о простых близнецах ; они включают гипотезу Диксона, гипотезу Шинцеля H и гипотезу Бейтмана – Хорна.
A эвристическую оценку для числа Софи Простое число Жермена меньше n равно
где
- константа двойного простого числа Харди – Литтлвуда. Для n = 10 эта оценка предсказывает ошибку 156 простых чисел Софи Жермен по сравнению с точным значением 190. Для n = 10 оценка предсказывает 50822, что на 10% меньше точного значения 56032. Форма этой оценки обусловлена GH Hardy a nd Дж. Э. Литтлвуд, который применил аналогичную оценку к простым числам-близнецам.
Последовательность {p, 2p + 1, 2 (2p + 1) + 1,...}, в которой все числа равны простое число называется цепочкой Каннингема первого рода. Каждый член такой последовательности, кроме последнего, является простым числом Софи Жермен, и каждый член, кроме первого, является безопасным простым числом. Расширяя гипотезу о том, что существует бесконечно много простых чисел Софи Жермен, также было высказано предположение, что существуют сколь угодно длинные цепочки Каннингема, хотя известно, что бесконечные цепочки невозможны.
Простое число q является сильным простым числом, если q + 1 и q - 1 имеют несколько больших (около 500 цифр) простых множителей. Для безопасного простого числа q = 2p + 1 число q - 1, естественно, имеет большой простой множитель, а именно p, и поэтому безопасное простое число q удовлетворяет части критериев сильного простого числа. Время работы некоторых методов разложения числа с q в качестве простого множителя частично зависит от размера простых множителей q - 1. Это верно, например, для p− 1 метод.
Безопасные простые числа также важны в криптографии из-за их использования в методах на основе дискретного логарифма, таких как ключ Диффи – Хеллмана обмен. Если 2p + 1 - безопасное простое число, мультипликативная группа чисел по модулю 2p + 1 имеет подгруппу большого простого порядка. Обычно желательна именно эта подгруппа простого порядка, и причина использования безопасных простых чисел состоит в том, чтобы модуль был как можно меньше по сравнению с p.
Простое число p = 2q + 1 называется безопасным простым числом, если q простое. Таким образом, p = 2q + 1 является безопасным простым числом тогда и только тогда, когда q является простым числом Софи Жермен, поэтому поиск безопасных простых чисел и поиск простых чисел Софи Жермен эквивалентны по сложности вычислений. Понятие безопасного простого числа можно усилить до сильного простого числа, для которого и p - 1, и p + 1 имеют большие простые множители. Безопасные и сильные простые числа были полезны в качестве факторов секретных ключей в криптосистеме RSA, поскольку они предотвращают взлом системы некоторыми алгоритмами факторизации, такими как алгоритм p - 1 Полларда.. Однако с нынешней технологией факторизации преимущество использования безопасных и сильных простых чисел оказывается незначительным.
Подобные проблемы применяются и в других криптосистемах, включая обмен ключами Диффи – Хеллмана и т.п. системы, которые зависят от безопасности проблемы дискретного журнала , а не от целочисленной факторизации. По этой причине протоколы генерации ключей для этих методов часто полагаются на эффективные алгоритмы генерации сильных простых чисел, которые, в свою очередь, основываются на предположении, что эти простые числа имеют достаточно высокую плотность.
В режиме счетчика Софи Жермен было предложено использовать арифметику в конечном поле порядка, равном простому числу Софи Жермен 2 + 12451, для устранения недостатков в Режим Галуа / счетчика с использованием двоичного конечное поле GF (2). Однако было показано, что SGCM уязвим для многих из тех же криптографических атак, что и GCM.
В первой версии статьи AKS primality test, гипотеза о простых числах Софи Жермен используется для понижения сложности наихудшего случая с O (logn) до O (logn). Показано, что более поздняя версия статьи имеет временную сложность O (logn), которая также может быть понижена до O (logn) с помощью гипотезы. Было доказано, что более поздние варианты AKS имеют сложность O (logn) без каких-либо предположений или использования простых чисел Софи Жермен.
Безопасные простые числа, подчиняющиеся определенным сравнениям, могут использоваться для генерации псевдослучайных чисел для использования в моделировании Монте-Карло.
Аналогично, Софи Простые числа Жермена могут использоваться при генерации псевдослучайных чисел. Десятичное разложение 1 / q даст поток из q - 1 псевдослучайных цифр, если q - безопасное простое число простого числа p Софи Жермен, причем p конгруэнтно 3, 9 или 11 ( мод 20). Таким образом, "подходящими" простыми числами 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. Обратите внимание, что эти цифры не подходят для криптографических целей, поскольку значение каждой может быть получено из своего предшественника в цифровом потоке.
Простые числа Софи Жермен упоминаются в постановке Доказательство и последующем фильме.
