JP3515462B2 - Remainder arithmetic device and method - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to modulo large integers, such as in the field of public key cryptography applied to cryptographic communication and digital signatures, or in the field of number theory algorithms applied to prime factorization. The present invention relates to a remainder system arithmetic device and method capable of realizing arithmetic processing including a large number of additions or subtractions.

[0002]

2. Description of the Related Art For example, in an information communication network or a computer system (hereinafter referred to as a computer system), information is electronically exchanged and stored. When such a computer system or the like is used by an unspecified large number of users due to its large scale, there is a problem that a malicious user taps or falsifies information. Therefore, in computer systems and the like, public key cryptography is normally used from the viewpoint of preventing these problems.

This type of public key cryptography is generally realized by an arithmetic operation using a multiple integer as a modulus (modulus), and the performance depends on the operation speed. For the representation of multiple long integers, the standard number system with a radix of 2 (Radix repr
esentation) (so-called binary representation) and coset representation (R
NS; Residue Number System, hereinafter referred to as RNS expression).

The RNS representation is a number of modulo a ₁ , a ₂ ,
, A _n , the integer x is their modulus {a ₁ , a ₂ ,
, A _n } is a method of expressing by a set of residual values x ₁ , x ₂ , ..., X _n .

For example, in the RNS representation, the integer x = (x₁，
x_Two, ..., x_n) Is expressed. However, x₁= X mo
da₁, X_Two= X mod a_Two, ..., x_n= X m
oda_nIs. In the following specification, RNS is used.
Set of mods used in expression {a ₁, A_Two, ..., a_n} Is the basis
It is called B. In RNS representation, each element of the base is
A prime positive integer is usually used. In addition, the Chinese Remainder Theorem
Therefore, positive integers less than the product of each element of the base are uniquely expressed.
Is guaranteed.

For example, the basis B = {a ₁ , a ₂ , ...,
a _n } and a positive integer A = a ₁ * a ₂ * ... * a _n , a positive integer less than A is uniquely expressed in the RNS expression. Hereinafter, in the present specification, R by R
The NS-expressed integer x is expressed as <x> _A.

Such an RNS expression has an advantage that addition, subtraction and multiplication modulo A can be easily executed.
That is, in the RNS expression, as shown in the following expressions (1) to (3), each element of the operation target <x> _A , <y> _A is individually added or subtracted by each method of the base B. , The result of multiplication is the calculation result.

[0008] <X>_A+ <Y>_A(Mod A) = (x₁+ Y₁(Mod a₁), X_Two+ Y _Two (Mod a_Two), ..., x_n+ Y_n(Mod a_n))… (1) <X>_A-<Y>_A(Mod A) = (x₁-Y₁(Mod a₁), X_Two-Y _Two (Mod a_Two), ..., x_n-Y_n(Mod a_n))… (2) <X>_A* <Y>_A(Mod A) = (x₁* Y₁(Mod a₁), X_Two* Y _Two (Mod a_Two), ..., x_n* Y_n(Mod a_n))… (3) Therefore, the RNS representation is represented by each of n arithmetic units.
Each method {a₁, A_Two, ..., a_n} Parallel processing
Since it is possible, it is suitable for high-speed calculation.

However, when the RNS expression is applied to public key cryptography, for example, the following problem remarkably appears. That is, since the modulus p used in public key cryptography is often a prime number or a product of a few prime numbers, the modulus p
If the factor of is an element of the base B, then n = 2 to 3, and the degree of speedup by parallel processing is low.

Therefore, in the RNS representation, the basis B =
The product A of each element is maintained while maintaining {a ₁ , a ₂ , ..., A _n }.
There is a demand for p (: p <A) below to be the p of public key cryptography.

Accordingly, the remainder addition <x> _A in the modulus p is added.
+ <Y> _A (mod p), remainder subtraction <x> _A- <y
> _A (mod p) and modular multiplication <x> _A * <y> _A
It is desired to realize a high-speed (mod p) arithmetic method. However, among these, the modular multiplication with the modulus p is considered to be a high-speed arithmetic method based on Montgomery multiplication.

However, there is still no effective method for the remainder addition and the remainder subtraction in the modulus p. The reason is that the RNS representation has a property that it is difficult to compare the magnitude of two given numbers because it is a set of residue values, while the modulus p
This is because the remainder addition and subtraction in (1) requires comparison of the calculation result and the modulus p.

That is, the remainder system addition <x> _A + <y> _A
Needs to subtract <p> _A from the addition result when the obtained addition result is larger than the RNS expression <p> _{A of} modulus p.

The remainder subtraction <x> _A- <y> _A is
When <y> _A is larger than <x> _A , <p> _A needs to be added to the subtraction result.

This kind of two-value comparison is based on the conventional RN.
Despite the drawbacks of S-expression, there is still no efficient method. Therefore, the RNS expression is the product A of the base elements.
It is considered unsuitable for modulo addition and subtraction with modulus p different from.

[0016]

As described above, in the conventional coset arithmetic system, the two integers <x> _A and <y> _A represented by RNS in the modulus A are different from the modulus p in the modulus A. Although there is a demand for an efficient method of performing remainder addition or subtraction under the condition, there is still a situation where the demand cannot be satisfied.

The present invention has been made in consideration of the above-mentioned circumstances, and efficiently performs a remainder addition under a modulus p different from the modulus A for two numbers expressed by the modulus A in the modulus A. It is an object of the present invention to provide a residual coprocessor and method.

Another object of the present invention is to provide a coset arithmetic unit and method capable of highly efficiently performing coset subtraction under the same method p, in addition to the coset addition. is there.

[0019]

The invention corresponding to claim 1 is to provide a plurality of coset data <x> represented by cosets in the modulus A.
_A , <y> _A coprocessor for adding A and _A together under a modulus p (: p <A), which is a modulus p in a mixed radix representation in advance.
And a multiple radix data (p, 2p, ..., hp) obtained by multiplying h by (h = 1 to h is a positive integer) is set, and the modulus p is previously set to h by the remainder system expression. Multiple multiple data (<p> _A , 2 * <p> _A , ..., h * <
p> _A ) is set and the inputted remainder system data <x> _A , <y> _A are added in a remainder system expression, and a remainder system addition result <z> _A is obtained. Adding means,
Remainder system addition result <z obtained by the remainder system adding means
> Based on the expression conversion means for converting _A into the mixed radix representation, the addition result z displayed by the mixed radix displayed by the expression conversion means, and each multiple data in the mixed radix system multiple setting means, The fact that the addition result z displayed in the mixed radix includes a maximum of j times (0 ≦ j ≦ h) multiples data jp (jp
≦ z <(j + 1) p) and a multiple determining means for determining a multiple j, and a remainder addition obtained by the remainder adding means based on the multiple j obtained by the multiple determining means. result <z> a multiple data j * <p> _a of j times in the coset multiple setting means subtracts from _a, coset addition in the obtained modulo p result <z> and outputs the _a addition result output It is a coset system computing device including means.

The invention according to claim 2 is method A
Multiple coset data <x>_A, <Y>
_AWith respect to <x> under the law p (: p <A)_AFrom before
Note <y>_AA coprocessor for subtracting,
Pre-mixed radix representation modulo p times (h = positive integer from 1 to h)
Multiple multiple data (p, 2p, ..., hp)
Mixed radix system multiple setting means, and the remainder system expression
Multiple multiple data (<p>_A, 2 *
<P>_A,…, H * <p>_A) Is the remainder system multiple
The setting means and the remainder system expression of the modulus p are set to <p>._AAnd
The above <y> _AData that exceeds the upper limit of d * <p
>_AUsing the above d * <p>_AFrom above <y>_AThe remainder
Subtract by system expression, positive remainder subtraction result <S>_ASurplus
The coset subtraction means and the positive subtraction means obtained by the coset subtraction means.
Remainder subtraction result <S>_AAnd the above <x>_AAnd the remainder system table
Current addition, remainder addition result <z>_AModulo addition to obtain
Means and the remainder system addition obtained by the remainder system addition means
Result <z>_ARepresentation conversion means for converting to mixed radix representation
And the mixed radix obtained by the expression conversion means is displayed.
Addition result z and each multiple in the mixed radix system multiple setting means
Based on the numerical data and the addition result displayed in the mixed radix
The result z contains the multiple data jp of j times (0 ≦ j ≦ h) at maximum.
Judgment (jp ≦ z <(j + 1) p) and determine the multiple j
And a multiple obtained by the multiple determining means.
The remainder obtained by the remainder adder based on the number j.
Coset addition result <z>_AFrom the remainder system multiple setting means
j times multiple data j * <p>_ATo obtain the modulo p
Remainder subtraction result <z>_ASubtraction result output hand that outputs
It is a coset arithmetic unit including a stage.

Furthermore, the invention corresponding to claim 3 is method A
Plural remainder data <x> _A , <y expressed by the remainder system in
> _A coprocessor for adding _{A to} each other under a modulo p (: p <A).
= Positive integer of 1 to h), approximate value data (p ', 2p', ..., hp ') indicating the upper w digit among a plurality of multiple data
And binary number system multiple setting means, and a plurality of multiple data (<p
> _A , 2 * <p> _A , ..., h * <p> _A ) and a remainder system data input <x>
_A , <y> _A is added by the remainder expression, and the remainder addition result <
z> _A , a residue system addition means, an approximation conversion means for converting the residue system addition result <z> _A obtained by the residue system addition means into a binary representation with an approximate value of the upper w digits, and the approximation conversion. Approximate value data z'represented by a binary number obtained by the means
And the approximate value data z ′ of the addition result based on the approximate value data in the binary system multiple setting means is j at the maximum.
Including that double (0 ≦ j ≦ h) approximate value data jp ′ is included (j
p ′ <z ′ ≦ (j + 1) p ′) is determined and a multiple determining means for determining a multiple j and a multiple j obtained by the multiple determining means are obtained by the remainder adder. From the remainder system addition result <z> _A , j in the remainder system multiple setting means
This is a remainder system arithmetic device provided with addition result output means for subtracting the multiple data j * <p> _A of double and outputting a remainder system addition result <z> _A in the obtained modulus p.

The invention corresponding to claim 4 is the method A
Multiple coset data <x>_A, <Y>
_AWith respect to <x> under the law p (: p <A)_AFrom before
Note <y>_AA coprocessor for subtracting,
Preliminarily multiply the modulus p by a binary expression (h = 1 to a positive integer).
Approximate value data showing the upper w digit of multiple multiple data
A binary number system in which data (p ', 2p', ..., hp ') is set
With a multiple setting means, the modulus p is multiplied by h in advance with the remainder expression.
Multiple multiple data (<p>_A, 2 * <p> _A，… ，
h * <p>_A) Is set to the remainder multiple setting means, and
<P> is the coset representation of the notation p_AAnd the above <y>
_AData that exceeds the upper limit value of d * <p>_AUsing
Note d * <p>_AFrom above <y>_ASubtract with modulo expression
Then, the positive remainder subtraction result <S>_ARemainder subtraction means for obtaining
And the positive remainder subtraction obtained by the remainder subtraction means
Result <S>_AAnd the above <x>_AAnd are added in the remainder expression,
Remainder system addition result <z>_ARemainder system adding means for obtaining
Coset addition result <z> obtained by the coset addition means_A
Approximate converter that converts to the binary representation with the approximate value of the upper w digits
And the binary representation of the binary number obtained by the approximation conversion means.
The similar value data z'and each of the numbers in the binary system multiple setting means.
Approximate value data of the addition result based on similar value data
z'is maximum j times (0≤j≤h) approximate value data jp '
Is determined to include (jp '<z'≤ (j + 1) p'), and a multiple
a multiple determining means for determining j, and the multiple determining means
Based on the obtained multiple j, the remainder system adding means
Result of remainder addition <z>_AFrom the remainder system multiple setting
J times multiple data j * <p> in the determining means_ASubtract and get
Remainder subtraction result <z>_ASubtract to output
It is a coset arithmetic unit having a result output means.

Further, the invention according to claim 5 is based on a set of n disjoint integers {a ₁ , a ₂ , ..., _An }, and A = a ₁ * a ₂ * ... * a condition 0 ≦ x for _n ,
Let 2 integers that satisfy y <A be x, y, let the remainder system representation of the integer x be (x ₁ , x ₂ , ..., X _n ), and let the remainder system representation of the integer y be (y ₁ , y ₂ , , Y _n ), p
<A modulo p is a positive integer p that satisfies A, and the remainder addition result z = x + y (mod p) = (z ₁ , z ₂ ,
, Z _n ), which is a residue system operation method for calculating
Expression of remainder addition z _i = x _i + y _i (mod a _i ) (1
≦ i ≦ n) on the basis, and the coset addition step of calculating the modulo sum z for each elements z _i in the law A, each of said elements obtained in the residue system adds steps z _i and below v _i Based on the equation, the remainder addition result z is expressed as a mixed radix (v ₁ ,
v _2, ..., a representation conversion step of converting the v _n), the addition result z of the mixed radix obtained in representation conversion process,
A value obtained by multiplying the modulus p displayed in mixed radix by j {p, 2p, ...,
jp, ..., hp} (where 1 ≦ j ≦ h), and the remainder system expression of the method p is expressed by (p ₁ , p ₂ ,
, _Pn ), based on the comparison result of the method p comparison step, if (jp ≦ z <(j + 1) p, then z _i = z _i −j
* P _i (mod a _i ) (1 ≦ i ≦ n) is executed, and hp
If ≦ z, then z _i = z _i −h * p _i (mod a _i ) (1
.Ltoreq.i.ltoreq.n) is performed to calculate the remainder system addition result z in the modulus p (mod p), and the remainder system operation method is included.

[0024] v₁= Z₁(Mod a₁) v_Two= (Z_Two-V₁) * C₁₂(Mod a_Two) v_Three= ((Z_Three-V₁) * C₁₃-V_Two) * C_{twenty three}(Mod a_Three)     : v_n= ((Z_Three-V₁) * C_1n-V_Two) * C_2n-...- v_(n-1)) * C_{(n-1) n}( mod a_n)   However, C_ji= A_j ^-1mod a_i, (J = 1, 2, ..., i-1) The invention corresponding to claim 6 is such that n disjoint integers.
A set of numbers {a₁, A_Two, ..., a_n} As a base, and A = a₁
* A_Two* ... * a_nSatisfies the condition 0 ≦ x, y <A
Let 2 be x and y be the remainder system representation of the integer x
(X₁, X_Two, ..., x _n) And the remainder system table of the integer y
Present (y₁, Y_Two, ..., y_n), Satisfy p <A
The positive integer p modulo p and the remainder subtraction result of x and y
z = xy (mod p) = (z₁, Z_Two,…, Z_n)
Which is a residue system calculation method for calculating
Coset expression (p₁, P_Two,,, p_n) And the above
Modulo subtraction using multiple d * p of p that exceeds the upper limit of y
Expression s_i= D * p_i-Y_i(Mod a_i) (1 ≦ i ≦
n), the positive remainder subtraction result s = (s₁, S_Two，
…, S_n), The remainder subtraction step, and the remainder subtraction
The element s obtained by the arithmetic process _iUsing the remainder addition formula
z_i= S_i+ X_i(Mod a_i) (1 ≦ i ≦ n)
Then, the remainder system addition result z in the modulus A is set to the element z._iCalculated for each
Obtained by the remainder system addition step and the remainder system addition step
Element z_iAnd the following v_iBased on each equation of
Calculation result z is displayed in mixed radix (v₁, V_Two, ..., v_n)
The expression conversion step for converting the expression and the mixture obtained in the expression conversion step.
Addition result z displayed in mixed radix and modulus displayed in mixed radix
A value obtained by multiplying p by j {p, 2p, ..., jp, ..., hp} (however,
And 1 ≦ j ≦ h), the method p comparing step, and the method
Represent the remainder system of p by (p₁, P_Two,,, p_n)
Then, based on the comparison result of the method p comparison step, (jp ≦
If z <(j + 1) p then z_i= Z_i-J * p_i(Mod a
_i) (1 ≦ i ≦ n), and if hp ≦ z, z_i= Z
_i-H * p_i(Mod a_i) (1 ≦ i ≦ n)
To calculate the remainder subtraction result z by the above method p
Modal execution method including a mod p execution process
Is the law.

V ₁ = z ₁ (mod a ₁ ) v ₂ = (z ₂ −v ₁ ) * C ₁₂ (mod a ₂ ) v ₃ = ((z ₃ −v ₁ ) * C ₁₃ −v ₂ ) * _{C 23 (mod a 3):} v n = ((z 3 -v 1) * C 1n -v 2) * C 2n - ...... -v (n-1)) * C (n-1) n (mod a _n ) However, C _ji = a _j ^-1 mod a _i , (j = 1, 2, ..., i-1) Furthermore, the invention corresponding to claim 7 is a set of n disjoint integers { Based on a ₁ , a ₂ , ..., A _n }, A = a
Let ₁ * a ₂ * ... * a _{n be} two integers that satisfy the condition 0 ≦ x, y <A, and let the remainder representation of the integer x be (x
₁ , x ₂ , ..., X _n ) and the remainder system representation of the integer y is (y ₁ , y ₂ , ..., Y _n ), a positive integer p satisfying p <A is assumed to be the modulus p and the x , Y remainder system addition result z =
This is a remainder system operation method for calculating x + y (mod p) = (z ₁ , z ₂ , ..., Z _n ), and is a formula of remainder system addition z _i = x _i + y _i (mod a _i ) (1 ≦ i ≦ n) on the basis, and the coset addition step of calculating the modulo sum z for each elements z _i in the law a, a value obtained by dividing the a at the _{a i a i (= a /} a _i) and then, when the multiplicative inverse of the a _i and a _i ^-1 in modulo a _i, based on the element z _i obtained in the residue system adding step, a positive integer k satisfying the following equation Σ Based on the parameter calculation step for calculating, the element z _i obtained in the remainder system addition step, the positive integer k obtained in the parameter calculation step, and the formula of Σ below, the remainder system addition result z is a binary number. Approximate value z'of the upper w bits of the expressed value (however, w is less than the basic operation width of the arithmetic unit body)
And the approximate value z'in the binary number expression obtained in the approximate conversion step and the approximate value {p ', (w' of the upper w bits of the value obtained by multiplying the binary p expressed by the modulus p by j). Two
p) ', ..., (jp)', ..., (hp) '} (where 1
.Ltoreq.j.ltoreq.h), and when the remainder system expression of the method p is (p ₁ , p ₂ , ..., P _n ), based on the comparison result of the method p comparison step. , (Jp) '<z'
If ≦ ((j + 1) p) ′, then z _i = z _i −j * p _i (mod
a _i ) (1 ≦ i ≦ n) is executed, and if (hp) ′ <z ', then z _i = z _i −h * p _i (mod a _i ) (1 ≦ i ≦
n) is executed to calculate a remainder system addition result z in the modulus p (mod p), and a remainder system operation method is included.

[0026]

[Equation 4]

The invention corresponding to claim 8 is the residue system calculation method according to claim 7, wherein the parameter calculating step calculates a positive integer k according to the following equation.

[0028]

[Equation 5]

Further, in the invention corresponding to claim 9, in the coset operation method according to claim 7, in the modulo p comparing step, instead of an approximate value for j times p,
Approximate value of upper w bits of a value obtained by multiplying M * p by j {(M *
p) ′, (2M * p) ′, ..., (hM * p) ′} (where 1 ≦ j ≦ h), and the above (mo)
In the execution step, (jM * p) ′ <z ′ ≦ ((based on the comparison result for j times M * p by the method p comparison step, instead of the comparison result for j times p. j
+1) M * p) '(where j <h), then z _i = z _i −jM
* P _i (moda _i ) (1 ≦ i ≦ n) is executed, and (hM
* P) '<z' if _{z i = z i - (hM} * p i) (m
od a _i ) (1 ≦ i ≦ n) to calculate the residue system addition result z in the modulus p.

Further, the invention according to claim 10 is based on a set of n disjoint integers {a ₁ , a ₂ , ..., _An }, and A = a ₁ * a ₂ * ... * a condition 0 ≦ x for _n ,
Let 2 integers that satisfy y <A be x, y, let the remainder system representation of the integer x be (x ₁ , x ₂ , ..., X _n ), and let the remainder system representation of the integer y be (y ₁ , y ₂ , , Y _n ), p
<A modulo p is a positive integer p that satisfies A, and the remainder subtraction result z = xy (mod p) = (z ₁ , z ₂ ,
, Z _n ), which is a residue system operation method for calculating
When the remainder system expression of p is (p ₁ , p ₂ , ..., P _n ), a multiple d * p of p that exceeds the upper limit of y is used,
Modulus subtraction formula s _i = d * p _i −y _i (mod a _i ).
(1 ≦ i ≦ n), the positive remainder subtraction result s =
Using the remainder subtraction process for calculating (s ₁ , s ₂ , ..., S _n ) and the element s _i obtained by the remainder subtraction process, the formula z _i = s _i + x _i (mod a _i )
Based on (1 ≦ i ≦ n), the remainder system addition result z in the modulus A
Is added to each element z _i , and a value obtained by dividing A by the a _i is A _i (= A / a _i ), and A _i ⁻¹ is a multiplication of the A _i in the modulus a _i . When the inverse element, based on the element z _i obtained in the remainder system addition step, the following Σ
Based on the parameter calculation step of calculating a positive integer k satisfying the equation, the element z _i obtained in the remainder system addition step, the positive integer k obtained in the parameter calculation step, and the equation of Σ below. The approximation conversion step of calculating an approximation value z ′ of the upper w bits (where w is equal to or less than the basic operation width of the operation device main body) of the binary representation of the remainder addition result z, and the approximation conversion step. Approximate value z'in binary representation and 2
Approximate value of upper w bits {p ', (2p)', ..., (jp) ', ..., (h
p) ′} (where 1 ≦ j ≦ h) and the method p comparison step, and the coset expression of the method p is (p ₁ , p ₂ , ...,
p _n ), based on the comparison result of the method p comparison step, if (jp) ′ <z ′ ≦ ((j + 1) p) ′, then z _i =
z _i −j * p _i (mod a _i ) (1 ≦ i ≦ n) is executed, and if (hp) ′ <z ′, then z _i = z _i −h * p _i (m
od a _i ) (1 ≦ i ≦ n) is executed to calculate the remainder addition result z in the modulus p (mod p)
It is a remainder system calculation method including an execution step.

[0031]

[Equation 6]

(Operation) Therefore, in the invention corresponding to claim 1, by taking the above means, a plurality of multiple data (p, 2p,
, Hp) is set, and a plurality of multiple data (<p
> _A , 2 * <p> _A , ..., h * <p> _A ) is provided, and the remainder system addition means is provided, and the remainder system addition means inputs the remainder system data <x> _A , < When y> _A is added by a residue system expression and a residue system addition result <z> _A is obtained, the expression conversion unit obtains a residue system addition result <the residue system addition result <
z> _A is converted into the mixed radix representation, and the multiple determination means is the mixed radix represented addition result z obtained by the expression conversion means.
And the multiple data in the mixed radix system multiple setting means, it is determined that the addition result z displayed in the mixed radix includes a maximum of j multiple data jp, and the multiple j is determined. The output means, based on the multiple j obtained by the multiple determination means, from the remainder addition result <z> _A obtained by the remainder addition means, the j-fold multiple data j * <p in the remainder multiple setting means. > _A is subtracted, and the remainder addition result <z> _A in the obtained modulus p is output.

In this way, it is checked whether the result of modular addition in modulo A is converted into a mixed radix representation that is easy to compare and corresponds to j times mod p, and the modular addition in modulo A is performed in accordance with this multiple j. Since the result is converted to the remainder addition result of the modulus p, the remainder addition under the modulus p different from the modulus A can be executed with high efficiency for the two numbers expressed by the modulus A. .

In the invention according to claim 2, when the remainder subtraction means sets the remainder expression of the modulus p to <p> _A ,
Using multiple data d * _{<p> A} exceeds the upper limit of _{<y> A,} the _{<y> A} from d * _{<p> A} subtracts the modulo system representation,
When the positive remainder subtraction result <S> _A is obtained, the remainder adding means adds the positive remainder subtraction results <S> _A and <x> _A obtained by the remainder subtraction means by the remainder expression. Then, the remainder addition result <z> _A is obtained.

Hereinafter, similar to the operation corresponding to claim 1,
Through the expression conversion means, the multiple conversion means determines that the remainder addition result <z> _A corresponds to j times the modulus p, and the subtraction result output means is based on the multiple j obtained by the multiple determination means. And the remainder system addition result obtained by the remainder system addition means <
From z> _A, the multiple data j times j times in the remainder system multiple setting means
* <P> _A is subtracted, and the remainder subtraction result <z> _A in the obtained modulus p is output.

Thus, first, the subtraction number y is subtracted from the value dp that exceeds the upper limit of the subtraction number y, and the remainder subtraction result s
After ensuring the correctness of the operation by always making a positive value, the original subtraction number x is added to the remainder subtraction result to obtain the remainder subtraction result in the modulus A. Since the remainder subtraction result in this method A is converted into the remainder subtraction result in the method p, the remainder subtraction under the method p different from the method A is applied to the two numbers expressed in the method A. Can be performed with high efficiency.

Further, in the invention corresponding to claim 3, approximate value data (p ', 2p', ..., hp ') indicating the upper w digits of a value obtained by multiplying the modulus p by h in binary representation is set in advance. Binary number system multiple setting means, and multiple data (<p> _A , 2 * <p> _A , ..., H * <p> obtained by multiplying the modulus p by h in advance by the remainder system expression.
_A ) is set, and the remainder system multiple setting means is provided, and the remainder system adding means uses the inputted remainder system data <x> _A , <y>.
_{When A} is added by a residue system expression and a residue system addition result <z> _A is obtained, the approximation conversion means uses the residue system addition result <z> _A obtained by the residue system addition means as an approximate value of the upper w digit. The addition result is converted into a binary number representation, and the multiple determination means determines the addition result based on the approximate value data z ′ in the binary number representation obtained by the approximation conversion means and each approximate value data in the binary number system multiple number setting means. It is determined that the approximate value data z ′ includes j times the approximate value data jp ′ at the maximum, the multiple j is determined, and the addition result output means
On the basis of the multiple j obtained by the multiple determining unit, the j-th multiple data j * <p> _A in the remainder multiple setting unit is subtracted from the remainder addition result <z> _A obtained by the remainder adding unit. Then, the obtained remainder addition result <z> _A in the modulus p is output.

As described above, it is examined whether or not the residue system addition result in the modulus A is approximately converted into a binary number representation and approximately corresponds to j times the modulus p, and the remainder of the modulus A is calculated according to this multiple j. Since the system addition result is converted into the remainder system addition result of the modulus p, the remainder system addition under the modulus p different from the modulus A is efficiently performed for the two numbers represented by the modulus A in the modulus A. You can

Since the invention corresponding to claim 4 applies the residue subtraction method corresponding to claim 2 to claim 3, in addition to the operation corresponding to claim 3,
Similar to the action corresponding to, the remainder subtraction under the modulus p different from the modulus A can be executed with high efficiency for the two numbers represented by the modulus A in the modulus A.

Further, the invention corresponding to claims 5 and 6 is achieved by each step including the specific mathematical expressions described above.
The action corresponding to can be easily and reliably achieved.

Furthermore, the invention according to claim 7 can easily and surely achieve the action corresponding to claim 3 by each step including the above-mentioned specific mathematical expression. Also,
Since the above-mentioned mathematical expression is in a form suitable for parallel calculation, it is possible to reduce the processing time of coset operation by executing parallel calculation.

Further, the invention according to claim 8 provides a more specific formula of the parameter calculation step, so that the operation corresponding to claim 7 can be more easily and surely achieved.

Furthermore, the invention corresponding to claim 9 is the method p
In the comparison step and the (mod p) execution step, instead of the approximation value for j times p, approximate values {(M * p) ′, (2M * p) ′, ... (HM *
Since p) ′} is used, it is possible to obtain a modification of the action corresponding to claim 7.

Further, the invention according to claim 10 can easily and surely obtain the action corresponding to claim 4 by each step including the above-mentioned specific mathematical expression. Also,
Similar to the operation corresponding to claim 7, it is possible to shorten the processing time of the coset operation.

[0045]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below with reference to the drawings. It should be noted that each of the following embodiments can be combined with the remainder multiplication method in the RNS representation assuming the same device configuration, and for example, elliptic curve cryptography under the RNS representation can be efficiently implemented. Therefore, specifically, it provides an efficient operation procedure in the modulo p of the two numbers x and y expressed in RNS.

Here, in each of the following embodiments, as described above, the basis used in the RNS expression is B = {a ₁ , a ₂ ,
, A _n }, and the product of the base elements is A = a ₁ * a ₂ * ... *
_Let an. Since the calculation result is expressed as a unique value in RNS expression, there is a relation of p <A. Also, 2 integers x,
y satisfies the conditions 0 ≦ x and y <A.

In many cases, public key cryptography is an algorithm that obtains a final calculation result through a combination of exponentiation and addition / subtraction multiplication in the modulus p. Such an algorithm does not require the calculation result in the middle to be less than p,
If the calculation result is less than 2p (including the case where it is larger than the exact remainder value by the modulus p by p), it can be input to the next calculation.

That is, in a series of algorithms in which various coset arithmetic operations are combined, the magnitude relation between the final arithmetic result and the modulus p is compared, the multiple of the modulus p is subtracted from the arithmetic result, and finally the modulus p is obtained. If the structure is such that an accurate remainder value of 1 is obtained, the intermediate calculation result may be less than 2p. Note that the property that the operation result may be restricted to less than p only when an accurate remainder value is required is not limited to public key cryptography, and is the same in general number theory algorithms.

Therefore, in each of the following embodiments, a coset arithmetic unit and method capable of executing coset addition / subtraction that guarantees an arithmetic result of less than 2p (including naturally less than p) will be described.

(First Embodiment) FIG. 1 shows a first embodiment of the present invention.
FIG. 3 is a block diagram showing the configuration of a coset arithmetic unit according to the embodiment.
Is. This remainder-based arithmetic device is provided with an arithmetic controller 10
And m arithmetic circuits 20 ₁~ 20_mVia bus 30
Connected to each other.

Here, the arithmetic controller 10 has a function of exchanging data with the arithmetic circuits 20 _{1 to} 20 _m, and
It has a function of controlling the operation contents (remainder system addition, remainder system subtraction, remainder system multiplication) of each of the arithmetic circuits 20 _{1 to} 20 _m , and has a function of causing each arithmetic circuit to execute a desired arithmetic operation. As the control of the content of operation, for example, that the selector is provided to select the adder circuit and the multiplier circuit of the arithmetic circuit 20 ₁ in to 20 _m gives a control signal to the selector to the arithmetic circuit 20 within _one to 20 _m Can be realized by.

Specifically, the arithmetic controller 10 has a function of causing each of the arithmetic circuits 20 _{1 to} 20 _m to perform remainder system addition of two integers <x> _A and <y> _A represented by RNS. as shown in 2 controls each arithmetic circuits ₂₀ 1 to 20 _m, and a function for converting the mixed radix displayed using modulo sum _{<z> a} halfway algorithm Garner, the arithmetic circuit ₂₀ 1 to 20 _{For m} , the addition result z displayed in mixed radix and the multiple p of the modulus p displayed in mixed radix {p, 2p,
, (Jp), ..., (hp)} are compared with each other to determine the multiple j, and based on the multiple j, the remainder addition result <for each arithmetic circuit 20 _{1 to} 20 _m z> has a function of subtracting the <uk> _a the modulus p and j times from _a, and a function of outputting a coset addition result <z> _a in the resulting modulus p.

On the other hand, the arithmetic circuits 20 _{1 to} 20 _m are electrically arranged in parallel with each other and have the same configuration. Therefore, in the following description, an arbitrary arithmetic circuit 20 _i (where i = 1, 2, ..., M) will be described as a typical example.

That is, the arithmetic circuit 20 _i includes the RAM 21
_i and the arithmetic unit 22 _i , for example, a 32-bit CPU mounted on a well-known personal computer can be used. From the viewpoint of increasing the speed of computation by parallel processing, the number m of the arithmetic circuits ₂₀ 1 to 20 _m is
It is preferably the same as the number n of base elements.

Operation unit 22_iIs the arithmetic controller
RAM21 according to the control from 10. _iW bits in each other
Addition and subtraction of integers, addition and subtraction of remainder system in w-bit modulus
The multiplication is executed and the execution result is stored in the RAM 21._iThe ability to write to
Has and RAM 21_iThrough the arithmetic controller 10
And other arithmetic circuits 20₁~ 20_i-1, 20_{i + 1}~ 20_mMutual
It also has a function to execute parallel operations while exchanging data.
ing.

Next, the coset operation method by the coset operation device configured as described above will be described with reference to the flowchart of FIG. Now, for example, it is assumed that it is necessary to perform addition processing of the remainder system of two numbers x and y while executing the public key encryption algorithm. In each of the arithmetic units 22 _{1 to} 22 _m , a modulus value ai that is the basis B of the RNS expression is set via an external CPU (not shown) via a bus 30, and the basis-dependent parameter C _{(i- 1) i} is set (ST1).

Further, the arithmetic controller 10 is an external C
When the modulo value p and its multiples p, 2p, ..., hp are input from the PU, these are set in the arithmetic units 22 _{1 to} 22 _m . However, it may be directly set in each of the arithmetic units 22 _{1 to} 22 _m without going through the arithmetic controller 10.

Of the set values related to the modulus p, each of the arithmetic units 22 _{1 to} 22 _m displays i * p as a mixed radix representation (for comparison of magnitude), and divides p, 2p, ..., hp by the modulus a _i. RNS expression (for j-fold subtraction) and hold the values by both expressions (ST2).

Further, each of the arithmetic units 22 _{1 to} 22
_m is the number of 2 x from an external CPU, y is input, these x, by dividing y by law _{a i} RNS representation by elements _x i, holds converted to _{y i} (ST3).

The above steps ST1 to ST3 are phases which are performed only once in advance, and when the data already expressed in RNS is added to the remainder system, step ST3 is unnecessary. Based on the above preparations, the remainder addition is actually executed below.

As described above, the remainder addition is x + y <A
Under the premise of, the processing is performed for each element xi, yi by addition with the modulus a _i .

That is, the remainder addition is <z> _A = <x
> A + <y> A, <z> _A = <x> A + <y
> A (mod A) = (x ₁ + y ₁ (mod a ₁ ),
x ₂ + y ₂ (mod a ₂ ), ..., X _n + y _n (mod
a _n )) = (z ₁ , z ₂ , ..., Z _n ).

Therefore, each arithmetic unit 22₁~ 22
_mAre controlled by the arithmetic controller 10
x_i, Y_iMethod a for each_i(ST4), the husband
Each addition result z _iRAM22₁~ 22_mOutput to. Performance
The arithmetic controller 10 has each RAM 22. ₁~ 22_mInner connection
Fruit z₁~ Z_nAre sequentially read and the remainder addition result <z>_A
To get

However, in the remainder addition <x> _A + <y> _A , when the obtained addition result <z> _A is larger than the RNS expression <p> _{A of} modulus p, <p> _A is added. You need to subtract from the result. On the other hand, the addition result <z> _A has a property that it is difficult to compare the given two numbers, because the addition result <z> _A is an RNS expression composed of a set of remainder values.

Therefore, in order to compare the addition result <z> _A with the modulus p, the addition result <z> _A is once converted into the mixed radix representation.

Specifically, the arithmetic controller 10 is shown in FIG.
As shown in FIG. 5, each arithmetic unit 22 _{1 to} 22 _m is controlled in order, the well-known Garner algorithm is used halfway, and the addition result <z> A is displayed as a mixed radix (v ₁ , v ₂ , ..., V _n ).
(ST5).

Garner's algorithm is
It is as shown in the equation showing a ₁ to v _n.

V ₁ = z ₁ (mod a ₁ ) v ₂ = (z ₂ −v ₁ ) * C ₁₂ (mod a ₂ ) v ₃ = ((z ₃ −v ₁ ) * C ₁₃ −v ₂ ) * _{C 23 (mod a 3):} v n = ((z 3 -v 1) * C 1n -v 2) * C 2n - ...... -v (n-1)) * C (n-1) n (mod a _n ) However, C _ji = a _j ⁻¹ mod a _i , (j = 1, 2, ..., i−1) Here, each arithmetic unit 22 _i is, as shown in FIG.
Arithmetic unit 2 with subscript i-1 less than its own subscript i
While using the 2 _i-1 of the operation result v _i-1 performs its own processing, writes the computation result v _i in RAM 21 _i.

The arithmetic unit 2 having the maximum subscript m
When 2 _m writes the calculation result v _n in the RAM 21 _m , the conversion process to the mixed radix display is completed.

Next, each arithmetic unit 22 _i uses the obtained mixed radix representation z = (v ₁ , v ₂ , ..., V _n ) and compares it with the multiple of modulo p (the mixed radix representation thereof). I do. In the mixed radix display, the numbers (v ₁ , v ₂ , ..., V _n ) of the two mixed radix displays, (p ₁ , p ₂ , ..., P _n ).
In between, the elements are compared in size from the side with the larger subscript (right side), and the detected larger element is larger in binary notation.

The multiple jp of the modulus p is determined by the following relational expression (ST6).

J satisfying jp ≦ z <(j + 1) p,
(However, 0 ≦ j <h) When hp ≦ z, j = h.

Next, when the multiple j is determined, the arithmetic control
The roller 10 is provided in each arithmetic unit 22. ₁~ 22_mTo control
Therefore, the addition result in step ST4 <z>_AFrom next
Subtract j times the modulus p as shown in equation (4), and add the remainder system with the modulus p.
Calculation result <z>_ATo get

<Z> _A = <z> _A- j * <p> _A (4) At this time, each of the arithmetic units 22 _{1 to} 22 _m is controlled by the arithmetic controller 10 and each element z _i , jp _i. The subtraction by the modulus a _i is executed every time (ST7), and the subtraction results z _i are output to the RAMs 22 _{1 to} 22 _m , respectively. Arithmetic controller 1
0 sequentially reads the results z _{1 to} z _n in the RAMs 22 _{1 to} 22 _m , and obtains the remainder addition result <z> _A in the modulus p.

As described above, according to the present embodiment, the residue system addition result <z> _A is represented by z in the mixed radix representation for easy comparison.
And the result is compared with the multiple of the modulus p, and the remainder j <p> of the modulus p is subtracted from the remainder addition result <z> _A based on the comparison result, and the remainder addition result <z> of the modulus p is obtained. _Since I ask for _A ,
It is possible to efficiently perform remainder addition under the modulus p different from the modulus A for two numbers expressed in the modulus A by the modulus A.

In this embodiment, the Garner's algorithm is operated in parallel by each of the arithmetic circuits 20 _{1 to} 20 _m , so that in each arithmetic unit 22 _i , (z _(i-1) −v _i ) * c
The subtraction and multiplication of the remainder system of _{(i-1) i} (mod a _i ) is the processing unit. That is, the number of cycles required for conversion to the mixed radix display is n− as each processing unit is one cycle.
It becomes one cycle.

As a modification of the conversion process, the mixed radix representation of z (v ₁ , v ₂ , ..., V _n ) is expressed in the notation system by the following equation (5) and expressed in binary notation. A magnitude comparison with a multiple of the modulus p may be performed.

[0078] Further, since the multiple of p is calculated in advance in step ST2,
It is possible to easily perform a magnitude comparison between the addition result and a plurality of multiples of p.

(Second Embodiment) Next, a coset arithmetic unit according to a second embodiment of the present invention will be described. In this embodiment, the same parts in FIGS. 1 to 3 described above are denoted by the same reference numerals, and detailed description thereof will be omitted. Here, different parts will be mainly described. Also, in each of the following embodiments, duplicate description will be omitted in the same manner.

That is, in the present embodiment, in addition to the remainder addition of the first embodiment, 2 number <x expressed by RNS in modulus A
> _A , <y> _A target, modulo p subtraction result <z
> = <X> _A − <y> _A (however, p <A).

First, the principle of this embodiment will be described. Note that the modulus A in the RNS representation is now the product A of the basis, not the modality p of interest. For modulo subtraction, x ≧
In the case of y, xy (mod A) = xy (mod
p) and get the correct result, but if x <y then x
-Y (modA) ≠ xy (mod p), resulting in an error.

When x <y, x + (py) (m
od A) = x−y (mod p), therefore, normally, x and y are first compared in magnitude, and if x ≧ y, subtraction is performed, and if x <y, z and (py) are obtained. ) And modulo addition,
Should be done. However, in such an ordinary idea, in addition to the magnitude comparison of the subtraction results z and p, the magnitude comparison of x and y is necessary before the subtraction.

In the present embodiment, considering such a situation,
The value dp (: d times the modulus p) that exceeds the upper limit of the input y is uniquely added to-<y> _A without comparing the magnitudes of x and y, and the subtraction result is positive. In this state, x is added by the remainder addition of the first embodiment in the state of being a value, and finally the multiple of the modulus p is subtracted from the obtained addition value, and the remainder subtraction of the modulus p is executed. However, this remainder subtraction is based on the premise that the upper limit of the input y is y <dp.

Here, the arithmetic controller 10 is described above.
In addition to the functions _iControl function of
Input <y to be subtracted in advance when performing modular subtraction
>_AValue that exceeds the upper limit of d * <p>_AFrom <y>_ARequires
Element z_iThe function to subtract each time and the subtraction result
<X> to be subtracted_AThe element x_iWith the function to add each
Be prepared.

Next, the remainder operation performed as described above
The remainder system calculation method by the device uses the flowchart of FIG.
And explain. Now, as described above, steps ST1 to ST
2 is completed, each arithmetic circuit 20₁~ 20 _mCalculation parameter
Data (method ai, basis-dependent parameter C_{(i-1) i}, Mod p times
It is assumed that the numbers p to hp) have already been set.

Similarly, each of the arithmetic units 22 _{1 to} 22
_When two numbers x and y are input from an external CPU (however, x, y <dp), m is divided by the modulus ai to obtain R.
It is converted into the elements xi and yi expressed in NS and held (S
T3-S).

The above steps ST1 to ST3-S are the phases to be performed only once in advance, and when the data already expressed in RNS is subjected to the remainder subtraction, step ST3-S is unnecessary. With the above preparations, the remainder subtraction is actually executed below.

In the remainder subtraction, as described above, x
Under the premise of −y <A, the subtraction by the modulus a _i is performed for each element xi, yi. That is, the remainder subtraction is basically
<Z> _A = <x> A- <y> A, <z> _A =
<X> A- <y> A (mod A) = (x ₁ −y ₁ (m
oda ₁ ), x ₂ −y ₂ (mod a ₂ ), ..., X _n −
This is a process of setting y _n (mod a _n )) = (z ₁ , z ₂ , ..., Z _n ).

However, from the viewpoint of preventing a result error when x <y, as shown in the following expression (6), d * <p> _A having a relation of y <d * p is previously defined as-<y. > Add to _A (ST
4-S1).

<S> _A = d * <p> _A− <y> _A (6) That is, each of the arithmetic units 22 _{1 to} 22 _m is controlled by the arithmetic controller 10, and each element d * p _i , y. performs subtraction of by law _{a i} for each _i, respectively subtraction result _{s i} RAM2
Output to 1 _{1 to} 21 _m . Operation controller 10 sequentially reads the result _s 1 ~s _n in each RAM 21 ₁ through 21 _m, to obtain a positive value _{<S> A} as a subtraction result. That is,
Since the input y satisfies 0 <y <d * p, a positive value of 0 <S <d * p is obtained, where S is the result of d * py.

Here, <S> _A ≡d * p−y (mod
Note that if p) ≡−y (mod p), then S
By performing the remainder addition of the present invention on x and x, z≡S +
The result z is obtained such that x (mod p) = xy (mod p).

Therefore, with respect to this positive value <S> _A , the original calculation target <x> _A is similarly calculated in each of the calculation units 22 _1- .
22 _m , add for each element si and xi (ST4-S
2) Obtain the remainder subtraction result <z> _A.

In the same manner as in steps ST5 to ST7 described above, the subtraction result is converted into the mixed radix representation, it is determined that the conversion result includes j mod p, and the subtraction result <z> _{A is} determined based on the determination result. Then, a multiple j * <p> _A of the modulus p is subtracted from to finally obtain <z> A.

As described above, according to the present embodiment, first, the subtraction number y is subtracted from the value dp that exceeds the upper limit value of the subtraction number y, and the remainder subtraction result s is always a positive value. Then, the original subtraction number x is added to the remainder subtraction result to obtain the remainder subtraction result in the modulus A.
As in the first embodiment, since the remainder subtraction result in the method A is converted into the remainder subtraction result in the method p, the remainder system is represented by the modulus A in addition to the effect similar to the first embodiment. The remainder subtraction under the modulus p different from the modulus A can be executed with high efficiency for two numbers.

(Third Embodiment) Next, a third embodiment of the present invention will be described. First, the principle will be described. In this embodiment, an algorithm different from those in the first and second embodiments is used to convert the residue system addition result in the modulus A from the RNS expression to the binary number representation, perform the magnitude comparison with the modulus p, and perform the comparison according to the comparison result. , The modulo A remainder addition result is converted to the modulo p remainder addition result. Specifically, it is realized according to the following principle. The following equation (7) is known as an equation for converting the RNS expression of the modulus A into a binary number expression. In the equation (7), n terms have a symmetric structure with respect to each modulus a _i . have.

Z = z ₁ * N ₁ * A ₁ + z ₂ * N ₂ * A ₂ + ... + z _n * N _n * A _n (mod A) (7) where A _i = A / a _i , N _i = A _i ⁻¹ (mod a _i ), (1 ≦ i ≦ n) The following formula (8) obtained by modifying this formula is also equivalent.

Z = g ₁ * A ₁ + g ₂ * A ₂ + ... + g _n * A _n (mod A) (8) where g _i = z _i * (A _i ^-1 (mod a _i )) ( mod a _i ) Here, in formula (8), g _i is a _i for both z _i and A _i ^-1.
Since it is less than (mod a _i ), the arithmetic circuits 50 _{1 to} 5 5
It can be calculated in parallel by 0 _m . However, A _i (=
a ₁ * a ₂ * ... * a _n / a _i ) and the method A (= a ₁ * a _2).
* ... * a _n ) are multiple long integers, respectively, and their values are very large. Therefore, it is impossible to calculate them using the equation (8).

However, in the present invention, the equation (8) is modified as follows so that z can be calculated. That is, g _i
Is less than a _i , g _i * A _i is an integer less than A. Therefore, the following expression (9) is established.

[0099]

[Equation 7]

When this k can be obtained accurately, the upper w of z
The value of the bit can be approximated using the value of the upper w bits of A _i and A.

Here, a method of calculating k (a positive integer) will be described.

By transforming the above equation (9), the following equation (10) is obtained.

[0103]

[Equation 8]

Since 0 ≦ z <A, the integer part on the left side is k.
And the fractional part is z / A. Therefore, k is
It is calculated as in the equation 1) ([] is converted to an integer by truncating the decimal part).

[0105]

[Equation 9]

When each arithmetic unit can perform division by the modulus a _i , k can be calculated by directly using the equation (11). In addition, regardless of whether or not the division of the modulus ai can be performed, g _i /
By transforming a _i as shown in the following equation (12), 1 + α _i /
If (2 ^wi −α _i ) is calculated in advance and set in each arithmetic unit, the calculation of k can be realized only by multiplication and addition calculation without using division by the modulus a _i .

G _i / a _i = (g _i / 2 ^wi ) * (2 ^wi / a _i ) = (g _i / 2 ^wi ) * (1 + α _i / (2 ^wi −α _i )) (12) However, , A _i = 2 ^wi −α _i (: α _i is an integer that is sufficiently smaller than 2 ^wi . In the case of this format, the modulo a _i modulo operation is made more efficient.) As described above, k is calculated. Explained. Next, a method of approximating the value of the upper w bits of z will be described.

Here, A _i , A, g _i used for the approximate calculation
It is assumed that the approximate value of the higher order bits of A'is represented by A _i ′, A ′, g _i ′, and | A ′ | represents the bit length of A ′. Specifically, as shown in the following equations (13) to (15), the approximate value g
Let _i ', A _i ' be the value of the upper bit obtained by cutting off the lower c ₁ and c ₂ bits of g _i , A _i , and the approximate value A ', the value of the upper bit obtained by cutting the lower c bit of A 1 is added to.

G _i '= [g _i / 2 ^c1 ] ... (13) A _i ' = [A _i / 2 ^c2 ] ... (14) A '= [A / 2 ^c ] +1 (15) where c = C ₁ + c ₂ where | A _i ′ | = | A _i ′ | = | g _i ′ | ≦ w, n arithmetic units are used to obtain an approximate value z ′ of the upper w bits of z. It can be calculated as z≈z ′ * 2 ^c (c is the number of bits truncated to the lower bits of z).

Specifically, the approximate value z ′ is calculated by the following (16)
It is calculated by a formula.

[0111]

[Equation 10]

Here, z ′ * 2 ^c is the first term (g _i * A _i ) which is a rounded down value, and the second term (k is a rounded up value).
Since it is the value obtained by subtracting * A), the value is always equal to or smaller than the true value z according to the equation (9) described above (z '* 2 ^c ≤z).
Becomes

That is, when the maximum value of the approximation error is e,
z−e <z ′ * 2 ^c ≦ z.

It should be noted that e can be evaluated as in the following expression (17).

E <2 ^c * n * (2 ^{t + 1} +2) (17) (t is the maximum bit length of | g _i ′ |, | A _i ′ | (1 ≦ i ≦ n)) , The maximum bit length t of g _i ′, A _i ′ is determined by appropriate setting of the truncation bit numbers c, c ₁ and c ₂ ,
A desired approximation error such as e <p can be set as in the above equation (17).

As described above, it is assumed that the upper digit of the addition result z is represented in the binary number as the approximate value z '. Next, method A
In order to convert the residue system addition result z in z into the residue system addition result in the method p, the approximate value z ′ of z and 1 to h times the method p (p, 2
p, ..., hp) is compared with the upper word (: the rest excluding the lower c bits) to determine the multiple of p.

Here, the upper word of the modulus p is represented by p ′, the upper word twice the modulus p is represented by (2p) ′, and the upper word of the modulus p times h is represented by (hp ) '.

Specifically, Is an approximate value. However, [] represents a value obtained by converting the value in [] into an integer by truncating the decimal part.

At this time, z'and (jp) 'are compared in size (where 0≤j <h) and (jp)'<z'≤ ((j +
1) When p) ', subtract j * p from z. Also, (h
p) When '<z', subtract h * p from z. Also, z '
When <p ', do not subtract a multiple of p.

Here, the range of z is approximated by an error (z−z ′ *).
2 ^c ) with the maximum value e. (Jp) '<z' ≦
When ((j + 1) p) ′ (0 ≦ j <h), ze <
Since z ′ * 2 ^c ≦ ((j + 1) p) ′ * 2 ^c holds, z <((j + 1) p) ′ * 2 ^c + e <(j + 1) p + e. Next, z-j * p is set, but it is examined whether z becomes negative.

When jp '<z', (jp) '+ 1≤
z ′, and (jp) ′ * 2 ^c ≦ j * p <((jp) ′
+1) * 2 ^c , so j * p <((jp) ′ + 1)
* 2 ^c ≤ z holds. Therefore, the modulus p is not overdrawn. Therefore, j * p is subtracted from z, and 0 <z <p + e
Becomes

Next, when (hp) '<z', the input x,
If there is a constraint of y <((h + 1) / 2) * p, z <(h +
1) * p, and h * p is subtracted from z, and z <p.

Usually, since the number h of multiples of the modulus p for comparison is determined in advance from the constraint of the input size, the constraint on the output is set. As described above, (jp) '<z' ≦
In either case of ((j + 1) p) 'or (hp)'<z', the result z is guaranteed to be less than p + e (: z <p + e).

For example, the parameter c, so that e <p,
If c1 and c2 are set, the output z becomes less than 2p, and if the inputs x and y are also less than 2p, the output of this algorithm can be directly input to the next stage. In this case, z ',
It is sufficient to make a size comparison with p ′ and (2p) ′ (h = 2 is sufficient).

Next, when the multiple j is determined as described above, the remainder subtraction of z−j * p (multiple j is one of 1 to h) is given by the following equation (18). , For each element.

Z = z−j * p (mod A) = (z ₁ −j * p ₁ (mod a ₁ ), z ₂ −j * p ₂ (mod a ₂ ), ..., Z _n −j * p _n (mod a _n )) (18) This subtraction result z is the remainder addition result z in the obtained modulus p.

Now, according to the above principle, the present embodiment is
Specifically, it has the following configuration. FIG. 5 shows a third embodiment of the present invention.
FIG. 3 is a block diagram showing the configuration of a coset arithmetic unit according to the embodiment.
Is. This remainder-based arithmetic device is provided with an arithmetic controller 40.
And m arithmetic circuits 50 ₁~ 50_mVia bus 30
Connected to each other.

[0128] Here, operation controller 40, as before is basically a function of exchanging data between the arithmetic circuits ₅₀ 1 to 50 _m, content of operation of the arithmetic circuits ₅₀ 1 to 50 _m ( It has a function of controlling a remainder system addition, a remainder system subtraction, a remainder system multiplication, and a function of causing each of the arithmetic circuits 50 ₁ to 50 _m to execute a desired arithmetic operation.

However, specifically, the arithmetic controller 40
, For each arithmetic circuits ₅₀ 1 to 50 _m, RNS representation has been 2 integer _<x> A, and controls a function to execute a coset addition of _{<y> A,} each arithmetic circuits ₅₀ 1 to 50 _m, The function of converting the remainder addition result <z> _A into an approximate value z ′ of the upper bit in the binary representation using the algorithm of the principle described above, and an approximate value z ′ for each of the arithmetic circuits 50 ₁ to 50 _m.
And an approximate value {p ', (2p)', ..., (jp) ', ..., Of the upper bits of a value obtained by multiplying the binary representation of the modulus p by an integer.
(Hp) ′} and a function of determining the multiple j by comparing the magnitude relationship with (hp) ′}, and each of the arithmetic circuits 50 ₁ to 50 based on the multiple j.
_A function of subtracting j * <p> _A obtained by multiplying modulo p by j from _m of the remainder system addition result _m with respect to _m , and a function of outputting the remainder system addition result <z> _A of the obtained modulus p. Has.

On the other hand, the arithmetic circuits 50 ₁ to 50 _m are the same as the arithmetic circuits 20 _i described above. However, the function of each arithmetic unit 52 _i is slightly different from that described above.

That is, the arithmetic unit 52 _i basically performs the addition / subtraction of integers of w bits in the RAM 51 _{i under} the control of the arithmetic controller 40, as described above.
The RAM 5 _i has a function of executing addition / subtraction multiplication of the remainder system in the w-bit modulus and writing the execution result in the RAM 51 _i.
1 _i via the arithmetic controller 40 and other arithmetic circuit 50
_It has a function of executing parallel operation while exchanging data with each other with ₁ to 50 _i−1 and 50 _{i + 1} to 50 _m .

However, the arithmetic units 52 _{1 to} 52 _m are
Unlike the above-described arithmetic units 52 _{1 to} 52 _m , the processing function regarding the display of the mixed radix can be omitted.
Next, a coset system computing method by the coset system computing device configured as described above will be described with reference to the flowchart of FIG. Now, for example, it is assumed that it is necessary to perform addition processing of the remainder system of two numbers x and y while executing the public key encryption algorithm.
Each of the arithmetic units 52 _{1 to} 52 _m is supplied from an external CPU (not shown) via the bus 30 to each arithmetic unit 52 _{1 to} 52 _m, which is a base value B _i of the RNS expression and an approximation value A _i ′ = A _i ′ = [A
_i / a ^{2 c],} while its multiplicative inverse _{A i} ^-1 (mod _{a i)} is set, the upper digit of the approximate value A of the law A to operation controller ^{40 '= [A / 2 c} ] +1 Is set (ST
11), this A ′ is set via the arithmetic controller 40 to the arithmetic unit 52 ₁ for calculating k * A ′ described later. The approximate value A ′ may be directly set in the arithmetic unit 52 ₁ without going through the arithmetic controller 40.

Further, the arithmetic controller 40 uses an external C
When the modulo value p and its multiples p, 2p, ..., hp are input from the PU, these are set in the respective arithmetic units 52 _{1 to} 52 _m . Similarly, the modulus p and its multiples are directly calculated by the arithmetic units 52 _{1 to} 5 5 without passing through the arithmetic controller 40.
It may be set to 2 _m .

Of the multiples of these modulo p, each of the arithmetic units 52 _{1 to} 52 _m leaves (i * p) 'as a binary representation (for comparison of magnitude) and p, 2p, ..., hp modulo a. It is divided by _i to be an RNS expression (for j-fold subtraction), and the values of both expressions are held (ST12).

Further, each of the arithmetic units 52 _{1 to} 52
_m is the number of 2 x from an external CPU, y is input, these x, by dividing y by law _{a i} RNS representation by elements _x i, holds converted to _{y i} (ST13).

The above steps ST11 to ST13 are the phases to be performed only once in advance, and when the data already expressed in the RNS is subjected to the remainder system addition, the step ST13 is unnecessary. Based on the above preparations, the remainder addition is actually executed below.

That is, each of the arithmetic units 52 _{1 to} 52 _m
Under the control of the arithmetic controller 40, each element x _i ,
The addition by the modulus a _i is executed for each y _i (ST14), and the addition results z _i are output to the RAMs 52 ₁ to 52 _m , respectively. The arithmetic controller 40 uses the result z in each of the RAMs 52 _{1 to} 52 _m .
_{1 to} z _n are sequentially read to obtain the remainder addition result <z> _A.

Then, in order to compare the addition result <z> _A with the modulus p, the addition result <z> _A is once converted into a binary number representation.

Specifically, the arithmetic controller 40 is shown in FIG.
As an example of n = 8, the arithmetic units ₅₂ 1-5
2 _m are controlled in order to calculate k in the equation (11) (ST
15).

This step ST15 is executed by the procedure of substeps 1 to 5 in FIG. First, g _i = z _i *
A _i ^-1 (mod a _i ) is calculated in parallel in each arithmetic unit 52 _i (substep 1), and then g _i / a _i is calculated in parallel in each arithmetic unit 52 _i (substep 2) ,
Then, k is obtained from the sum of each g _i / a _i (substeps 3 to 5).

Each g_i/ A_iThe process of obtaining k from the sum of
N / 2 maximum operation units 52 ₁~ 52_{n / 2}By
The depth of the logn tournament formula
Done. Next, the arithmetic controller 40 determines each arithmetic unit.
52₁~ 52_mAre controlled in order, and z ′ in the equation (16) is changed to
It is calculated (ST16).

This step ST16 is executed by the procedure of substeps 6 to 11 in FIG. First, the g _i calculated in substep 1 significant digit g _{i 'and} A _i' calculates the product of the parallel arithmetic unit 52 _i (substep 6), followed by, n pieces obtained in g _i ' -Calculate the sum of A _i '(substeps 7-9).

As in the above, the process of obtaining the sum is n
/ 2 arithmetic units 52₁~ 52 _{n / 2}Depth by logn
It is executed by the addition process of the tournament formula. One last
Arithmetic unit 52₁To calculate k * A '((sub
Step 10), subtracting from the obtained total sum to obtain an approximate value z '.
(Sub-step 11).

Next, each arithmetic unit 52 _i obtains the obtained approximate value z ′ and the approximate value {p ′, (2
p) ', ..., (jp)', ..., (hp) '}.

The multiple jp of the modulus p is determined by the following relational expression (ST17).

J satisfying (jp) '<z'≤ ((j + 1) p)' (where 0≤j <h) Note that when (hp) '<z', j = h. .

When the arithmetic controller 40 determines the multiple j based on the comparison result of the arithmetic units 52 _i , the arithmetic controller 40 controls the arithmetic units 52 _{1 to} 52 _m to execute step ST4.
From the addition result <z> _{A in} Eq.
To obtain the remainder addition result <z> _A by the modulus p.

<Z> _A = <z> _A- j * <p> _{A (19)} At this time, each of the arithmetic units 52 _{1 to} 52 _m is controlled by the arithmetic controller 40 and each element z _i , jp _i. The subtraction with the modulus a _i is executed for each time (ST18), and the subtraction result z _i
Is output to the RAMs 52 ₁ to 52 _m . The arithmetic controller 40 sequentially reads the results z _{1 to} z _n in the RAMs 52 _{1 to} 52 _m , and obtains the remainder addition result <z> _A in the modulus p. However, z <p + e (e is an approximation error in step ST16).

As described above, according to this embodiment, the method A
Approximately convert the remainder addition result in binary to a binary representation to check whether it is approximately j times the modulus p, and according to this multiple j, the remainder addition result of the modulus A is converted to the remainder system of the modulus p. Since it is converted to the addition result, the modulo A is applied to the 2
It is possible to highly efficiently perform coset addition under the modulus p different from.

The process of obtaining the approximate value z'in the binary representation of the remainder addition result z in the modulus A is performed as a whole by parallel processing of n (n = m) arithmetic units 50 ₁ to 50 _m. 2 * logn + 7 steps, and the calculation amount is O (l
Since it is sufficient, it can be executed with a smaller calculation amount than the calculation amount of the first embodiment (Garner's algorithm). Therefore, the processing time can be shortened as a whole compared to the first embodiment.

Further, in the present embodiment, the algorithm is modified so that instead of performing the magnitude comparison with the approximate value of the multiple of h, the upper word (M *) of each of the multiple of h of M * p.
p) ', (2M * p)', ..., (hM * p) 'may be compared.

That is, (jM * p) '<z'≤ ((j
+1) M * p) '(where j <h), then z to jM * p
, And if (hM * p) '<z', subtract hM * p from z.

(JM * p) '<z'≤ ((j + 1) M *
p) ′ (where j <h), z−e <z ′ * 2 ^c ≦
((J + 1) M * p) '* 2 ^c , so z <(j +
1) M * p + e holds. At this time, from z to jM * p
As a result, z <M * p + e.

In this case, the output size becomes larger than that of the original algorithm. However, if the input size constraint is the same as the original algorithm, the number of multiples of M * p required for the determination can be reduced.

Furthermore, in the present embodiment, each arithmetic unit 52 _i performs a magnitude comparison with a multiple of the modulus p. However, the present invention is not limited to this, and the arithmetic controller 40 replaces each arithmetic unit 52 _i with the modulus p. A magnitude comparison with a multiple may be made.
For example, when h = 2 due to the setting of the approximation error, the arithmetic controller 40 and the two arithmetic units 5
Also which of the 2 _{1-52 2} performs magnitude comparison, significant difference is considered to not occur in the processing time.

(Fourth Embodiment) Next, a coset arithmetic unit according to a fourth embodiment of the present invention will be described with reference to the device shown in FIG. This remainder system arithmetic device is a modification of the third embodiment, and is intended to shorten the processing time by changing the sharing of parallel arithmetic operations. Specifically, step ST15 and step ST15 shown in FIG. Instead of ST16, as shown in FIG. 8, both steps ST15, ST16
The configuration is such that step ST20 (FIG. 9; substeps 1S to 8S), which is a combination of the above processing procedures, is executed.

Here, the arithmetic controller 40 has been described above.
Among the functions, each arithmetic unit 52 _iParallel operation on
It has a configuration in which the sharing control of is changed.

Specifically, the arithmetic controller 40 has a maximum of n / 2 (= 4) arithmetic units 52 ₁ shown in FIG.
~ 52 _{n / 2} summation processing (sum of g _i / a _i (FIG. 7;
As shown in substeps 4S to 6S of FIG. 9, instead of the control function of performing the substeps 3 to 5) and the sum of g _i '* A _i ' (FIG. 7; substeps 7 to 9)) in series. , And has a control function of causing a maximum of n (= 8) arithmetic units 52 _{1 to} 52 _{n / 2} to execute these two summing processes in parallel.

Next, a coset system computing method by the coset system computing device configured as described above will be described with reference to the flowchart of FIG. Now, similarly to the above, steps ST11 to ST11
It is assumed that ST14 ends. Next, the arithmetic controller 4
0, at Step ST20, as shown in FIG. 9, to perform a parallel operation on the operation controller ₅₂ 1-52 _8.

[0160] That is, the sub-step 1S～3S, obtaining a _{g i} / _a i required for the calculation of k, and * _{A i} '' _{g i} required for the calculation of 'that z in parallel. Then, the sub-step 4S～6S, these and the n _g i / _{a i,} the n _{g i} '* _{A i'} and each is added in parallel tournament a.

Then, in substeps 7S and 8S, an approximate value z '= r-kA' is calculated. As a result, in the entire step ST20, the logn processing is executed.
Can be shortened to +5 steps.

Thereafter, similarly, steps ST17 to ST18 are performed.
By executing, the remainder addition result in the modulus p is obtained. It should be noted that although the logn + 8 steps are required for the entire processing, the processing time can be reduced to about half as compared with the third embodiment when n is large.

As described above, according to the present embodiment, in the conversion processing into the binary number representation, the two types of tournament methods that require a maximum of n / 2 arithmetic units 52 _{1 to} 52 _{n / 2} as shown in FIG. of the addition process, since a parallel processing configuration with up to n arithmetic units 52 ₁ to 52 _n as shown in FIG. 9, in addition to the effects of the third embodiment, the processing time when n is greater It can be reduced to about half.

(Fifth Embodiment) Next, a coset arithmetic unit according to a fifth embodiment of the present invention will be described with reference to the device shown in FIG. In the present embodiment, in addition to the remainder addition of the third embodiment, two numbers <x> _A represented by RNS in the modulus _A ,
<Y> _A target, modulo p subtraction result <z> = <
x> _A − <y> _A (where p <
A). The specific principle is the same as the principle described in the second embodiment. Here, the arithmetic controller 40 uses the control function of each arithmetic unit 52 _i in addition to the functions described in the third embodiment to set the upper limit value of the input <y> _A to be subtracted in advance when performing the remainder subtraction. Exceeding value d * <p> From _A <
It has a function of subtracting y> _A for each element z _i and a function of adding <x> _A to be subtracted for each element x _i to the subtraction result.

Next, the coset system computing method by the coset system computing device configured as described above will be described with reference to the flowchart of FIG. Now, similarly to the above, steps ST11 to ST11
ST12 is completed, the approximate value A'has been set in the arithmetic controller 40, and the arithmetic parameters (modulus a _i , approximate value A _i ′, multiplicative inverse element A _i) are assigned to the arithmetic circuits 50 ₁ to 50 _m.
^-1 , the multiple p to hp of the modulus p) is set.

Similarly, each of the arithmetic units 52 _{1 to} 52 _1
When two numbers x and y are input from an external CPU (where x, y <d * p), m is an element x _i , y expressed in RNS by dividing these x and y by the modulus a _{i. It} is converted to _i and held (ST13-S).

The above steps ST11 to ST13-S are the phases to be performed only once in advance, and when the data already expressed in RNS is subjected to remainder subtraction, step ST13.
-S is unnecessary. Based on the above preparations, the remainder subtraction is executed in the following procedure.

In the remainder subtraction, as described above, x
Under the premise of −y <A, the subtraction by the modulus a _i is performed for each element x _i , y _i . However, from the viewpoint of preventing a result error when x <y, y <d * p
The d * <p> _A having the relationship of is added to-<y> _A (ST14-S1).

<S> _A = d * <p> _A− <y> _A (20) That is, each of the arithmetic units 52 _{1 to} 52 _m is controlled by the arithmetic controller 40, and each element d * p _i , y. performs subtraction of by law _{a i} for each _i, respectively subtraction result _{s i} RAM5
Output to 1 _{1 to} 51 _m . Operation controller 10 sequentially reads the result _s 1 ~s _n in each RAM 51 ₁ to 51 _m, to obtain a positive value _{<S> A} as a subtraction result. That is,
Since the input y satisfies 0 <y <d * p, a positive value of 0 <S <d * p is obtained, where S is the result of d * py.

[0170] In this _{case, <S> A ≡d * p} -y (mod
Note that if p) ≡−y (mod p), then S
By performing the remainder addition of the present invention on x and x, z≡S +
The result z is obtained such that x (mod p) = xy (mod p).

Therefore, with respect to this positive value <S> _A , the original operation target <x> _A is similarly calculated in each of the operation units 52 ₁ to 52 ₁ .
52 _m add for each element s _i , x _i (ST14-S
2) Obtain the remainder subtraction result <z> _A.

Hereinafter, the above-mentioned steps ST15 to ST1
Similar to 7, the subtraction result is converted into a binary number representation, it is determined that the conversion result includes j mod p, and based on the determination result, the subtraction result <z> _A to the multiple p of mod p j * <p> Subtract _A to finally obtain <z> _A.

The upper limit of the size of the result z satisfies 0 ≦ z <p + e <2p due to the nature of the remainder addition method. (However, when the approximation error e <p).

As described above, according to this embodiment, first, the subtraction number y is subtracted from the value dp that exceeds the upper limit value of the subtraction number y, and the remainder subtraction result s is always set to a positive value. Then, the original subtracted number x is added to the remainder subtraction result to obtain the remainder subtraction result in the modulus A.
In the same manner as in the above embodiment, since the remainder subtraction result in the modulus A is converted into the remainder subtraction result in the modulus p, in addition to the effect of the third embodiment, the remainder system represented by the modulus A is represented by two numbers. On the other hand, the remainder subtraction under the method p different from the method A can be executed with high efficiency.

The processing of this embodiment is 2 * as a whole.
It becomes about logn + 8 steps, which is O (logn) on the premise of parallel processing of n arithmetic units, and has an advantage that the amount of calculation can be suppressed smaller than that of the second embodiment (Garner's algorithm).

The present embodiment can be realized also by using step ST20 which is a combination of step ST15 and step ST16 as in the modification procedure shown in FIG. 8. In this case, as described above, when n is large. Can reduce the processing time to about half.

In addition, the present invention can be variously modified and implemented without departing from the scope of the invention.

[0178]

As described above, according to the present invention, a modulus p different from the modulus A is used for the two numbers expressed by the modulus A in the modulus A.
It is possible to provide a remainder system operation device and method capable of performing remainder system addition under high efficiency with high efficiency. Further, it is possible to provide a remainder system arithmetic device and method capable of highly efficiently performing remainder system subtraction under the same modulus p in addition to the above remainder system addition.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a coset arithmetic unit according to a first embodiment of the present invention.

FIG. 2 is a schematic diagram showing a control system of each arithmetic circuit in the same embodiment.

FIG. 3 is a flowchart for explaining a remainder system calculation method in the same embodiment.

FIG. 4 is a flowchart for explaining a coset arithmetic method by a coset arithmetic unit according to the second embodiment of the present invention.

FIG. 5 is a block diagram showing a configuration of a coset arithmetic unit according to a third embodiment of the present invention.

FIG. 6 is a flowchart for explaining a remainder system calculation method in the same embodiment.

FIG. 7 is a schematic diagram showing a control system of each arithmetic circuit in the same embodiment.

FIG. 8 is a flowchart for explaining a coset arithmetic method by a coset arithmetic device according to a fourth embodiment of the present invention.

FIG. 9 is a schematic diagram showing a control system of each arithmetic circuit in the same embodiment.

FIG. 10 is a flowchart for explaining a coset arithmetic method by a coset arithmetic unit according to a fifth embodiment of the present invention.

[Explanation of symbols]

10, 40 ... Arithmetic controller 20 _{1 to} 20 _m , 50 ₁ to 50 _m ... Arithmetic circuit 21 _{1 to} 21 _m , 51 _{1 to} 51 _m ... RAM 22 _{1 to} 22 _m , 52 _{1 to} 52 _m ... Arithmetic unit 30 ... Bus

─────────────────────────────────────────────────── ─── Continuation of the front page (56) Reference JP-A 52-116126 (JP, A) JP-A 11-340817 (JP, A) JP-A 1-149129 (JP, A) JP-A 64- 30332 (JP, A) JP-A-1-99325 (JP, A) K.K. C. Posch et al. , Modulo reduction in residue number systems, IEEE Trans. On Parallel and D Distributed Systems, USA, IEEE, May 1995, Vol. 6, No. 5, pp. 449-454 (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 7/72

Claims (10)

(57) [Claims] 1. A remainder system arithmetic unit for adding a plurality of remainder system data <x> _A , <y> _A represented by the remainder system by the modulus A under the modulus p (: p <A). In advance, in the mixed radix notation, the modulus p is multiplied by h (h = 1 to a positive integer)
Mixed radix system multiple setting means for setting a plurality of multiple data (p, 2p, ..., hp), and a plurality of multiple data (<p> _A , 2 obtained by multiplying the modulus p by h in advance by the remainder system expression). * <P> _A , ..., h * <p> _A ) and the remainder system data <x> _A , <y> _A that is input and the remainder system multiple setting means are set by the remainder system expression to obtain the remainder. System addition result <z> remainder system addition means for obtaining _A , and remainder system addition result <z obtained by the remainder system addition means
> Based on the expression conversion means for converting _A into the mixed radix representation, the addition result z displayed by the mixed radix displayed by the expression conversion means, and each multiple data in the mixed radix system multiple setting means, Addition result z displayed in mixed radix
Is determined to include the multiple data jp of j times (0 ≦ j ≦ h) at the maximum (jp ≦ z <(j + 1) p), and the multiple determination means determines the multiple j, and the multiple determination means. Based on the obtained multiple j, the remainder addition result <z> obtained by the remainder addition means
Multiple data j from _A to j times in the remainder system multiple setting means
* <P> _A subtraction system, and an addition result output means for outputting a remainder system addition result <z> _A in the obtained modulus p. 2. A plurality of coset systems represented by cosets by the method A.
Data <x>_A, <Y>_AWith respect to the law p (: p <A)
And the above <x>_AFrom above <y>_ARemainder for subtracting
System arithmetic device, Pre-mixed radix representation modulo p times (h = positive integer from 1 to h)
Multiple multiple data (p, 2p, ..., hp)
Mixed radix system multiple setting means, In advance, a plurality of multiple d
Data (<p>_A, 2 * <p>_A,…, H * <p>_A)But
Remainder system multiple setting means to be set, <P> is the remainder system representation of the modulus p_AAnd then <y
>_AData that exceeds the upper limit value of d * <p>_AUsing
D * <p>_AFrom above <y>_ASubtract with modulo expression
Then, the positive remainder subtraction result <S>_ARemainder subtraction means for obtaining
When, Positive remainder subtraction result obtained by the remainder subtraction means
<S>_AAnd the above <x> _AAnd are added in the remainder system representation, and the remainder
System addition result <z>_ARemainder system addition means for obtaining Remainder system addition result <z obtained by the remainder system adding means
>_AExpression conversion means for converting to a mixed radix representation, The added number displayed by the mixed radix obtained by the expression conversion means.
The calculation result z and each multiple number in the mixed radix system multiple setting means.
And the addition result z displayed as the mixed radix based on
Contains a maximum of j times (0 ≦ j ≦ h) multiple data jp
(Jp ≦ z <(j + 1) p) is determined and the multiple j is determined.
Number determination means, Based on the multiple j obtained by the multiple determining means,
Remainder system addition result <z> obtained by the remainder system addition means
_AFrom j to the multiple data j in the remainder system multiple setting means
* <P>_AIs subtracted, and the remainder subtraction result by the obtained modulus p
<Z>_AAnd a subtraction result output means for outputting
Characteristic remainder arithmetic unit. 3. A coset arithmetic unit for adding a plurality of coset data <x> _A and <y> _A represented by coset modulo A under modulo p (: p <A). Then, approximate value data (p ′, 2p ′, ..., hp ′) showing the upper w digit among a plurality of multiple data obtained by multiplying modulo p by a binary expression in advance (h = 1 to a positive integer). And a plurality of multiple data (<p> _A , 2 * <p> _A , ..., H * <p> _{A) obtained} by multiplying the modulus p by h in advance by the remainder system representation. ) Is set, and the remainder system addition means that obtains the remainder system addition result <z> _A by adding the inputted remainder system data <x> _A , <y> _A in a remainder system expression , The remainder addition result <z obtained by the remainder addition means
> An approximate conversion means for converting the _A into a binary number expressed in the approximation of upper w positions, the approximate value of the binary representation to the data z 'obtained by the approximate conversion means, each of said binary number system multiple configuration means Based on the approximate value data, the fact that the approximate value data z ′ of the addition result includes the maximum j times (0 ≦ j ≦ h) approximate value data jp ′ (jp ′ <z ′ ≦ (j + 1) p ') is determined to determine the multiple j, and the remainder addition result <z> obtained by the remainder addition unit based on the multiple j obtained by the multiple determination means.
Multiple data j from _A to j times in the remainder system multiple setting means
* <P> _A subtraction system, and an addition result output means for outputting a remainder system addition result <z> _A in the obtained modulus p. 4. A plurality of cosets represented by cosets by method A
Data <x>_A, <Y>_AWith respect to the law p (: p <A)
And the above <x>_AFrom above <y>_ARemainder for subtracting
System arithmetic device, Preliminarily multiply the modulus p by a binary expression (h = 1 to a positive integer).
Approximate value data showing the upper w digit of multiple multiple data
A binary number system in which data (p ', 2p', ..., hp ') is set
Multiple setting means, In advance, a plurality of multiple d
Data (<p>_A, 2 * <p>_A,…, H * <p>_A)But
Remainder system multiple setting means to be set, <P> is the remainder system representation of the modulus p_AAnd then <y
>_AData that exceeds the upper limit value of d * <p>_AUsing
D * <p>_AFrom above <y>_ASubtract with modulo expression
Then, the positive remainder subtraction result <S>_ARemainder subtraction means for obtaining
When, Positive remainder subtraction result obtained by the remainder subtraction means
<S>_AAnd the above <x> _AAnd are added in the remainder system representation, and the remainder
System addition result <z>_ARemainder system addition means for obtaining Remainder system addition result <z obtained by the remainder system adding means
>_AIs converted to a binary number with an approximate value of the upper w digits.
Exchange means, Approximate value data in binary representation obtained by the approximate conversion means
Data z'and the approximate value data in the binary system multiple setting means.
The approximate value data z ′ of the addition result based on
Includes maximum j times (0 ≦ j ≦ h) approximate value data jp ′
(Jp '<z' ≤ (j + 1) p ') is determined and the multiple j is determined.
A means for determining a multiple to be determined, Based on the multiple j obtained by the multiple determining means,
Remainder system addition result <z> obtained by the remainder system addition means
_AFrom j to the multiple data j in the remainder system multiple setting means
* <P>_AIs subtracted, and the remainder subtraction result by the obtained modulus p
<Z>_AAnd a subtraction result output means for outputting
Characteristic remainder arithmetic unit. 5. A set of n disjoint integers {a₁，
a_Two, ..., a_n} As a base, and A = a₁* A_Two* ... * a
_nFor two integers that satisfy the condition 0 ≦ x, y <A
And the remainder system representation of the integer x is (x₁, X_Two, ..., x
_n) And the remainder system representation of the integer y is (y₁, Y_Two，
…, Y_n), A positive integer p satisfying p <A is modulo p
As the remainder system addition result of x and y, z = x + y (mod
  p) = (z ₁, Z_Two,…, Z_n) To calculate
A coset operation method, Remainder addition formula z_i= X_i+ Y_i(Mod a_i) (1
≦ i ≦ n), the remainder system addition result z in Modulus A is required.
Element z_iThe remainder system addition process calculated for each The element z obtained in the remainder system addition step_iAnd the following v_iof
Based on each formula, the remainder system addition result z is displayed as a mixed radix
(V₁, V_Two, ..., v_n) Expression conversion process, Addition result displayed in the mixed radix obtained in the expression conversion step
A value obtained by multiplying the result z and the modulus p displayed in the mixed radix by j {p, 2
p, ..., jp, ..., hp} (where 1 ≦ j ≦ h)
Comparing method p comparing step, The remainder system representation of the modulus p is (p₁, P_Two,,, p_n)
Based on the comparison result of the method p comparison step, (j
If p ≦ z <(j + 1) p, z_i= Z_i-J * p_i(Mod
 a_i) (1 ≦ i ≦ n), and if hp ≦ z, z_i
= Z_i-H * p _i(Mod a_i) (1 ≤ i ≤ n)
By executing the calculation, the remainder addition result z in the modulus p is calculated.
And the execution process to be executed (mod p).
Remainder system calculation method. v₁= Z₁(Mod a₁) v_Two= (Z_Two-V₁) * C₁₂(Mod a_Two) v_Three= ((Z_Three-V₁) * C₁₃-V_Two) * C_{twenty three}(Mod a_Three)     : v_n= ((Z_Three-V₁) * C_1n-V_Two) * C_2n-...- v_(n-1)) * C_{(n-1) n}( mod a_n)   However, C_ji= A_j ^-1mod a_i, (J = 1, 2, ..., i-1) 6. A disjoint set of n integers {a₁，
a_Two, ..., a_n} As a base, and A = a₁* A_Two* ... * a
_nFor two integers that satisfy the condition 0 ≦ x, y <A
And the remainder system representation of the integer x is (x₁, X_Two, ..., x
_n) And the remainder system representation of the integer y is (y₁, Y_Two，
…, Y_n), A positive integer p satisfying p <A is modulo p
As the remainder subtraction result of x and y, z = xy (mod
  p) = (z ₁, Z_Two,…, Z_n) To calculate
A coset operation method, The remainder system representation of p is (p₁, P_Two,,, p_n) And
At this time, using a multiple d * p of p that exceeds the upper limit of y,
Cosmic subtraction formula s_i= D * p_i-Y_i(Moda_i)
(1 ≦ i ≦ n), the positive remainder subtraction result s =
(S₁, S_Two,…, S _n) Calculating remainder system subtraction process
When, The element s obtained by the remainder subtraction step_iUsing
Formula z of coset addition_i= S _i+ X_i(Mod a_i) (1 ≤
i ≤ n) based on the remainder system addition result z in the modulus A
z_iThe remainder system addition process calculated for each The element z obtained in the remainder system addition step_iAnd the following v_iof
Based on each formula, the remainder system addition result z is displayed as a mixed radix
(V₁, V_Two, ..., v_n) Expression conversion process, Addition result displayed in the mixed radix obtained in the expression conversion step
A value obtained by multiplying the result z and the modulus p displayed in the mixed radix by j {p, 2
p, ..., jp, ..., hp} (where 1 ≦ j ≦ h)
Comparing method p comparing step, The remainder system representation of the modulus p is (p₁, P_Two,,, p_n)
Based on the comparison result of the method p comparison step, (j
If p ≦ z <(j + 1) p, z_i= Z_i-J * p_i(Mod
 a_i) (1 ≦ i ≦ n), and if hp ≦ z, z_i
= Z_i-H * p _i(Mod a_i) (1 ≤ i ≤ n)
By executing the calculation, the remainder subtraction result z in the modulus p is calculated.
And the execution process to be executed (mod p).
Remainder system calculation method. v₁= Z₁(Mod a₁) v_Two= (Z_Two-V₁) * C₁₂(Mod a_Two) v_Three= ((Z_Three-V₁) * C₁₃-V_Two) * C_{twenty three}(Mod a_Three)     : v_n= ((Z_Three-V₁) * C_1n-V_Two) * C_2n-...- v_(n-1)) * C_{(n-1) n}( mod a_n)   However, C_ji= A_j ^-1mod a_i, (J = 1, 2, ..., i-1) 7. A set of n disjoint integers {a₁，
a_Two, ..., a_n} As a base, and A = a₁* A_Two* ... * a
_nFor two integers that satisfy the condition 0 ≦ x, y <A
And the remainder system representation of the integer x is (x₁, X_Two, ..., x
_n) And the remainder system representation of the integer y is (y₁, Y_Two，
…, Y_n), A positive integer p satisfying p <A is modulo p
As the remainder system addition result of x and y, z = x + y (mod
  p) = (z ₁, Z_Two,…, Z_n) To calculate
A coset operation method, Remainder addition formula z_i= X_i+ Y_i(Mod a_i) (1
≦ i ≦ n), the remainder system addition result z in Modulus A is required.
Element z_iThe remainder system addition process calculated for each The A is the a_iA divided by_i(= A / a_i)When
Then A_i ^-1The law a_iIn A_iMultiplicative inverse element of
Then, the element z obtained in the remainder addition step_iBased on
To calculate a positive integer k that satisfies the following Σ
Data calculation process, The element z obtained in the remainder system addition step_i, The parameter
The positive integer k obtained in the step of calculating
Based on the value obtained by expressing the remainder system addition result z in binary.
Higher-order w bits (however, w is less than the basic operation width of the arithmetic unit body
An approximation conversion step of calculating an approximation value z ′ of (below), Approximate value z'in the binary representation obtained in the approximate conversion step
And the upper w bits of the value obtained by multiplying the binary representation modulo p by j
The approximate value of {p ', (2p)', ..., (jp) ', ...,
(Hp) ′} (where 1 ≦ j ≦ h)
Comparison process, The remainder system representation of the modulus p is (p₁, P_Two,,, p_n)
Based on the comparison result of the method p comparison step, (j
If p) '<z' ≤ ((j + 1) p) ', then z_i= Z _i-J *
p_i(Mod a_i) (1 ≦ i ≦ n), and (h
If p) '<z', then z_i= Z_i-H * p_i(Mod a
_i) (1 ≦ i ≦ n),
Execution step of calculating the remainder system addition result z (mod p)
A coset arithmetic method characterized by including and. [Equation 1] 8. The coset arithmetic method according to claim 7, wherein the parameter calculating step calculates a positive integer k according to the following equation. [Equation 2] 9. The coset arithmetic method according to claim 7.
hand, The method p comparison step substitutes an approximate value for j times p.
Therefore, the approximate value of the upper w bits of the value obtained by multiplying M * p by j
{(M * p) ', (2M * p)', ..., (hM *
p) ′} (where 1 ≦ j ≦ h) is used to perform the comparison.
I The (mod p) execution step relates to j times the p.
Instead of the comparison result, j of M * p obtained by the method p comparison step is used.
(JM * p) '<z'
≤ ((j + 1) M * p) '(where j <h), z_i= Z_i
-JM * p_i(Mod a_i) (1 ≦ i ≦ n)
And if (hM * p) '<z', then z_i= Z _i-(HM *
p_i) (Mod a_i) (1 ≦ i ≦ n)
To calculate the remainder system addition result z by the above-mentioned method p
A coset arithmetic method characterized by. 10. A set of n disjoint integers {a₁, A
_Two, ..., a_n} As a base, and A = a₁* A_Two* ... * a_n
For two integers that satisfy the condition 0 ≦ x, y <A
Then, the remainder system representation of the integer x is (x₁, X_Two，… ，
x_n) And the remainder system representation of the integer y is (y₁, Y_Two，
…, Y_n), A positive integer p satisfying p <A is modulo p
As the remainder subtraction result of x and y, z = xy (mod
  p) = (z₁, Z_Two,…, Z_n) To calculate
A coset operation method, The remainder system representation of p is (p₁, P_Two,,, p_n) And
At this time, using a multiple d * p of p that exceeds the upper limit of y,
Cosmic subtraction formula s_i= D * p_i-Y_i(Moda_i)
(1 ≦ i ≦ n), the positive remainder subtraction result s =
(S₁, S_Two,…, S _n) Calculating remainder system subtraction process
When, The element s obtained by the remainder subtraction step_iUsing
Formula z of coset addition_i= S _i+ X_i(Mod a_i) (1 ≤
i ≤ n) based on the remainder system addition result z in the modulus A
z_iThe remainder system addition process calculated for each The A is the a_iA divided by_i(= A / a_i)When
Then A_i ^-1The law a_iIn A_iMultiplicative inverse element of
Then, the element z obtained in the remainder addition step_iBased on
To calculate a positive integer k that satisfies the following Σ
Data calculation process, The element z obtained in the remainder system addition step_i, The parameter
The positive integer k obtained in the step of calculating
Based on the value obtained by expressing the remainder system addition result z in binary.
Higher-order w bits (however, w is less than the basic operation width of the arithmetic unit body
An approximation conversion step of calculating an approximation value z ′ of (below), Approximate value z'in the binary representation obtained in the approximate conversion step
And the upper w bits of the value obtained by multiplying the binary representation modulo p by j
The approximate value of {p ', (2p)', ..., (jp) ', ...,
(Hp) ′} (where 1 ≦ j ≦ h)
Comparison process, The remainder system representation of the modulus p is (p₁, P_Two,,, p_n)
Based on the comparison result of the method p comparison step, (j
If p) '<z' ≤ ((j + 1) p) ', then z_i= Z _i-J *
p_i(Mod a_i) (1 ≦ i ≦ n), and (h
If p) '<z', then z_i= Z_i-H * p_i(Mod a
_i) (1 ≦ i ≦ n),
Execution step of calculating the modulo subtraction result z (mod p)
A coset arithmetic method characterized by including and. [Equation 3]