§ 9. Теоретико-числовые и полиномиальные методы выполнения ДПФ и сверток

А. Основные идеи.

Так же, как и при применении описанного в разделах § 5 алгоритма БПФ, при применении теоретико-числовых и полиномиальных методов преобразование заданного одномерного массива чисел (заданной последовательности) сводится к выполнению его для отдельных частей этого массива. Последний заменяется -мерным массивом. При соответствующем построении алгоритма преобразования это позволяет увеличить скорость выполнения операций. В данном случае тоже можно говорить о выполнении быстрого преобразования Фурье и о выполнении быстрых сверток.

Однако, в отличие от ранее рассмотренных преобразований, основанных на частотно-спектральном представлении процессов с использованием тригонометрических и отвечающих им показательных функций, заданная последовательность преобразуется здесь иначе. Используются другие понятия, другие способы обработки информации, сведения о которых приводятся в следующих разделах § 9.

При применении теоретико-числовых методов числа представляются в так называемой модулярной системе. Арифметические операции производятся без переносов от цифры к цифре, что обеспечивает увеличение скорости выполнения преобразований. Используются указываемые ниже выводы, более подробно рассматриваемые в разделе Б. Переход от одномерного массива данных к -мерному массиву производится на основе так называемой китайской теоремы об остатках. Применяя китайскую теорему об остатках, представляют в виде произведения к взаимно простых чисел Возникающие в ходе решения затруднения устраняются при использовании выводов, следующих из другой теоремы теории чисел. Это теорема Эйлера. Основными для рассматриваемых преобразований являются понятия делимости целых чисел, сравнений, вычетов, первообразных корней, квадратичных вычетов. Действия производятся с числами особого вида (числа Мерсенна, числа Ферма), применение которых упрощает выполнение арифметических операций.

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

В связи с рассмотрением вопросов выполнения быстрых преобразований Фурье и сверток теоретико-числовые и полиномиальные методы

обработки информации описаны книгах [35,76, 80]. В следующих разделах дается краткое изложению основной части соответствующих разделов книги [80]; при написании раздела приняты во внимание материалы, приведенные в книге [76].

Б. Сведения из теории чисел.

Используются следующие понятия:

1 . Для целых чисел при имеем где Если остаток то "делит" а (обозначается это как Если а делится только на само себя и на единицу, его называют простым числом, в противном случае составным числом. Составное число единственным образом представляется в виде произведения где целое число и простое число. Для наибольшего общего делителя чисел тоже при принято обозначение Если числа называют взаимно простыми. определяется с помощью алгоритма Евклида, описанного в книге [80]. Имеет место равенство где тип — целые числа. Называют диофантовым линейное целочисленное уравнение в котором х, у - неизвестные числа; с — коэффициенты. Это уравнение имеет решения только при Если о - какое-либо частное его решение, при котором то весь класс решений данного уравнения определяется равенствами целое число.

Все числа а, дающие при делении на один и тот же остаток (имеется в виду исходное равенство составляют, как говорят, класс вычетов по модулю Числа считаются сравнимыми по модулю если при делении на они дают один и тот же остаток который называют вычетом по модулю Для него приняты обозначения или просто (если задано значение Выражения указанного вида называются сравнениями. Выражение диофантова уравнения равносильно сравнению Последнее может быть представлено в виде сравнениях имеют ранее упомянутые значения. Данное сравнение, а соответственно и указанное диофантово уравнение, имеет только различных решений.

2. Для указываемых далее приложений является важным рассмотрение системы линейных уравнений с различными модулями: определяется целое число х, одновременно удовлетворяющее к сравнениям где к и все попарно взаимно простые числа, большие 1. Значение х находится на основании следующей теоремы, известной как китайская теорема об остатках: система линейных сравнений имеет единственное решение по модулю При доказательстве китайской теоремы об остатках (см. [80]) используются сравнения

где единственное решение последнего сравнения.

Многомерное представление одномерных массивов, получаемое при применении китайской теоремы об остатках, упрощается с помощью перестановок. Говоря о перестановках, имеют в виду следующее. Рассматривается N различных целых чисел Рассматривается также множество чисел Ставится условие, чтобы все были различными при изменении от до При выполнении этого условия представляют собой то же самое множество из вычетов, однако все являющиеся попарно различными, располагаются в другом порядке [80].

3. Из ранее сказанного следует, что два числа, имеющие одинаковые остатки при делении на сравнимы по модулю (например, числа 8 и 11 сравнимы по модулю 3, так как при их делении на 3 получается один и тот же остаток 2). Отношение сравнимости по модулю разделяет все целые числа на классов. Часть из них — классы взаимно простых с чисел. Принято обозначение для функции Эйлера, представляющей собой число меньших, чем неотрицательных вычетов, взаимно простых с Если является простым числом, то Для имеем

Функция Эйлера обладает следующими свойствами. Для взаимно простых чисел имеем Следствием являются указываемые ниже утверждения. Если разложить число N на простые множители то Для всех делителей имеем и соответственно Рассмотрим последовательность которая при целом задается соотношением причем для имеют место Имеется только отличающихся один от другого наименьших неотрицательных вычетов. Если минимальное из чисел, при которых не различаются вычеты то Отсюда делается вывод (см. [80], с, 18), что при последовательность является периодической с периодом, равным Если то, уже начиная с имеем цикл, определяемый с учетом того, что при всех соблюдается Данный цикл включает в себя все возможные значения отвечающие заданным Это имеет место при условиях, отвечающих теореме Эйлера, формулируемой следующим образом: если то . В случае, когда простое число, указанная теорема сводится к теореме Ферма: или Теорема Эйлера используется для решения сравнений. На основе ее вводится и понятие показателя (по-другому — порядка, степени) целого числа по заданному модулю.

4. Для выяснения того, что имеется в виду, когда говорят о первообразных корнях, еще раз напомним ранее упоминавшиеся выводы, которые согласно [80] формулируются следующим образом: последовательность периодическая с периодом начиная с 1-го значения. Если для некоторого то последовательность периодическая с самого начала, так как Если наименьшее положительное целое, такое, что то последовательность периодическая с

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

Для первообразных корней а по модулю выполняется равенство Определяют число корней заданной степени, используя следующие теоремы, доказательство которых приведено в книге [80] (см. в последней с. 19, 20): "если корень степени по модулю то числа попарно несравнимы по модулю "если то показатель числа делит "если то показатель числа делит "если где нечетное простое, то имеется в точности попарно несравнимых корней степени по модулю . В книге [80] отмечено, что теория первообразных корней достаточно сложна, и указана литература, в которой содержится более полное ее изложение. Указан также источник, в котором приведена таблица первообразных корней для простых модулей, меньших 10 000. Введенные определения поясняются следующим текстом: "Если или где нечетное простое, то первообразные корни имеют показатель Таким образом, число будет первообразным корнем, если для Более того, если разложение на простые множители, то каждое число, не являющееся первообразным корнем, будет корнем некоторой степени делящей Поэтому первообразный корень удовлетворяет условию

В теории чисел рассматриваются также квадратичные вычеты. Если то квадратичным вычетом по модулю называется число а при условии, что сравнение имеет решение, в противном случае число а называют квадратичным невычетом. На основании китайской теоремы об остатках делается вывод о том, что а является квадратичным вычетом по составному модулю если а — квадратичный вычет по каждому из взаимно простых модулей, содержащихся в разложении Квадратичный вычет а по модулю при нечетном простом имеется при условии, что а является квадратичным вычетом по модулю Ограничиваются изучением случая, когда нечетное простое, так как к нему согласно вышесказанному сводятся и другие случаи. Для определения числа различных квадратичных вычетов по и для выяснения того, является ли число квадратичным вычетом, используются следующие теоремы, доказательство которых приведено в книге [80]: "если нечетное простое число, то число квадратичных вычетов по модулю дается формулой если нечетное простое число, то произведение двух квадратичных вычетов или двух квадратичных невычетов будет вычетом"; при этом произведение квадратичного вычета на квадратичный невычет также есть квадратичный невычет. В связи с рассмотрением квадратичных вьиетов в теории чисел используется символ Лежандра определяемый следующим образом: при условии, что простое нечетное число и равняется 1 или —1 в зависимости от того, является ли а квадратичным вычетом или квадратичным невычетом по модулю При нахождении квадратичных вычетов используется так называемый критерий Эйлера и используются другие правила,

следующие из указываемых далее теорем: нечетное простое число целое число, то различные нечетные простые числа, то нечетное простое число, то

5. Перед тем как перейти к дальнейшему изложению, напомним исходное определение сравнения: где а — делимое, делитель, по модулю которого производится сравнение, остаток или, при принятой терминологии, вычет по модулю

Укажем, что представляет собой упомянутые в . А числа Мерсенна и числа Ферма. Первые из них определяются следующим образом: где нечетное простое число. При имеем соответственно с определением рассматриваемых нами функций, производятся на ЭВМ с использованием двоичной системы счисления (целое число а в двоичной системе счисления представляется как где есть или 1). Упрощение при вычислениях по модулю объясняется тем, что согласно указанному выше определению сравнения Например, при имеем Число делится на 7, частное нас не интересует. В остатке же остается, как и следует из формулы число При пользовании числами Мерсенна минимальный неотрицательный вычет а по модулю находится по формуле получаемой из указанной выше формулы представления числа а в двоичной системе счисления при замене на Существенно то, что нахождение наименьшего неотрицательного вычета производится здесь без выполнения операции деления. При выполнении действий с числами Мерсенна используются следующие теоремы, доказательство которых приведено в книге [80]: "каждый простой делитель числа Мерсенна имеет "все числа Мерсена взаимно простые".

Числами Ферма называют числа где положительное целое число. Первые пять чисел Ферма простые, это числа Остальные из чисел Ферма составные. При выполнении преобразований с использованием числа Ферма учитываются указываемые ниже их свойства. Они сформулированы в виде теорем, доказательство которых тоже дано в книге [80]: "все числа Ферма взаимно простые"; "для всех простых чисел Ферма число 3 является первообразным корнем". Используются также следствия теоремы: "каждый простой делитель составного числа Ферма имеет вид

Арифметические операции, выполняемые по модулю чисел Ферма, называют числовым преобразованием Ферма (ЧПФ), Прямое и обратное ЧПФ последовательностей длины определяются следующим образом [3, 76]:

Здесь — целое число порядка т.е. наименьшее целое положительное число, удовлетворяющее условию Учитывается то, что

В книгах [35, 76] описано и числовое преобразование Мерсенна (ЧПМ).

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

Произведением этих многочленов является многочлен

Сверткой двух последовательностей является новая последовательность, элементы которой являются коэффициентами полиномов, отвечающих исходным последовательностям. Для циклической свертки в указанных выше выражениях индексы определены по модулю

Действия с многочленами или, как говорят, над многочленами основаны на использовании общих понятий группы, кольца, поля. Под группой имеют в виду множество А элементов (чисел, многочленов или других), объединенных одной операцией, которую условно назовем сложением. Для нее примем обозначение Если элементы группы, то тоже является ее элементом. Для того чтобы множество А элементов составляло группу, должны выполняться следующие условия: существуют элемент и элемент а такие, что для любого из элементов а группы Если, кроме того, а то группу называют абелевой.

Множество А элементов, объединенных двумя операциями, одна из которых а другая (условно назовем ее умножением), назьшается кольцом, если соблюдаются следующие условия: А есть абелева группа с нулевым элементом Если а то кольцо называют коммутативным, а при существовании для операции нейтрального элемента и (элемента "единица", для которого а кольцом с единицей или унитарным кольцом.

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

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

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

Так же, как это было для теоретико-числовых представлений, исходными здесь являются понятия делимости и сравнения многочленов. Если для многочленов существует такой многочлен что говорят, что многочлен делит многочлен Если не имеет делителей, кроме тех, степень которых равна нулю или равна степени то многочлен называют неприводимым. Если не делит то остаток, степень которого меньше степени . О многочленах, при делении которых на получается один и тот же остаток говорят, что они сравнимы по модулю Так же, как и при теоретико-числовых представлениях, встречаемся здесь с классом вычетов. Это полиномиальные вычеты по модулю

При пользовании полиномиальным выражением последовательности множество N элементов представляется в виде многочлена Множество многочленов с операциями сложения и умножения по модулю является кольцом и является полем в случае, когда неприводимый многочлен. Если многочлен не неприводимый, то он разлагается в произведение степеней неприводимых многочленов. В книге [80] показано, как это разложение зависит от выбора поля коэффициентов. Приводится следующий пример: многочлен неприводим над полем рациональных чисел, но производится его разложение над полем комплексных чисел, так как

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

Здесь для имеем и

а для определения исцользуехся сравнение

При применении для многочленов китайской теоремы об остатках многочлены определяются с помощью специальных программ.