Главное


Выбор модели умножителя по модулю m

Умножители на основе закона квадратов (рис. 2.2 (а)) вычисляют модулярное произведение |x*y|m с помощью следующего равенства (закон квадратов):

(2.1)

где 0 ≤ x, y < m . Модулярное умножение на основе (3.1) можно записать следующим образом:

(2.2)

и произведение |x*y|m можно вычислять по формуле:

(2.3)

Рисунок 2.2 (а) - Схема модулярного умножителя по модулю m на основе закона квадратов

Существование операции деления на 2 ставит под угрозу целочисленность промежуточных вычислений и, соответственно, правильность результата после использования таблиц подстановок. Более того, существование обратного по умножению по модулю m для 2 элемента, , гарантируется только в случае, если 2 не делит m (т.е. m - нечётно). Тэйлор в работе [11] привёл доказательство теоремы, показав, что даже если при вычислении (2.2) будут промежуточные дроби, они взаимно уничтожатся.

Умножители, основанный на арифметике указателей [12, 13] является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования.

Метод работы этого умножителя связан с математическими свойствами полей Галуа [14, 15], обозначаемых GF(p) , где p - простое число. Все ненулевые элементы поля Галуа могут быть получены путём многократного возведения в степень примитивного элемента - порождающего поле GF(p) элемента gj . Это свойство полей Галуа можно использовать для умножения в GF(mj) благодаря использованию изоморфизма между мультипликативной по модулю mj группой Q = {1,2,…,m - 1}, и аддитивной по модулю (mj-1)- группой I ={0,1,…,m - 2}. Этот изоморфизм может быть установлен следующим образом:

(2.4)

и умножение над полем GF(m) может производиться по формуле:

(2.5)

Таким образом, умножение двух чисел qj и qk можно производить вычисляя модулярную сумму соответствующих указателей ij и ik , а затем проводя обратное преобразование из степенного пространства в исходный вид. Необходимо специально обрабатывать случаи, когда один из операндов на входе умножителя равен нулю и в этом случае назначать нулевой результат произведения. Это происходит потому, что не определён элемент в степенном пространстве, соответствующий нулевому элементу группы Q .

Степени ij и ik для qj и qk , соответственно, могут быть заранее вычислены и помещены в LUT. Сложение степеней выполняет сумматор по модулю mj-1. Обратное преобразование из степенного представления ij и ik в исходное qj и qk также может быть выполнено с помощью предварительно вычисленных LUT.

Рисунок 2.2 (б) - Схема модулярного умножителя, основанного на исчислении степеней (умножитель Галуа)

Рассмотрим в качестве примера работу этого умножителя на примере умножения двух чисел 14 и 28 по модулю 31.

Так как 31 - простое число, существует порождающий элемент g , дающий возможность ассоциировать каждый элемент мультипликативной группы

Q = {1,2,…,31} с элементом аддитивной группы I ={0,1,…,30} . Соответствие задаётся выражением . В табл.1 рассчитано соответствие между элементами группы Q и соответствующей степенью из аддитивной группы I . Эта таблица в сущности и представляет собой содержание LUT размером 25×5 прямого и обратного преобразования в умножителе, изображенном на рис. 2.2 (б).

Рассмотрим работу умножителя Галуа (рис. 2.2 (б), рис. 2.2 (в), табл. 1) на примере умножения |14 × 28 |31. Итак, qj = 14 и qk = 28, а произведение |qj × qk |31 получается посредством суммирования соответствующих им элементов ij и ik , выбранных из табл. 1. Таким образом, указатели оказываются ij = 22 и ik = 16 и | ij + ik |30 = 8. Элементу in = 8 в табл. 1 соответствует qn = 20, следовательно, |14 × 28|31 = 20 .

Перейти на страницу: 1 2

Другие статьи по теме

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

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

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

www.techspirit.ru © 2021