2.4. Теоретико-числовые преобразования

Базис теоретико-числовых преобразований «надлежит к классу обобшенного которого справедлива теорема о циклической свертке . Пара ТЧП определяется выражениями

Для того чтобы (2.24) удовлетворяло теореме свертки, необходимо выполнение следующих условии:

где сция Эйлер:

Условия (2.25) является достаточными, если определено в поле Бели же (2.24) определено в кольце то необходимо дополнительное условие

Для различных расширений поля Галуа необходимы дополнительные условия существования пары (2 24). Например, для построения в поле необходимо чтобы полином был не приводим в Другие конструкции возникают при условиях неприводимости над полиномов Построенные в этих случаях конструкции ТЧП соответственно эпрецеляются как комплексное Эйзенштейна и ТЧП квадратичных чисел.

В таблице приведены наиболее часто применяемые на лррктике конструкции ТЧП

Основным достоинством ТЧП является отсутствие погрешностей

(см. скан)

вычислений при условии согласования динамического диапазона свертки. Требуемый динамический диапазон обеспечивается соответствующим выбором модуля Для обеспечения достаточной длины необходимо выбрать достаточно большим так, чтобы части свертки были в интервале:

Иногда выбранное таким образом число слишком велико, что не обеспечивает удобства вычислений на ЭВМ. Для преодоления этого ограничения конструкция ТЧП расширяется на кольцо, которое образуется прямой суммой полей Галуа. Такое расширение определяется с помощью следующей теоремы.

Теорема 2.1. Пусть последовательность простых чисел. Положим Пусть кольцо остатков целых чисел по Тогда прямая сумма полей Галуа есть кольцо из элементов, которое изоморфно

Для определения примитивного корня степени из 1 в кольце, определяемом прямой суммой полей Галуа, полезна следующая теорема.

Теорема 2.2. Если примитивные корни степени из 1 в такие, что - единичный элемент в прямой сумме полей Галуа тогда соответствуют элементу который является примитивным корнем степени из 1 в Обратно, если а — корень степени из 1 в то а соответствует элементу так что примитивный корень степени из 1 в

Обратный изоморфизм из задается согласно китайской теореме остатков (КТО)

Перепишем преобразования (2.24) в матричном виде

где

Тогда согласно теоремам 2.1 и изоморфно системе ТЧП вида

Характер матшчной модели алгоритма ТЧП, так же как и ДПФ, единственным ооразом огоецеляется размерностью преобразования и Для перечисленных выше нструкций ТЧП вочможча факторизация как по методу произвольных, так и по методу взаимно-простых множителей в зависимости от допустимых размерностей модулей