Актуальные способы оценки простоты чисел

Раков Николай Борисович,

магистрант Юго-Западного государственного университета.

На современном этапе развития информационного общества применение простых чисел получило широкое распространение в области защиты информации, прежде всего, это вызвано изобретением криптографии с ассиметричным ключом, применяющейся в алгоритмах электронной цифровой подписи, являющихся одним из основных областей, где нашли практическое применение простые числа. На данный момент размер простых чисел используемых при формировании цифровой подписи с использованием эллиптических кривых составляет: в соответствии с ГОСТ Р 34.10-2012 не менее 254 бит (предлагается использование 512 битных ключей), а в ECDSA и стандарте подписи Германии не менее 160 бит [2]. Определить простоту чисел с такой разрядностью, посредством использования простых способов нахождения начального списка простых чисел (Решето Эратосфена, решето Сундарама и решето Аткина) вплоть до некоторого значения, не предоставляется возможным, вследствие низкой скорости работы данных алгоритмов и использования не малых вычислительных ресурсов системы.

Впрочем, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты.

Все существующие алгоритмы тестирования чисел на простоту можно разделить на два класса:

1.                  Вероятностные тесты, позволяют определить простоту числа с некоторой достаточно низкой вероятностью ошибки. Среди них можно выделить следующие, наиболее эффективные тесты простоты:

Тест Ферма – базируется на малой теореме Ферма. Весьма эффективен в обнаружении составных чисел, тем не менее, существуют составные числа, которые ведут себя как простые в малой теореме Ферма, не являясь при этом таковыми. Такие числа называются кармайкловыми.

Вероятность ошибки теста составляет ek, где k – число итераций теста, , где j(n) – Функция Эйлера, n — проверяемое число. Рекомендуется совершать где-то 50 итераций данного теста.

Тест Соловея-Штрассена основан на различии между символами Якоби и Лежандра. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Вероятность ошибки составляет ek, где k – число итераций теста,. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные [4]. Улучшение алгоритма данного теста предложенное Балабановым А.А., Агафоновым А.Ф. и Рыку В.А,. за счет перехода к вычислению величины, являющейся обратной символу Якоби позволяет его ускорить, особенно при работе с числами порядка до 30 бит почти в 1000 раз [1]. Не смотря на это, достоверности теста Соловея-Штрассена не является достаточной, вместо него используется тест Миллера-Рабина.

Тест Миллера-Рабина также, как и предыдущие тесты, является вероятностным тестом, однако реализовывается на ЭВМ более эффективно чем тест Соловея-Штрассена, а также вероятность ошибки у теста Миллера-Рабина гораздо ниже чем у первых двух тестов. Обычно для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций должно быть порядка , где n — проверяемое число. Вероятность ошибки теста на одной итерации составляет , то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма [3]. Теоретическая сложность вычислений всех выше перечисленных тестов оценивается как .

Вероятностные тесты в большинстве случаев применяют в связки с другими тестами (метод простого деления и тест Миллера-Рабина), а также между собой – тест BPSW на простоту чисел был получен благодаря объединению тестов Миллера-Рабина и Лукаса-Селфриджа, к алгоритму которого не было найдено ни одного контрпримера, равно как и не было найдено доказательство его абсолютной точности.

2.                  Детерминированные тесты – дают гарантированно точный ответ простое ли исследуемое число или нет. Не смотря на это не получили широкого практического применения вследствие сложности алгоритмов их реализации и ввиду того что они работают с определенными группами простых чисел (Мерсенна, Прота, Ферма и т. д.), за исключением теста Агравала-Каяла-Саксены, который на данный момент является единственным детерминированным, полиноминальным, универсальным тестом простоты чисел, время работы которого в соответствии с последними улучшениями алгоритма стремится к  [5].

В криптографических алгоритмах одной из важнейших задач является умение быстро отличить простое число от составного. Вероятностные тесты, как ни посмотри, куда больше под стать данному требованию, их скорость не имеет себе равных среди детерминированных тестов, да и случай возникновения ошибки имеет настолько малый процент вероятности, что при проведении подряд нескольких таких тестов стремится к нулю. Тест на простоту Миллера-Рабина, является самым эффективным из вероятностных тестов, он в совокупности с методом «простого деления» зарекомендовал себя как наиболее используемый в криптографии, для тестирования больших случайных чисел на простоту, и самым используемым в алгоритмах формирования цифровой подписи. Тем не менее, в случае дальнейшей доработки и улучшения детерминированного тест Агравала-Каяла-Саксены (увеличения скорости его выполнения), он может занять лидирующую позицию среди тестов проверки простоты чисел.

Литература

1.                  Балабанов А.А., Агафонов А.Ф., Рыку В.А. «Алгоритм быстрой генерации ключей в криптографической системе RSA»— Вестник научно-технического развития, 2009 №7(23). — С. 11.

2.                  ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».

3.                  Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом. – СПб.: БХВ-Петербург, 2005. 288 с.: ил.

4.                  Ниссенбаум О.В., Овсянко А.Г. Криптографические методы защиты информации. Генерация больших простых чисел в криптосистемах с открытым ключом: Учебно-методическое пособие. – Тюмень: Издательство Тюменского государственного университета, 2009. – 41 с.

5.                  H. W. Lenstra jr. and Carl Pomerance, «Primality testing with Gaussian periods», version of April 12, 2011.

Поступила в редакцию 22.04.2013 г.