RU2007034C1 - Device for generation of indexes of members of multiplicative groups from galois fields gf(p) - Google Patents

Abstract

FIELD: computer engineering. SUBSTANCE: device has multiplication unit 1, counter 2, multiplexer 3, two delay gates 4, 5, six OR gates 6-11, memory unit 12, switches unit 13, adder 14, subtraction unit 15, three comparison circuits 16-18 and two registers which are connected to each correspondingly. EFFECT: increased speed. 1 dwg

Description

 The invention relates to computer technology and can be used 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 memory block, a key block, an adder, the first and second comparison schemes, a subtracter, a multiplexer, first and second registers, a delay element, and five OR elements with corresponding functional relationships [1].

 The disadvantage of this device is its narrow functionality.

 The closest to the proposed technical essence and the achieved result is a device for generating a remainder modulo an arbitrary number modulus, containing a multiplication block, a counter, a delay element, three OR elements, a subtracter, two comparison schemes and two registers with corresponding functional relationships [2].

 The disadvantage of this device is its low performance when forming indices of elements of multiplicative groups of Galois fields GF (P), since the procedure for generating indices reduces to sequential subtraction of the product code of the module from the code.

 The purpose of the invention is to increase the speed of the device.

 The goal is achieved in that in a device for forming indices of elements of multiplicative groups of Galois fields GF (P), containing a multiplication unit, a counter, a first delay element, the first, second and third elements OR, a subtractor, the first and second comparison schemes and the first and second registers moreover, the input of the beginning of the computing device is connected to the input of the first delay element, the input of setting the counter to zero, and the input of writing the value of "unity" to the multiplication unit, the output of the first delay element is connected to the first input of the second OR element, the output to is connected to the input of the permission of multiplication of the multiplication block, the inputs of the bits of the element of the field of the device are connected respectively to the inputs of the first group of the first comparison circuit, the inputs of the second group of which are connected respectively to the bit outputs of the first register and the inputs of the multiplier of the multiplication block, whose inputs are multiplicable connected to the inputs of the antiderivative device element , the inputs of the bits of the module of which are connected respectively with the inputs of the first groups of the subtractor and the second comparison circuit, the output of the end of the block multiplication is clever The connection is connected to the first input of the third OR element and to the counting input of the counter, the input of the resolution of the output of which is connected to the input of the zeroing unit of the multiplication and the output is equal to the first comparison circuit, the output is not equal to which is connected to the second input of the second OR element, the recording and setting enable inputs of the first register are connected respectively to the first and second inputs of the first OR element, the output of which is connected to the control input of the first comparison circuit, and the counter output is an information output for triplets, a multiplexer, a second delay element, a fourth, fifth and sixth OR element, a memory block, a key block, an adder and a third comparison circuit are introduced, while the outputs of the multiplication block are connected to the information inputs of the first group of the multiplexer, the information inputs of the second group of which are connected respectively to the inputs of the first group of the third comparison circuit and the outputs of the subtractor, the inputs of the second group of which are connected respectively to the information inputs of the third group of the multiplexer, the inputs of the second group of the second comparison circuits and outputs of the adder, the inputs of which are connected respectively to the outputs of the key block, the inputs of the first group of which are connected to the outputs of the memory block, the address inputs of which are connected to the inputs of the bits of the device module and the inputs of the second group of the third comparison circuit, the inputs of the second group of the key block are connected to the outputs of the second register, the information inputs of which are connected respectively to the information inputs of the first register and the outputs of the multiplexer, the first control input of which is connected to the output of the fourth OR element, the first input of which is connected to the second input of the third OR element and with the output “greater than” the third comparison circuit, the output “less” of which is connected to the second input of the fourth OR element and the first input of the sixth OR element, the second input of which is connected to the second control the input of the multiplexer and with an output "less" of the second comparison circuit, the output of which is "equal" to the first input of the fifth OR element, the second input of which is connected to the output of "equal to the third comparison circuit, the output of the third OR element is connected to the control input of the memory block, the input enable recording of the second register and the input of the second delay element, the output of which is connected to the control input of the second comparison circuit, the output of "greater than" which is connected to the control input of the third comparison circuit, the outputs of the fifth and sixth elements OR are connected respectively to the installation input to zero and the entry permission entry of the first register.

 Functional diagram of a device for forming indices of elements of multiplicative groups of Galois fields GF (P) is shown in the drawing.

 The device comprises a multiplication unit 1, a counter 2, a multiplexer 3, the first and second delay elements 4 and 5, the first, second, third, fourth, fifth and sixth elements OR 6, 7, 8, 9, 10 and 11, a memory unit 12, block 13 keys, adder 14, subtractor 15, the first, second and third comparison circuits 16, 17 and 18, as well as the first and second registers 19 and 20.

 A device for forming indices of elements of multiplicative groups of Galois fields GF (P) works as follows.

; K - максимальная разрядность произведения по модулям P_j, с которыми предполагается работа устройства. На вход начала вычислений поступает импульс, который обнуляет счетчик 2 и осуществляет запись значения "единицы" в регистр множимого блока 1 умножения.In the initial state, all registers are reset to zero. In the block 12 of the memory pre-written previously calculated residues from the numbers 2 ⁱ , where i =

; K is the maximum capacity of the product by the modules P _j , with which the device is supposed to work. A pulse is received at the input of the beginning of the calculations, which resets the counter 2 and writes the value of the “unit” to the register of the multiplier block 1 of the multiplication.

, по модулю P

Блок 12 памяти имеет К групп выходов, каждая из которых состоит из l разрядов, необходимых для представления остатков чисел 2ⁱ по модулю P_j. Блок 13 ключей представляет собой группу K l-входовых ключей. В зависимости от того, на какой из управляющих входов блока ключей поступает логическая "1", тот из ключей блока 13 оказывается открытым и коммутирует на свои выходы входные сигналы. В результате на соответствующие входы сумматора 14 поступают остатки от чисел 2ⁱ, i =

, для тех i, для которых коэффициент a _i= 1 в представлении кода произведения, записанного в регистре 20. Сумматор 14 осуществляет суммирование чисел, поступающих на его входы, и эта сумма в двоичном параллельном коде оказывается на его выходах. При этом на первые входы схемы 17 сравнения воздействует код модуля P_j, а на вторые входы - код вычисленной суммы с выходов сумматора 14. К этому моменту времени на выходе элемента 5 задержки появляется импульс, который, поступая на управляющий вход схемы 17 сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы. Если в результате сравнения оказывается, что код числа, воздействующий на второй вход схемы 17 сравнения, меньше кода модуля, то на выходе "меньше" схемы 17 сравнения появляется импульс, который поступает на второй управляющий вход мультиплексора 3 и через элемент ИЛИ 11 на вход разрешения записи регистра 19. В результате мультиплексор 3 коммутирует на выходы свои третьим входы и в регистр 19 при этом записывается с выходов сумматора 14 код остатка. В результате с выхода регистра 19 остаток от произведения по модулю поступает на первый вход схемы 16 сравнения, а импульс конца формирования остатка с выхода элемента ИЛИ 6 поступает на управляющий вход схемы 16 сравнения, разрешая сравнение остатка от произведения по модулю и элемента поля, подаваемого на вход устройства. Если остаток от произведения не равен элементу поля, то с выхода "не равно" схемы 16 сравнения импульс поступает на первый вход элемента ИЛИ 7 и с его выхода на запускающий вход блока умножения. Процесс формирования повторяется сначала, а количество перемножения подсчитывается счетчиком 2. С выхода счетчика 2, являющегося выходом устройства, в параллельном двоичном коде снимается индекс элементов мультипликативных групп. Если остаток от произведения по модулю численно равен элементу поля, то с выхода "равно" схемы 16 сравнения поступает импульс, который обнуляет регистр множимого блока 1 умножения, останавливает работу счетчика 2 и поступает на выход конца вычисления, свидетельствуя о том, что вычисление закончено, а на выходах счетчика 2 формируется индекс от заданного элемента поля по первообразному элементу.The module by which residuals are generated is defined by a parallel binary code supplied to the input of the device module. The pulse of the beginning of the calculation, passing through the delay element 4, enters the second input of the OR element 7 and starts the multiplication unit 1. In the multiplier register of the multiplication unit 1, the antiderivative element θ is written. After multiplication, the pulse of the end of the multiplication is counted by the counter 2 and, passing through the OR element 8, is fed to the read enable input of the memory unit 12, to the write enable input of the register 20 and to the input of the delay element 5. At the same time, a code of the product coming from the output of the multiplication unit 1 is recorded in the register 20 through the multiplexer 3, and the residues from the numbers 2 ⁱ , i = appear at the outputs of the memory unit 12

modulo P

The memory unit 12 has K groups of outputs, each of which consists of l bits necessary to represent the remnants of the numbers 2 ⁱ modulo P _j . The key block 13 is a group K of l-input keys. Depending on which of the control inputs of the key block the logical "1" is received, that of the keys of block 13 is open and commutates the input signals to its outputs. As a result, the corresponding inputs of the adder 14 receive the remainder of the numbers 2 ⁱ , i =

, for those i for which the coefficient a _i = 1 in the representation of the product code recorded in register 20. The adder 14 sums the numbers arriving at its inputs, and this sum in the binary parallel code is at its outputs. Wherein the first inputs of the comparison circuit 17 acts code module P _j, and the second input - the calculated code amount with the outputs of the adder 14. At this point in time appears on the output pulse of the delay element 5, which, acting on a control input of the comparison circuit 17, authorizes comparison of codes of numbers affecting its inputs. If, as a result of the comparison, it turns out that the code of the number acting on the second input of the comparison circuit 17 is less than the module code, then the output is “less” of the comparison circuit 17 and an impulse appears, which arrives at the second control input of the multiplexer 3 and through the OR element 11 to the enable input register entries 19. As a result, the multiplexer 3 switches its third inputs to the outputs, and the remainder code is written from the outputs of the adder 14 to the register 19. As a result, from the output of register 19, the remainder of the product modulo arrives at the first input of the comparison circuit 16, and the pulse of the end of the formation of the remainder from the output of the OR element 6 is fed to the control input of the comparison circuit 16, allowing comparison of the remainder of the product modulo and the field element supplied to device input. If the remainder of the product is not equal to the field element, then the output is not "equal" to the comparison circuit 16, the pulse is supplied to the first input of the OR element 7 and from its output to the triggering input of the multiplication block. The formation process is repeated first, and the number of multiplication is counted by the counter 2. From the output of the counter 2, which is the output of the device, the index of the elements of the multiplicative groups is taken in parallel binary code. If the remainder of the product modulo is numerically equal to the field element, then the output is equal to the comparison circuit 16 and an impulse arrives that resets the register of the multiplicable multiplication unit 1, stops the operation of counter 2 and goes to the output of the end of the calculation, indicating that the calculation is complete, and at the outputs of the counter 2, an index is generated from the given field element by the antiderivative element.

If in the process of comparing the product code and the module code, the pulse appears at the output “equals” the comparison circuit 17, this indicates that the remainder of the product code is equal to the module P _j , which means that the product code is identically equal to zero. In this case, the pulse from the output is "equal to" the comparison circuit 17, passing through the OR element 10, zeroes the register 19 and through the OR element 6 enters the control input of the comparison circuit 16.

The appearance of the pulse at the output of "more" of the comparison circuit 17 indicates that the formation of the remainder is not completed. The pulse from the output "more" of the comparison circuit 17 is supplied to the control input of the comparison circuit 18, allowing comparison of codes of numbers acting on its inputs. In this case, the module code P _j acts on its first inputs, and the code of the number from the output of the subtractor 15, numerically equal to the difference of the code of the number from the output of the adder 14 and the module code, acts on the second inputs. If, as a result of the operation of the comparison circuit 18, the pulse appears “equal to” at its output, then this indicates that the product code is identically equal to zero modulo P _j . This pulse, passing through the element OR 10, is fed to the nulling input of the register 19 and to the second input of the element OR 6.

 If the pulse appears at the output “less” than the comparison circuit 18, then this also indicates that the formation of the residue is completed. This pulse through the OR element 9 is fed to the first control input of the multiplexer 3 and through the OR element 11 to the write enable input of the register 19. As a result, the outputs of the multiplexer 3 are switched with its second inputs and the number code from the outputs of the subtractor 15 is written to the register 19. at the control input of the comparison circuit 16, an impulse of the end of the remainder formation appears.

 If the pulse appears at the output of "more" of the comparison circuit 18, then this indicates that the formation of the remainder is not yet completed. This pulse enters through the element OR 9 to the first control input of the multiplexer 3, commuting its outputs with its second inputs, as well as to the second input of the element OR 8. In this case, the code 20 from the outputs of the subtractor 13 is recorded in the register 20, which acts on the information inputs of the register 20 through the multiplexer 3. The process of forming the remainder continues until at the outputs of the adder 14 or subtractor 15 there is a number less than or equal to the module.

 By setting the next element and applying a pulse to the input of the beginning of the calculation, we obtain the index of this field element at the outputs of the device counter 2, etc. Moreover, the formation of field indices can occur with various primitive elements, as well as in different fields GF (P). (56) Copyright certificate of the USSR N 1633495, cl. H 03 M 7/18, 1989.

 USSR author's certificate N 1686702, cl. H 03 M 7/18, 1989.

Claims (1)

 DEVICE FOR FORMING INDEXES OF ELEMENTS OF MULTIPLICATIVE GROUPS OF GALOIS FIELDS GF (P), containing a multiplication block, counter, first delay element, first, second and third OR elements, a subtractor, first and second comparison schemes and first and second registers, and the input of the beginning of the device's calculations connected to the input of the first delay element, the input of the setting to "0" counter and the input of the unit value recording to the multiplication unit, the output of the first delay element is connected to the first input of the second OR element, the output of which is connected to the input of the bit Solutions of multiplication of the multiplication block, the inputs of the bits of the element of the field of the device are connected respectively to the inputs of the first group of the first comparison circuit, the inputs of the second group of which are connected respectively to the bit outputs of the first register and the inputs of the multiplier of the multiplication block, the inputs of the multiplicable of which are connected to the inputs of the antiderivative element of the device, the inputs of the bits of the module which are connected respectively to the inputs of the first groups of the subtractor and the second comparison circuit, the output of the end of the multiplication of the multiplication block is connected to the first input of the third OR element and with a counting input of the counter, the output resolution enable input of which is connected to the installation input at “0” of the multiplication unit and the output “Equal” of the first comparison circuit, the output of “Not equal” of which is connected to the second input of the second OR element, recording permission inputs and the settings in "0" of the first register are connected respectively to the first and second inputs of the first OR element, the output of which is connected to the control input of the first comparison circuit, and the counter output is an information output of the device, characterized in that, with In order to increase the speed, a multiplexer, a second delay element, a fourth, fifth and sixth OR element, a memory block, a key block, an adder and a third comparison circuit are introduced into it, and the outputs of the multiplication block are connected to the information inputs of the first group of the multiplexer, the information inputs of the second group of which connected respectively to the inputs of the first group of the third comparison circuit and the outputs of the subtractor, the inputs of the second group of which are connected respectively to the information inputs of the third group of the multiplexer, the input the second group of the second comparison circuit and the outputs of the adder, the inputs of which are connected respectively to the outputs of the key block, the inputs of the first group of which are connected to the outputs of the memory block, the address inputs of which are connected to the inputs of the bits of the device module and the inputs of the second group of the third comparison circuit, the inputs of the second group a block of keys connected to the outputs of the second register, the information inputs of which are connected respectively with the information inputs of the first register and the outputs of the multiplexer, the first control input cat It is connected to the output of the fourth OR element, the first input of which is connected to the second input of the third OR element and the output “More” of the third comparison circuit, the output “Less” of which is connected to the second input of the fourth OR element and the first input of the sixth OR element, the second input of which is connected with the second control input of the multiplexer and the output "Less" of the second comparison circuit, the output of "Equal to" which is connected to the first input of the fifth OR element, the second input of which is connected to the output of "Equal" of the third comparison circuit, the output of the third element OR is connected to the control input of the memory block, the recording enable input of the second register and the input of the second delay element, the output of which is connected to the control input of the second comparison circuit, the output of "More" of which is connected to the control input of the third comparison circuit, the outputs of the fifth and sixth elements OR are connected respectively, with the installation input at “0” and the first register write enable input.