Безопасное простое число — это простое число вида 2 p + 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, … ( )

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

Приложения

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

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

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

Другие свойства

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

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

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

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

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

Рекорды

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

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

Примечания

Ссылки

• от 13 февраля 2013 на Wayback Machine на planetmath.org
• and , eds., Handbook of Mathematical Functions , National Bureau of Standards, Applied Math. Series 55, Tenth Printing, (1972): 870