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

безопасное простое число - это простое число вида 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 в OEIS

За исключением 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. Это верно, например, для Pollard rho +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) безопасного простого числа. См. Рекорды дискретных логарифмов.

Ссылки

• M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, (1972): 870

Внешние ссылки

• Safe prime на planetmath.org