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

Простые числа такого вида названы безопасными ввиду их связи с сильными простыми числами. Простое число q называется строгим простым числом, если q + 1 и q − 1 оба имеют большие простые делители^{[уточнить]}. Для безопасного простого числа q = 2p + 1, число q − 1 , естественно, имеет большой делитель, а именно p, так что q удовлетворяет частично критерию сильного простого числа. Время работы некоторых методов разложения на множители числа, имеющего q в качестве делителя зависит частично от величины простых делителей q − 1. Это верно, например, для ρ-aлгоритм Полларда +1 и −1 методов. Хотя большинство известных эффективных методов разложения не зависят от величины простых делителей в разложении q−1, это считается, тем не менее, важным для шифрования: например, ANSI X9.31 стандарт требует, чтобы сильные простые числа (не безопасное простое) использовалось для RSA.

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

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

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

За исключением 5, нет простых чисел Ферма, являющихся также и безопасными числами. Из того, что простые числа Ферма имеют вид m F = 2ⁿ + 1, следует, что (F − 1)/2 есть степень двух.

За исключением 7, нет простых чисел Мерсенна, являющихся также и безопасными числами. Это следует из упомянутого выше факта, что все безопасные простые числа за исключением 7 имеют вид 6k − 1. Числа Мерсенна имеют вид 2^m − 1, но тогда 2^m − 1 = 6k − 1, откуда следует, что 2^m делится на 6, что невозможно.

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

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

К марту 2010 наибольшее известное безопасное число есть 183027·2²⁶⁵⁴⁴¹−1. Это число, как и соответствующее наибольшее известное число Софи Жермен, было найдено Томом Ву (Tom Wu) 22 марта 2010 с использованием программ sgsieve и LLR[1].

5 февраля 2007 был вычислен модуль дискретного логарифма 160-значного (530-bit) безопасного простого числа. См. рекорды дискретных логарифмов.

• Safe prime Архивная копия от 13 февраля 2013 на Wayback Machine на planetmath.org
• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, (1972): 870