JP2519288B2 - Multiplier / divider - Google Patents

Description

The present invention relates to a multiplier / divider, and is particularly suitable for use in obtaining x × y (mod n) for integers x, y, n. Regarding the multiplier / divider.

[Conventional technology]

In general, integers x, y, n are x <n, y <n, y = (y _m , y _m-1 , y _m-2 , ..., y ₁ , y ₀ ) _2, where m ≧ 0 , X × y (mod n) is: x × y (mod n) = {{{... {{{{{x × y _m } (mod n)} × 2} (mod n) + x × y _m-1 } (Mod n)} × 2} (mod n) + ... + x × y ₁ } (mod n)} × 2} (mod n) x × y ₀ } (mod n) ...... (1) It can be calculated by an arithmetic expression.

As a conventional technique for realizing such an arithmetic expression as an arithmetic unit and performing the above-described arithmetic operation, for example, a technique described in JP-A-57-206964 is known.

FIG. 5 is a block diagram showing the structure of a multiplier / divider according to the prior art which performs an operation based on the above-mentioned arithmetic expression (1). In FIG. 2, 1 is an x × y _i calculator, 2 is an adder,
Reference numeral 4 is a doubler, and 5 and 6 are mod n (modulo n) arithmetic units.

In the multiplier / divider shown in FIG. 5, the x × y _i calculator 1 is
The adder 2 calculates x × y _i from the input integers x and y.
Adds this multiplication result x × y _i and the operation result up to now. The modulo n calculator 5 finds the modulo n of the addition result, and the doubler 4 doubles the result of the modulo n. The modulo n calculator 6 further modulos the result of the doubler 4. As a result, the module 6
Outputs {{{... + x × y _i } (mod n)} × 2} (mod n). This result is returned to the adder described above, and x × y _i-1
Is calculated and is calculated in the same manner as described above.

Such an operation is performed by setting m from 0 to m and m + 1.
By repeatedly performing the operation twice, the multiplier / divider shown in FIG. 5 executes the operation of the arithmetic expression (1), and the modular n operator 5
Output x × y (mod n).

In the multiplier / divider shown in FIG. 5, a modular n calculator 5,
Reference numeral 6 is an arithmetic unit that performs subtraction of n once, and the input value t given to each input must be within the range of 0 ≦ t <2n. In order to satisfy this condition, the multiplier / divider shown in FIG. 2 is provided with two sets of modulo n arithmetic units.

[Problems to be Solved by the Invention]

In the prior art, as described above, in order to perform a one-digit operation, it is necessary to perform n subtraction twice, that is, two modulo n arithmetic operations, which results in a slower operation speed and multiplication and division. There is a problem that the circuit scale of the calculator becomes large.

The object of the present invention is to solve the above-mentioned problems of the prior art.
An object of the present invention is to provide a multiplier / divider that can execute x × y (mod n) operations only by performing modulo operations by performing addition or subtraction once in digit operations.

[Means for solving the problem]

According to the present invention, the object is to provide a multiplier / divider that performs an operation of x × y (mod n), an operation unit that obtains x × y (mod-n), and an n by adding n to the operation result. Xy (mo
dn) and a conversion unit.

[Work]

xx (mod-n) can be expanded as the following arithmetic expression.

x × y (mod-n) = {{{... {{{x × y _m } (mod-n)} × 2 + x × y _m-1 } (mod-n)} × 2 + ... + x × y ₁ } (mod-n)} × 2 + x × y 0} (mod-n) ...
(2) In the second formula, the point to be careful is that after × 2, (mo
d-n) is not required. This is because the calculation result t of (mod-n) executed before x2 is -n <t≤
Because it is in the range of 0. This result is doubled and x × y _i
Even if is added, the result 2t + x × y _i is −2n <2t
Within the range of + x × y _i <n. Then, the modulo (−n) of 2t + x × y _i can be obtained by one addition or subtraction as follows. That is, (1) When 2t + x × y _i > 0, the result of modulo (−n) can be obtained by executing the operation of −n.

(2) When 2t + x × y _i <0, the operation of + n is executed,
When the result is positive, the original value before the calculation of + n is the result of modulo (-n), and when the result is negative, the negative value is the result of modulo (-n).

As mentioned above, the calculation of 1-digit modulo (-n) is 1
It is possible to perform the calculation of modulo (-n) by adding or subtracting twice, and therefore x × y (mod-n)
Operation of, when the _{y = y m, y m-} 1, ... y 0, can be executed by one modulo (-n) calculator m + 1 iterations used.

〔Example〕

Hereinafter, an embodiment of a multiplier / divider according to the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing a schematic configuration of an embodiment of the present invention, FIG. 2 is a block diagram showing a configuration of a mod-n arithmetic unit in FIG. 1, and FIG. 3 is x × y _{i in} FIG. FIG. 4 is a block diagram of the arithmetic unit, and FIG. 4 is a block diagram of the mod-n arithmetic unit in FIG. 1 to 4, 3 is a mod
-N (modulo (-n)) computing unit, 7 is xxy (mod-
n) calculating unit, 8 conversion unit, 201 X register, 2
02 is a Y register, 203 is a shifter, 211 is an input register, 21
Reference numeral 2 is an N register, 213 is an adder / subtractor, 214 is an accumulator, 215 is a selector, and other symbols are the same as those in FIG.

In FIG. 1, an integer x, y, n is given to a calculation unit 7 for obtaining x × y (mod-n). The calculation unit 7 executes a calculation of x × y (mod-n) on the given integers x and y. The calculation result T of this modulo (-n) is generally 0≤T <-n. The conversion unit 8 performs an operation of + n on the operation result T of the operation unit 7 to obtain an operation result T
Xxy (mod-n) is converted into xxy (mod-n). At this time, the conversion unit 8 operates so as to output "0" without performing + n calculation when the given calculation result T is "0".

In the above description, when the calculation result T of the calculation unit 7 for obtaining x × y (mod−n) is “0”, the conversion unit 8 outputs the calculation result “0” as it is, but the conversion unit 8 is simply , + N addition, it is possible to output "-n" when the calculation result T becomes "0" in the calculation unit 7 described above. In this case, the configuration of the conversion unit 8 can be a simple configuration including only the adder.

The operation unit 7 for obtaining x × y (mod-n) described above is
As shown in FIG. 2, an x × y _i calculator 1, an adder 2, and
It is composed of a module (-n) arithmetic unit 3 and a doubler 4. In FIG. 2, integers x and y are data lines 11 and 12,
Is input to the x × y _i calculator 1 and the output of the calculator 1 is given to the left input terminal of the adder 2 via the data line 13. The output of the adder 2 is input to the module (-n) calculator 3 via the data line 14 and the module (-n)
n) The output of the arithmetic unit 3 is given to the doubler 4 via the data line 16. The output of the doubler 4 is sent via the data line 18.
It is applied to the right input terminal of the adder 2 described above. An integer n is given to the modulo (-n) computing unit 3 via the data line 15, and the output thereof is output as the computation result of x × y (mod-n) via the data line 17. To be done.

Next, the operation of the arithmetic unit 7 for obtaining x × y (mod-n) configured as described above will be described.

(1) Reset all circuits. As a result, the output of each computing unit becomes "0".

(2) Put the integers x, y, n on the data lines 11, 12, 15 respectively,
input.

(3) i = m.

(4) The x × y _i calculator 1 calculates x × y _m .

(5) The adder 2 calculates 0 + x × y _m .

(6) The modulo (-n) calculator 3 calculates the modulo of (-n). As a result, {x × y _m } on the data line 16
(Mod-n) is obtained.

(7) This result is doubled by the doubler 4. As a result, {{x × y _m } (mod-2)} × 2 is obtained on the data line 18.

(8) Let i = m-1.

(9) The x × y _i calculator 1 calculates x × y _m−1 .

(10) The adder 2 adds the output of the doubler 4 and x × y _m−1 . As a result, {{x × y _m } (mod-n)} × 2 + x × y _m-1 is obtained on the data line 14.

(11) The module (-n) calculator 3 calculates the module (-n). As a result, on the data line 16, {{{x × y _m } (mod−n)} × 2 + x × y _m−1 } (mod−
n) is obtained.

(12) Double the result with the doubler 4. As a result,
On the data line 18, {{{{x × y _m } (mod-n)} × 2 + x × y _m-1 } (mod
-N)} * 2 is obtained.

(13) The above steps (8) to (12) are repeated m-1 times while changing i from m-2 to 0. As a result, on the data line 18, {{{... {{{{x × y _m } (mod-n) × 2 + xx
y _m-1 } (mod-n)} × 2 + ... + x × y ₁ } (mod-
n)} × 2 + x × y 0} (mod-n) is obtained.

(14) At this time, x × y (mod−
n) is output.

The operation unit 7 for obtaining x × y (mod−n) can operate as described above to obtain x × y (mod−n),
The calculation result is converted into n modules by the conversion unit 8 shown in FIG. 1 and output as x × y (mod−n).

Next, regarding the blocks constituting the above-mentioned arithmetic unit 7,
The details will be described. Since the adder 2 and the doubler 4 have a trivial configuration, the x × y _i calculator 1 and the modulo (−n) calculator 3 will be described here.

As shown in FIG. 3, the x × y _i calculator 1 has an X register 201 for storing an integer x and a Y register 2 for storing an integer y.
02, shift 203, and AND gate 204. At the start of the calculation, the integer x is stored in the X register 201 via the data line 11, and the integer y is Y via the data line 12.
It is stored in the register 202. After that, first, X register 201
All the bits in the above and the most significant bit of the Y register 202, that is, y _m , are given to the AND gate 204, logically ANDed and output to the data line 13. This allows data line 13
That is, x × y _m is obtained above. Next, the Y register 20
The value in 2 is shifted one bit in the upper bit direction by the shifter 203 and reset in the Y register 202. As a result, the highest bit of the Y register 202 becomes y _m-1 .
By giving the most significant bit of the Y register 202 and all the bits of the X register 201 to the AND gate 204, the data line
We get x × y _m−1 on 13. By repeating such an operation, the x × y _i calculator 13 sequentially outputs x on the data line 13.
It is possible to output xy _m , xxy _m-1 , ... xxy ₁ , xxy ₀ .

The module (-n) arithmetic unit 3 is, as shown in FIG.
Input register 211 that stores the value from input data line 14
And an N register 212 that stores an integer n, and both registers 21
An adder / subtractor 213 that performs addition and subtraction of 1,212 values and an adder / subtractor 213
Of the input register 211 and a selector 215 for selecting one of the outputs of the accumulator 214.

At the start of calculation, the integer n is registered in the N register via the data line 15.
Stored in 212. When the addition result value data from the adder 2 shown in FIG. 2 is given via the data line 14, this input data is latched in the input register 211. The sign bit s ₁ in the input register 211 is given to the adder / subtractor 213 as a calculation instruction signal via the signal line 216.

If the sign bit s ₁ is “0”, that is, if the input data value that is the addition result value is positive, the adder / subtractor 213 is instructed to subtract, and if the sign bit s ₁ is “1”, that is, the addition result value. If the input data value of is negative, the adder / subtractor 213 is instructed to perform addition. The adder / subtractor 213 receives the input register 21 according to the operation instruction by the sine bit s _1.
The value of the N register 212 is subtracted from the value of 1, or the value of the input register 211 and the value of the N register 212 are added, and the result is output to the accumulator 214. The sign bit s _{2 of the} accumulator 214 is given as a selection signal to the selector 215 via the signal line 217. When the sign bit s ₂ is “0”, that is, when the operation result of the adder / subtractor 213 is positive, the selector 215 determines that the input register 211
When the sign bit s ₂ is “1”, that is, when the operation result of the adder / subtractor 213 is negative, the selector 2
15 selects the value in the accumulator 214. This result is output to the data line 16 as the calculation result of module (-n).

To summarize the operation of the modulo (-n) calculator 3 which operates as described above, the following calculation is performed according to the magnitude of the input value on the input data line 14.

(1) If 0 ≤ input value <n, output = input value -n (2) -n ≤ input value <0, output = input value (3) -2n ≤ input value <-n, output = Input + n In the calculation of the module (-n) calculator 3 shown in FIG. 4, the point to be noted is that when the result of the module (-n) is "0", it becomes "0". Instead, it outputs "-n". Therefore, in the above-described embodiment, as already described in the explanatory diagram of FIG. 1, x × y (mod-n) is set to x.
The conversion unit 8 for converting to xy (mod n) can be simply configured by a tn circuit, and further, the circuit configuration of the modulo (-n) computing unit 3 itself can be simplified.

According to the embodiments of the present invention described above. x × y (mod n)
Can be performed by using only one modulo arithmetic unit, so that the arithmetic speed can be improved and the amount of logic gates necessary for constructing the predicate divider can be reduced. Becomes

〔The invention's effect〕

As described above, according to the present invention, x × y (mod
n) can be performed by one modulo arithmetic unit, which can improve the operation speed and reduce the number of logic gates of the predicate-divider performed by modulo n. You can

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic configuration of an embodiment of the present invention, FIG. 2 is a block diagram showing a configuration of a mod-n arithmetic unit in FIG. 1, and FIG. 3 is x × y _{i in} FIG. FIG. 4 is a block diagram of the arithmetic unit, FIG. 4 is a block diagram of the mod-n arithmetic unit in FIG. 1, and FIG. 5 is a block diagram showing an example of the prior art. 1 …… x × y _i calculator, 2 …… adder, 3 …… mod-n calculator, 4 …… doubler, 5,6 …… mod n calculator, 7 …… xx
Calculation unit for y (mod-n), 8 ... conversion unit, 201 ...
X register, 202 ... Y register, 203 ... shifter, 204
...... AND gate, 211 …… Input register, 212 …… N register, 213 …… Adder / subtractor, 214 …… Akymulator, 215
……selector.

Claims (2)

(57) [Claims] 1. A given integer x, y, n (where x <n, y <n,
y = (y _m , y _m-1 ,, y _m-2 , ..., y ₁ , y ₀ )}, x × y (mo
In the multiplier / divider that calculates dn), x × y (mod−n)
A multiplier / divider, comprising: a calculation unit for calculating the calculation result and a conversion unit for converting the calculation result calculated by the calculation unit into x × y (mod n). 2. An arithmetic unit for obtaining the x × y (mod-n) comprises an x × y _i (where i = m, m−1, ..., 1,0) arithmetic unit, an adder, and 2 It is composed of a multiplier and a (-n) module operator, and the output of the x × y _i calculator and the output of the doubler are added by the adder, and the output of the adder is added to the above ( −
n) is repeated by the modulo arithmetic unit of n), and the process of doubling the modulo output by the doubler is repeated m + 1 times from m to 0 to obtain x from the modulo arithmetic unit of (-n). The multiplier / divider according to claim 1, which outputs xy (mod-n).