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

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

безопасное простое число - это простое число вида 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 = 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) безопасного простого числа. См. Рекорды дискретных логарифмов.

Ссылки

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

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


Wikimedia Foundation. 2010.

Нужен реферат?

Полезное


Смотреть что такое "Безопасное простое число" в других словарях:

  • Сильное простое число — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка… …   Википедия

  • 563 (число) — 563 пятьсот шестьдесят три 560 · 561 · 562 · 563 · 564 · 565 · 566 Факторизация: простое Римская запись: DLXIII Двоичное: 1000110011 Восьмеричное: 1063 Шестнадцатеричное: 233 Натуральные числа …   Википедия

  • Металл — (Metal) Определение металла, физические и химические свойства металлов Определение металла, физические и химические свойства металлов, применение металлов Содержание Содержание Определение Нахождение в природе Свойства Характерные свойства… …   Энциклопедия инвестора

  • Кутузов, Михаил Илларионович — князь Михаил Илларионович Кутузов (Голенищев Кутузов Смоленский), 40 й генерал фельдмаршал. Князь Михаил Илларионович Голенищев Кутузов [Голенищевы Кутузовы произошли от выехавшего в Россию к великому князю Александру Невскому из Германии… …   Большая биографическая энциклопедия

  • TLS — (англ. Transport Layer Security  безопасность транспортного уровня), как и его предшественник SSL (англ. Secure Socket Layers  уровень защищенных сокетов)  криптографические протоколы, обеспечивающие защищённую передачу… …   Википедия

  • Олово — (Tin) Металл олово, добыча и месторождения олова, производство и применение металла информация о металле олово, свойства олова, месторождения и добыча олова, производство и применение металла Содержание Определение термина История… …   Энциклопедия инвестора

  • Петр I Алексеевич Великий — первый император всероссийский; родился 30 мая 1672 года от второго брака царя Алексея Михайловича с Натальей Кирилловной Нарышкиной, воспитанницей боярина А. С. Матвеева. Вопреки легендарным рассказам Крекшина, обучение малолетнего П. шло… …   Большая биографическая энциклопедия

  • Семейство полорогие —         (Bovidae)** * * Семейство полорогих, или бычьих самая обширная и разнообразная группа парнокопытных, включает 45 50 современных родов и около 130 видов.         Полорогие животные составляют естественную, ясно очерченную группу. Как ни… …   Жизнь животных

  • Олово — 50 Индий ← Олово → Сурьма …   Википедия

  • Limbo (игра) — У этого термина существуют и другие значения, см. Limbo (значения). Limbo Обложка игры в XBLA, на которой изображён главный герой, идущий через лес …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»