Сильный прайм
 | Эта статья нуждается в дополнительных цитатах для проверки . ( октябрь 2018 г. ) |
 |
В математике сильное простое число — это простое число с определенными особыми свойствами. Определения сильных простых чисел различаются в криптографии и теории чисел .
Определение в теории чисел [ править ]
В теории чисел сильное простое число — это простое число, которое больше среднего арифметического ближайшего простого числа сверху и снизу (другими словами, оно ближе к следующему простому числу, чем к предыдущему). Или, выражаясь алгебраически, записав последовательность простых чисел в виде ( 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 было слишком большим для правдоподобных вычислительных ресурсов, чтобы криптоаналитик произведения мог факторизовать 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 (и, в свою очередь, число на единицу меньше этого имеет большой простой множитель 1683837087591 611009), 439351292910452432574786963588089477522344332 имеет большой простой делитель 864608136454559457049 (и, в свою очередь, число на единицу меньше этого имеет большой простой делитель 105646155480762397). Даже используя более продвинутые алгоритмы, чем пробное деление , эти числа будет сложно разложить вручную. В современной системе компьютерной алгебры эти числа можно факторизовать почти мгновенно. Криптографически сильный prime должно быть намного больше, чем в этом примере.
Применение сильных простых чисел в криптографии [ править ]
Криптосистемы на основе факторинга [ править ]
Некоторые полагают, что в процессе генерации ключей в криптосистемах RSA модуль n следует выбирать как произведение двух сильных простых чисел. Это делает факторизацию n = pq с использованием алгоритма Полларда p - 1 вычислительно невозможной. По этой причине сильные простые числа требуются стандартом ANSI X9.31 для использования при генерации ключей RSA для цифровых подписей . Однако сильные простые числа не защищают от факторизации по модулю с использованием новых алгоритмов, таких как факторизация эллиптической кривой Lenstra и сита числового поля алгоритм . Учитывая дополнительные затраты на генерацию сильных простых чисел, RSA Security в настоящее время не рекомендует их использовать при генерации ключей . Аналогичный (и более технический) аргумент приводят Ривест и Сильверман. [1]
логарифма основе дискретного на Криптосистемы
показали В 1978 году Стивен Полиг и Мартин Хеллман , что если все факторы p - 1 меньше log с p , то задача решения дискретного логарифма по модулю p находится в P . Следовательно, для криптосистем, основанных на дискретном логарифме, таких как DSA , требуется, чтобы p - 1 имел хотя бы один большой простой делитель.
Разные факты [ править ]
Большое в вычислительном отношении безопасное простое число , скорее всего, будет криптостойким простым числом.
Обратите внимание, что критерием определения того, является ли псевдопростое число сильным псевдопростым числом, являются сравнения со степенями основания, а не неравенство среднего арифметического соседних псевдопростых чисел.
Когда простое число равно среднему значению соседних простых чисел, оно называется сбалансированным простым числом . Когда оно меньше, оно называется слабым простым числом (не путать со слабо простым числом ).
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Рон Ривест и Роберт Сильверман, Нужны ли «сильные» простые числа для RSA? , Архив криптологии ePrint: отчет 2001/007. http://eprint.iacr.org/2001/007
Внешние ссылки [ править ]
- Руководство по криптографии и стандартам
- 3.1.4. Что такое сильные простые числа и необходимы ли они для системы RSA? - Объяснение RSA Lab о сильных и слабых простых числах