с другой стороны, алгоритм 2-точечнон свертки содержит эле-

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

И содержит три умножения. Причина необходимости трех умножений кроется в том, что над полем GF (2) многочлен - I пе разлагается в произведение двух взаимно простых множителей, так как в полях характеристики два -1 - 1, п. следовательно, х + \ {х -\- 1) следовательно, в конструкцию алгоритма в качестве модуля входит многочлен + 1 степени два.

Такая ситуация, когда число умножений в конечном поле больше числа умножений в рациональном поле, .встречается для циклических сверток многих ,длин. Это происходит потому, что несколько простых делителей многочлена х - 1 оказываются равными. С другой стороны, некоторые циклические свертки в полях конечной характеристики требуют меньше умножений, чем свертки тех же длин в рациональном поле. Это происходит потому, что круговые многочлены в конечных полях могут распадаться в произведение простых множителей. Например, над полем рациональных чисел разложение на неприводимые множители многочлена - I имеет вид

л - 1 = (х - 1) (д: + д: + X* + + + X + 1),

а над полем характеристики два это разложение можно продолжить:

1 = 1) (х х + 1) (л + + 1).

Следовательно, согласно выписанной в разд, 3.8 обш,ей границе, оптимальный (относительно числа умножений) алгоритм 7-точечной циклической свертки над полем рациональных чисел должен содержать 12 умножений, а оптимальный алгоритм 7-точечной циклической свертки над полем характеристики два должен,-содержать П умножений. Для первого случая известен хороший с практической точки зрения алгоритм, содержащий 16 умножений, а для второго - хороший алгоритм q 13 умножениями.

Последний алгоритм строится методами главы 3 и задается равенством ,

11111

0 10 0 1

о о 1

1 1 1 I

1110 10 0 1

1 1 1 о

0 10 1110

] I 1

0 0 10 1 I

1 10 0 10 10 0 10 1 1 1 10 0 1

1111

110 0 1110 0 0 0 10 1 0 10)!

1 1 о

10 11 110 1 0 10 0 10 10 0 1 10 0 1110 0 10 0 111 0 0 1110 1

о 1

0 111 10 0 1 0 0 11 1110

0 1110 10 11] 10 0 10 0 0 10 1 о 1 !

о 1 о

I о 1

1 о о

0 10 0 1

10 0 11

Такого сорта улучшения можно найти и в полях большей характеристики. Например, в поле GF (11) разложение на простые множители того же многочлена - 1 имеет вид

-I = {х - \) (х -\- -j- 4х - I) {х - 4х - 5x - 1).

Следовательно, в полях характеристики одиннадцать алгоритм вычисления 7-точечнон циклической свертки содержит 11 умножений. Такнм алгоритмом является

4-1 0-4 1-J 3 О 2

-12 4 2 4-1 4-3-1--1 4-5 0-1 4 2 4-2-I 3 0-5-5 1-1 О ? D I I 4 I О I 1 4 01-12001-120

0 0 1-0-S 2--5 ОЗ -4-4-1 -3 3-2 О 0-1-0 5-1 -

В алгоритм входит только 11 умножений общего вида, но умножений на малые фиксированные константы (±2, ±3, dz4, i=5) он содержит достаточно много. Каждое из таких умножений можно заменить несколькими сложениями, но тогда мы получим большое число сложений. Возможности улучшения этого алгоритма и являются открытой задачей. Ее решение зависит от стоимости сложений и умножений. В достаточно больших расширениях поля GF (П ) умножения обходятся существенно дороже сложений, так что такой алгоритм может оказаться вполне пригодным. В простом поле GF (11), по-видимому, замена умножений сложениями не дает преимуществ.

6.5. Комплексная свертка в суррогатных полях

В последних двух разделах мы видели, как свертку в вещественном поле можно вложить в поле Галуа, где ее удобнее вычислять. Теперь мы займемся этой же задачей для свертки комплексных чисел. В зависимости от наличия в поле GF (р) элемента /-1 здесь имеются два различных случая, которые приводят к совершенно разным действиям. Мы рассмотрим только два класса простых чисел; простые числа Мерсенна и простые числа Ферма. В случае простых чисел Мерсенна поле GF (р) не содержит элемента У~-1; в случае простых чисел Ферма элемент >-I принадлежит полю GF (р). Мы будем рассматривать лишь этн два класса простых чисел, но к любому другому простому числу можно применить один из этих методов.

Мы начнем с простых чисел Мерсенна, р = 2 * - 1, где т - нечетное простое число. Эго поле не содержит элемента у-1. Расширим поле GF (2 - 1) до поля GF {(2 - 1)) подобно тому, как поле вещественных чисел R расширяется до поля комплексных чисел С. Тогда преобразование Фурье в поле GF ((2 -

- l)) можно использовать для вычисления свертки в поле комплексных чисел.

В поле вещественных чисел многочлен х -- 1 не имеет корней. Обозначим через / некоторый новый элемент и присоединим его к полю вещественных чисел, образуя множество С = а + bj\f где а и 6 - вещественные числа, а сложение и умножение задаются правилами

(а -1- bjj + {с + djl = (а -f с] + (6 + d) /,

(а + 6/7 (с + d/J = {ас - bdl + {ad + be) j.

Легко проверить, что это множество образует поле.

Аналогично, в поле Галуа GF (2 - 1) многочлен д: -f- 1 не имеет корней. Расширим это поле, присоединив к нему некоторый обозначаемый через / элемент и сформировав множество GF ((2 -

- 1)) = \а + bj], где а и Ь - произвольные элементы поля OF (2 - 1), Сложение и умножение опять зададим правилами

{а + bj) + {с + dj) {а +с) + {b + d) j,

{а + bj) {с + dj) = {ас- bd) + {ad + be) j,

где операции справа являются операциями в исходном поле i QF (2 - 1). Легко проверить, что такое определение задает поле, содержащее (2 - 1) элементов.

Г1одытожим сказанное в виде двух теорем.

Теорема 6.5.1. Если 2 - 1 - простое число Мерсенна, то поле. GF {2 - 1) не содержит среди своих элементов квадратного корня из -1; следовательно, многочлен х + \ не имеет в этом поле корней.

Доказательство отложим до конца раздела.

Теорема 6.5.2. Относительно определенных выше операций сложения и умножения множество GF ((2 - 1)) образует поле.

Доказательство. Утверждение вытекает непосредственно из того, что многочлен х -- 1 прост. □

Теперь рассмотрим преобразование Фурье в поле GF ((2 - - 1)). Длина преобразования равна (2 - If - 1 или делит это число. Так как имеет место разложение (2 - I) - 1 = = 2 +1 (2 - 1), то возможной длиной преобразования Фурье в поле GF ((2 - I)) является 2 +, и тогда это преобразование можно вычислять с помощью БПФ-алгоритма Кули-Тьюки по основанию два. Другие возможные длины преобразования Фурье задаются делителями числа 2 --1.

Выберем, например, т = 17. Тогда (2, - 1) - 1 = 2 X X 3-5-17-257. В качестве длины преобразования можно взять любую степень двойки вплоть до 2 , а большие длины получаются присоединением остальных делителей. Пусть п делит 2 и пусть

= S к = 0, ... , п-1,

где ю -элемент поля GF {{2 - \)) порядка п. {В табл. 6.1 приведены найденные на ЭВМ соответствующие элементы а.) Так как п равно некоторой степени двух, то для вычисления преобразования Фурье можно воспользоваться БПФ-алгоритмом Кули- Тьюки по основанию два.

Возможности выбора длины преобразования Фурье в поле GF ((2 - 1)) существенно шире, чем в поле GF (2 - 1); в частности, это относится к длинам, равным степени двойки. Поэтому для вычисления циклической свертки в (2 - I) можно перейти в поле GF ((2 - 1)*), рассматривая исходную свертку как свертку целых чисел поля GF {{2 ~ 1)).

В случае, когда р является простым числом Ферма, у -1 является элементом простого поля, и построение расширения GF (р) с операцией умножения, аналогичной умножению в поле комплексных чисел, невозможно. Действительно, для р = 2 -f 1, где т равно степени двух, возведением в квадрат легко убедиться, что

У -1 = г * (2 - 1). Для вычисления свертки s (х) = = g{x)d (х), где

g (X) = gn (X) + jg, (X) и d (X) = dn (X) + id, (X),

приходится вычислять четыре свертки gj, (х) (х), gn (х) d, (х), gy (х) dj, (х) и g, (х) dj (х) и пользоваться равенствами

Sh (х) = g (х) (х) - gr (х) dj (х),

S/ (х:) = gH () dr (х) + g, (X) da (х). Лучшая процедура, содержащая вдвое меньше умножений, основана на определении в кольце GF (р) [xlx -1) многочленов

а () = 4- fen (X) - r gj (X)) (da (X) - 2 = dj (X)),

6 W = 4- + 2° (W + 2 dT (X)),

для вычисления которых надо сделать только две свертки. Все вычисления проводятся в кольце GF (р) [хУХх - !), и свертка S (х) вычисляется по правилу

SH>=(a(x)-f6(x)),

S, (х) = 2 / {а (X) - Ь (х))\

Для завершения раздела нам осталось провести доказательство теоремы 6.5.1. Оно достаточно длинно и опирается на понятие квадратичного вычета. Те элементы простого поля GF (р), для которых в этом поле существуют квадратные корни, называются квадратичными вычетами (поскольку по модулю р они равны квадратам своих квадратных корней). Если р нечетно, то ровно поло вина элементов поля GF (р) имени квадратные корни. Чтобы это показать, заметим сначала, что каждая четная степень примитивного элемента а имеет квадратный корень. С другой стороны, каждый элемент, равный квадратному корню, может быть записан 3 виде а для некоторого i, так что его квадрат равен аК , где двойные скобки в показателе степени использованы для обозначения того, что вычисления проводятся по модулю р - 1, так как мультипликативная группа поля является циклической порядка р - 1. Но число р - 1 четно, и, следовательно, ((2i)) также четно. Таким образом, только четные степени элемента а могут иметь квадратный корень.

Теорема 6.5.3. Для нечетных р в поле GF (р) элемент г является квадратичным вычетом тогда и только тогда, когда

Доказательство, Предположим, что тр-мф 1. Тогда т не может существовать в данном поле, так как в противном случае