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

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

будет

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

 

4.3. Трехмерное преобразование Фурье в поле

 

Рассмотрим ДПФ длины N=255, ядром которого является примитивный элемент поля .

 

(1)

В этом случае, М=255=3 5 17, =3, = 5, =17, так что n (, , ), где

, ,

 

(2)

 

Произвольный ненулевой элемент поля ) задается как степень примитивного элемента поля: = ,

Согласно (2)

(3)

= (,

, = , = = ,

 

Где приняты обозначения: = , = , =

 

Более того, в силу попарной взаимной простоты модулей , если i (, , ) и j (, , ), то ij (, , ). Таким образом, формулу (4.1) определяющую ДПФ, можно переписать в виде:

(4)

, = , =

Это сразу подсказывает следующий алгоритм вычисления вектора по вектору . Сначала разбиваем координаты вектора на тройки чисел (прификсированных и ) и к каждой из них применяем 3-точечное преобразование с ядром = ; это дает набор из 255 величин

(5)

, = , = .

Затем к этому вектору длины 255 применяется 5-точечное ДПФ с ядром = по правилу: координаты вектора группируются по 5 чисел (по фиксированным и ) и для каждой такой совокупности вычисляется 5-мерный вектор ,

(6)

, = , = .

Наконец, к вектору длины 255 применяется 17-точечное ДПФ с ядром = , приводящее к искомому 255-мерному вектору :

(7)

, = , = .

(8)

Описанный алгоритм вместо умножений при прямом вычислении по формуле (4.1) требует

(9)

умножений, где - число умножений, необходимое для выполнения i-точечного ДПФ, i=3,5,17. Аналогично выписывается и формула для числа сложений (кстати, напомним, что характеристика рассматриваемого поля равна 2, так что вычитание совпадает со сложением)

 

Экспериментально установлено, что переход от одномерной структуры к трехмерной, уменьшает время, требуемое на вычисление ДПФ примерно в 10 раз.

 

Таким образом, переход от ДПФ длины 255 к ДПФ длин 3, 5 и 17, каждое из которых вычисляется 255 раз в цикле, очень существенно понижает вычислительную сложность алгоритма.

 

Следующий наш шаг – полностью избавиться от ДПФ внутри циклов, заменив их на БПФ (быстрое преобразование Фурье) длин 3, 5 и 17, которые основаны как на свойствах поля , так и на свойствах алгоритмов быстрого умножения многочленов, заданных над конечным полем.

 

 

4.4 Быстрое преобразование Фурье БПФ длины 3

3-точечное ДПФ с ядромβдля вектора задается формулой

 

)=

Так как ядро β удовлетворяет тождеству 1+ , то легко проверить непосредственно, что числа могут быть вычислены по правилу:

, которое содержит только одно умножение и 5 сложений (вместо 4 умножений и 6 сложений). Если , .

 

4.5. Быстрое преобразование Фурье длины 5

5-точечное ДПФ с ядром задается равенством

,

непосредственное вычисление по которому требует 16 умножений и 20 сложений. Использование только тождества на ядре (которое в данном случае имеет вид 1+ + + ) дает 9 умножений и 21 сложение. Это достигается, например, следующим образом:

,

Аналогично,

,

,

и, наконец,

 

Дальнейшего уменьшения числа умножений можно добиться за счет перехода к циркулянту и использования полиномиальной свертки (ПС). Приведем необходимые сведения:

 

Утверждение 4.5.1. Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.

Действительно, ()()≜ , где , и

Если умножение происходит вполе F , то , где ,

Следствие 4.5.1. Два многочлена степени m над полем F можно перемножить, выполняя не более умножений чисел в поле F.

Например, для m=3 (с учетом, что charGF()=2) имеем:

(10)

≜ ≜ =

≜

где t≜ (так что при вычислении по модулю многочлена надо делать редукцию по модулю ); согласно утверждению 4.5.1:

≜

≜

≜

Для вычисления , , опять воспользуемся утверждением 4.5.1. Имеем

(11)

Таким образом, для вычисления коэффициентов многочлена необходимо только 9 (вместо 16) умножений. Точные формулы для коэффициентов многочлена (при ) имеют вид:

(12)

 

Для коэффициентов при , согласно (10)-(12)

,

,

,

,

(13)

,

,

,

Если произведение вычисляется в кольце F (так что ), то формулы (10)-(12) принимают вид:

≜ , (10а)

(11a)

, ≜

,

.

Вычисление вектора где а – циркулянт, первая строка которого задается вектором , равносильно вычислению в F произведения , где и .

 

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

 

Утверждение 4.5.2. Для ДПФ простой длины n всегда существует такая перестановка строк и столбцов матрицы Фурье, что она может быть превращена в окаймленный циркулянт.

 

Этот результат принадлежит Рейдеру. Мы подробно проиллюстрируем соответствующий алгоритм в следующем пункте, посвященному БПФ длины 17, а сейчас вернемся к БПФ длины 5.

Прежде всегоизбавимся от единичного окаймления матрицы Фурье:

= )

В столбцах и строках матрицы, стоящей в правой части равенства выполним перестановку .Если выполним такую же перестановку координат у векторов d и его спектра А, получаем

) (14)

 

Циркулярная матрица для БПФ длины 5 получается, если задать нумерацию ненулевого элемента поля GF (5) с образующей 3: 1 (mod5), 3 3 (mod5), 4 (mod5), 2 (mod5): .

 

Этим задача свелась, согласно утверждения 4.5.2, к вычислению многочлена c (x)=d(x)w(x)mod(x -1), где d(x)= или, иначе, циклической свертки с=с

Для вычисления этой циклической свертки длины 4, перепишем формулы (13) в более удобном для организации экономного вычисления виде:

, ;

(15)

Этот алгоритм содержит 9 умножений и 17 сложений. Но если появляются какие-то условия на коэффициенты или ,то число вычислений уменьшается. Например, если =0 или 1, то число умножений равно только 5. В нашем случае и так как - ядро БПФ длины 5, то =1. Учитывая это, из формул (13) – (14) окончательно приходим к следующему алгоритму:

 

, , , , , , , , , , , . (16)

 

Так что алгоритм БПФ длины 5 в поле в нашем случае содержит 5 умножений и 11сложений.

4.6 Быстрое преобразование Фурье длины 17

 

17-точечное ДПФ с ядром задается равенством

(17)

В = .

 

Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдерадля перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17), то имеем:

i	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N=5	5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1

 

Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (17) (соответствующих координат преобразуемого вектора а и спектра А), которая дается второй строкой этой таблицы: единичное окаймление остается на месте, а первая строка циркулянта соответственно имеет вид:

получаем,

, (18)

где , – вектор, полученный из спектра А указанной перестановкой координат, а - вектор столбец, определяемый вторым равенством в (18).

 

Согласно утверждению 4.5.2, задача вычисления (18) эквивалентна задаче вычисления циклической свертки

(19)

Вычислять свертку (19) будем следующим образом. Пусть (так что ) и пусть

Так что

,

,

 

Сначала будем полагать переменную х параметром и найдем циклическую свертку по модулю . Обозначая , согласно равенствам (15) имеем:

 

(20)

 

В поле для элемента выполняется тождества:

; ;

(21)

 

Эти тождества позволяют упростить вычисления величин, входящих в (20). Например,

 

Aлгоритм вычисления R(x)=r(x) для произвольного многочлена содержит 4 умножения и 12 сложений. А именно, воспользуемся равенством (12) и учтем, что в поле согласно второму из тождеств в (20) выполняется равенство ,char =2. Имеем:

 

При табличной реализации умножения необходимо иметь только один массив длины 256 произведений всех элементов поля на элемент . Алгоритм:

(22)

Для остальных 5 умножений вида R(x)=r(x)b(x) число умножений не уменьшается, равно 9, и алгоритм, согласно (12), можно записать в виде:

 

Алгоритм: , , , , , ,

, , , , , , (23) , , , , , , , , .

 

Так как суммы коэффициентов , естественно, вычисляются заранее и вводятся в алгоритм фиксированными константами, то всего имеем 9 умножений и 17 сложений. Для входящих в (20) коэффициентов, величины

соответственно равны:

 

Полное число сложений и умножений для этой реализации равно соответственно 129 и 61. Для полного БПФ по длине 255 имеем 1935 сложений и 1255 умножений.