JPH0332229A - Arithmetic and logic unit - Google Patents

Abstract

PURPOSE: To unnecessitate a complicated design by receiving a residue expression value by a first adder input terminal, receiving the output of a lookup table equivalent to an integer by a second adder input terminal, and collectively generating the residue expression value of each kind of sum of received modulo by the additive modulo of each integer. CONSTITUTION: This unit is provided with a subtracter 1, a lookup table 2, and an adder 3, and the subtracter 1 is provided with substracter sub-circuits 1A and 1B, and the adder 3 is provided with adder sub-circuits 3A and 3B. In the lookup table 2, a residue expression modulo n1(j1 ) is generated in a field 8A of an output terminal 8 in response to the supply of a modulo (p-1) expression value to input terminals 7A and 7B. In the adder sub-circuit 3A, the residue expression modulo n1 of the sum (r1 +j1 ) of first and second values is generated at an output terminal 13A is response to the supply of the residua expression value of the modulo n1. In the same way, in the adder sub-circuit 3B, a remainder expression modulo n2 of the sum (r2 +j2 ) of first and second values r2 and j2 is generated at an output terminal 13B. Thus, a need for complicated design can be eliminated.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of the Invention] The present invention relates to X where g X = X and gk/ = Y
In response to the input remainder representation modulo (p-1) of y being supplied, the generated New Year's Day is calculated by modulo p operation to the value (X+A
The present invention relates to an arithmetic device for generating a remainder expression modulo (p-1) with an exponent of 1 that needs to be raised to a power of -Y).

[Background of the invention]

For information on this type of device, see “The Theory of
Error Correction Code” (North-Holland Publishing Co., Ltd. 977, Par 11
P, J, acWi l]iams and N, J
, A., 5loane), pages 91-92.

Computing the arithmetic sum of the input quantities is faster than computing the arithmetic product of the input quantities and uses logarithms to convert multiplication or division operations into addition or subtraction operations, respectively. However, this requires first converting the input quantities into their logarithms, and finally converting the outputs into their inverse logarithms. Although these drawbacks have been alleviated to an extent with the introduction of so-called Zech tables, which will be described in detail later, they still require a fairly complex design.

[Disclosure of the invention]

It is an object of the present invention to make use of the fact that the power of the generated New Year's Day itself can be expressed by a remainder number system, in particular, to make it useful for the device as mentioned at the beginning.

In the present invention, in response to the input remainder representation modulo (p-4) of X where gX = )
In the arithmetic unit for generating the remainder expression modulo (pH) of the hex index i that needs to be raised to a power to
, X and y are each composed of a plurality of n remainder components modulo of a uniform set of integers that are mutually prime numbers and whose product is equal to (p-1), and for each integer, a separate input subtractor receiving an input remainder representation value for the integer; and a look-up table to which the outputs of all the subtractors are supplied; Upon receipt of the result, each modulo of the plurality of n remainder components of each of the integers is generated at the output terminal of the lookup table, and each of these modulos together generates an arbitrary number among the set values of k. In response to the remainder representation modulo (pl) of is supplied to the input terminal of the lookup table, construct the remainder representation modulo (p-1) of the exponent j that needs to be raised to the power of g to be g''+A. and a first adder input terminal receives a remainder representation value for said integer of one of the input remainder representation values, and a second adder input terminal receives said integer representation value and said integer representation value; a separate adder for receiving the output of the look-up table corresponding to and collectively producing a remainder representation value of the sum of each flight of the received modulo (p-1,) by the additive modulo of each of these integers; and the tolerance value for A is →-1.-1.

[Explanation of conventional example] Hereinafter, first, predetermined conventional components will be evaluated.

First, basic operations can be performed using the remainder number system (RNS). A word in which the multiplicative operation modulo p (where p is a prime number or its power) maps to modulo (p-1,) addition, T, E4. E. Trans.

on Computers Vol, C-25No.
11 (November 1976) S, S, Ya
Paper by U and J. Chung °0nthe Des
tgn of Modulo Arithmetic
l1nits Ba5edon Cyclic Gro
upsl' and lE, E, li, Trans, on
Computers, Vol. C-29No. 1
0 (October 1980) G, 8, Ju
Paper by llien” Implementation
no Multiplication, Modul
o a Prime Number, withapp
lications to Number Theor
etic Transforms. In other words, let mojiko4rop base input oberant'(g be (p
-1) Unit of root, i.e. g(p-” = Imod
The "logarithms" of each hex) of the generated light g, where p is itself modulo (p-1). Therefore, as a simple example, if you want to perform basis operations modulo 13 of the RNS channel (applying g-2), first convert the basis input operands to their "logarithms" according to the following table: I can do it.

'mod13=n) The multiplication operation in this case is, for example, using two modulo 13 couple operands old and 02, calculate the corresponding values of X modulo 12 together, and find the value corresponding to this addition result. This can be done by

For example, to multiply 3 by 5, add 4 and 9 modulo 12 to get l nod 12. From the table, x=1 corresponds to n=2, which is 15 mod 13 as required. Many calculations involve a mixture of multiplication/division and addition/subtraction. - Once logarithmic transformation has been performed, it is difficult to perform addition/subtraction unless one proceeds with the result obtained by taking the inverse logarithm, and the result also needs to be logarithmically transformed again.

This at least partially negates the advantage gained by taking the logarithm first. In order to eliminate such drawbacks, it is known, for example, from pages 91 to 92 of the above-mentioned document, to use the processing/device shown in the block diagram in FIG. 1, at least when performing calculations in the Galois domain. . The expression value of the output amount i when gk-X-1-Y and g is the generated light is the input amount X and y (where gX=
X and gy=Y) are generated by a subtracter 1, a look-up table 2, and an adder 3. Since this actually performs an addition operation while maintaining the input and output quantities in logarithmic form, it is sufficient to simply take the "anti-logarithm" at the end of the entire calculation. Expression values of input quantities X and y are input to input terminals 4 and 5 of subtractor 1 via input terminals 10 and 11, respectively.
supply each. An output terminal 6 of this subtracter 1 is connected to an input terminal 7 of a look-up table 2. The output terminal 8 of the lookup table 2 is connected to one input terminal 9 of the adder 3, and the second input terminal 12 of the adder 3 is connected to the input O:! It is connected to the f-son 11 and thus supplies this second input terminal with the representation value of the input quantity y. Output terminal 1 of adder 3
3 is connected to the output terminal 14 of the device. The subtractor 1 produces at its output terminal 6 the representation value of the quantity (x-y). The lookup table 2 is a so-called Zech table, which outputs the expression value of the quantity j to the output terminal 8 when the expression value of -(x-y) is supplied to the input terminal 7. ,child\
then g J −g l″+1.The adder 3 produces at the output terminal 13 the representation value of the quantity t=r+j (here gk=gゞ+1). Note that, as desired, g” -g
y′J = g yg j= g y (g x −
y + 1) = g J, g y = X + Y,
Moreover, this result was obtained by one subtraction operation, one addition operation, and one lookup operation. For example, the Zech table for g=2 for Moji, :I-mouth 13 basis operations is as follows.

1 entry rNij2'' indicates a special state corresponding to the number O which cannot be expressed in the form g7 and must therefore be expressed in another way.

In the above example, the input operand is transformed when the base operation in a predetermined channel of the RNS permutation is modulo a prime number ρ (p=1.3 in this case) or a power of a prime number. A power of the generator g can itself be decomposed (
In this case 3 and 4) number (P-1=12 in this case)
This is an example where the modulus is .

Therefore, these powers can also be expressed by a system of remainder numbers during which we deal with those powers for the required calculations, as shown in the first of the two documents mentioned above. Therefore, the input and output quantities n in the above table can be expressed as follows.

2 n n mod 3
n mod 40 0
01 1 1
2 2 23
0 34 1
05 2
16 0 2
7 1 38
2 09 0
110 1
211 2
From 3n-12 (the product of the moduli used), the expression repeats, 12 = 0.0; 13 = L 1, etc., but the number of values of n that can be uniquely represented is larger and/or even larger. It is clear that it can be extended arbitrarily by using the modulus of . Arithmetic operations can be performed independently on each remainder component. For example, 4+5-(1,0
)+ (2,1)= (1+2.0+1) −(Omo
d 3.1 mod 4), which is the representation value of 9 as required. Similarly, 2X3= (2゜2)
X (0,3) −(2XO,2X3)=(Omod3
, 2 mod 4), which is 6 as required
is the expression value of

These calculations do not involve time-consuming carry propagation, and the operations on the various moduli are completely independent of each other.

[Other considerations]

A device of the general type shown in Figure 1 can be used even when the input quantity is of more than one remainder form and the output quantity needs to be of more than one remainder form; can be done without needing to convert to non-plural remainder form. The addition operation can be performed on a pair of power-expressing input operands, each operand can be positive or negative, each power itself in this case is of plural remainder form, and the execution of this operation requires 4 still benefits considerably from plural remainder representation.

If X or Y is 0, the corresponding value of 鈥 or 鈱 is -. While the subtracter, force Il calculator, and look-up table circuits can be easily arranged to respond accurately for x-0, problems arise for Y-0. Therefore, if Y=0 is indeed possible, detect when a representation value of y corresponding to Y-0 is applied to the second input of the device, and otherwise respond to this condition. Preferably, the device is provided with a circuit for replacing any representation value that is to be applied to the output of the device with any representation value that is in this case applied to the first input of the device. In this case, the device will generate a correct output even in the case of Y-0.

The representation values used for the input and output quantities of the adder and subtracter subcircuits can be chosen arbitrarily.

These can, for example, each be in the form of a 1-out-of-m coat, and this! Let m be each corresponding integer.

〔Example〕

An example will be explained below with reference to the drawings. In response, the generator g is modulo, and the remainder expression modulo (
1, p-1,) is shown in a block diagram similar to FIG. 1. The part indicated by the solid line in the block diagram of FIG. 2 is the subtracter 1, similar to the device shown in FIG.
, a look-up table 2, and an adder 3 connected as shown. However, the subtracter 1 in this case comprises two subtracter subcircuits IA and IB, respectively;
Also, the adder 3 has two power 11 adder/sub circuits 3A and 3.
Each has B. The device input terminal 10 has two component terminals 108 and IOB, which have non-overlapping fields (non-overlapping fields) whose inputs do not overlap with each other.
verlapping field). The input terminal 11 of the device also has two component terminals 11A and 11B.
and these also constitute a non-overlapping field. Component terminals 10A and IIA are connected to respective input terminals 48 and 58 of subtracter subcircuit LA, and component terminals 10B and 11B are connected to respective input terminals 4B and 5B of subtractor subcircuit IB. The input terminal 7 of the look-up table 2 has two component terminals 7A and 7B constituting a non-overlapping field, which component terminals are connected to the output terminals 6A and 6B of the subtractor 1, respectively. The components appearing at output terminals 68 and 6B constitute respective non-overlapping fields of subtractor output terminal 6. The output terminal 8 of the look amplifier table 2 similarly has two component terminals 8A and 8B forming a non-overlapping field, and these component terminals are connected to the first input terminals 9A and 9B of the adder subcircuits 3A and 3B. Connect each. Device input terminal 11
component terminals 11A and IIB are connected to second input terminals 12A and 12B of adder subcircuits 3A and 3B, respectively. The device output terminal 14 also has two component terminals 14A and 14B, each forming a non-overlapping field, and these component terminals are connected to the output terminals 13A of the adder nub circuits 38 and 3B.
and 13B, respectively. These output terminals 13
The A and 13B components constitute each non-overlapping 7 field of the output 13 of the adder circuit. Other components indicated by broken lines will be explained below.

The subtracter subcircuit 18 responds to the input terminals 4A and 5A being supplied with the remainder representation values of the first quantity x and the second quantity y modulo n1. The difference from the quantity y1 (
The remainder representation modulo of a specific integer nl of x+-y+) is configured to be output to the output terminal 6A. Similarly, the subtracter subcircuit 1B responds to the fact that its input terminals 4B and 5B are supplied with the remainder representation value of the first quantity x2 and the second quantity y2 modulo n2. Difference from 2'ttyz (×2y
output terminal 6B for the remainder expression modulo of the specific integer n2 of z)
It will be configured to be placed on the ground. nl and n2 are relatively prime;
That is, they do not have a common factor other than 1.

This makes it possible for the subtracter 1, consisting of subtractor subcircuits IA and IB, to represent the values
Each of these representation values is of the form modulo n1 and n2, i.e. X is of the form XI mod nl, X2 mod n2. , IO
B, IIA and IIB to produce an xy representation value at the output terminal 6 of the subtractor 1. The expression value of x-y itself is the modulo n1 and n2 of the remainder form, and the remainder modulo n1 (-x+-V+) is generated in the field 6A of the output terminal 6, and the remainder modulo n2 (-X2-'
7z) is generated in field 6B of output terminal 6. These remainder expression values are supplied as remainder components and 2 to respective fields 7A and 7B of input terminal 7 of look-up table 2, respectively.

The lookup table 2 is such that the modulo (p-1) expression value of k for an arbitrary number among the set values of k is input to the input terminal 7A.
, 7B, generates at the output terminal 8 the expression modulo (p −1) of the exponent j that needs to be raised to the power of the generator g to the value gkl−l by modulo n1 arithmetic. , where n1Xn2-(p-1), the representation value of j is the modulo n1 and n2 of the remainder form, the remainder representation modulo n1(j+) is generated by the field 8 of the output terminal 8, and the remainder representation modulo The configuration is such that n2(jz) is generated in the field 8B of the output terminal 8.

The adder subcircuit 3A, in response to being supplied at its respective input terminals 1.2A and 98 with the remainder representation values modulo n1 of the first quantity r1 and the second quantity j1, It is configured to generate a remainder expression modulo n1 of the sum of two quantities (r++j+) at the output terminal 13A. Similarly, the adder subcircuit 3B, in response to being supplied to its respective input terminals 12B and 9B with the remainder representation values modulo n2 of the first quantity r2 and the second quantity j2, The sum of two quantities r2 and y2 (
output terminal 13B for the remainder expression modulo n2 of rz+jz)
Configure to generate. Therefore, adder subcircuit 3
8 and 3B, the adder 3 has its input terminals 9 and 12.
is supplied with the representation values of the quantities y(-r) and j, each of these representation values is of the form n2, as seen in V
z y21 j+ and y2 expression values are input field 1
2A, 12B, 9A and 9B, respectively, to generate a representation (l!i) of y+j at the output terminal 13. This representation value i itself is in the remainder form modulo n1 and n2, and the remainder modulo n1 (=y++
j−r + ) is produced in field 13A and supplied to field 148 of the device output terminal, and a representation value of the remainder modulo n2 is produced in field l” 13B and supplied to field 148 of the device output terminal. 14B.

For this reason, the output terminals of the device according to the invention shown in FIG. 2 are the representations of X (l!
Supply and input fields IIA and HII of χ1 and 2
In response to the supply of the representation values yl and y2 of y to B, it sets gX-X and gy=y, producing representation values 11 and 12 of i in output fields 14A and 14B, respectively.

Each of the remainder representation values may be in the form of a compact binary code, or a "1 out of m" code, for example;
Here, m is the absolute value (modulus) used for the corresponding expression value. Therefore, in the latter case, input 10 in FIG.
A and IOB are inputs 11^ and IIB and outputs 14A and 14B, respectively, n1 bit and n2 bit 1~
The multiple values that the expression value corresponding to this one case can take are indicated by a binary value of "1" (or "0") for each associated focus. As a simple example, when the values of n and n2 are 3 and 4, respectively, the number n from 0 to 11 can be expressed as follows.

n nod 3 n mocl
ool 0001010
0010 100 0100 001 1000 010 0001 100 0010 001 0100 010 1000 100 0001 001 0010 010 0100 100 1000 2 The above encoding method can be expressed as the input amount (x-y) to lookup table 2 in FIG. from up table When used for the output quantity j, it is necessary to program this lookup table to generate the following relationship between its input code and output code.

Daisa 22 Upper Ban Momme λ 2 Upper N1j2 001 0001001 0
001 010 0010010 0010
010 0001100 0100
001 0010001 1000 10
0 0001010 0001 100
0100100 001'0 100 10
00001 0100 N1j2010
1000 001 0100100 0
001 010 0100001 0010
100 0010010 0100
01.0 1000100 1000 0
01 10003 Entry "rNiff" is a special unique coat, e.g.
．． It can be represented by 110000. Such a relationship can be obtained, for example, by suitably programming a read-only memory or by means of suitable combinatorial logic.

FIG. 3 shows a circuit configuration for the modulo-3 adder subcircuit 3A of FIG. 2 when the above-described encoding method and a specific code for "NiI!" are used.

This circuit of the configuration shown in FIG. 3 is preferably implemented in a programmed logic array (1) LA) which is interconnected as shown and has input terminals 12A and 98 and an output 12 connected to terminal 13A
NAND gates 15 to 26 and 6 imparks 2
7 to 32. Consecutive bins of codes l'y+o+y+ for input 1y. , y12 to input terminal 12A
and successive bits jlo+L++L2 of the code for the input quantity jl are supplied to each line of the input terminal 9A. Continuous Bisotto II of code for output weighing
O+ jll, L2 appears on each line to output terminal 13. It is clear that a true 4 logic table for the configuration of FIG. 3 is required.

The circuit configuration of FIG. 3 is also suitable for use as the modulo-3 subtracter subcircuit 14 of FIG.
Reference symbol 12^+ used for input terminal and output terminal in the figure
9A+ 13A+ V+o+ Vll+ VI2+ J
IO + Jth + JI2111゜+ Ill and 11□ 4^+ 5A+ 6A+ X+o+ X++XI21
y+o+ 3'+z+ yl ++(x+
J+)o+ (x+=y −)+ and (X+
-V+) It is necessary to replace it with z, as shown here x+.

X11 and X1□ are consecutive bits of the code for the input quantity X, and (x+-y+). + (X+-V+)
z (X+-y+L are the consecutive bits of the code for the output quantity (X+-y+). These permutations require that a negative number is equal to (p-1) minus that number. use.

FIG. 4 shows an example of a circuit configuration for the modulo-4 adder subcircuit 3B of FIG. 2 when a particular encoding method is used. A circuit of this configuration is also preferably implemented in a programmed logic array, which is connected as shown and has input terminals 12B and 9B.
It includes 17 NAND gates 33-49 connected to the output terminal 13B and 8 in-hook gates 50-57. Input It y z
Consecutive bits of code for yz. ,y21+ Y2□
and y23 are supplied to each line of the input terminal 12B as shown, and the consecutive bits Jt of the code for the input quantity j2 are supplied to each line of the input terminal 12B as shown.
o-J21. jzz and iz3 are supplied to each line of the input terminal 9B as shown. Continuous pitch of code I~12°+ +21+ 122 and iz for output amount 12
3 appears on each line of the output terminal 13B as shown.

The circuit configuration shown in FIG. 4 is also suitable for use as the modulo 4 subtraction circuit IB of the second garden, and in this case, the reference numeral 12B+ 9B+ used for the input terminal and output terminal in FIG.
13B+ Vzo+ yz+, V2z+ y231
jzo, jzz 221 jz++ iz. +1
21+ 122 and 123 48.5B, 68X20
1 X211 χZZ+ X23+ V20+ y23
．． V22+ V2++ (X2yz). , (Xz-Vz)
++ It is necessary to replace each with (z-Vzh and (Xz-Vz) 3, and here \X20+χ21.X
22 and L23 are consecutive bits of the code for quantity x 2, and (Xi-yz). + (Xi-!/2) +
+ (Xi-V2) 2 and (Xi-VzL are the quantities (Xz
-yz) is a continuous bit of code.

The circuit shown in solid lines in FIG. 2 is the input terminal 118.

The code V1.11B supplied to V1.11B. If the quantity represented by y2 is ``rNij2'' (which itself is the hex expression value of Y=,O), it will not give a correct result.

The output obtained from the adder 3 is a quantity that is a power expression value of X,
That is, under these circumstances, it should be XI and X2, but in reality the output of lookup table 2 is 0,
The output from adder 3 becomes IFi IJ. If such a value of 1FipJ is possible for y++ y2, other circuit components shown in dashed lines in Figure 2 should also be provided to ensure that the circuit gives the correct output even in such a case. These circuit components are a decoder 58 and a multiplexer 61, the input terminals 59 and 60 of the decoder 58 are connected to the respective component terminals 11A and JIB of the device input terminal 11, and the control input terminal 62 of the multiplexer 61 is connected to the decoder 58. Connect to the output terminal 63 of. Each component terminal 64 of the first signal input terminal 64 of the multiplexer 6e
8 and 64B are each component input terminal of the device input terminal 10],
connected to OA and IOB, and also the second
Component input terminals 65A and 65B of the signal input terminal 65 are connected to respective output terminals 13A and 13B of the adder circuit 3, respectively. Component output terminals 148' and 14B' of output terminal 14' of multiplexer 61 constitute new respective component output terminals of the device.

Decoder 58 detects the code for "rNij2" at device input terminals 11A and IIB and is configured not to generate a signal at output terminal 63 when this code occurs.

In response to the output signal from the decoder 58 being supplied to the control input terminal 62, the multiplexer 61 switches the component terminals 64A and 6411 of the first input terminal 64 to each component output terminal 14 of the output terminal 14. When there is no output signal from the decoder 58, the component terminals 65A and 65B of the second input terminal 65 of the multiplexer 61 are connected to the component output terminals 14/l' and 14B' of the output terminal 14. Configure it to connect to each.

Therefore, unless the code supplied to input terminal 111], B is 1FizJ, the device shown in FIG. , 14B'. In this last case, the code Xl+
x2 appears as requested at the output terminals 141)', 14B'.

The look-up table circuit 2 in FIG. 2 has 31 outputs (p-
1) may be configured to generate the value of g in response to the representation modulo (p-1) of any number of set values of k being provided to input terminal 711.7B. It is necessary to raise it to a power and use the modinilo p operation to obtain the expression gk1. In such a case, g゛-gy゛-gygl-
(gX - V - 1) - g
Instead of x+, y), it is necessary to calculate the value (X-Y) using modulo pfi calculation. For example, in the illustrated example described with reference to FIG. - When representing the 9th B3 code as 1-out-off 4 coats, program the lookup table so that the following relationship is obtained between the input code and output code of lookup table 2. You can also.

Include 672 Dan So Kako 1 Njjl! 001 0100001
0001 Ni! ! .

010 0010 001 0001100
0100 010 0001001 1
000 100 1000010 0001
,, 010 0010100 0010
001. 0010001 0100
010 1000010 1000, 0
10 0100too 0001 001
1000001 0010 100 0
100010 0100 1.00 000
1100 1000. 100 0010 modulo p-13 operation and n-2 remainder component modulo 0 lo 3 and 4 quantities x, y (-r), (x-y) (-
k), j and i were selected as in the example.

In practice, fairly large values of p are used. Thus, as another example, the operation modulo Op =181 can be used, where each representation value of the quantities χ, y, (x-y), j, and i is divided into n=3 remainder components modulo 4.5 and 9, respectively. It can be a format. In such a case, it is necessary to configure the subtracter circuit 1 with three subtracter subcircuits that calculate modulo 4, modulo 5, and modulo 9, and each of these subcircuits has input terminals 10 and 11. Between the adders 11
83 also needs to be configured with three adder subcircuits that calculate modulo 4, modulo 5, and modulo 9.
Each of these sub-circuits is also supplied with an input from each corresponding non-overlapping field of the input terminal 11 and output terminal 8 of the look-up table 2.

In the example described above, the output from lookup table 2 was generated on lines 9A, 9B under composite addressing on lines 6A, 6B, but lookup table 2 could also be configured as combinatorial logic. can. The adder or subtracter subcircuits IA1B, 3^ and 3B can also be implemented by combinatorial logic circuits, for example as described with respect to FIGS. 3 and 4, so that each of them can be stored in an appropriately programmed read-only memory It is clear that it can be formed.

Although, as mentioned above, the same encoding scheme is used for the quantities for each part of the device, it is clear that this need not be the case. For example, the amount XI + X2
+ V++ y2+ j+ and 12 can use a 1-out-of-N coding method, whereas the subtracter circuits IA and IB and the look amplifier table 2 have conventional compact binary coding at their output terminals. The output can be configured to produce an output in the form of a code, with the lookup table 2 and adder subcircuits 3A and 3B being modified accordingly to respond in a desired manner to the compact binary code used.

Since the arithmetic processing is carried out in three separate stages, namely the subtraction, look 2 up and addition stages, the so-called "pipelining" can easily be used to optimize the processing of successive input operands everywhere.

If desired, techniques for reducing the dimensions of the Zech table 2, such as those described in the applicant's co-pending Japanese Patent Application No. 1, may be used in the device according to the invention.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an example of a conventional arithmetic device; FIG. 2 is a block diagram showing a first example of the arithmetic device according to the present invention; FIG. Block diagram showing an example of the configuration; The fourth garden is a block diagram showing an example of the configuration of the modulo 4 subtracter subcircuit in the device of the second garden. l...Subtractor IA, IB...Subtractor subcircuit 2...Lookup table 3...Adder 3A, 3B...Adder subcircuit 3 15-26...NAND gate 33- 49...NAND gate 58...Decoder 27-32...Inverter 50-57...Inverter 1...Multiplexer

Claims (1)

[Claims] 1. ¥x¥ where g^x=X and ¥y where g^y=Y
In response to the input remainder representation modulo (p-1) of ¥ being supplied, the generator ¥g¥ is converted to a value (X+A・
In an arithmetic unit for generating a remainder expression modulo (p-1) of a power index i that needs to be raised to a power of Y), each residue expression value of i, x, and y is (p-1), each comprising a plurality of n-residue components modulo of a uniform set of integers, each of which is equal to (p-1), and for each said integer said device receives an input remainder representation value for said integer; a subtractor and a look-up table to which the outputs of all the subtractors are provided, the modulo of each of the plurality of n remainder components of each said integer upon receipt of the subtraction result for each set of representation values of x and y; are generated at the output terminal of the lookup table, and together, the remainder representation modulo (p-1) of an arbitrary number of the set values of k is supplied to the input terminal of the lookup table. The remainder expression modulo (p−
1) a lookup table for constructing the integer, a first adder input terminal receiving a remainder representation value for the integer of one of the input remainder representation values, and a second adder input terminal receiving the remainder representation value for the integer; separate integers for receiving the outputs of lookup tables corresponding to the same integers and collectively generating a remainder representation value of the sum of each value of the received modulo (p-1) by the additive modulo of each of these integers. has an adder of
An arithmetic device characterized in that the allowable values for A are +1 and -1. 2. Detecting when a representation value of y corresponding to Y=0 is provided to the second input terminal of the arithmetic device, and otherwise being provided to the output terminal of the arithmetic device in response to this condition. 2. The arithmetic device according to claim 1, further comprising a circuit for replacing any one of the expression values with any one of the expression values supplied to the first input terminal of the arithmetic device in this case.