RU2829089C1 - Modulus multiplier - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: device comprises switches, adders, three-input adders, which contain single-bit full adders and (m+1)-bit adder, and five-input multiplexers; wherein when calculating the product of numbers modulo P by successively performing (n/2) operations, where n is the number of bits of the input number A, reduction of calculation results by an arbitrary modulus at each conversion stage is performed in one step, simultaneously with the operation of summation of intermediate calculations.

EFFECT: faster operation of the device.

1 cl, 2 dwg

Description

Region techniques, To which refers to invention

The invention relates to computing technology and can be used in digital computing devices, in cryptographic applications, as well as in digital signal processing devices and in control systems.

Level techniques

A multiplier by two modulo is known, containing an adder and a multiplexer [1]. The device is a solution in the field of multiplying numbers by two modulo an arbitrary number. It includes an adder and a multiplexer, which together provide increased efficiency and speed of the multiplication process. The disadvantage of this device is its limited functionality, namely the lack of the ability to multiply by a number other than two.

A device for multiplying numbers by an arbitrary modulus is known, containing adders, multiplexers, keys, shift units, an inverter and an adder by modulus [2]. The device is an effective solution for multiplying numbers by an arbitrary modulus. This device offers advanced functionality that can be used in digital computing devices and systems for forming elements of finite fields. The disadvantage of this device is low performance, since multiplication is performed in ( n − 1) successive conversion steps, where n is the capacity of the device.

The closest in technical essence to the claimed invention is a modulo multiplier containing keys, adders, multiplexers [3], selected as a prototype. A modulo multiplier allows multiplying two numbers by an arbitrary modulus in n /2 stages of conversion, forming conversion steps, where n is the bit depth of the device, simultaneously processing two digits of the multiplicand. However, at each conversion step, the reduction of the calculation results by an arbitrary modulus is performed in two steps, first the operation of summing the intermediate calculations is performed, and then the reduction of the obtained value by modulus is performed, which reduces the speed of the device.

The technical result of the invention is increased performance.

Disclosure entities inventions

In order to achieve the technical result in a modulo multiplier containing multiplicand code inputs, multiplier code inputs, product code outputs, n /2 conversion stages, where n is the device bit depth, and the first conversion stage contains n /2 nodes, and the (2… n /2)-th conversion stages contain one node each, each conversion node of the first conversion stage contains the first and second keys, a two-input adder and a three-input multiplexer, and the conversion nodes of the (2… n /2)-th conversion stages contain two-input adders and five-input multiplexers, the information inputs of all keys of the first conversion stage are connected to the multiplier code inputs, the control inputs are connected to the corresponding bits of the multiplicand code, the information outputs of the first keys of each node of the first conversion stage are connected to the first information inputs of the corresponding two-input adders with a shift of one bit toward the higher ones, the information outputs of the second keys of each node of the first conversion stage are connected to the second information inputs of the corresponding two-input adders, the information outputs of the two-input adders are connected to the first information inputs of the corresponding three-input multiplexers, the information outputs of the three-input multiplexer of the first node of the first conversion stage are connected with a shift of two bits toward higher digits to the first information inputs of the two-input adder of the second conversion stage, the information outputs of the three-input multiplexers of the j -th node of the first conversion stage, where j = 2… n /2, are connected to the second information inputs of the two-input adders of the j -th conversion stage, the information outputs of the two-input adders of the j -th conversion stage are connected to the first information inputs of the corresponding five-input multiplexers, the information outputs of the five-input multiplexers of the j -th conversion stage, where j = 2,…, n /2−1 are connected with a shift of two bits toward higher digits to the first information inputs of the two-input adders of the ( j +1)-th conversion stage, and n /2-th stage of the transformation are the outputs of the product codes additionally introduced at the first stage of the transformation into each node the first and second three-input adders, and at the (2… n /2)-th stage of the transformation the first, second, third and fourth three-input adders are introduced, wherein the first information inputs of the first and second three-input adders of the first stage of the transformation are connected to the information outputs of the first keys of the corresponding node with a shift of one bit towards the most significant, the second information inputs are connected to the information outputs of the second keys of the corresponding node, the inverse code of the modulus is fed to the third information inputs of the first three-input adders, and the inverse code of the doubled modulus is fed to the third information inputs of the second three-input adders, the information outputs of the first three-input adders are connected to the second information inputs of the corresponding three-input multiplexers, the information outputs of the second three-input adders are connected to the third information inputs of the corresponding three-input multiplexers, the carry outputs of the first three-input adders are connected to the first control inputs of the corresponding three-input multiplexers, the carry outputs of the second three-input adders are connected to the second control inputs of the corresponding three-input multiplexers, the first information inputs of the first, second, third and fourth three-input adders of the second conversion stage are connected with a shift of two bits toward the higher bits to the information outputs of the three-input multiplexer of the first node of the first conversion stage, the second information inputs of the first, second, third and fourth three-input adders of the j -th conversion stage, where j = 2… n /2, are connected to the information outputs of the three-input multiplexer of the j -th node of the first conversion stage, the third information inputs of the first, second, third and fourth three-input adders of the j -th conversion stage are fed, respectively, with the inverse codes of the modulus, the inverse codes of the doubled modulus, the inverse codes of the tripled modulus and the inverse codes of the quadrupled modulus, the carry inputs of all three-input adders are supplied with a logical one signal, wherein each three-input adder contains m full single-bit adders and an ( m +1)-bit adder, the (1… m )-th bits of the information outputs of which are the information outputs of the three-input adder, and the ( m +1)-th bit is the carry output of the three-input adder, the first information inputs of the full single-bit adders are connected to the corresponding bits of the first information inputs of the three-input adder, the second information inputs are connected to the corresponding bits of the second information inputs of the three-input adder, the third information inputs are connected to the corresponding bits of the third information inputs of the three-input adder, the information outputs of the (1… m )-th full single-bit adders are connected to the (1… m )-th bits of the first information inputs of the ( m +1)-bit adder, and the carry outputs are connected to the (2… m +1)-th bits of the second information inputs of the ( m +1)-bit adder, the first bit of which is connected to the carry input of the three-input adder, a logical zero signal is fed to the ( m +1)-th bit of the first information inputs of the ( m +1)-bit adder.

The essence of the invention lies in the implementation of the following method for calculating the product of numbers A and B modulo P. Let

( A B ) ≡ R (mod P ), (1)

where A is a non-negative integer which is the multiplicand;

B is a non-negative integer that is a factor, where B<P ;

P is a non-negative integer called the modulus;

R is a non-negative integer that is the remainder of the product of numbers A and B modulo P , R <P .

In this case, let

A = a _{n −1} 2 ^{n −1} + a _{n −2} 2 ^{n −2} + a _{n −3} 2 ^{n −3} + a _{n −4} 2 ^{n −4} + . . . + a ₃ 2 ³ + a ₂ 2 ² + a ₁ 2+ a ₀ , (2)

B = b _{m −1} · 2 ^{m −1} + . . . + b ₁ 2+ b ₀ , (3)

P = p _{m −1} · 2 ^{m −1} + . . . + p ₁ 2 ¹ + p ₀ , (4)

R = r _{m −1} · 2 ^{m −1} + . . . + r ₁ 2 ¹ + r ₀ , (5)

where a _i , – coefficients that take the value 0 or 1 depending on the value of the number A ;

n is the number of digits in the representation of the multiplicand, n is even;

b _i , – coefficients that take the value 0 or 1 depending on the value of the number B ;

p _i , – coefficients that take the value 0 or 1 depending on the value of the modulus P ;

r _i , – coefficients that take the value 0 or 1 depending on the value of the remainder R ;

m is the number of digits in the representation of the multiplier B , the modulus P and the remainder R.

Let us represent the product of numbers A and B as follows:

A · B = ( a _{n −1} · 2 ^{n −1} + a _{n −2} · 2 ^{n −2} + a _{n −3} · 2 ^{n −3} + a _{n −4} · 2 ^{n −4} + . . + a ₃ 2 ³ + a ₂ 2 ² + a ₁ 2+ a ₀ ) B. (6)

Let us rewrite expression (6) as follows:

A B = ( a _{n −1} 2 ^{n −1} B + a _{n −2} 2 ^{n −2} B + a _{n −3} 2 ^{n −3} B + a _{n −4} 2 ^{n −4} B +...

... + a ₃ 2 ³ B + a ₂ 2 ² B + a ₁ 2 B + a ₀ B ), (7)

Let us transform expression (7) into the following form by combining two adjacent terms:

A·B= (a _{n -1} ·2 ^{n -1}·B+a _{n -2} ·2 ^{n -2}·B)+ (a _{n -3} ·2 ^{n -3}·B+a _{n -4} ·2 ^{n -4}·B)+ . . .

. . . +( a ₃ 2 ³ B + a ₂ 2 ² B )+( a ₁ 2 B + a ₀ B ), (8)

From each sum in brackets in expression (8), we take 2 ⁱ out of the brackets, where , takes only even values:

A · B = 2 ^{n −2} ( a _{n −1} · 2 · B + a _{n −2} · B )+2 ^{n −4} ( a _{n −3} · 2 · B + a _{n −4} · B )+ . . .

. . . +2 ² ( a ₃ 2 B + a ₂ B )+( a ₁ 2 B + a ₀ B ), (9)

In expression (9), before each of the n /2 resulting sums of the form
( a _{i +1} · 2· B + a _i · B ), we obtain the factor 2 ⁱ , where , takes only even values.

Next, we factor out the smallest non-zero power of 2 in (9):

A·B= 2²(2 ^{n -4}(a _{n -1} ·2·B+a _{n -2}·B)+ 2 ^{n -6}(a _{n -3} ·2·B+a _{n -4}·B)+ . . .

. . . + ( a ₃ 2 B + a ₂ B ))+( a ₁ 2 B + a ₀ B ), (10)

By sequentially performing the transformation (10) ( n /2)-2 times we obtain:

A · B = 2 ² (2 ² …(2 ² ( a _{n -1} · 2· B + a _{n -2} · B )+( a _{n -3} · 2· B + a _{n -4} · B ))+ .

. . . + ( a ₃ 2 B + a ₂ B ))+( a ₁ 2 B + a ₀ B ), (11)

where 2 ² occurs ( n /2)−1 times.

Then expression (1) can be represented as follows:

A · B ≡ (2 ² (2 ² …(2 ² ( a _{n −1} · 2· B + a _{n −2} · B )+( a _{n −3} · 2· B + a _{n −4} · B )) + .

. . . + ( a ₃ 2 B + a ₂ B ))+( a ₁ 2 B + a ₀ B )) mod P . (12)

From number theory it is known that the operation of modulo reduction is invariant to addition and multiplication, i.e. the value of the remainder does not depend on whether it is calculated from the sum (product) or from each term (factor), and then the corresponding partial remainders are summed (multiplied) and the remainder is calculated from the result modulo.

Based on the above, expression (12) can be calculated as follows.

At the first stage of the transformation, the values t _{1 i} are calculated simultaneously in ( n /2) nodes, :

t ₁₁ =( a _{n −1} · 2 · B + a _{n −2} · B ) mod P ,

t ₁₂ =( a _{n −3} · 2 · B + a _{n −4} · B ) mod P , (13)

… ,

t _{1( n /2)} =( a ₁ · 2· B + a ₀ · B ) mod P .

At the second stage of the transformation, the value is calculated

t ₂ =(2 ² t ₁₁ + t ₁₂ ) mod P . (14)

Calculations are performed in a similar manner at subsequent stages of transformation.

At the last ( n /2)-th stage of the transformation, the value is calculated

t _{n /2} =(2 ² t _{n /2−1} + t _{1( n /2)} ) mod P , (15)

which is the desired product of numbers A and B modulo P.

The operation of reduction modulo P at the first stage of transformation in all nodes is performed based on the following considerations.

By definition, the value of the multiplier B lies in the range 0≤ B ≤ P -1. Therefore, the value of any quantity t _{1 i} in (13) before reducing it by modulus is in the range from 0 to 3 P -3.

Modulo reduction of the quantity t _{1 i} , is carried out according to the following rules:

t _{1 i} (modP)=t _{1 i} , if 0 ≤t _{1 i} <P, (16)

t _{1 i} (modP)=t _{1 i} -P, If P≤t _{1 i} < 2P,

t _{1 i} (modP)=t _{1 i} - 2P, if 2P≤t _{1 i} ≤ (3P- 3),

The conditions for the value t _{1 i} to fall into one of the intervals specified in (16) are determined by the values of the carry signals at the carry outputs of the adders that perform the subtraction operation ( t _{1 i} − kP ), where k = 1, 2 in accordance with Table 1.

Table 1.

t _{1 i} t _{1 i} -P t _{1 i} - 2P 0 ≤ t _{1 i} < P 0 0 P ≤ t _{1 i} < 2 P 1 0 2 P ≤ t _{1 i} < (3 P - 3) 1 1

Thus, if the value of the carry signals is equal to “1” at the carry outputs of two adders, then t _{1 i} (mod P )= t _{1 i}  − 2 P , if the carry signal value is “1” at the carry outputs of one adder, then t _{1 i} (mod P ) = t _{1 i}  – P . If the value of the carry signals is “0” at the carry outputs of the two adders, then t _i (mod P )= t _i , i.e. the subtraction operation is not performed.

The operation of reduction modulo P at the second and subsequent stages of the transformation is performed as follows. The value of the quantities t _i , in (14), (15) before the modulo reduction is in the range from 0 to 5 P -5.

Modulo P reduction of the quantity t _i , is carried out according to the following rules

t _i (mod P )= t _i , if 0 ≤ t _i < P , (17)

t _i (modP)=t _i -P, If P≤t _i < 2P,

t _i (modP)=t _i - 2P, if 2P≤t _i < 3P,

t _i (modP)=t _i - 3P, if 3P≤t _i < 4P,

t _i (modP)=t _i - 4P, if 4P≤t _i ≤ (5P-5).

The conditions for the value t _i to fall into one of the intervals specified in (17) are determined by the values of the carry signals at the carry outputs of the adders that perform the subtraction operation ( t _i − kP ), where k = 1, 2, 3, 4 in accordance with Table 2.

Table 2.

t _i t _i − P t _i − 2 P t _i − 3 P t _i − 4 P 0 ≤ t _i < P 0 0 0 0 P ≤ t _i < 2 P 1 0 0 0 2 P ≤ t _i < 3 P 1 1 0 0 3 P ≤ t _i < 4 P 1 1 1 0 4P ≤ t _i ≤ (5 P −5) 1 1 1 1

Thus, if the value of the carry signals is equal to “1” at the carry outputs of all four adders, thent _i (modP)=t _i - 4P, if the value of the carry signals is equal to “1” at the carry outputs of the three adders, then
t _i (modP)=t _i - 3P, if the value of the carry signals is equal to “1” at the carry outputs of the two adders, thent _i (modP)=t _i - 2P, if the carry signal value is equal to “1” at the carry outputs of one adder, then
t _i (modP)=t _i -P. If the value of the carry signals is "0" at the carry outputs of all four adders, thent _i (modP)=t _i , i.e. the subtraction operation is not performed.

In the prototype device, at each stage of the transformation, the reduction of the calculation results by an arbitrary modulus according to expressions (13)-(15) is performed in two steps - first, the operation of summing up the intermediate calculations is performed, and then the reduction of the obtained value by modulus is performed. In the proposed device, the operation of summing up the intermediate calculations and the operation of reduction by modulus are performed simultaneously.

Brief description drawings

Fig. 1 shows the circuit diagram of a modulo multiplier.

The modulo multiplier contains inputs of the multiplicand code 7, inputs of the multiplier code 6, outputs of the product code 8, n /2 conversion stages, where n is the bit depth of the multiplicand code. The first conversion stage contains n /2 nodes including n switches 1, n /2 adders 2, n three-input adders 3 and n /2 three-input multiplexers 4. The second and subsequent conversion stages each contain an adder 2, four three-input adders 3 and a five-input multiplexer 5. The control inputs of switches 1 are connected to the corresponding bits of the inputs of the multiplicand code 7, and the information inputs are connected to the inputs of the multiplier code 6. The information outputs of the first switch 1 of each node of the first conversion stage are connected with a shift of one bit toward the higher ones with the first information inputs of adder 2, as well as the first and second three-input adders 3 of the same node. The information outputs of the second switch 1 of each node of the first stage of the transformation are connected to the second information inputs of the adder 2 and the first and second three-input adders 3. The inverse code of the module is fed to the third information inputs of the first three-input adders 3, and the inverse code of the doubled module is fed to the third information inputs of the second three-input adders. The information outputs of adder 2 of each node of the first stage of conversion are connected to the first information inputs of three-input multiplexer 4. The information outputs of the first three-input adders 3 are connected to the second information inputs of the corresponding three-input multiplexers 4, the information outputs of the second three-input adders 3 are connected to the third information inputs of the corresponding three-input multiplexers 4, the carry outputs of the first three-input adders 3 are connected to the first control inputs of the corresponding three-input multiplexers 4, the carry outputs of the second three-input adders 3 are connected to the second control inputs of the corresponding three-input multiplexers 4. The information outputs of three-input multiplexer 4 of the first node of the first stage of conversion are connected with a shift of two bits toward the higher ones with the first information inputs of adder 2, the first, second, third and fourth three-input adders 3 of the second stage of conversion. The information outputs of the three-input multiplexer 4 of the j -th node of the first stage of conversion, where j = 2, ..., n /2, are connected to the second information inputs of the adder 2, the first, second, third and fourth three-input adders 3 of the j -th stage of conversion. The inverse codes of the modulus, inverse codes of the doubled modulus, inverse codes of the tripled modulus and inverse codes of the quadrupled modulus are fed to the third information inputs of the first, second, third and fourth three-input adders 3 of the j -th stage of conversion, respectively. A logical one signal is fed to the carry inputs of the three-input adders 3 of all stages of conversion. The information outputs of adder 2, the first, second, third and fourth three-input adders 3 of the j -th conversion stage are connected, respectively, to the first, second, third, fourth and fifth information inputs of five-input multiplexer 5 of the same conversion stage, and the carry outputs of the first, second, third and fourth three-input adders 3 are connected, respectively, to the first, second, third and fourth control inputs of the five-input multiplexer 5. The information outputs of the five-input multiplexer 5 of the j -th conversion stage, where j = 2, …, n /2-1, are connected with a shift of two bits toward the higher ones to the first information inputs of adder 2, the first, second, third and fourth three-input adders 3 of the ( j +1)-th conversion stage. The information outputs of the five-input multiplexer 5 of the n /2-th conversion stage are connected to the outputs of the product codes 8 of the device.

Fig. 2 shows the circuit diagram of a three-input adder.

The three-input adder contains m full single-bit adders 9.1÷9. m and an ( m +1)-bit adder 10, the (1… m )-th bits of the information outputs of which are the information outputs of the three-input adder 3, and the ( m +1)-th bit is the carry output of the three-input adder 3. The first, second, and third information inputs of the full single-bit adders 9.1÷9. m are connected to the corresponding bits of the first, second, and third information inputs of the three-input adder 3. The information outputs of the full single-bit adders 9.1÷9. m are connected respectively to the (1… m )-th bits of the first information inputs of the ( m +1)-bit adder 10, and the carry outputs are connected respectively to the (2… m +1)-th bits of the second information inputs of the ( m +1)-bit adder 10, the first bit of which is connected to the carry input of the three-input adder 3. A logical zero signal is fed to the ( m +1)-th bit of the first information inputs of the ( m +1)-bit adder 10.

Implementation of the invention .

The modulo multiplier operates as follows (see Fig. 1).

Input 7 of the device is fedn-digit binary code of the multiplicandA. Input 6 of the device is fedm-digit code of the multiplierB. The inverse code of the module is fed to the third information inputs of the first and second three-input adders 3 of the first stage of conversion and, accordingly, inverse code of the doubled module. A logical one is fed to the carry inputs of the first and second three-input adders 3 of all nodes of the first stage of conversion. The inverse code of the module, the inverse code of the doubled module, the inverse code of the tripled module and the inverse code of the quadrupled module are fed to the third information inputs of the first, second, third and fourth three-input adders 3 of the second and subsequent stages of conversion, respectively.

At the first stage of the transformation, the values t _{1 i} are calculated simultaneously in ( n /2) nodes, , where i is the node number:

t ₁₁ =( a _{n -1} · 2 · B + a _{n -2} · B ) mod P ,

t ₁₂ =( a _{n -3} · 2 · B + a _{n -4} · B ) mod P ,

… ,

t _{1( n /2)} =( a ₁ · 2· B + a ₀ · B ) mod P .

Multiplication of the digits of the multiplicanda _i by a factorBis carried out using keys 1. Multiplication of the multiplierBby 2 is carried out by shifting the digits by one towards the higher ones from the information outputs of the first keys 1 of each node when connecting to the first information inputs of adders 2, the first information inputs of the first and second three-input adders 3 of the corresponding node. In parallel, adder 2, the first and second three-input adders 3 of each node of the first stage of conversion perform summation of the valuesa _i ·2·B And a _{i - 1}·B, A the first and second three-input adders 3 also reduce the resulting sums to their absolute value by simultaneously subtracting the values from itPand 2Pand a three-input multiplexer 4 of the corresponding node, which switches the values of the transfer signals received at its information inputs to the outputs, in accordance with Table 1.

As a result, the values t _{1 i} are formed at the outputs of all nodes of the first stage of transformation, in accordance with expression (13).

At the second stage of the conversion, the value t ₂ = (2 ² t ₁₁ + t ₁₂ ) mod P is calculated, where t ₁₁ and t ₁₂ are the values at the outputs of the first and second nodes of the first stage of the conversion. The value t ₁₁ is multiplied by 2 ² by shifting the digits of the code t ₁₁ by two towards the higher digit. Modulo reduction P is performed in a similar manner by simultaneously subtracting the values of the modulus, doubled modulus, tripled modulus and quadrupled modulus from the sum and selecting the final value using a five-input multiplexer 4 depending on the control signals fed to its input in accordance with Table 2. The subtraction operation is performed using the corresponding three-input adders 3, to the third information inputs of which the code of the corresponding modulus values is fed in inverse form, and a logical one signal is fed to the carry input, converting the inverse code into an additional one.

Three-input multiplexer 4, depending on the combination of signals at its control inputs, switches the signal from one of its three information inputs to its output. Five-input multiplexer 5, depending on the combination of signals at its control inputs, switches one of its five information inputs to its output in accordance with Table 2.

Three-input adders 3 (see Fig. 2) sum the codes of numbers arriving at their first and second information inputs and simultaneously subtract from this sum the codes of numbers arriving at their third information inputs. Since a logical one signal is fed to the carry inputs of these adders, and inverse codes of the modulus values (doubled modulus, tripled modulus or quadrupled modulus) are fed to the third information inputs, the corresponding additional codes are formed as a result, which lead to the implementation of the subtraction operation. At the outputs of each of the m full single-bit adders 9.1÷9. m three-input adders 3, a partial sum signal and end-to-end carry signals of three numbers arriving at their inputs are formed. As a result, bit-by-bit partial sum signals are formed at the information outputs of the full single-bit adders 9.1÷9. m , and bit-by-bit end-to-end carry signals are formed at the carry outputs. The partial sum signals from the information outputs of the full single-bit adders 9.1÷9. m are fed to the (1, …, m )-th bits of the first information inputs of the ( m + 1)-bit adder 10, to the ( m +1)-th bit of which the logical zero signal is fed. The signals from the carry outputs of the full single-bit adders 9.1÷9. m are fed to the (2, …, ( m +1))-th bits of the second information inputs of the ( m +1)-bit adder 10, to the first bit of which the logical one signal is fed, converting the inverse code of the module into an additional one. As a result, at the (1, …, m )-th bits of the information outputs of the ( m +1)-bit adder 10, the sum value is formed in accordance with (13), (14) or (15), and the value formed at the ( m +1)-th bit of the information outputs of the ( m +1)-bit adder 10 is the carry signal.

Similar calculations are performed at subsequent stages of the transformation. As a result of these calculations, the output of the last ( n /2)-th stage of the transformation yields the value of the product of the numbers A and B modulo P .

Since at each stage of the conversion two digits of the multiplicand are processed simultaneously, then after ( n /2) steps of conversion at the output of the product code 8 of the device a binary code of the product of numbers A and B modulo P will be formed. In this case, the reduction of the calculation results to an arbitrary modulus at each stage of the conversion is performed in one step, simultaneously with the operation of summing the intermediate calculations, which increases the speed of the device.

Sources of information

1. Multiplier by two modulo. Russian Federation Patent No. 2015537, IPC G06F 7/49 (1990.01), published 30.06.1994.

2. Device for multiplying numbers by an arbitrary modulus. Russian Federation Patent No. 2316042, IPC G06F 7/523 (2006.01), G06F 7/72 (2006.01), published 27.01.2008. Bulletin No. 3.

3. Modulo multiplier. Russian Federation Patent No. 2751802, IPC G06F 7/72 (2006.01), G06F 7/523 (2006.01), published 19.07.2021. Bulletin No. 20.

Claims (1)

A modulo multiplier containing multiplicand code inputs, multiplier code inputs, product code outputs, n /2 conversion stages, where n is the device capacity, the first conversion stage containing n /2 nodes, and the (2… n /2)th conversion stages containing one node each, each conversion node of the first conversion stage containing the first and second switches, a two-input adder and a three-input multiplexer, and the conversion nodes of the (2… n /2)th conversion stages containing two-input adders and five-input multiplexers, the information inputs of all switches of the first conversion stage are connected to the multiplier code inputs, the control inputs are connected to the corresponding bits of the multiplicand code, the information outputs of the first switches of each first conversion stage node are connected to the first information inputs of the corresponding two-input adders with a shift of one bit toward the higher ones, the information outputs of the second switches of each first conversion stage node are connected to the second information inputs of the corresponding two-input adders, the information outputs of the two-input adders are connected to the first information inputs of the corresponding three-input multiplexers, the information outputs of the three-input multiplexer of the first node of the first conversion stage are connected with a shift of two bits toward higher digits to the first information inputs of the two-input adder of the second conversion stage, the information outputs of the three-input multiplexers of the j -th node of the first conversion stage, where j = 2… n /2, are connected to the second information inputs of the two-input adders of the j -th conversion stage, the information outputs of the two-input adders of the j -th conversion stage are connected to the first information inputs of the corresponding five-input multiplexers, the information outputs of the five-input multiplexers of the j -th conversion stage, where j = 2,…, n /2−1, are connected with a shift of two bits toward higher digits to the first information inputs of the two-input adders of the ( j +1)-th conversion stage, and n /2-th stage of the transformation are outputs of the product codes, characterized in that the first and second three-input adders are introduced into it at the first stage of the transformation in each node, and the first, second, third and fourth three-input adders are introduced at the (2… n /2)-th stage of the transformation, wherein the first information inputs of the first and second three-input adders of the first stage of the transformation are connected to the information outputs of the first keys of the corresponding node with a shift of one bit towards the most significant ones, the second information inputs are connected to the information outputs of the second keys of the corresponding node, the inverse code of the modulus is fed to the third information inputs of the first three-input adders, and the inverse code of the doubled modulus is fed to the third information inputs of the second three-input adders, the information outputs of the first three-input adders are connected to the second information inputs of the corresponding three-input multiplexers, the information outputs of the second three-input adders are connected to the third information inputs of the corresponding three-input multiplexers, the outputs the carry outputs of the first three-input adders are connected to the first control inputs of the corresponding three-input multiplexers, the carry outputs of the second three-input adders are connected to the second control inputs of the corresponding three-input multiplexers, the first information inputs of the first, second, third and fourth three-input adders of the second conversion stage are connected with a shift of two bits toward the higher digits to the information outputs of the three-input multiplexer of the first node of the first conversion stage, the second information inputs of the first, second, third and fourth three-input adders of the j -th conversion stage, where j = 2… n /2, are connected to the information outputs of the three-input multiplexer of the j -th node of the first conversion stage, the inverse codes of the modulus, inverse codes of the doubled modulus, inverse codes of the tripled modulus and inverse codes of the quadrupled modulus are fed to the third information inputs of the first, second, third and fourth three-input adders of the j -th conversion stage, respectively. module, a logical one signal is applied to the carry inputs of all three-input adders, wherein each three-input adder contains m full single-bit adders and an ( m +1)-bit adder, the (1… m )-th bits of the information outputs of which are the information outputs of the three-input adder, and the ( m +1)-th bit is the carry output of the three-input adder, the first information inputs of the full single-bit adders are connected to the corresponding bits of the first information inputs of the three-input adder, the second information inputs are connected to the corresponding bits of the second information inputs of the three-input adder, the third information inputs are connected to the corresponding bits of the third information inputs of the three-input adder, the information outputs of the (1… m )-th full single-bit adders are connected to the (1… m )-th bits of the first information inputs of the ( m +1)-bit adder, and the carry outputs are connected to the (2… m +1)-th the bits of the second information inputs of the ( m +1)-bit adder, the first bit of which is connected to the carry input of the three-input adder, a logical zero signal is fed to the ( m +1)-bit of the first information inputs of the ( m +1)-bit adder.

Images