RU2007035C1

RU2007035C1 - Device for generation of indexes of members of multiplicative groups of galois fields gf(p)

Info

Publication number: RU2007035C1
Authority: RU
Inventors: Вячеслав Иванович Петренко; Александр Федорович Чипига
Original assignee: Вячеслав Иванович Петренко; Александр Федорович Чипига
Priority date: 1991-04-02
Filing date: 1991-04-02
Publication date: 1994-01-30

Abstract

FIELD: computer engineering. SUBSTANCE: read-only memory unit 7, AND gates unit 8, arbitrary modulo adders unit 10, inverters unit 9, second and third AND gates 11 and 12 are introduced to accomplish the goal of invention. When indexes are generated given modulo is computed by means of parallel addition of comparison results. EFFECT: increased speed. 1 dwg

Description

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования сигнально-кодовых конструкций в конечных полях. The invention relates to computer technology and can be used in digital computing devices, as well as in devices for generating signal-code structures in the final fields.

Известно устройство для формирования остатка по произвольному модулю от числа, содержащие блок умножения, схему сравнения, регистр, счетчик, элемент ИЛИ, элемент задержки, а также элемент И с соответствующими связями. A device is known for generating a remainder modulo an arbitrary number, containing a multiplication block, a comparison circuit, a register, a counter, an OR element, a delay element, and an AND element with corresponding relationships.

Недостатком этого устройства является низкое быстродействие формирования индексов элементов мультипликативных групп полей Галуа GF(P). The disadvantage of this device is the low speed of forming indices of elements of multiplicative groups of Galois fields GF (P).

Целью изобретения является повышение быстродействия формирования индексов элементов мультипликативных групп полей Галуа GF(P). The aim of the invention is to increase the speed of forming indices of elements of multiplicative groups of Galois fields GF (P).

Сущность изобретения заключается в том, что первоначально выбирается первообразный элемент θ , по которому предполагается формировать индексы. Затем задается элемент поля а, от которого необходимо сформировать индекс. Элемент поля θ умножается на единицу, затем результат умножения - произведение - умножается на элемент θ , далее результат произведения умножается на θ и т. д. Каждый результат приводится по заданному модулю Р и затем сравнивается с элементом поля а, а также подсчитывается количество умножений. The essence of the invention lies in the fact that initially the primitive element θ, which is supposed to form indices, is selected. Then the element of the field a is specified from which it is necessary to form an index. The element of the field θ is multiplied by one, then the result of the multiplication — the product — is multiplied by the element θ, then the result of the product is multiplied by θ, etc. Each result is given by the given modulus P and then compared with the element of the field a, and the number of multiplications is also calculated.

Процедура приведения по заданному модулю реализуется за счет возможности почленного складывания сравнений, т. е. так как
(a_k2^k + a_k-12^k-1 + . . . + a₁2 + a_o)modP = a_k2^k(modP) + a_k-12^k-1(modP) + . . . + a₁2(modP) + a_o(modP), (1) где k - разрядность полученного произведения, причем для двоичной системы счисления a_i = 0v1, то, суммируя заранее вычисленные остатки по модулю Р от чисел 2_i, i =

, для которых коэффициент ai = 1, получают остаток по модулю Р от кода произведения. Для модулей P_j, с которыми предлагается работа устройства, в блоке постоянной памяти запоминаются заранее вычисленные остатки от чисел 2ⁱ, i =

, где k - разрядность кодов произведений, от которых необходимо формировать остатки.The reduction procedure for a given module is implemented due to the possibility of termwise folding of comparisons, i.e., since
(a _k 2 ^k + a _k-1 2 ^k-1 +.. + a ₁ 2 + a _o ) modP = a _k 2 ^k (modP) + a _k-1 2 ^k-1 (modP) +. . . + a ₁ 2 (modP) + a _o (modP), (1) where k is the bit depth of the resulting product, and for the binary number system a _i = 0v1, then, summing up the precomputed remainders modulo P of the numbers 2 _i , i =

for which the coefficient ai = 1, get the remainder modulo P of the product code. For the modules P _j , with which the device is proposed to work, the previously calculated residues from the numbers 2 ⁱ , i =

, where k is the capacity of product codes from which it is necessary to form residues.

Как только приведенный по модулю указанный выше результат умножения станет численно равным значению элементов поля а, то это означает, что количество выполненных умножений численно равно индексу элемента а по основанию θ в поле GF(P), т. е. индекс элемента а сформирован. As soon as the above multiplication result modulo becomes numerically equal to the value of the elements of the field a, this means that the number of multiplications performed is numerically equal to the index of the element a and the base θ in the field GF (P), i.e., the index of the element a is formed.

На чертеже представлена функциональная схема устройства для формирования индексов элементов мультипликативных групп полей Галуа GF(P). The drawing shows a functional diagram of a device for forming indices of elements of multiplicative groups of Galois fields GF (P).

Устройство содержит первый элемент 1 задержки, элемент ИЛИ 2, схему 3 сравнения, регистр 4, блок 5 умножения, счетчик 6, блок 7 памяти, блок 8 элементов И, блок элементов 9 НЕ, сумматор 10 по произвольному модулю, второй 11 и третий 12 элементы задержки. The device comprises a first delay element 1, an OR element 2, a comparison circuit 3, a register 4, a multiplication block 5, a counter 6, a memory block 7, an AND element block 8, an AND element block 9, an adder 10 modulo 10, a second 11 and a third 12 delay elements.

Устройство для формирования индексов элементов мультипликативных групп полей Галуа GF(P) работает следующим образом. A device for forming indices of elements of multiplicative groups of Galois fields GF (P) works as follows.

В исходном состоянии регистр 4 обнулен. В блок 7 памяти предварительно записаны заранее вычисленные остатки от чисел 2ⁱ, i =

где k - максимальная разрядность произведения, по модулям P_j, с которыми предлагается работа устройства. На вход 15 "Начало вычисления" поступает импульс, который обнуляет счетчик 6 и осуществляет запись единицы в регистр множимого блока 5 умножения.In the initial state, register 4 is reset. In the block 7 of the memory pre-written pre-calculated residues from the numbers 2 ⁱ , i =

where k is the maximum capacity of the product, according to the modules P _j , with which the device is proposed to work. Input 15 "Beginning of calculation" receives a pulse, which resets the counter 6 and writes a unit to the register of the multiplier block 5 of the multiplication.

Модуль P_i, по которому осуществляется формирование остатков, задается параллельным двоичным кодом, подаваемый на вход 16 устройства. Импульс начала вычисления, пройдя через элемент 1 задержки, поступает на первый вход элементе ИЛИ 2 и запускает блок 5 умножения. В регистр множителя блока умножения записывается поступающий на вход 14 первообразный элемент θ . После перемножения импульс конца умножения подсчитывается счетчиком 6, поступает на вход разрешения считывания блока 7 памяти и на вход элемента 11 задержки. Поэтому на выходах блока 7 памяти появляются остатки от чисел 2ⁱ, i =

, по модулю P

Одновременно с информационных выходов блока 5 умножения на блок 8 элементов И поступает код произведения и в зависимости от того, на какую из групп элементов И поступает логическая "1", та из групп оказывается открытой и коммутирует на свои выходы входные сигналы. В результате на соответствующие входы сумматора 10 по произвольному модулю поступают остатки от чисел 2ⁱ, i =

, для тех i, для которых коэффициент a _i= 1 при представлении произведения в позиционной системе счисления с основанием два. На управляющие входы сумматора 10 по произвольному модулю поступает значение модуля в прямом и инверсном коде. Поэтому сумматор 10 осуществит суммирование по модулю P_i поступающих на его входы чисел, эта сумма в двоичном параллельном коде оказывается на его выходах и поступает на информационные входы регистра 4. Так как время задержки элемента 11 задержки равно времени формирования остатка, то на его выходе появляется импульс, который записывает код остатка в регистр 4 и поступает на вход третьего элемента 12 задержки. В результате с выхода регистра 4 остаток от произведения по модулю поступает на первые входы схемы 3 сравнения, а импульс с выхода элемента 12 задержки поступает на разрешающий вход схемы 3, разрешая сравнение остатка от произведения по модулю и элемента поля, подаваемого на входы 13 устройства. Если остаток от произведения не равен элементу поля, то с выхода "Не равно" схемы 3 сравнения импульс поступает на второй вход элемента ИЛИ 2, и с его выхода на запускающий вход блока 5 умножения. Процесс формирования остатка повторяется сначала, а количество перемножений подсчитывается счетчиком 6. Если остаток от произведения по модулю численно равен элементу поля, то с выхода "Равно" схемы 3 сравнения поступает импульс, который обнуляет регистр множимого блока 5 умножения, останавливает работу счетчика 6 и поступает на выход 17 "Конец вычисления", свидетельствуя о том, что вычисление закончено, а на выходах счетчика 6 сформирован индекс от заданного на входах 13 устройства элемента поля по первообразному элементу θ , заданному на входах 14 устройства.The module P _i , by which the formation of residues is carried out, is set by a parallel binary code supplied to the input 16 of the device. The pulse of the beginning of the calculation, passing through the delay element 1, goes to the first input of the OR element 2 and starts the multiplication block 5. In the multiplier register of the multiplication block, the antiderivative element θ arriving at input 14 is recorded. After multiplication, the pulse of the end of the multiplication is counted by the counter 6, and is fed to the read permission input of the memory unit 7 and to the input of the delay element 11. Therefore, at the outputs of the memory unit 7, residues from the numbers 2 ⁱ , i =

modulo P

Simultaneously with the information outputs of block 5 of multiplication by block 8 of AND elements, the product code is received and, depending on which of the groups of elements AND receives a logical “1”, that of the groups is open and commutates input signals to its outputs. As a result, the corresponding inputs of the adder 10 modulo receive the remainder of the numbers 2 ⁱ , i =

, for those i for which the coefficient a _i = 1 when representing the product in a positional number system with a base of two. The control inputs of the adder 10 through an arbitrary module receives the value of the module in direct and inverse code. Therefore, the adder 10 will perform a summation modulo P _{i of the} numbers arriving at its inputs, this sum in binary binary code appears at its outputs and goes to the information inputs of register 4. Since the delay time of the delay element 11 is equal to the time the remainder is formed, the output appears a pulse that writes the remainder code to register 4 and is input to the third delay element 12. As a result, from the output of register 4, the remainder of the product modulo arrives at the first inputs of the comparison circuit 3, and the pulse from the output of the delay element 12 is fed to the enable input of the circuit 3, allowing comparison of the remainder of the product modulo and the field element supplied to the inputs of the device 13. If the remainder of the product is not equal to the field element, then from the output "Not equal" of the comparison circuit 3, the pulse is supplied to the second input of the OR element 2, and from its output to the triggering input of the multiplication block 5. The process of generating the remainder is repeated first, and the number of multiplications is calculated by the counter 6. If the remainder of the product modulo is numerically equal to the field element, then the output of the "Equal" comparison circuit 3 receives an impulse that resets the register of the multiplicable multiplication unit 5, stops the operation of counter 6 and receives output 17 "End of calculation", indicating that the calculation is completed, and at the outputs of counter 6 an index is generated from the field element specified at the inputs 13 of the device according to the antiderivative element θ specified at the input dah 14 device.

Задавая следующий элемент и подавая импульс на вход 15, получают индекс этого элемента поля на выходах счетчика 6 и т. д. При этом формирование индексов элементов поля может происходить при различных первообразных элементах, а также в различных полях GF(P). By setting the next element and applying a pulse to input 15, we obtain the index of this field element at the outputs of the counter 6, etc. In this case, the formation of the field element indices can occur with various primitive elements, as well as in different fields GF (P).

Технико-экономическая эффективность изобретения заключается в повышении быстродействия формирования индексов элементов мультипликативных групп полей Галуа GF(P). Feasibility study of the invention is to increase the speed of forming indices of elements of multiplicative groups of Galois fields GF (P).

Положительный эффект от использования изобретения заключается в том, что за счет сокращения времени формирования индексов достигается повышение производительности систем, использующих изобретение. (56) Авторское свидетельство СССР N 1686702, кл. H 03 M 7/18, 1989. The positive effect of the use of the invention lies in the fact that by reducing the time of formation of indices, an increase in the productivity of systems using the invention is achieved. (56) Copyright certificate of the USSR N 1686702, cl. H 03 M 7/18, 1989.

Claims

DEVICE FOR FORMING INDICES OF ELEMENTS OF MULTIPLICATIVE GROUPS OF GALOIS FIELDS GF (P), containing a multiplication block, a comparison circuit, a register, a counter, a first delay element, an OR element, and an AND element block, and the input of the device’s computation beginning is connected to the installation input in the “0” counter , by the input of a unit value record to the multiplication unit and through the first delay element with the first input of the OR element, the output of which is connected to the input of the multiplication resolution of the multiplication unit, and the second input of the OR element is connected to the "Not equal" output of the circuit whose output is “Equally” which is the output of the end of the device’s calculations and is connected to the enable output of the counter result and the installation input at “0” of the multiplication unit, the output of the end of the multiplication of which is connected to the counter input of the counter, the bit outputs of which are the outputs of the device index and the bit the outputs of the register are connected respectively to the information inputs of the first group of the comparison circuit and the inputs of the multiplier of the multiplication block, the inputs of the multiplicable of which are the recording inputs of the antiderivative element of the device field, the inputs of the discharges of the field element of which are connected respectively to the information inputs of the second group of the comparison circuit, characterized in that, in order to improve performance, a memory block, an adder modulo an arbitrary module, a block of elements NOT and a second and third delay elements are introduced into it, and the bit outputs of the block multiplications are connected respectively to the inputs of the first group of the block of elements AND, the inputs of the second group of which are connected respectively to the outputs of the memory block, and the outputs of the block of elements AND are connected to the inputs of the first group an adder according to an arbitrary module, the inputs of the second group of which are connected respectively to the address inputs of the memory block, the input of the device module and the input of the block of elements NOT, the output of which is connected to the inputs of the third group of the adder according to an arbitrary module, the bit outputs of which are connected respectively to the information inputs of the register, the end output of the multiplication of the multiplication unit is connected to the control input of the memory unit and through the second delay element with the register enable input and the input of the third delay element od is connected to the control input of the comparison circuit.