RU2007038C1

RU2007038C1 - Device which produces indexes of members of multiplicative groups of galois fields gf(p)

Info

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

Abstract

FIELD: computer engineering. SUBSTANCE: device has multiplication unit 1, two commutators 2, 3, subtraction unit 4, register 5, AND gates unit 6, two comparison circuits 7, 8, two pulse generators 9, 10, counter 11, adder 12, memory unit 13, OR gate 14, AND gate 15. EFFECT: increased speed. 1 dwg

Description

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей. The invention relates to computer technology and can be used in devices for generating code sequences, the construction of which is based on the theory of finite fields.

Известно устройство для формирования остатка по произвольному модулю от числа [1] . A device is known for generating a remainder modulo an arbitrary modulus of a number [1].

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

Известно устройство для формирования остатка по произвольному модулю от числа, содержащее вычитатель, первый и второй блоки сравнения, два регистра, две группы элементов ИЛИ, два формирователя импульсов, блок умножения, счетчик, третий элемент ИЛИ и элемент задержки с соответствующими связями и позволяющее формировать индексы элементов мультипликативных групп полей Галуа GF(P) [2] . A device is known for generating a remainder modulo an arbitrary number, containing a subtractor, first and second comparison blocks, two registers, two groups of OR elements, two pulse shapers, a multiplication unit, a counter, a third OR element and a delay element with corresponding connections and allowing the formation of indices elements of multiplicative groups of Galois fields GF (P) [2].

Недостатком устройства является низкое быстродействие формирования индексов элементов мультипликативных групп, так как для каждого элемента а поля процедура формирования индекса r по основанию θ сводится к умножению θ на единицу, затем на θ , приведению к заданному модулю Р, далее умножению результата приведения по модулю на элемент θ и т. д. до тех пор, пока приведенный по модулю указанный выше результат умножения станет численно равен значению элемента поля а. В этом случае количество выполненных умножений численно равно индексу r элемента а по основанию θ в поле GF(P). The disadvantage of this device is the low speed of forming indices of elements of multiplicative groups, since for each element of a field, the procedure for forming the index r on the basis of θ is reduced to multiplying θ by one, then by θ, converting to a given module P, then multiplying the result of casting modulo by element θ, etc., until the multiplication result indicated above modulo becomes numerically equal to the value of the field element a. In this case, the number of multiplications performed is numerically equal to the index r of the element a at the base θ in the field GF (P).

Цель изобретения - повышение быстродействия. The purpose of the invention is improving performance.

Цель достигается тем, что в устройство для формирования индексов элементов мультипликативных групп полей Галуа GF(P), содержащее блок умножения, вычитатель, первую схему сравнения, регистр, два коммутатора, блок элементов И, элемент ИЛИ, два формирователя импульсов, счетчик, вторую схему сравнения и элемент задержки, причем входы разрядов модуля устройства соединены с входами соответствующих разрядов вычитаемого вычитателя и соответствующими входами первой группы первой схемы сравнения, входы второй группы которой подключены к разрядным выходам первого коммутатора, первые и вторые входы которого попарно объединены с первыми и вторыми входами второго коммутатора, выходы которого соединены с входами соответствующих разрядов уменьшаемого вычитателя, выходы разрядов которого соединены с соответствующими информационными входами регистра, выходы разрядов которого через блок элементов И соединены с первыми входами первого коммутатора, выход элемента ИЛИ соединен с входом разрешения сравнений первой схемы сравнения, выход "больше" которой соединен с входом разрешения вычитателя и входом первого формирователя импульсов, выход которого соединен с входом разрешения записи регистра и входом второго формирователя импульсов, выход которого соединен с вторыми входами блока элементов И и с первым входом элемента ИЛИ, второй вход которого соединен со счетным входом счетчика, вход начало вычисления устройства соединен с входом установки в нулевое состояние счетчика, входы записи первообразного элемента поля устройства являются первыми входами блока умножения, информационные выходы которого соединены с вторыми входами блока элементов ИЛИ, введены блок памяти, сумматор и элемент И, при этом входы разрядов модуля устройства дополнительно соединены с первыми входами второй схемы сравнения, вторые входы которой соединены с информационными выходами сумматора, на первые входы которого постоянно подается код числа "два", а вторые входы соединены с информационными выходами счетчика и информационными входами блока памяти, вход записи которого соединен с входом элемента задержки и выходом "меньше" первой схемы сравнения, а адресные входы соединены с вторыми входами блока умножения, выходами первого коммутатора и являются входами разрядов элементов поля устройства, вход начала вычисления устройства соединен с младшим разрядом входа первой группы первого коммутатора и с третьим входом элемента ИЛИ, выход элемента задержки соединен с вторым входом элемента ИЛИ и с первым входом элемента И, второй вход которого соединен с выходом "равно" второй схемы сравнения, а выход является выходом окончания работы устройства, вход чтения блока памяти является входом считывания устройства, а выходы блока памяти - информационными выходами устройства, выход второго формирователя импульсов дополнительно соединен с управляющими входами первого и второго коммутаторов. 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 subtractor, a first comparison circuit, a register, two switches, an AND block, an OR element, two pulse shapers, a counter, a second circuit comparison and a delay element, and the inputs of the bits of the device module are connected to the inputs of the corresponding bits of the subtracted subtractor and the corresponding inputs of the first group of the first comparison circuit, the inputs of the second group of which are connected to the bit the outputs of the first switch, the first and second inputs of which are paired with the first and second inputs of the second switch, the outputs of which are connected to the inputs of the corresponding bits of the diminishing subtracter, the outputs of the bits of which are connected to the corresponding information inputs of the register, the outputs of the bits of which through the block of elements And are connected to the first inputs of the first switch, the output of the OR element is connected to the input of the resolution of comparisons of the first comparison circuit, the output of "more" of which is connected to the input of the resolution of the calcul device and the input of the first pulse shaper, the output of which is connected to the register enable input and the input of the second pulse shaper, the output of which is connected to the second inputs of the block of AND elements and the first input of the OR element, the second input of which is connected to the counter input of the counter, the input begins to calculate the device connected to the input of the installation in the zero state of the counter, the recording inputs of the antiderivative element of the device field are the first inputs of the multiplication unit, the information outputs of which are connected to the second the inputs of the block of OR elements, a memory block, an adder and an AND element are introduced, while the inputs of the bits of the device module are additionally connected to the first inputs of the second comparison circuit, the second inputs of which are connected to the information outputs of the adder, the first inputs of which are constantly supplied with the code of the number “two”, and the second inputs are connected to the information outputs of the counter and the information inputs of the memory block, the recording input of which is connected to the input of the delay element and the output is "less" of the first comparison circuit, and the address inputs are connected to by the inputs of the multiplication block, the outputs of the first switch and are the inputs of the bits of the elements of the field of the device, the input of the beginning of the calculation of the device is connected to the lowest bit of the input of the first group of the first switch and to the third input of the OR element, the output of the delay element is connected to the second input of the OR element and to the first input of the element And, the second input of which is connected to the output "equals" the second comparison circuit, and the output is the output of the end of the device, the read input of the memory block is the read input of the device, and the outputs are memory lock - information outputs of the device, the output of the second pulse shaper is additionally connected to the control inputs of the first and second switches.

Сущность изобретения заключается в том, что предварительно для всех индексов r_i ((i= 0,

)) первообразного элемента θ поля GF(P) находятся элементы a ∈ GF(P), которые определяют адрес блока памяти, в информационные ячейки которого записываются значения r_i. В рабочем режиме элементы a ∈ GF(P) подаются на адресные входы блока памяти, в режиме чтения которого с его информационных выходов снимаются коды индексов r_i.The essence of the invention lies in the fact that previously for all indices r _i ((i = 0,

)) of the primitive element θ of the field GF (P), there are elements a ∈ GF (P) that determine the address of the memory block into the information cells of which r _i values are written. In the operating mode, elements a ∈ GF (P) are supplied to the address inputs of the memory block, in the reading mode of which index codes r _i are removed from its information outputs.

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

Устройство содержит блок 1 умножения, первый 2 и второй 3 коммутаторы, вычитатель 4, регистр 5, блок 6 элементов И, первую и вторую схемы 7 и 8 сравнения, первый и второй формирователи 9 и 10 импульсов, счетчик 11, сумматор 12, блок 13 памяти, элементы ИЛИ 14, И 15 и элемент 16 задержки. Вход 17 начала вычисления устройства соединен с обнуляющим входом счетчика 11, третьим входом элемента ИЛИ 14 и с выходом первого разряда блока 1 умножения. Входы 18 разрядов модуля устройства соединены с входами соответствующих разрядов вычитаемого вычитателя 4, соответствующими информационными входами первой группы первой схемы 7 сравнения и первыми входами второй схемы 8 сравнения. Входы 19 задания первообразного элемента поля соединены с первыми информационными входами блока 1 умножения. Входы 20 разрядов элемента поля соединены с вторыми информационными входами блока 1 умножения, с информационными входами второй группы первой схемы 7 сравнения и адресными входами блока 13 памяти. Вход 21 чтения соединен с вторым управляющим входом блока 13 памяти. Выход 22 является выходом окончания процесса записи индексов, а выходы 23 являются информационными выходами устройства. The device comprises a multiplication unit 1, first 2 and second 3 switches, a subtractor 4, a register 5, a block of 6 And elements, a first and second comparison circuit 7 and 8, a first and second pulse shaper 9 and 10, a counter 11, an adder 12, a block 13 memory, elements OR 14, AND 15 and delay element 16. The input 17 of the beginning of the calculation of the device is connected to the zeroing input of the counter 11, the third input of the OR element 14 and with the output of the first discharge of the multiplication unit 1. The inputs 18 bits of the device module are connected to the inputs of the corresponding bits of the subtracted subtractor 4, the corresponding information inputs of the first group of the first comparison circuit 7 and the first inputs of the second comparison circuit 8. The inputs 19 of the job of the primitive field element are connected to the first information inputs of the multiplication unit 1. The inputs 20 bits of the field element are connected to the second information inputs of the multiplication unit 1, with the information inputs of the second group of the first comparison circuit 7 and the address inputs of the memory unit 13. A read input 21 is connected to a second control input of the memory unit 13. Output 22 is the output of the end of the index recording process, and outputs 23 are information outputs of the device.

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

В исходном состоянии регистр 5 обнулен, в блоке 13 памяти информация отсутствует, на вторые входы сумматора 12 подан код числа "два". In the initial state, the register 5 is reset, in the memory block 13 there is no information, the code of the number two is supplied to the second inputs of the adder 12.

Модуль, по которому определяется порядок поля GF(P), задается параллельным двоичным кодом, подаваемым на вход 18 модуля устройства. Код первообразного элемента θ, по которому предлагается формировать индексы, подается на вход 19. Импульс начала вычисления поступает на вход 17 "Начало вычислений". Этот импульс обнуляет счетчик 11, через коммутатор 3 поступает на вход вычитателя, через коммутатор 2 поступает на вход схемы 7 сравнения, а, пройдя через третий вход элемента ИЛИ 14, разрешает сравнение кода единицы с кодом модуля. При этом схема 7 сравнения на выход "меньше" выдает импульс, который поступает на вход элемента 16 задержки и на вход записи блока 13 памяти. На адресные входы блока 13 памяти с выходов коммутатора 2 поступает код единицы, а на информационных входах информация отсутствует, так как счетчик 11 обнулен. Поэтому по первому адресу блока 13 памяти записывается код нуля. После записи кода нуля на выходе элемента 16 задержки появляется импульс, который поступает на первый вход элемента И 15, записывает единицу в счетчик 11 и поступает на второй вход элемента ИЛИ 14. На выход элемента И 15 импульс не проходит, так как с выхода схемы 8 сравнения на второй его вход поступает нулевой потенциал. The module by which the field order GF (P) is determined is defined by a parallel binary code supplied to the input 18 of the device module. The code of the antiderivative element θ, according to which it is proposed to form indices, is fed to input 19. The pulse of the beginning of the calculation goes to the input 17 "Start of calculations". This pulse resets the counter 11, through the switch 3 it enters the input of the subtractor, through the switch 2 it enters the input of the comparison circuit 7, and, passing through the third input of the OR element 14, it allows the comparison of the unit code with the module code. In this case, the comparison circuit 7 outputs an “less” output pulse, which is fed to the input of the delay element 16 and to the recording input of the memory unit 13. A unit code is supplied to the address inputs of the memory unit 13 from the outputs of the switch 2, and information is absent at the information inputs, as the counter 11 is reset. Therefore, a zero code is recorded at the first address of the memory unit 13. After recording the zero code at the output of the delay element 16, a pulse appears that arrives at the first input of the AND element 15, writes the unit to the counter 11 and goes to the second input of the OR element 14. The pulse does not pass to the output of the And 15 element, since the output of circuit 8 Comparison at its second input receives zero potential.

Так как одновременно с процессом записи информации в блок 13 памяти в блоке 1 умножения происходит перемножение кода первообразного элемента, поступающего на вход 19 устройства, с кодом, поступающим с выходов коммутатора 2, то импульс, поступающий с выхода элемента ИЛИ 14 в схему 7 сравнения, разрешает сравнение кода произведения с кодом модуля. Since simultaneously with the process of recording information in the memory unit 13 in the multiplication unit 1, the code of the antiderivative element arriving at the input of the device 19 is multiplied with the code coming from the outputs of the switch 2, the pulse coming from the output of the OR element 14 to the comparison circuit 7, Allows comparing the product code with the module code.

Если код произведения меньше кода модуля, то устройство работает так, как описано выше, причем адрес блока памяти определяется состоянием выходов блока 1 умножения, а записываемая информация определяется состоянием счетчика 11. If the product code is less than the module code, then the device operates as described above, and the address of the memory block is determined by the state of the outputs of the multiplication block 1, and the recorded information is determined by the state of the counter 11.

Если произведение по своему значению больше модуля, схема 7 сравнения выдает импульс на выход "больше". Этот импульс поступает на вход формирователя 9 импульсов и на вход разрешения вычитания вычитателя 4. На вход вычитаемого вычитателя 4 поступает значение модуля с входа 18 устройства, а на вход уменьшаемого - значение произведения через коммутатор 3. Значение разности с выхода вычитателя 4 под воздействием импульса, сформированного формирователем 9 импульсов, по фронту входного импульса записывается в регистр 5. По срезу импульса, сформированного формирователем 9, формирователь 10 импульсов выдает сигнал, который открывает блок 6 элементов И, поступает через элемент ИЛИ 14 на вход разрешения схемы 7 сравнения и, воздействуя на управляющие входы коммутаторов 2 и 3, подключает выходы блока 6 элементов И к входам уменьшаемого вычитателя 4 и к входам схемы 7 сравнения. Код разности, записанный в регистр 5, через блок 6 элементов И и коммутатор 2 поступает на входы схемы 7 сравнения, на вторые входы которой поступает с входа 18 код модуля. Под действием импульса с выхода элемента ИЛИ 14 схема 7 сравнения сравнивает коды чисел, поступающих на его входы. If the product in its value is larger than the module, the comparison circuit 7 gives a pulse to the output "more". This pulse is fed to the input of the pulse shaper 9 and to the input of the subtractor 4 subtraction. The input of the subtracted subtractor 4 receives the module value from the input 18 of the device, and the input of the subtracted subtracter receives the value of the product through the switch 3. The difference value from the output of the subtractor 4 under the influence of the pulse, generated by the shaper 9 pulses along the front of the input pulse is recorded in register 5. By the slice of the pulse generated by the shaper 9, the shaper 10 pulses generates a signal that opens the block 6 of the elements And, stumble through an OR gate 14 to enable input of comparison circuit 7 and acting on the control inputs of the switches 2 and 3, connects the outputs of the AND unit 6 to the minuend input of subtractor 4 and to the inputs of the comparison circuit 7. The difference code recorded in register 5, through block 6 of AND elements and switch 2 is fed to the inputs of the comparison circuit 7, to the second inputs of which the module code is received from input 18. Under the influence of a pulse from the output of the OR element 14, the comparison circuit 7 compares the codes of the numbers received at its inputs.

В результате сравнения могут возникнуть две ситуации, при которых схема 7 сравнения выдает импульс в зависимости от результатов сравнения на один из своих двух выходов. Процесс вычисления остатка по модулю от произведения продолжается до тех пор, пока полученное в результате вычитания значение окажется меньше величины модуля. В результате с выхода регистра 5 через блок 6 элементов И и коммутатор 2 код остатка поступает на адресные входы блока 13 памяти, в ячейки памяти которого записывается информация о состоянии счетчика 11. As a result of the comparison, two situations may arise in which the comparison circuit 7 gives an impulse, depending on the comparison results, to one of its two outputs. The process of calculating the remainder modulo the product continues until the value obtained by subtraction is less than the modulus. As a result, from the output of register 5 through block 6 of AND elements and switch 2, the remainder code is sent to the address inputs of memory block 13, in the memory cell of which information about the status of counter 11 is recorded.

Работа устройства в таком режиме продолжается до момента поступления на вход счетчика 11 Р - 2 импульсов. Как только счетчик 11 сосчитает Р - 2 импульса, на выходе сумматора 12 появляется код модуля, поэтому на выходе схемы 8 сравнения появляется сигнал, поступающий на второй вход элемента И 15. Поэтому очередной импульс, поступающий с выхода элемента 16 задержки на первый вход элемента И 15, поступает на выход 22 устройства, сигнализируя об окончании процесса записи информации в блок 13 памяти. The operation of the device in this mode continues until the moment at the input of the counter 11 P - 2 pulses. As soon as the counter 11 counts P - 2 pulses, the module code appears at the output of the adder 12, therefore, at the output of the comparison circuit 8, a signal appears at the second input of the element And 15. Therefore, the next pulse coming from the output of the delay element 16 to the first input of the element And 15, is output 22 of the device, signaling the end of the process of recording information in block 13 of the memory.

В рабочем режиме на вход 20 устройства подаются коды элементов поля, которые определяют адрес памяти блока 13, а на вход 21 подаются импульсы считывания. При этом с выходов 23 устройства снимаются коды индексов элементов мультипликативных групп полей Галуа. Например, для поля GF(P) при θ = 3 по первому адресу записывается код нуля, по третьему адресу - код единицы, по второму адресу - код двойки, по шестому адресу - код тройки, по четвертому адресу - код четверки и по пятому адресу - код пятерки. Поэтому в процессе формирования индексов на адресные входы блока 13 памяти подаются коды элементов поля, а с выходов в режиме чтения снимаются коды индексов. In the operating mode, codes of field elements that determine the memory address of block 13 are supplied to the input 20 of the device, and read pulses are sent to input 21. In this case, the codes of indices of elements of multiplicative groups of Galois fields are removed from the outputs 23 of the device. For example, for the field GF (P) with θ = 3, the zero code is written at the first address, the unit code at the third address, the two code at the second address, the three code at the sixth address, the four code at the fourth address and the fifth address - five code. Therefore, in the process of forming the indices, the codes of the field elements are supplied to the address inputs of the memory unit 13, and the codes of the indices are removed from the outputs in the reading mode.

Для формирования индексов элементов мультипликативных групп других полей стирается информация с блока 13 памяти, на входы устройства подаются коды нового модуля и первообразного элемента, производится запись в блок памяти, а затем осуществляются процессы формирования индексов путем подачи кодов элементов поля на адресные входы и считывания информации из блока 13 памяти. (56) Авторское свидетельство СССР N 1396281, кл. H 03 M 7/18, 1986. To form indices of elements of multiplicative groups of other fields, information from the memory unit 13 is erased, codes of a new module and antiderivative element are sent to the device inputs, a memory block is written, and then index formation processes are carried out by supplying field element codes to address inputs and reading information from block 13 memory. (56) Copyright certificate of the USSR N 1396281, cl. H 03 M 7/18, 1986.

Авторское свидетельство СССР N 1686702, кл. H 03 M 7/18, 1989. USSR author's certificate N 1686702, cl. H 03 M 7/18, 1989.

Claims

DEVICE FOR FORMING INDEXES OF ELEMENTS OF MULTIPLICATIVE GROUPS OF GALOIS FIELDS GF (P), containing a multiplication unit, first and second switches, a subtractor, a register, an AND block, the first and second comparison circuits, the first and second pulse shapers, the counter, the OR element, and the delay element OR moreover, the inputs of the discharges of the device module are connected respectively to the inputs of the subtracted subtractor and 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 switch a, the inputs of the first group of which are connected respectively to the bit outputs of the multiplication unit and the inputs of the first group of the second switch, the inputs of the second group of which are connected respectively to the inputs of the second group of the first switch and with the outputs of the block of elements AND, the first inputs of which are connected respectively to the bit outputs of the register, information the inputs of which are connected respectively to the bit outputs of the subtractor, the inputs of which is reduced which are connected respectively to the bit outputs of the second switch, in the strokes of the discharges of the primitive element of the field of the device are connected respectively to the inputs of the first group of the multiplication block, the output of the OR element is connected to the control input of the first comparison circuit, the output of "More" of which is connected to the control input of the subtractor and the input of the first pulse shaper, the output of which is connected to the register enable input and with the input of the second pulse shaper, the output of which is connected to the second inputs of the block of AND elements and with the first input of the OR element, the second input of which is connected to the counting input ohm of the counter, the input of the setting “0” of which is connected to the input of the beginning of the device’s calculations, characterized in that, in order to improve performance, a memory block, an adder and an AND element are introduced into it, and the inputs of the bits of the device module are connected respectively to the inputs of the first group of the second comparison circuits, the inputs of the second group of which are connected respectively to the bit outputs of the adder, the inputs of the first group of which are connected to the code bus of the number two devices, and the inputs of the second group of the adder are connected respectively to the bit counter moves and information inputs of the memory block, whose address inputs are connected respectively to the inputs of the second group of the multiplication block, the bit outputs of the first switch and the bit inputs of the device field elements, the output of the second pulse shaper is connected to the control inputs of the first and second switches, the output is “Less” of the first circuit comparison is connected to the recording input of the memory unit and to the input of the delay element, the output of which is connected to the second input of the OR element and to the first input of the AND element, the second input of which the second one is connected to the output of “Equal to” the second comparison circuit, and the output of the AND element is the output of the device’s end of operation, the input of the beginning of the device’s calculations is connected to the low-order bit of the input of the first group of the first switch and the third input of the OR element, and the read input of the device is connected to the block read permission input memory, the bit outputs of which are the information outputs of the device.