Изменения

Есть полином с целыми коэффициентами. Нужно проверить, является ли полином тождественным нулем. Будем считать что полином представлен в виде арифметической схемы. Арифметическая схема похожа на логическую только вместо операций <tex>{\land, \lor, \neg}</tex> она использует операции <tex>{+, -, \times}</tex>. Формально это ориентированный граф в котором есть <tex>n</tex> источников и каждая вершина не являющаяся источником имеет два входа и один выход. Есть одна вершина являющаяся стоком. Каждая внутрення внутренняя вершина помечена одной из трех aрифметических операций. Значение полинома считается путем помещения на источники целых чисел и применения всех операций в порядке заданном графом.

Заметим что исходная задача звучала как проверка двух полиномов не равенство. Мы свели сведем ее к проверке полинома на равенство нулю путем такого преобразования. Пусть : пусть у нас было две арифметические схемы <tex>C, C'</tex> которые нужно проверить на равенство. Мы строим новую схему <tex>D : D(x_1, ..., x_n) = C(x_1, ..., x_n) - C'(x_1, ..., x_n)</tex>. Определим класс <tex>ZEROP</tex> как класс всех схем которые обращаются в ноль на всех возможных входах.Тогда задача будет звучать как проверить принадлежит ли <tex>D</tex> классу <tex>ZEROP</tex>

Если <tex>C \in ZEROP</tex>, то алгорим алгоритм всегда выдаст правильный ответ. Если <tex>C \notin ZEROP</tex> то алгоритм выдаст правильный ответ с вероятностью <tex>\ge \frac{9}{10}</tex>. Однако есть проблема. Числа которые получаются в результате вычисленний могут быть порядка <tex>(10 \cdot 2^m)^{2^m}</tex>. Такие числа требуют экспоненциальное число бит только для представления не говоря уже про операции над ними.

Мы решим эту проблему с помощью вычислений по модулю <tex>k</tex>, где <tex>k</tex> - слуйчайное число <tex>\le 2^{2^m}</tex>. Таким образом вместо вычисления <tex>y = C(x_1, x_2, ..., x_m)</tex>, мы считаем значение <tex>y \ (mod \ k)</tex>. Очевидно что если <tex>y = 0</tex>, то <tex>y \ mod \ k = 0</tex>. Утверждается что если <tex>y \ne 0</tex>, то с вероятностью хотя бы <tex>\\delta = \frac{1}{10m}</tex>, <tex>k</tex> не делится на <tex>y</tex>. Действительно, пусть <tex>y \ne 0</tex> и пусть <tex>S = {p_1, ..., p_l}</tex> {{---}} множество простых делителей <tex>y</tex>. Достаточно показать что с вероятностью <tex>\ge \delta</tex>, <tex>k</tex> будет простым числов <tex>\notin S</tex>. По теореме о простых числах верятность того что <tex>k</tex> будет простым числом <tex>\ge \frac{1}{5m} = 2 \delta</tex>. А так как <tex>y</tex> может иметь максимум <tex>logy log(y) \le 5m2^m</tex> различных простых делителей, вероятность того что <tex>k \in S \le \frac{5m2^m}{2^{2^m}} << \frac{1}{[10m]} = \delta</tex>. Объединяя эти факты получаем что с вероятнотью хотя бы <tex>\delta</tex>, <tex>y</tex> не будет делиться на <tex>k</tex>.