Сложность арифметических проблем

§ 1. Сложность проверки простоты числа.

§ 2. Сложность вычислений в модулярной арифметике.

§ 3. Рандомизированная полиномиальная проверка простоты.

§ 4. Недетерминированные проверки простоты.

Самостоятельные занятия

[3], раздел 2, глава 3.

[1] .глава 11.5.

[2], раздел 1.

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

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

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

Найдем двоичное представление (p-1)₂ = a _n -1a _{n -2 …} a₀, или.

P -1 = a ₀ + 2a₁ + 4a ₂ +…+2 ^n-1a _n -1, где каждое a _i есть 0 или 1. Тогда.

_x ^{p — 1} _{= x} a₀ + 2 a₁ + 4 a₂ +…+2 ^{n — 1}a _n -1

есть произведение степеней x ²ⁱ, для которых a_i = 1. Поскольку эти степени вычислены в п. 1 и являются n-битовыми, их произведение можно вычислить за время O (n³). Таким образом, все вычисление x ^p -1 занимает время O (n³).

Рандомизированная полиномиальная проверка простоты.

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

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

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

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

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

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

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

x ^c -1 =1 (mod c),.

в частности для взаимно простых с «c». Эти числа требуют еще одной, более сложной проверки, чтобы убедиться, что они составные.

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

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

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

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

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

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

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

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

Распознавание простых чисел с помощью НМТ сложнее. Можно было угадать, что число (делитель) не является простым, но надо еще проверить, что число p действительно простое, т. е. что существует число x между 1 и p-1, имеющее порядок p-1. Значит, ни одно из чисел x ², x ³,…, x ^p-2 не равно 1. Такая проверка потребует времени не менее 2 ⁿ для 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.

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

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

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

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

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

Построенный недетерминированный алгоритм полиномиален вдоль каждой ветви, кроме шага 3. Рассмотрим рекурсивное вычисление на шаге 3, представив его в виде дерева, в корне которого находится n-битовое число p, сыновьями являются угаданные сомножители числа p-1, под каждым q _i угадываемые сомножители числа q _i -1, которые также надо проверить данной рекурсивной процедурой, и т. д. — до листьев, состоящих не более, чем из 2 бит.

Произведение сыновей меньше самого узла, тем более меньше p.

Время работы, выполняемой для узла, исключая работу в рекурсивных вызовах, оценивается как a^. (log₂ i)⁴, для некоторой константы a. Верхнюю оценку для любого уровня j можно получить суммированием по узлам, и так как соответствующие узлам угаданные сомножители составляют произведение, не большее p-1, то суммы ограничены сверху a (log₂ p)⁴, что не превосходит an⁴.

Итак, время работы на каждом уровне O (n ⁴), не более n, общее время работы на каждой ветке O (n⁵).