JP3129526B2 - Multiplication circuit over integers - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiplication circuit for integers, and more particularly to a circuit for multiplying a large number of digits using a multiplier of a small number of digits. The present invention provides an RSA cryptosystem that requires multiplication of a large number of digits (Shinichi Ikeno, Kenji Koyama:
“Modern Cryptography”, IEICE, 1986, Chapter 6)
It can be used for many integer operations including encryption techniques such as.

[0002]

2. Description of the Related Art In designing a gate array or a substrate, a multiplier on an integer having a small number of digits can be easily configured because a cell library, TTL, and the like are provided. However, when trying to realize a multiplication circuit with a large number of digits, there is no cell library or the like, so that the user has to design it by himself. However, when designing a multiplier with a large number of digits by itself, if the circuit configuration of the multiplier with a small number of digits is directly expanded, the circuit configuration becomes extremely complicated and difficult to realize.

In the case where an input value is divided for each predetermined bit and multiplication is performed by a plurality of clocks, the Galois field (Yo Miyagawa, Hiroshi Harashima, Hideki Imai:
It is known that in an arithmetic system having no carry such as "Theory of Information and Codes", Iwanami Koza, 1982, Chapter 6, multiplication is performed by a circuit as shown in FIG. In FIG. 4, *
B _i is _{B i (i = 0, ...} , n-1) multiplier and the m bits * m bits of the Galois field on the multiplier, EX is EXOR of m bits, r is a register m bits.

However, in multiplication on integers, if a division operation as shown in FIG. 4 is performed, a carry is generated for each digit obtained by the division operation, so that it is difficult to realize an efficient multiplier.

SUMMARY OF THE INVENTION The present invention eliminates the above-mentioned drawbacks, and provides an efficient and extended method that takes into account carry-up using a multiplier with a small number of digits when dividing and calculating an input value with a large number of digits in a multiplication circuit. It is an object of the present invention to provide a multiplication circuit on integers which is rich.

[0006]

In order to solve this problem, a multiplication circuit on an integer according to the present invention provides an integer A of (n × m) bits when h, m, and n are positive integers. And (h ×
m) A multiplication circuit on an integer for multiplying a bit by an integer B, comprising the same arithmetic element PE _i (i = 0,..., n−1) connected in series in an n- stage pipeline. , Said P
E _i is a specific A obtained by dividing the integer A into m bits.
_i (i = 0,..., n-1) and an integer B sequentially input from the lower digit for each clock, divided into m bits
_j (j = 0,..., h-1) and the calculation result of the preceding stage PE _{i-1
When S (i-1)} is input, S (i) = Ai.Bj + S (i-1)
Is calculated, and the calculation results _{S (i)} and B _j are calculated as S (i)
B _j-1 delayed by one clock is output to the next stage PE _{i + 1} , and the multiplied values of A and B are output in order from the lower digit from the last stage PE _n-1. I do.

Here, the PE is a multiplier for performing multiplication of m bits × m bits, a register of m bits for storing the upper m bits of the output of the multiplier, and a lower m for the output of the multiplier. A three-input m-bit adder for adding the bit, the output of the register and the result of the preceding PE calculation, latches the carry output of the adder, and outputs the result to the carry input of the adder again one clock later. A flip-flop and a delay circuit for delaying Bj by one clock from S (i) .

The PE includes a multiplier for performing multiplication of m bits × m bits, and an output of the multiplier and a PE at a preceding stage.
And a 2-m-bit register for storing the output of the adder, a 2-m-bit register for storing the output of the adder, and latching the carry output of the adder. A two-bit buffer which outputs again to the carry input of the adder with a delay of clock, and
Is delayed by one clock from S (i) .

[0009]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS In this embodiment, an integer A and hm
It is assumed that a multiplier with a bit integer B is used. This limitation does not cause loss of generality. That is, it is assumed that two integers of nm bits are A and B, and an operation of AB = C is executed. Here, multiplication a · b of two integers a and b of m bits
= C can be easily realized by a known configuration such as a cell library or TTL.

When the integers A and B are each divided into n for every m bits, the following expression can be obtained.

A = A _n-1 · X ^n-1 + A _n-2 · X ^n-2 + ...
_{+ A 1 · X + A 0} B = B n-1 · X n-1 + B n-2 · X n-2 + ... + B 1 · X +
B ₀ Here, X = 2 ^m−1, and bit sequences obtained by dividing A and B from the upper digit for each m bits are A _i and B _i (i
= N-1, ..., 0). In this case, since the integers A and B can be regarded as polynomials, AB can be expressed as follows.

[0012]

(Equation 1) Therefore, a multiplier can be constituted by a circuit as shown in FIG. FIG.
Has a configuration called a systolic array (Yoichi Muraoka: "parallel processing", Shokodo, 1986, pp 131-133). The operation of the systolic array is performed by pipeline processing using small identical functional blocks called processing elements (PE).

The above PE is configured as shown in FIG. FIG.
Is a multiplier for executing m-bit multiplication a · b = c (A _i × B _{j in} this example) and an m-bit register (R _{1 to} R ₄ )
, A 3-input m-bit adder, and a flip-flop FF which latches the carry output of the adder and outputs the result again to the carry input of the adder one clock delay later. Here, A _i (i = 0,..., N−1) is a division value of the integer A described above, and is set in advance in each PE as shown in FIG.

In FIG. 1, B _j is from B ₀ to B ₁ .
Inputs are in the order of _n−1 , and the previous-stage input S _j to PE ₀ is all “0”.

In the first PE ₀ (when A _i is A ₀ ), a 2 m-bit output A ₀ · B is output from the multiplier in response to the input of B _j (j = 0,..., N-1). ₀ , A ₀ · B
_{1, ..., A 0 · B} n-1 is output. Here, the lower m bits of the output from the multiplier is directly input to the adder, upper m bits is input to the adder is delayed Yotsute 1 clock in the register R _1. This is because the output from the multiplier is 2 m-bits and the output from the multiplier overlaps every m-bits when considered at intervals of m bits represented by X in equation (1). , In the same m-bit unit as the input.

Since this addition is performed from the lower digit, the output carry is set to 1 by the flip-flop FF.
By delaying the clock, it is used as a carry carry in the operation of the upper digit performed in the next clock. Thus, in the first PE ₀ , S _j ←
The operation of A ₀ · B _j is output.

Next, the second PE ₁ (A _i = A ₁ ) in FIG.
), The same operation is performed, but A ₁ · B
_{In the operation of j} (j = 0,..., n-1), B _j is input one clock behind S _j by two registers R ₃ and R ₄ , so that the operation is one digit higher than S _j. It is treated as A ₁ · B _j · X. Therefore, the output from the adder is S _j ← A _1.
It is sequentially output as B _j-1 + S _j .

Hereinafter, the same processing is performed at the last PE _{n-1 in} FIG.
By repeating (A _i = A _n-1 ), the output from PE _n-1 of the systolic array of FIG. 1 is changed to C _k (k = 0) representing each m bits from the lower order of AB. , ..., 2n-
It turns out that it becomes 2).

The internal structure of the PE is changed as shown in FIG. 3 by directly inputting a 2-mbit output from the multiplier to the adder.
Similar multiplication can be performed by outputting 2 m-bit S _j . However, r in FIG. 3 is a register of 2 m bits, and BF is a 2-bit buffer for delaying the carry from the adder by two clocks. This is because, as described above, the output from the multiplier is not m bits but 2 bits.
This is because the data is output in units of m bits.

As described above, when an input value is input after being divided into n units of m bits, an n · m bit multiplying circuit can be efficiently provided by the systolic array using an m bit multiplier. It has been shown that it can be realized. It is clear that multiplication can be performed by a similar circuit even when h ≠ n. Thereby, when the value of the integer A is divided and input, the calculation of AB is efficiently performed.

The systolic array is a simple PE.
Therefore, it is easy to configure a large-scale circuit such as a VLSI. Also, the control is the same for each PE, and the data operates synchronously with the same clock, so that it can be realized very easily. Further, no matter how large the number of digits of A and B becomes, it is sufficient to simply add PEs and the expandability is high.

Also, in this method, since the carry is not output as a carry to another PE calculated in one PE, there is no problem such as a delay related to the carry which becomes a problem in multiplication on an integer.

The present invention may be applied to a system constituted by a plurality of devices or to an apparatus constituted by a single device. It is needless to say that the present invention can be applied to a case where the present invention is achieved by supplying a program to a system or an apparatus.

[0024]

According to the present invention, multiplication of a large integer can be performed by a digit.
Execute using a multiplier with a small number of digits while considering the rise
Control is simple, easy to speed up, efficient and
It is possible to provide a multiplication circuit on integers which is rich in scalability .

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a multiplication circuit on an integer according to an embodiment.

FIG. 2 is a diagram illustrating an example of an internal configuration of a PE of the present embodiment illustrated in FIG. 1;

FIG. 3 is a diagram showing another example of the internal configuration of the PE of the present embodiment shown in FIG. 1;

FIG. 4 is a diagram showing a known polynomial multiplication circuit on a Galois field.

[Explanation of symbols]

PE: processing element, R: register of m bits, FF: flip-flop of 1 bit, r: 2 m
Bit register, BF ... Buffer for 2 bits, EX
... m bit EXOR

Claims (3)

(57) [Claims] 1. When h, m, and n are positive integers,
(N × m) bit integer A and (h × m) bit integer B
Shall apply in the multiplication circuit on integers for multiplying with the same calculation elements connected in n stages in series in a pipeline _{PE i (i = 0, ...} , n-1) wherein the PE _i each , A specific A _i (i = 0,..., N−1) obtained by dividing the integer A by m bits, and B _{j obtained} by dividing the integer B sequentially inputted from the lower digit for each clock by m bits (J = 0,..., H−1) and the calculation result _{S (i−1) of} the preceding stage PE _i−1 , S (i) = Ai · Bj + S (i
-1) to calculate the said calculation results _{S (i)} and B _j calculation result S
B _i−1 delayed by one clock from (i) and PE _{i + 1 of the} next stage
A multiplication circuit on integers, which outputs the multiplied values of A and B in order from the least significant digit from the last stage PE _n−1 . 2. The PE includes a multiplier for performing multiplication of m bits × m bits, a register of m bits for storing upper m bits of an output of the multiplier, and lower m bits of an output of the multiplier. A 3-input m-bit adder for adding the output of the register and the result of the PE calculation at the preceding stage; latching the carry output of the adder; and outputting a flip-flop to the carry input of the adder again one clock later. 2. The integer multiplication circuit according to claim 1, further comprising a delay circuit for delaying said Bj by one clock from S (i) . 3. The PE has a multiplier for executing a multiplication of m bits × m bits, and a 3-input for adding an output of the multiplier, a calculation result of a PE at a preceding stage, and a carry two clocks before the buffer. A 2 m-bit adder, a 2 m-bit register for storing the output of the adder, a 2-bit buffer for latching the carry output of the adder and outputting again to the carry input of the adder with a delay of 2 clocks; Bj
2. The integer multiplying circuit according to claim 1, further comprising a delay circuit for delaying one clock from S (i) .