4.2. Китайская теорема об остатках

Рассмотрим более детально формулу (4.1), задающую ДПФ над полем . Например, для того, чтобы вычислить ДПФ над полем вектора длины, требуется умножений в поле. Как известно, умножение является одной из наиболее затратных по времени операций, т.е. алгоритм ДПФ имеет сложность порядка O(. Известные алгоритмы многомерного преобразования Фурье, а так же БПФ (быстрое преобразование Фурье) позволяют снизить эту цифру до N*logN умножений. Данные алгоритмы основаны на следующей китайской теореме об остатках.

Теорема 4.2.1. (Китайская теорема об остатках, единственность)

Для заданного множества целых положительных попарно взаимно-простых чисели множества неотрицательных целых чисел

при, система сравнений

имеет не более одного решенияc в интервале

Теорема 4.2.2. (Китайская теорема об остатках, существование)

Пусть –произведение целых положительных попарно взаимно-простых положительных чисел, пусть и пусть удовлетворяют равенству , тогда единственным решением системы сравнений

будет

Эта теорема позволяет каждое число n,0≤n<M однозначно задать системой остатков по модулям , i=1,k.