Безопасное простое число

Безопасное простое число — простое число вида ${\displaystyle 2p+1}$ такое, что ${\displaystyle p}$ — тоже простое; ${\displaystyle p}$ в этом случае является простым Софи Жермен. Первые безопасные простые числа^[1]:

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, …

Безопасное простое число ${\displaystyle q>7}$ представимо в виде ${\displaystyle 12k-1}$, то есть ${\displaystyle q\equiv 11{\pmod {12}}}$.

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

Имеют большое значение в криптографии; наименование получили благодаря связи с криптографически сильными простыми числами: для безопасного простого числа ${\displaystyle q=2p+1}$ число ${\displaystyle q-1}$ имеет большой делитель — ${\displaystyle p}$, то есть по меньшей мере частично удовлетворяет критерию сильного простого числа. Время работы некоторых методов разложения на множители числа, имеющего ${\displaystyle q}$ в качестве делителя, зависит частично от величины простых делителей ${\displaystyle q-1}$, в частности, таков ρ-aлгоритм Полларда. Хотя большинство известных эффективных методов разложения не зависят от величины простых делителей в разложении ${\displaystyle q-1}$, свойство считается, тем не менее, важным для шифрования: например, ANSI X9.31 стандарт требует, чтобы сильные простые числа использовалось для RSA.

Другое криптографическое применение безопасных простых чисел — использование в подходах, основанных на дискретных логарифмах, таких как алгоритм Диффи — Хеллмана. Если ${\displaystyle 2p+1}$ — безопасное простое, то мультипликативная группа чисел по модулю ${\displaystyle 2p+1}$ имеет подгруппу высокого порядка. Обычно эта та подгруппа, которая нужна, и причина использования безопасных простых чисел заключается в том, что модуль мал относительно ${\displaystyle p}$.

В 2019 году вычислен дискретный логарифм по модулю 240 (795-битного) простого числа RSA-240 + 49204 (первое безопасное простое число больше RSA-240) с использованием алгоритма решета числового поля.

Свойства

Не существует теста для безопасных простых, какие есть для чисел Ферма и чисел Мерсенна. Однако, может быть использован критерий Поклингтона, позволяющий проверить простоту ${\displaystyle 2p+1}$, когда простота ${\displaystyle p}$ установлена.

За исключением 5, нет простых чисел Ферма, являющихся также и безопасными числами. За исключением 7, нет простых чисел Мерсенна, являющихся также и безопасными числами. Если безопасное простое ${\displaystyle q}$ равно 7 по модулю 8, оно является делителем числа Мерсенна, которое соответствует числу Софи Жермен (используемому как степень).

Все элементы последовательности Куннингама за исключением первого являются числами Софи Жермен первого рода, так что все элементы, за исключением первого в цепочке, являются безопасными простыми. Простые числа, заканчивающиеся на 7, то есть вида ${\displaystyle 10n+7}$, если встретятся в таких цепочках, всегда последние, поскольку ${\displaystyle 2(10n+7)+1=20n+15}$ делится на 5.