Министерство образования и науки Российской Федерации
Министерство образования Саратовской области
Национальный исследовательский Саратовский государственный университет имени Н.Г. Чернышевского
Саратовский областной институт развития образования
Комитет по информатизации Саратовской области
Комитет по образованию администрации муниципального образования «Город Саратов»
Автономная некоммерческая организация «Информационные технологии в образовании»
Автономная некоммерческая организация «Научно-исследовательский центр «Образование. Качество. Отрасль»»
IX Всероссийская (с международным участием) научно-практическая конференция
«Информационные технологии в образовании»
«ИТО-Саратов-2017»
2-3 ноября 2017 года, г. Саратов

Сложность проверки на простоту целого числа

Авторы: Самохина Ксения Алексеевна 1, Гамова Алла Николаевна 2
1 ФГБОУ ВПО "Саратовский государственный университет имени Н.Г. Чернышевского", 2 Саратовский государственный университет им.Н.Г.Чернышевского
Задача, которую поставило наше правительство, - усиление защиты информации, что требует специальных знаний, т.е. предполагает необходимость получения дополнительного образования, в частности в вопросах криптографии, чему и посвящена эта статья. На простых числах основаны важные системы шифрования. NP- полнота языка простых чисел давала бы гарантию безопасности этих систем. Однако последнее невозможно. Рандомизированная проверка простоты гарантирует простоту числа с вероятностью 1-2-k .Еще одна гарантия безопасности в том, что разложение на простые множители требует экспоненциального времени.

Вопросы сложности вычислений лежат в основе криптографических методов. Надежность шифров базируется на уверенности, что дешифрование является труднорешаемой задачей, т.е. отсутствует детерминированный полиномиальный алгоритм, который решает задачу, стоящую перед противником. Но здесь возникает серьезное препятствие в невозможности найти нижние оценки сложности для конкретных задач данного класса. Так безопасность шифров, основанных на RSA-схеме, гарантируется невозможностью разложить целое, равное произведению двух больших простых чисел, за полиномиальное время. Проблема принадлежит классу NP. Некоторой гарантией безопасности была бы принадлежность языка простых чисел или языка составных чисел к NP-полным классам, но равенство NP = co-NPсомнительно. Более того, доказано, что язык простых чисел принадлежит классу RP, так что NP-полнота языка простых чисел приводила бы к равенству RP = NP, что тоже маловероятно.

Что касается вопроса о достаточности предположения P не равно NP при выборе NP - полной задачи для построения на ее основе криптографической схемы, то возникает уже упоминавшаяся проблема асимптотического характера оценки сложности. Любая NP - полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входов. Иными словами, в определении класса NP заложена мера сложности в “худшем случае”. Для стойкости же криптографической схемы необходимо, чтобы задача противника была сложной “почти всюду”. По этой причине в криптографии используются зачастую проблемы, сложные “в среднем”, а не NP-полные.

Модулярная арифметика [1] используется в проверке простоты натурального числа, так что дадим некоторые оценки сложности вычислений по модулю простого числа p. Двоичное представление числа p занимает n битов, т.е. само p близко к 2n, так что любое вычисление, включающее шагов неполиномиально по времени, а занимает не менее O(2n) шагов.

Сложение и умножение по модулю p требует O(n) и O(n2) шагов, соответственно. Возведение в степень методом рекурсивного удвоения также полиномиально. Метод состоит в следующем: вычислить xp-1 (или другую степень до p) можно следующим образом:

1.     Вычисляем (не более степеней) x, x2, x4, пока степень не превысит p-1. Каждое значение является n-битовым числом, которое находится за время O(n2) путем возведения в квадрат предыдущего, поэтому общее время равно O(n3). 

2.     Найдем двоичное представление числа   p-1: (p-1)2 = an-1an-2…a0, или p-1 = a0 +2a1 + 4a2 +…+2n-1an-1,  где  каждое  ai  есть  0  или 1. Тогда xp- 1 =  xa0  + 2a1+ 4a2+…+2^(n-1)an-1  есть  произведение  степеней  x2i,  для  которых  ai = 1.  Поскольку эти степени вычислены в п.1 и являются n-битовыми, их произведение можно вычислить за время O(n3). Таким образом, все вычисление xp-1   занимает время O(n3).

Рандомизированная полиномиальная проверка простоты. [2] Опишем, как применять рандомизированные алгоритмы для поиска больших простых чисел. Покажем, что язык составных чисел принадлежит RP. Метод генерации n-битовых простых чисел состоит в следующем: случайно выбирается n-битовое число и много раз применяется алгоритм Монте-Карло для распознавания составных чисел. Если некоторая проверка показала, что число составное, то число точно не простое. Если все проверки не показывают, что число составное, то вероятность, что оно составное не больше 2-k, где k – число проверок. Т.е. с большой долей уверенности можно сказать, что число простое, и этим обосновать безопасность криптографических операций. 

Идея рандомизированного алгоритма базируется на теореме Ферма: если p – простое число, то для любого x, xp-1 = 1(mod p).  Если p - составное, то существует x, для которого   xp-1 не равно 1(mod p), для не менее половины чисел из интервала [1, p-1].

Рандомизированный алгоритм типа Монте-Карло для составных чисел:

1.     Выбираем случайное число x в интервале [1, p-1].

2.     Вычисляем xp-1 (mod p). Если p n-битовое, вычисление займет время O(n3).

3.     Если xp-1 не равно 1(mod p), то допустим вход x, в противном случае остановимся без допускания.

Если p – простое, то xp-1= 1(mod p), машина Тьюринга (МТ) остановится без допускания. Это одна ветвь работы машины типа Монте-Карло – если вход не принадлежит языку, то он никогда не допускается и при повторном запускании на этом входе.  Для составных чисел “c” не менее половины чисел x из интервала [1, c] удовлетворяют уравнению Ферма: xc-1 = 1 (mod c), в частности, для взаимно простых с “c”. Эти числа требуют еще одной, более сложной проверки, чтобы убедиться, что они составные.

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

Недетерминированная проверка простоты. [2] Здесь будет доказано, что языки простых и составных чисел принадлежат NP пересечение с co-NP. Отсюда следует, что вероятность NP-полноты этих языков ничтожна, иначе NP= co-NP, что совершенно невероятно. 

Теорема.  Множество составных чисел принадлежит NP.

Доказательство. Строим недетерминированный полиномиальный алгоритм распознавания составных чисел:

1.     Имея n-битовое число p, угадываем сомножитель q, состоящий не более, чем из n битов (q не равно 1, p).

2.     Разделим p на q и проверим, что rm (p, q) = 0.  Если это так, то эта часть детерминирована и может быть выполнена за время O(n2) на многоленточной МТ.

Если p - составное, то оно имеет хотя бы один сомножитель q не равное 1, p. Недетерминированная машина Тьюринга (НМТ), угадывающая все возможные числа, содержащие не более n битов, на одной из веток угадает q. Эта ветка ведет к допусканию.

Наоборот, допускание НМТ означает, что найден делитель числа p, отличный от 1 и p. Язык описанной НМТ содержит все составные числа. 

Распознавание простых чисел с помощью НМТ сложнее.  Можно было угадать, что число (делитель) не является простым, но надо еще проверить, что число p действительно простое, т. е.  что существует число x между 1 и p-1, имеющее порядок p-1.  Значит, ни одно из чисел x2, x3xp-2 не равно 1. Такая проверка потребует времени не менее 2n для n-битового числа p. Поэтому используем факт, что для простого p порядок x по mod p делит p-1 (ord (x) | p-1). Таким образом, достаточно для простых делителей q числа p-1 проверить, что x(p-1)/q не равно 1. Число таких проверок – O(n), поэтому все их можно выполнить с помощью полиномиального алгоритма.

Теорема.  Множество простых чисел принадлежит NP.

Доказательство.  Пусть  p  n-битовое  число,  не  равное  1, 2, 3. 

1. Угадываем список сомножителей {q1, q2,…,qk}, двоичные представления которых вместе занимают не более 2n битов, и ни одно из них не имеет более n - 1 битов. На каждой ветви НМТ время работы O(n).

2. Перемножаем все сомножители qi и проверяем, равно ли их произведение p-1. Это потребует времени не более O(n2).

3. Если произведение совпало с p-1, рекурсивно проверим, что каждый сомножитель является простым.

4. Если не все сомножители q являются простыми, угадаем значение x и проверим неравенство x(p-1) / q не равно 1 для каждого q, делящего p-1. Тем самым устанавливается, что порядок x равен p-1, в противном случае порядок x должен делиться на один из множителей (p-1) /q.

Возведение в степень осуществляется описанным выше эффективным алгоритмом, делающим не более умножений (k< n), затратив времени O(n3), так что общее время – O (n4).

Построенный недетерминированный алгоритм полиномиален вдоль каждой ветви, кроме шага 3. Рассмотрим рекурсивное вычисление на шаге 3, представив его в виде дерева, в корне которого находится n-битовое число p, сыновьями являются угаданные сомножители числа p-1, под каждым qi угадываемые сомножители числа qi –1, которые также надо проверить данной рекурсивной процедурой, и т. д. - до листьев, состоящих не более, чем из 2 бит. Произведение сыновей меньше самого узла, тем более меньше p. Время работы, выполняемой для узла, исключая работу в рекурсивных вызовах, оценивается как a(log2 i)4, для некоторой константы a. Верхнюю оценку для любого уровня j можно получить суммированием по узлам, и так как соответствующие узлам угаданные сомножители составляют произведение, не большее p-1, то суммы ограничены сверху a(log2 p)4, что не превосходит an4

Итак, время работы на каждом уровне O(n4), уровней не более n, общее время работы на каждой ветке O(n5). Таким образом, НМТ работает за полиномиальное время.

Список использованных источников
  1. Дж.Хопкрофт, Рад. Мотвани, Дж.Ульман . Введение в теорию автоматов, языков и вычислений. Пер.с англ.-М.: Издательский дом “Вильямс”,2002.
  2. А.Н. Гамова. Сложность вычислений. Учебное пособие для студентов и магистров факультета компьютерных наук и информационных технологий. Издательство Саратовского университета. 2015.- 81с.
Вид представления доклада  Публикация
Ключевые слова  сложность проверки простоты числа, безопасность шифров

В статусе «Черновик» Вы можете производить с тезисами любые действия.

В статусе «Отправлено в Оргкомитет» тезисы проходят проверку в Оргкомитете. Статус «Черновик» может быть возвращен тезисам либо если есть замечания рецензента, либо тезисы превышают требуемый объем, либо по запросу участника.

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

Статус «Опубликован» означает, что издана бумажная версия тезиса и тезис изменить нельзя. В некоторых крайне редких ситуацих участник может договориться с Оргкомитетом о переводе тезисов в статус «Черновик».

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.