8.1. ПРЕОБРАЗОВАНИЯ ФУРЬЕ В ПОЛЕ ГАЛУЛ 241

Доказательство. В любом поле

X" - 1 = (л: - 1) + ] ... 4 X + 1).

По определению элемента а элемент а при всех г является корнем многочлена в левой части. Следовательно, для всех г О по модулю п элемент а/ является корнем последнего многочлена. Но это эквивалентно равенству

S ai = 0, гфО) (mod п)\ /=о

если же г = О по модулю п, то

£ ai = п (mod р),

что всегда отлично от нуля, если п не кратно характеристике р. Комбинируя эти равенства, получаем

/1-1 п-1 n-i ;г-1

и a-i S = Ц Ц аС-")/ = (nmodp)-

i=0 fe=-0 fe=0 7=0

Наконец, q"" - 1 = p - 1 кратно n и поэтому n не кратно p. Следовательно, n =/= О (mod р). Это доказывает теорему. □

Преобразование Фурье обладает многими сильными свойствами, которые переносятся на случай конечных полей. Примером является свойство свертки, доказываемое в приведенной ниже теореме. (Можно доказать и обратную теорему, поменяв местами временную и частотную области).

Теорема 8.1.3 (теорема о свертке). Предположим, что et = figi, i = О, n - l.

Тогда

Е,- = (1М) S Fai-k))Gk, j = 0, п-1,

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

Доказательство. Найдем преобразование Фурье вектора с компонентами = figt:

- (1/n) fa = (1/n) £ GuFar,),y □

Заметим также, что выбор / = О в формуле свертки

1=0 А=0

приводит к формуле типа равенства Парсеваля:

i=-0 /г=0

Теорема 8.1.4 (свойство сдвига), сла {Vj} является

парой преобразования Фурье, то парами преобразований Фурье являются moKOfe

{aVi} и \vac-i))} {ccVj}.

Доказательство получается непосредственной подстановкой. □

Иногда вектор v задается многочленом v (х). С помощью преобразования Фрье в поле Галуа многочлен

V (Х) = t)„ iX«-l -\----+ViX +Vo

может быть преобразован в многочлен

V (х) = + +Vix + V„

который называется спектральным многочленом или ассоциированным с V (х) многочленом. Как устанавливает следующая теорема, свойства спектра тесно связаны с корнями многочленов.

Теорема 8.1.5.

( i) Элемент а является корнем многочлена v (х) тогда и только тогда, когда j-я частотная компонента Vj равна нулю.

(ii) Элемент а~ является корнем многочлена V (х) тогда и только тогда, когда i-я временная компонента Vi рсена нулю.

Доказательство утверждения (i) очевидно, так как

/2-1

t)(aO= S UittV = Vj.

Утверждение (ii) доказывается тем же путем. □

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

8.2. ОГРАНИЧЕНИЯ СОПРЯЖЕННОСТИ И ИДЕМПОТЕНТЫ

Преобразование Фурье длины п над GF (q) принимает значения в расширении поля GF (q"). Если мы начнем с произвольного п-мерного вектора над GF {q") и вычислим обратное преобразование Фурье, то в общем случае не получим временного вектора над GF (q); возможны компоненты из большего поля. Нам надо найти ограничения на спектр, которые бы гарантировали попадание компонент временного вектора в GF (q).

Ограничения такого рода знакомы по полю комплексных чисел. Напомним, что в поле комплексных чисел спектр Р (/) имеет вещественное обратное преобразование Фурье тогда и только тогда, когда Р* (-/) = Р (/). Следующая теорема описывает множество ограничений, которые называются ограничениями (или условиями) сопряженности и устанавливают аналогичное условие для конечного поля.

Теорема 8.2.1. Пусть V есть п-мерный вектор с компонентами из GF ("), где п делит (/" - 1. Тогда обратное преобразование Фурье V является вектором с компонентами из GF (q) тогда и только тогда, когда выполняются следующие равенства:

Vi-Va.m, / = 0, п-1.

Доказательство. По определению

Vj= Т> OLVi, j = 0, nl.

в поле характеристики р для любого целого г справедливо равенство (а Ь)р = аР -\- Ьр". Далее, если Uj - элемент поля GF (q), то гя = V. при всех i. Следовательно,

= ( S av- " = = е = V(,/),.

Обратно, предположим, что V- = Vagi)) ля всех /. Тогда av = I>a""vc, / = О, ..., n - 1.

Пусть k = qj. Так как q взаимно просто с n = q" - I, то, когда / принимает все значения от О до п - 1, число k также принимает все значения от О до п - 1. Следовательно,

Jl аЧ = о!%, = О, ..., п - 1,

4=0 1=0