Лучшие вопросы
Таймлайн
Чат
Перспективы
Безопасное простое число
простое число вида 2p + 1, где p также простое Из Википедии, свободной энциклопедии
Remove ads
Безопасное простое число — простое число вида такое, что — тоже простое; в этом случае является простым Софи Жермен. Первые безопасные простые числа[1]:
- 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, …
Безопасное простое число представимо в виде , то есть .
Remove ads
Криптография
Суммиров вкратце
Перспектива
Имеют большое значение в криптографии; наименование получили благодаря связи с криптографически сильными простыми числами: для безопасного простого числа число имеет большой делитель — , то есть по меньшей мере частично удовлетворяет критерию сильного простого числа. Время работы некоторых методов разложения на множители числа, имеющего в качестве делителя, зависит частично от величины простых делителей , в частности, таков ρ-aлгоритм Полларда. Хотя большинство известных эффективных методов разложения не зависят от величины простых делителей в разложении , свойство считается, тем не менее, важным для шифрования: например, ANSI X9.31 стандарт требует, чтобы сильные простые числа использовалось для RSA.
Другое криптографическое применение безопасных простых чисел — использование в подходах, основанных на дискретных логарифмах, таких как алгоритм Диффи — Хеллмана. Если — безопасное простое, то мультипликативная группа чисел по модулю имеет подгруппу высокого порядка. Обычно эта та подгруппа, которая нужна, и причина использования безопасных простых чисел заключается в том, что модуль мал относительно .
В 2019 году вычислен дискретный логарифм по модулю 240 (795-битного) простого числа RSA-240 + 49204 (первое безопасное простое число больше RSA-240) с использованием алгоритма решета числового поля.
Remove ads
Свойства
Не существует теста для безопасных простых, какие есть для чисел Ферма и чисел Мерсенна. Однако, может быть использован критерий Поклингтона, позволяющий проверить простоту , когда простота установлена.
За исключением 5, нет простых чисел Ферма, являющихся также и безопасными числами. За исключением 7, нет простых чисел Мерсенна, являющихся также и безопасными числами. Если безопасное простое равно 7 по модулю 8, оно является делителем числа Мерсенна, которое соответствует числу Софи Жермен (используемому как степень).
Все элементы последовательности Куннингама за исключением первого являются числами Софи Жермен первого рода, так что все элементы, за исключением первого в цепочке, являются безопасными простыми. Простые числа, заканчивающиеся на 7, то есть вида , если встретятся в таких цепочках, всегда последние, поскольку делится на 5.
Remove ads
Примечания
Литература
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads