Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математике , сильный премьер является простым числом с некоторыми специальными свойствами. Определения сильных простых чисел различаются в криптографии и теории чисел .

Определение в теории чисел [ править ]

В теории чисел , А сильное простое простое число, которое больше , чем среднее арифметическое от ближайшего простого числа выше и ниже (другими словами, это ближе к следующему , чем в предыдущем расцвете). Или, говоря алгебраически, записав последовательность простых чисел как ( p 1 , p 2 , p 3 , ...) = (2, 3, 5, ...), p n - сильное простое число, если p n >п п - 1 + п п + 1/2. Например, 17 - это седьмое простое число: шестое и восьмое простые числа, 13 и 19, в сумме дают 32, а половина - 16; 17 больше 16, поэтому 17 - сильное простое число.

Первые несколько сильных простых чисел

11 , 17 , 29 , 37 , 41 , 59 , 67 , 71 , 79 , 97 , 101 , 107 , 127 , 137 , 149 , 163 , 179 , 191 , 197 , 223 , 227 , 239 , 251 , 269 , 277 , 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499 (последовательностьA051634 в OEIS ).

В простой паре- близнеце ( p ,  p  + 2) с p  > 5 p всегда является сильным простым числом, так как 3 должно делить p  - 2, которое не может быть простым.


Определение в криптографии [ править ]

В криптографии простое число p называется «сильным», если выполняются следующие условия. [1]

  • p достаточно велико, чтобы быть полезным в криптографии; как правило , это требует р быть слишком большим для правдоподобных вычислительных ресурсов , чтобы позволить криптоаналитик к факторизовать продукты р с другими сильными штрихами.
  • p  - 1 имеет большие простые множители. То есть p  =  a 1 q 1  + 1 для некоторого целого числа a 1 и большого простого числа q 1 .
  • q 1  - 1 имеет большие простые множители. То есть q 1  =  a 2 q 2  + 1 для некоторого целого числа a 2 и большого простого числа q 2 .
  • p  + 1 имеет большие простые множители. То есть p  =  a 3 q 3  - 1 для некоторого целого числа a 3 и большого простого числа q 3 .


Простое число может быть сильным простым числом как в криптографическом, так и в теоретико-числовом смысле. Для иллюстрации 439351292910452432574786963588089477522344331 является сильным простым числом в теоретико-числовом смысле, потому что среднее арифметическое двух его соседних простых чисел на 62 меньше. Без помощи компьютера это число было бы сильным простым числом в криптографическом смысле, потому что 439351292910452432574786963588089477522344330 имеет большой простой множитель 1747822896920092227343 (и, в свою очередь, число, которое на единицу меньше этого числа, имеет большой простой множитель 16838370875916111200947832624353494782943253494783262435349473262435348 864608136454559457049 (и, в свою очередь, число на единицу меньше этого имеет большой простой фактор 105646155480762397). Даже используя алгоритмы более продвинутые, чемпробное деление , эти числа будет трудно факторизовать вручную. В современной системе компьютерной алгебры эти числа можно разложить на множители почти мгновенно. Криптостойкий премьер должен быть значительно больше , чем в этом примере.

Применение сильных простых чисел в криптографии [ править ]

Криптосистемы на основе факторинга [ править ]

Некоторые люди предполагают, что в процессе генерации ключа в криптосистемах RSA модуль n следует выбирать как произведение двух сильных простых чисел. Это делает факторизацию n  =  pq с использованием  алгоритма Полларда p - 1 вычислительно невыполнимой. По этой причине строгие простые числа требуются стандартом ANSI X9.31 для использования при генерации ключей RSA для цифровых подписей . Однако сильные простые числа не защищают от факторизации модуля с использованием новых алгоритмов, таких как факторизация эллиптической кривой Ленстры и Решето числового поля.алгоритм. Учитывая дополнительные затраты на создание сильных простых чисел, RSA Security в настоящее время не рекомендует их использовать при генерации ключей . Аналогичные (и более технические) аргументы также приводятся Ривестом и Сильверманом. [1]

Криптосистемы на основе дискретного логарифма [ править ]

Это показывает Стивеном Полиг и Мартин Хеллман в 1978 году , что если все коэффициенты р  - 1 меньше , чем лог гр р , то задача решения дискретного логарифма по модулю р в Р . Следовательно, для криптосистем, основанных на дискретном логарифме, таких как DSA , требуется, чтобы p  - 1 имело хотя бы один большой простой множитель.

Разные факты [ править ]

Вычислительно большое безопасное простое число , вероятно, будет криптографически стойким простым числом.

Обратите внимание, что критерии для определения того, является ли псевдопростое число сильным псевдопростом, основываются на сравнении степеней основания, а не на основании неравенства со средним арифметическим соседних псевдопростых чисел.

Когда простое число равно среднему значению соседних простых чисел, оно называется сбалансированным простым числом . Когда оно меньше, оно называется слабым простым числом (не путать со слабым простым числом ).

Ссылки [ править ]

  1. ^ a b Рон Ривест и Роберт Сильверман, Нужны ли «сильные» простые числа для RSA? , Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007

Внешние ссылки [ править ]

  • Руководство по криптографии и стандартам
  • 3.1.4 Что такое сильные простые числа и необходимы ли они для системы RSA? - Объяснение RSA Lab о сильных и слабых простых числах