8.11. ЕЩЕ РАЗ О ПРИМЕНЕНИИ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

Мы обещали показать, как применить НОД-алгоритм для построения асимптотически быстрого алгоритма, который восстанавливал бы целое число по его вычетам без предварительной обработки данных. Вспомним, что алгоритм 8.5, использующий предварительную обработку, тратит времени на восстановление числа и по вычетам, взятым по модулям, содержащим по двоичных разрядов. Задача состоит в вычислении где модули, их произведение.

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

Так как произведение всех модулей, отличных от оно должно быть взаимно просто с Если представить в виде — некоторое целое число, то в силу предыдущего будут взаимно просты, т. е. Поэтому, если х и у таковы, что то Следовательно, Но такие числа х и у вычисляются расширенным алгоритмом Евклида.

Хотя процедура НОД была разработана, чтобы вычислять только мы строили процедуру ПНОД так, чтобы она вычисляла матрицу Поэтому простая модификация НОД-алгоритма могла бы вычислять и Тогда можно было бы получить поскольку это левый верхний элемент матрицы Сформулируем результат о времени работы китайского алгоритма без предварительной обработки данных.

Теорема 8.21. В случае целых чисел китайский алгоритм имеет сложность где число используемых модулей, содержащих двоичных разрядов каждый.

Доказательство. В силу анализа, проведенного выше, первый член выражения для сложности соответствует вычислению чисел и выполнению алгоритма 8.5. Второй соответствует вычислению чисел поскольку вычисление чисел х и у можно вести по используя везде -битовые операции.

Следствие. Китайский алгоритм без предварительной обработки данных имеет временную сложность