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

Безопасное простое число — это простое число вида 2p + 1, где p также простое (и наоборот, p есть простое число Софи Жермен). Несколько первых безопасных простых чисел:

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, … (A005385)простое число Якобсталя в

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

Приложения

Простые числа такого вида названы безопасными ввиду их связи с сильными простыми числами. Простое число 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.

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