7.3. Вычисления в алгебрах многочленов и полях Галуа

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

В регистре сдвига, состоящем из разрядов, изображенном на рис. 7.6, хранится элементов поля, которые можно рассматривать как коэффициенты многочлена

степени или меньшей. При сдвиге регистра на единицу вправо этот многочлен переходит в многочлен

Последнее слагаемое возникает из-за наличия обратной связи. Это соотношение может быть записано в виде

Таким образом, многочлены лежат в одном и том же классе вычетов по модулю и поскольку степень многочлена меньше, чем то многочлен должен совпадать с единственным многочленом в классе вычетов степень которого меньше, чем

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

Используем для иллюстрации наинх рассуждений многочлен и поле из двух элементов. Это — примитивный многочлен, и поэтому класс вычетов где я — корен, многочлена является примитивным элементом поля Соответствующий регистр сдвига показан на рис. 7.11. Если в младший разряд поместить единицу, а в остальные разряды — нули, то последовательные сдвиги регистра дают представление последовательных степеней элемента а, корня многочлена в точности в той же самой форме, в которой они приведены в табл. 6.1. Заметим, что единице, сдвигаемой из старшего разряда, соответствует элемент и наличие обратной связи заменяет его на равный ему элемент 1.

Другой вариант подобной схемы приводится на рис. 7.12. Сдвиг влево соответствует делению на а, так что сдвиг из младшего разряда дает значение заменяемое эквивалентным ему значением Таким образом, эта схема может использоваться для счета "назад", т. е. для получения элементов поля Галуа, перечисляемых в обратном порядке.

Рис. 7.11. Схема для вычисления в поле Галуа.

Рис. 7.12. Схема для счета в обратном направлении в поле Галуа.

Умножение элементов поля можно производить, помещая один сомножитель в устройство А, подобное схеме, изображенной на рис. 7.11, а другой сомножитель — в устройство В, аналогичное схеме, изображенной на рис. 7.12. Затем производятся сдвиги в обоих устройствах до тех пор, пока в схеме В не появится единица. Тогда в схеме А появится произведение. Деление производится аналогичным способом.

Умножение можно также проводить способом, аналогичным обычно используемому в вычислительных машинах. Для этого применяется регистр сдвига типа регистра, изображенного на рис. 7.11, используемый в качестве запоминающего устройства. Этот способ пригоден для действий над элементами в любой алгебре многочленов по модулю многочлена в частности, в полях Галуа. Для примера рассмотрим умножение векторов и (1101) как элементов из поля представленного в табл. 6,1. Приведем содержимое "запоминающего устройства" после каждой операции (заметим, что используется векторное сложение).

Кроме того, используя схему, приведенную на рис. 7.6, можно вычислять значение многочлена при X, равном некоторому элементу поля а. Для этого в качестве многочлена следует взять минимальную функцию для а. Представление в виде элемента поля Галуа для

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

Пример. Пусть а — примитивный элемент использованный для представления элементов поля в табл. 6.1. Представление в виде элемента поля Галуа для

может быть вычислено при помощи схемы, изображенной на рис. 7.11, в которую поступает вектор

Вычисление значений для 1 (или 0) значительно усложняется, если результат должен быть найден в виде многочлена от низших степеней а. Один из известных методов основан на использовании регистра сдвига, производящего автоматически умножение на Для того чтобы разъяснить основные принципы этого метода, рассмотрим пример для . В соответствии с табл. 6.1 имеем:

так что

Таким образом, новое значение равно прежнему значению суммы новое значение равно прежнему значению суммы и т. д.

Рис. 7.13. Схема для умножения на в

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