ДОЛЖНО бы было выполняться равенство гУ =1, которое не выполняется.

Предположим, что г>~>>/= 1, и пусть а - примитивный элемент поля GF (р). Очевидно, что все четные степени элемента а являюггся квадратичными вычетами, а все нечетные степени элемента а квадратичными вычетами не являются. Надо только показать, что г равно четной степени элемента а. Допустим противное; г = а +; тогда, так как порядок элемента а равен р - I, имеем

Zi+lVP-D/ (l-I) (l-l)/2 (P-I)/2

Таким образом, из равенства г->2= I вытекает, что г равно четной степени элемента а и, следовательно, является квадратичным вычетом. □

Теперь у нас уже все готово для доказательства теоремы 6.5.1.

Теорема 6.5.1. Элемент -1 поля GF (2 - 1), где 2 - 1 -

простое число Мерсенна, не имеет в этом поле квадратного корня. Следовательно, многочлен + \ не u.tieem в этом поле корней.

Доказательство. Предположим, что -1 имеет квадратный корень, равный г. Тогда = -1 и, согласно теореме 6.5.3, г - = = I. Так как р = 2 - 1, то г°~ = 1 или г- = 1.

Но = -1 и m - 1 четно. Следовательно, = 1 и г = 1. Но тогда г не равно -1. Полученное противоречие показывает, что в данном поле не существует квадратного корня из -1.

□

6.6. Преобразования в числовом кольце

Если поле F содержит элемент порядка я, то в этом поле существует преобразорание Фурье д.пины п. Если преобразование Фурье существует, то оно обладает всеми элементарными свойствами такого преобразования.

Часто возможно также определить преобразование в кольце, но при этом ситуация не является столь простой. В настоящем разделе рассматриваются преобразования в кольце Z/(?) целых чисел по модулю q. Если q - простое число, то zliq) является полем, и, как мы уже видели, в нем существует преобразование . Фурье со всеми его основными свойствами. Поэтому надо рассью-треть только случай составного числа q. Как мы увидим, даже для составных q можно дать осмысленное определение преобразования , Фурье. Однако структура этих преобразований представляет со-бой точную копию преобразований Фурье для простых делителей числа q, так что переход к составному q прибавляет мало возыож-1 ностей.

Мы хотим определить в целочисленном кольце преобразование

п~.\

= Е м о А = 0.....

вектора v над кольцом zKq) так, чтобы существовало обратное преобразование

i = 0.....л - 1,

и была справедлива теорема о свертке. Для того, чтобы такое определение преобразования Фурье было возможным, необходимо выполнение двух условий; (1) должен существовать элемент ш порядка п; (2) элемент п в кольце zl{q) должен быть обратимым. Нужна, конечно, еще и обратимость элемента ш, но из условия = 1 автоматически следует, что ш = <й ~Ч Итак, надо определить те значения п, для которых существует элемент m порядка п. Начнем с простейшего случая q, равного степени простого нечетного числа р, q = р *. Кольцо Z/ip ) не образует поля, так как его умножением является умножение по модулю р . Согласно теореме 5.1.8, в этом кольце имеются элементы порядка (р - 1) р -1, и согласно теореме 5.1.5 (теореме Эйлера), порядок каждого взаимно простого р * элемента делит (р - I) р -. Согласно этому условию, для каждого делителя п числа (р- 1) р -! можно выбрать элемент m порядка п. Однако теорема 5.2.2 утверждает, что число п обратимо тогда и только тогда, когда пир взаимно просты. Следовательно, п не может делиться на р. Таким образом, в качестве ш можно выбрать только элементы, порядок которых п делит р - 1. Следующая теорема показывает, что для каждого такого п существует соответствующее преобразование Фурье. Однако длины такого преобразования в гЛр ) в точности совпадают о теми длинами, которые допустимы для преобразования Фурье в поле GF (р). Изменения касаются только разрядности используемых чисел, которая уве.1ичивается примерно с loga р до m loga p. Но обычно разрядность является достаточно большой и для преобразований в поле GF (р). что еще больше уменьшает преимущества перехода к z/ip ).

Ситуация для произвольного q аналогична и описывается следующей тоеремой.

Теорема 6.6.1. Обратимое преобразование Фурье длины п над кольцом zl(q) существует тогда и только тогда, когда п делит Р - 1 для всех простых делителей р числа q.

Доказательство. Сначала мы приведем доказательство для случая, когда q равно степени простого числа. Затем используем

iiL 1л. О. оычисления в суррогатныл полм

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

Проще всего доказывается обратная часть теоремы. Длина л преобразования обратима, только если п л q взаимно просты, так как

firj- = 1 +

и, следовательно, любой делитель чисел п п q должен быть и делителем единицы, так что он должен равняться единице. Далее, теорема 5.1.5 утверждает, что если порядок п элемента и взаимно прост с q, то он делит ф {q) = {р - 1) р -Следовательно, преобразование Фурье в кольце /(р ) существует только на длинах п, которые делят- р - 1.

Теперь докажем прямое утверждение теоремы. Полагать р равным 2 смысла нет, так как тогда л равно 1 и утверждение тривиально. Следовательно, р - нечетное простое число и согласно теореме 5.1.8 существует элемент я порядка (р - 1) р -. Для любого делителя Ь числа р - 1 положим ю = sf ; тогда порядок элемента ш равен (р - l)/ft. Таким образом, для любого делителя Ъ числа р - 1 имеется элемент ю этого порядка, и остается доказать существование обратного преобразования Фурье. Для этого запищем

А=0 А=0 (=0

Если i = i, то сумма по к равна п. Для ( ф I имеем

Так как оба индекса 1 и Г меньше па 1 - !фО (mod п), то выражение справа равно нулю. Таким образом,

п-1 -1

что и требовалось доказать.

Теперь предположим, что qрТр? - р7- Воспользуемся.] китайской теоремой об остатках и алгоритмом Гуда-Юмаса для

отображения кольца z/(q) в прямое произведение z/ipT) У

lliPi ) X... X Z/(pr ). Условия существования преобразования Фурье в кольце zl{q) связаны с условиями существования

преобразований Фурье в каждом из z/(o Г), так что условие делимости Pi - 1 на /г должно выполняться для всех i.n

По-видимому, описываемое теоремой 6.6.1 преобразование Фурье в целочисленном кольце zl{q) при составном q может иметь весьма ограниченные приложения. Тем не менее они могут в некоторых специальных случаях оказаться весьма подходящими.

Рассмотрим, например, разложение

2 Н- 1 = (257) (4278255361) = pip.

В кольце z/(2 -f I) существует преобразование Фурье длины 256, так как 256 делит и pi- 1 и р - 1, Это преобразование при разрядности чисел в 41 бит обеспечивает точность вычислений в 40 бит. Кольцо допускает БПФ-алгоритм Кули-Тьюки по основанию два. Арифметика переполнения легко учитывается равепство.м 2 ~ -1. Элемент 2 нельзя в этом случае использовать в качестве ядра преобразования, так как порядок 2 равен 80, а порядок ядра должен быть равен 256. С.педовательно, умножения не могут быть реализованы в виде циклических сдвигов, а являются умножением 40-битовых чисел общего вида. Таким образом, такая конструкция приводит к процедуре 256-точечной циклической свертки, содержащей примерно 256 -f 2.561og2 256 умножений общего типа для 40-разрядных двоичных чисел с точностью в 40 битовых разрядах. По сравнению с комплексным БПФ-алгоритмом для 40-разрядных двоичных чисел эта процедура является л более точной и содержит меньшее число умножений.

6.7. Числовые преобразования Шевилла

Числа Шевилла (как правило, простые, но не всегда) в нестрогом определении задаются как числа q, для которых в кольце 7i{q] существует преобразование Фурье по одному основанию ЛЛ11 больших длин преобразования. Числа Шевилла связаны только хорошими преобразованиями Фурье и не имеют специального теоретико-числового значения. Таблица этих чисел, построен-Н.ЫХ с помощью ЭВМ, приведена на рис. 6,3,

Если элемент ш кольца zH,q) имеет порядок, равный степени малого простого числа, то преобразование Фурье

Vk = Е

kO, ... , 1.

в ЭТОМ кольце удобно вычислять с помощью БПФ-алгоритма Ку ли-Тьюки по одному основанию. В приведенной на рис. b.i таблице для каждого q указан порядок, определяющий длину преобразования п, равную степени малого простого числа.

Длина слаба

Эфктивмая

д длина

длина Зхини

$дина ВПФ па адноиу

максимальна махсимвлиная

длина длина бпф преобразования по одному аснадамин!

8262 13750 14406 15360 16000 16072 16192 16300 16362 16368

17496 18432 25600 28750 28812 30870 32076 32250 32256 32400 32536 32562 3260S 48

39366 40960 52488 61440 62500 250 64152 64512 65088 65100 65170 65268 96 65448 65520

243 625 2401 1024 128, 125 49 64 25 81 16

2187 2(М8 1024 625 2401 343 729 125 512 25 49 243 32 J6

19683 8192 6561 4096 15625 125 729 1024 64 25 343 49 32 81 16

Рис. 6.3. Таблица алгоритмов Шевилла дла преобразовав

Фурье по одному основанию.