Безопасное простое число — это простое число вида 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 = 2n + 1, следует, что (F − 1)/2 есть степень двух[англ.].
За исключением 7, нет простых чисел Мерсенна, являющихся также и безопасными числами. Это следует из упомянутого выше факта, что все безопасные простые числа за исключением 7 имеют вид 6k − 1. Числа Мерсенна имеют вид 2m − 1, но тогда 2m − 1 = 6k − 1, откуда следует, что 2m делится на 6, что невозможно.
Все элементы последовательности Куннингама за исключением первого являются числами Софи Жермен первого рода, так что все элементы за исключением первого в цепочке являются безопасными простыми. Простые числа, заканчивающиеся на 7, то есть вида 10n + 7, если встретятся в таких цепочках, всегда последние, поскольку 2(10n + 7) + 1 = 20n + 15 делится на 5.
Если безопасное простое q равно 7 по модулю 8, оно является делителем числа Мерсенна, которое соответствует числу Софи Жермен (используемому как степень).
Рекорды
К марту 2010 наибольшее известное безопасное число есть 183027·2265441−1. Это число, как и соответствующее наибольшее известное число Софи Жермен, было найдено Томом Ву (Tom Wu) 22 марта 2010 с использованием программ sgsieve и LLR[1].
5 февраля 2007 был вычислен модуль дискретного логарифма 160-значного (530-bit) безопасного простого числа. См. рекорды дискретных логарифмов.
Примечания
Ссылки
