2.3. Мультипликативное обращение

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

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

Затем полагаем

Итерацию продолжаем до тех пор, пока не получим При этом решение задается равенствами при Так как нам необходимо найти только практически нам не нужно), то можно обойтись только величинами

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

2.31. Вычисления.

(кликните для просмотра скана)

Начиная с для величин имеем

Чтобы избежать запоминания коэффициентов целесообразно выполнять эти вычисления одновременно с вычислением Это позволяет записать

2.32. Вычисления.

(см. скан)

Коэффициенты для определяются следующим образом:

2.33. Вычисления.

(см. скан)

(Вычисления 2.33 являются сокращением вычислений 2.31 и 2.32.) Здесь мы используем запись, при которой старшие коэффициенты располагаются в крайнем левом положении, а старшие коэффициенты в крайнем правом положении. Используя такую запись, можно производить вычисления с помощью всего лишь двух основных регистров, каждый из которых содержит ячейки. Правила вычисления сводятся к следующему.

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

Если крайний левый элемент верхнего регистра равен нулю, то сдвигаем верхний регистр (вместе с его запятой) на одну позицию влево.

Если крайний левый элемент нижнего регистра равен нулю, то сдвигаем нижний регистр (вместе с его запятой) на одну позицию влево.

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

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

После установки запятых и осуществления сдвига четность к изменяется. Для четных к нижняя запятая находится слева от (или совпадает с) верхней запятой; для нечетных к нижняя запятая находится справа от (или совпадает с) верхней запятой.

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

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

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

2.35. Вычисления.

Заметим, что окончание алгоритма отмечается появлением нуля в крайней левой позиции маркерного регистра.

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

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

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