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

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

 , 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, \ldots
 За исключением 7, безопасное простое число q имеет форму6k − 1 или, что эквивалентно, q ≡ 5 (mod 6) — гдеp \textgreater 3. Таким же образом, за исключением 5,безопасное простое число q представимо в форме 4k − 1 или,что эквивалентно, q ≡ 3 (mod 4) — тривиальное утверждение,поскольку (q − 1) / 2 должно быть нечетным натуральным числом.Комбинируя обе формы с использованием НОК(6,4) мы получим, чтобезопасное простое число q \textgreater 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, нет простых чисел Ферма, являющихся также ибезопасными числами. Из того, что простые числа Ферма имеют вид mF = 2\textsuperscriptn + 1, следует, что(F − 1)/2 есть .
 За исключением 7, нет простых чисел Мерсенна, являющихся также ибезопасными числами. Это следует из упомянутого выше факта, что всебезопасные простые числа за исключением 7 имеют вид 6k − 1. ЧислаМерсенна имеют вид 2\textsuperscriptm − 1, но тогда2\textsuperscriptm − 1 = 6k − 1, откуда следует, что2\textsuperscriptm делится на 6, что невозможно.
 Все элементы последовательности Куннингама за исключением первогоявляются числами Софи Жермен первого рода, так что все элементы заисключением первого в цепочке являются безопасными простыми. Простыечисла, заканчивающиеся на 7, то есть вида 10n + 7, есливстретятся в таких цепочках, всегда последние, поскольку2(10n + 7) + 1 = 20n + 15 делится на 5.
 Если безопасное простое q равно 7 по модулю 8, оно являетсяделителем числа Мерсенна, которое соответствует числу Софи Жермен(используемому как степень).

Рекорды


 К марту 2010 наибольшее известное безопасное число есть183027·2\textsuperscript265441−1. Это число, как и соответствующеенаибольшее известное число Софи Жермен, было найдено Томом Ву (Tom Wu)22 марта 2010 с использованием программ sgsieve иLLR.1
 5 февраля 2007 был вычислен модуль дискретного логарифма 160-значного(530-bit) безопасного простого числа. См. рекорды дискретных логарифмов.