2.4. Умножение

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

Любой элемент У этого поля может быть однозначно представлен в виде многочлена от а степени в виде где числа из двоичного поля. В соответствии с этим элемент У может быть записан в -разрядном регистре, ячейки которого содержат двоичные числа

2.41. Умножение «регистра» на фиксированную константу. Рассмотрим прежде всего умножение элемента записанного в регистре, на постоянный элемент А поля. Элемент А дюжет быть представлен в виде некоторого двоичного многочлена от а. Так как то

Выражая в виде многочлена от а степени т. е. в виде получим, что

Таким образом, умножение элемента поля на элемент А поля эквивалентно умножению -мерной двоичной вектор-строки на матрицу размерности элементами которой являются числа Строки этой матрицы представляют собой произведения Пусть, например, и нужно умножить записанный в регистре элемент У на элемент Сначала вычисляем

Равенство эквивалентно равенству

Такая операция легко может быть реализована с помощью схемы, изображенной на рис. 2.11.

Если требуется умножить записанный в регистре элемент на элемент а, то надо построить схему, умножающую на матрицу

Такая схема приведена на рис. 2.12.

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

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

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

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

Такая схема изображена на рис. 2.13.

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

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

2.42. Умножение двух «регистров». Рассмотрим произведение двух элементов поля записанных в регистрах памяти.

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

Рис. 2.15. Схема циклического сдвига V вправо.

Каждая из компонент этого произведения является линейной комбинацией двоичных произведений Следовательно, эта операция записывается с помощью -тензора. Такое умножение может быть непосредственно реализовано с помощью метода, предложенного Бэрти и Шнейдером [1963]. В зависимости от вида неприводимого многочлена эта реализация многочлена требует порядка сумматоров с двумя входами.

Рис. 2.16. Схема для прибавления кратных к

Даже при хорошем выборе неприводимого многочлена столь большое число сумматоров с двумя входами делает эту процедуру чрезвычайно дорогой для больших Если нет необходимости в максимальной скорости вычислений (один временной цикл, гарантируемый методом Бэрти — Шнейдера), то предпочтительней более длительные, но менее дорогие способы умножения. Одним из таких способов является следующий метод умножения, очень близкий к методу, предложенному Питерсоном [1961].

Пусть множитель записан в регистре с обратной связью, позволяющей по команде заменять V на Пример такого регистра для корня а многочлена приведен на рис. 2.14. Множитель V запоминается в регистре, в котором можно осуществить циклический сдвиг вправо, как показано на рис. 2.15. Произведение накапливается в регистре, к содержимому которого можно прибавлять содержимое -регистра, как показано на рис. 2.16.

Начальное состояние -регистра является нулевым. В зависимости от значения низшего разряда множителя V множитель прибавляется или не прибавляется к Если то прибавляется к если то остается без изменений. После этого -регистр сдвигается вправо, -регистр умножается на а и процесс повторяется. На шаге умножения вместо записано а” вместо записано и -регистр содержит После таких шагов умножение закончено и -регистр содержит произведение исходных и -регистров. При этом -регистр циклически сдвинут в свое исходное положение, а -регистр содержит Поэтому если для дальнейших вычислений требуется восстановить первоначальный вид множителя то нужно добавить дополнительную схему. Исходный вид множителя можно восстановить в один шаг с помощью схемы умножения на константу Зачастую, однако, эта операция требует так много дополнительных сумматоров, что оказывается дешевле построить специальный регистр для запоминания первоначального состояния

Более дешевым методом восстановления исходного состояния регистра множимого является -кратное умножение на константу Если вес равен 3, то такая процедура, хотя и требует временных циклов, использует всего один сумматор с двумя входами. Возможны также и вариации этого метода, как, например, умножение на и сокращение необходимого времени до временных циклов. Другим возможным решением является осуществление умножения -регистра на и сдвигов -регистра сразу на две позиции вправо и влево и на одну позицию вправо. При этом произведение можно накапливать в -регистре согласно правилу

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

2.43. Таблицы логарифмов. В качестве последнего метода выполнения операций умножения, деления, возведения в степень и извлечения корня рассмотрим использование таблиц логарифмов. Такие таблицы могут быть построены для ненулевых элементов в любом поле. Например, если а — корень неприводимого двоичного многочлена то умножение на а может быть выполнено с помощью регистра сдвига с обратной связью, изображенного на рис. 2.17. Отправляясь от начального состояния регистра

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

Рис. 2.17. Регистр сдвига с обратной связью для умножения на а.

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

частное

степень

и корень

так как

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

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

как и для многих приложений это оказывается значительно дороже, чем прямой метод, описанный в разд. 2.42.

Если известен некоторый метод, позволяющий легко вычислять логарифмы элементов поля (основанный не на просмотре таблиц, а на операциях над координатами двоичных представлений элементов поля в виде многочленов от а), то логарифмический подход может составить основу экономной реализации операций умножения и деления. В общем случае, однако, не известно никаких простых методов непосредственного вычисления логарифмов. Некоторые очень частные результаты в этом направлении содержатся в задачах 4.3 и 4.4.

2.44. Квадраты и квадратные корни. Другим частным случаем умножения, заслуживающим отдельного рассмотрения, является умножение элемента поля, записанного в регистре на самого себя, Так как с помощью регистров сдвигов мы умеем выполнять операцию умножения вектор-строки на матрицу, то в принципе мы можем реализовать любую линейную операцию над элементами поля. В частности, это относится и к такой операции, как возведение в квадрат. Для большинства полей возведение в квадрат не является линейной операцией. Однако в полях, содержащих двоичное поле, всегда выполняется равенство следовательно, в этом случае возведение в квадрат — линейная операция, и квадрат любого элемента поля может быть представлен в виде соответствующей линейной комбинации квадратов базисных элементов. Например, если а — корень многочлена

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

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

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

Рис. 2.18. Схема для вычисления .

Рис. 2.19. Схема для вычисления .

Таким образом, преобразование может быть представлено в форме и реализовано с помощью схемы, изображенной на рис. 2.19.