JP2005208327A - Surplus device, surplus method, program, and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To realize a high-speed residue calculation in a use environment where a high-speed residue calculation cannot be performed conventionally.
The A residue subject c in the case where expressed as _{c = Σ i = 0 c i} x i, enter each coefficient c _i, in contraction means 16, using the coefficients c _i and multiplier coefficient p _h, Each coefficient c _i ′ satisfying Σ _{i = 0} ^u−1 c _i 'x ⁱ = Σ _{i = 0} c _i ' x ⁱ mod f (x) is calculated. Where L: number of bits of modn value, w: number of bits in word, u: minimum integer greater than or equal to L / w, Q: integer greater than or equal to 2, E = uw-L, modulus n = Q ^L -Σ _{j = 0} ^L-1 d _j Q ^j , multiplication factor p _h = Σ _{k = 0} ^w-1 d _{wh + kE} Q ^k (h = 0,1, ..., u-1), f (x) = x ^u −Σ _{i = 0} ^u−1 p _i x ⁱ .
Then, after calculation of all the coefficients c _i ′, carry-up correction between the terms x ⁱ of the coefficient c _i ′ when x = Q ^w is performed collectively.
[Selection] Figure 1

Description

  The present invention relates to a remainder device, a remainder method, a program for realizing the function, and a recording medium, and more particularly to a remainder apparatus, a remainder method, a program, and a recording medium that can perform a remainder operation at high speed.

Multiple-multiple modular multiplication is performed from the implementation of public key cryptography and digital signatures based on the difficulty of the discrete logarithm problem, and the speed of modular multiplication determines the speed of public key cryptography and digital signatures. It is no exaggeration to say. For this reason, many techniques for increasing the speed of remainder multiplication have been devised.
In many remainder multiplication methods,
m ← ab mod n (0 ≦ a, b ≦ n)
When calculating
Step 1: calculate c ← ab Step 2: often calculate c mod n.

ここで、ｕは、

<Speedup of Step 1>
The method of Non-Patent Document 1 is known as a high-speed mounting method of multiple length multiplication required in Step 1. The procedure for obtaining the product of a and b by the method of Non-Patent Document 1 using a multiplier that generates 2 W bits from a product of W bits and a 2 W bit adder will be described below. Note that a and b are within L bits. Note that L indicates the number of bits of standardized data such as security parameters.
First, a, ^{Q w} ary as follows b (Q ≧ 2) represents.

Where u is

を以下のように計算する。
Ｓｔｅｐ１−１ 初期化：「ｃ_ｉ←０」とする。
Ｓｔｅｐ１−２ 語長乗算：全ての０≦ｓ,ｔ≦ｕに対し、「ｃ_ｓ＋ｔ←ｃ_ｓ＋ｔ＋ａ_ｓｂ_ｔ」を計算する。
Ｓｔｅｐ１−３ 繰り上がり補正：ｉ＝０,１,...,２ｕ-２に対し、

In addition, the condition of the expression (3) is that when the multiplication is calculated by the textbook method, the data of (Q ^w −1) ² may be added u times, but even in such a case, This is to prevent the calculation result from exceeding the processing capability Q ^2W of the 2W bit multiplier (no overflow occurs). In addition, an expression like Expression (1) is called a redundant expression.
At this time, it is the product of a and b

Is calculated as follows.
Step 1-1 Initialization: “c _i ← 0”.
Step 1-2 Word length multiplication: “c _{s + t} ← c _{s + t} + a _s b _t ” is calculated for all 0 ≦ s, t ≦ u.
Step 1-3 Carrying correction: For i = 0,1, ..., 2u-2,

Here, since w is selected so as to satisfy the condition of Expression (3), overflow does not occur in the addition of Step 1-2. In addition, the addition of Step 1-2 does not perform the carry-up correction, and the carry-up correction is collectively performed in the last Step 1-3, so that the processing can be speeded up.
Incidentally, L is not so large compared with W, is less the number of to be multiple-precision multiplication performed, redundant representation conversion cost of the usual representation using 2 ^W Decimal (Step 1-3) is not a fool. However, when a large number of multiplications are required as in cryptographic applications, multiplication using redundant expressions is often more advantageous even considering the conversion cost with normal expressions.

となるｎを利用する。ただし、ｋはｗｋ＝Ｌを満たす自然数である。すなわち、Ｌはｗの倍数である。
以下では、例として、
Ｑ＝２，ｗ＝６４，ｋ＝３，Ｌ＝１９２，
ｎ＝（２^６４）^３‐２^６４‐１ …(5)
を選んだ場合のＳｔｅｐ２の処理を説明する。 <Speedup of Step2>
Further, there is a method of selecting a method n suitable for calculation and calculating the remainder of Step 2 at high speed. This is a method used when configuring public key cryptography, for example. As one of such methods, the method of Patent Document 1 is known. Below, the method of this patent document 1 is demonstrated.
In the method of Patent Document 1,

N is used. However, k is a natural number satisfying wk = L. That is, L is a multiple of w.
In the following, as an example
Q = 2, w = 64, k = 3, L = 192,
n = (2 ⁶⁴ ) ³ −2 ⁶⁴ −1 (5)
The process of Step 2 when selecting is described.

と表されているとする。
このとき式（５）より、
（２^６４）^３≡２^６４＋１（ｍｏｄ ｎ） …(7)
であり、この合同式（７）を式（６）に複数回利用すると、
ｃ≡（ｃ_０＋ｃ_３＋ｃ_５）＋（ｃ_１＋ｃ_３＋ｃ_４＋ｃ_５）２^６４＋（ｃ_２＋ｃ_４＋ｃ_５）（２^６４）^２（ｍｏｄ ｎ） …(8)
となる。 In addition, the remainder object c is

Is expressed.
At this time, from equation (5),
^{(2 64) 3 ≡2 64 +1} (mod n) ... (7)
When this congruence formula (7) is used multiple times in formula (6),
c≡ (c ₀ + c ₃ + c ₅ ) + (c ₁ + c ₃ + c ₄ + c ₅ ) 2 ⁶⁴ + (c ₂ + c ₄ + c ₅ ) (2 ⁶⁴ ) ² (mod n) (8)
It becomes.

Here, from the _c i ^{<2 64} of formula (6), the right side of the equation _{(8) (c 0 + c} 3 + c 5) + (c 1 + c 3 + c 4 + c 5) 2 64 + (c 2 + c 4 + c ₅ ) (2 ⁶⁴ ) ² (9)
Is less than or equal to 4 times n shown in Equation (5). Therefore, each coefficient (c ₀ + c ₃ + c ₅ ), (c ₁ + c ₃ + c ₄ + c ₅ ), (c ₂ + c ₄ + c ₅ ) of equation (9) is calculated, and equation ( ₅ ) is calculated from equation (9). The remainder result m can be obtained by subtracting n indicated by 3 at most. This means that the amount of calculation can be greatly reduced compared to the case where mod n of c is directly calculated from Equation (6).

In addition, the addition processing of each coefficient (c ₀ + c ₃ + c ₅ ), (c ₁ + c ₃ + c ₄ + c ₅ ), and (c ₂ + c ₄ + c ₅ ) in Expression (9) performs a carry-up correction to a higher term. Performed while doing. That is, for example, when the addition result is 2 ⁶⁴ or more at c ₀ + c ₃ in the addition process of (c ₀ + c ₃ + c ₅ ), the carry correction value (c ₀ + c ₃ ) mod 2 of the term at that time ⁶⁴ and (c ₀ + c ₃ ) / 2, which is the carry-up amount, is calculated to calculate a maximum integer equal to or less than ^64. If necessary, carry-up processing to higher terms is sequentially performed.
Intel Corporation, “Execution of Large Number Multiplication Using Streaming SIMD Extension Instruction 2 (SSE2),” Version 2.0, AP-941, Document No. 248606J-001, 2000 Mitsuru Matsui, “Calculation device, calculation method and recording medium recording the calculation method,” Japanese Patent No. 3183670, filed on Jan. 21, 1999, registered on Apr. 27, 2001

However, in the case of the conventional residue calculation method, the residue calculation may not be performed at high speed depending on the use environment.
That is, as shown in the description of Expression (4), the remainder method of Patent Document 1 is based on the assumption that L is a multiple of w, and cannot be used when L is not a multiple of w.
Further, in the remainder method of Patent Document 1, the addition process of each coefficient is performed while sequentially performing carry correction with a large calculation amount. Therefore, when there are many carry corrections, the remainder method of Patent Document 1 is used. Even if it is possible, the remainder calculation cannot be performed at high speed.

The present invention has been made in view of such a point, and an object of the present invention is to provide a remainder device that realizes a high-speed residue calculation in a use environment where a residue calculation cannot be performed at high speed.
Another object of the present invention is to provide a residue method that realizes a high-speed residue calculation in a use environment where a residue operation cannot be performed at a high speed.

を乗算係数格納手段に格納しておく。
また、剰余対象入力手段に、

各係数ｃ_ｉを入力する。
そして、縮約手段において、係数ｃ_ｉと乗算係数ｐ_ｈとを用い、

を満たす各係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。 In the present invention, in order to solve the above-mentioned problem, first, the value of mod n is L bits, the number of bits of a word as a processing unit viewed from software is w, u is the smallest integer equal to or greater than L / w, and Q Is an integer greater than or equal to 2, E = uw−L,

Is stored in the multiplication coefficient storage means.
In addition, the remainder target input means

Input each coefficient c _i .
Then, the contraction means, using the coefficients _{c i} and multiplier coefficient _{p h,}

Each coefficient c _i ′ satisfying the above is calculated without performing carry correction between the terms x ⁱ .

Then, the _'After calculating the in normalization means, the coefficient c _i in the case where the x = Q _^w' all the coefficients c _i are collectively a carry correction between each term x ⁱ of.
Here, E means an error between the minimum number of L bits or more that can be processed in word units (w bits) and the L bit, and the multiplication coefficient _ph is set in consideration of this error E. Is. Therefore, the multiplication coefficient _ph and f (x) defined by using this take into consideration the case where L is not a multiple of w. Then, by using this multiplication coefficient _ph and each coefficient c _i and using each coefficient c _i ′ calculated by the contraction means, c mod with a small amount of calculation, as in the remainder method of Patent Document 1 described above. n can be obtained. That is, even if L is not a multiple of w, c mod n can be obtained at high speed. For the same reason, even if L is not a multiple of w, the present invention and the multiplication method of Non-Patent Document 1 can be used in combination, and high-speed modular multiplication can be realized.

Further, the contraction means calculates each coefficient c _i ′ of c ′ without performing the coefficient carry-over correction between the terms. Therefore, the processing becomes faster than when calculating each coefficient while performing carry correction.
Furthermore, by carrying out carry-up correction collectively at the end, it is possible to reduce the calculation amount of carry-up correction compared to the case where each coefficient is calculated while performing carry-up correction, and the processing becomes faster.

を満たす各係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。
この乗算係数ｐ_ｈ及びｆ（ｘ）は、Ｌがｗの倍数でない場合をも考慮したものである。そして、その演算結果を用いることにより、少ない計算量でｃ ｍｏｄ ｎを算出することができる。また、繰り上がり補正を逐一行わないため、従来繰り上がり補正が多く計算量が多くなっていた場合であっても、高速に剰余演算処理を実行することができる。
以上より、本発明では、従来高速に剰余演算を行うことができなかった使用環境において高速な剰余演算を実現することが可能となる。 In the present invention, using the coefficients _{c i} and multiplier coefficient _{p h,}

Each coefficient c _i ′ satisfying the above is calculated without performing carry correction between the terms x ⁱ .
The multiplication coefficients _ph and f (x) take into consideration the case where L is not a multiple of w. Then, by using the calculation result, c mod n can be calculated with a small amount of calculation. In addition, since the carry correction is not performed step by step, the remainder calculation process can be executed at high speed even when the carry correction is large and the calculation amount is large.
As described above, according to the present invention, it is possible to realize a high-speed residue calculation in a use environment where a conventional high-speed residue calculation cannot be performed.

Embodiments of the present invention will be described below with reference to the drawings.
[First Embodiment]
First, a first embodiment of the present invention will be described.
<Overview>
FIG. 1 is a block diagram illustrating the overall configuration of the surplus apparatus 10 according to the present embodiment, and FIG. 4 is a flowchart for explaining the entire processing of the surplus apparatus 10. Hereinafter, the outline of this embodiment will be described with reference to these drawings.

As illustrated in FIG. 1, the remainder device 10 of this embodiment includes a multiplication target input unit 11, a multiplication unit 12, an addition unit 13 (corresponding to “fourth addition unit”), a residue target input unit 14, and a multiplication coefficient storage. Means 15, contraction means 16, normalization means 17, and control means 18. Under the control of the control means 18, the remainder multiplication (c ← ab, m ← cmd n for the inputted a and b) )I do.
The remainder device 10 according to the present embodiment is assumed to be a remainder multiplication using a word length of W bits, and is constructed by causing a known computer having a processing unit as viewed from hardware to have 2 W bits to execute a predetermined program. It is. In other words, an environment is assumed in which multiplication for obtaining 2 W bits from W bits and addition of 2 W bits can be efficiently calculated.

とおく。ここで、Ｌ（ビット）は出力するｍｏｄ ｎの値のビット数を意味し、例えば、セキュリティビット等が該当する。また、Ｑは２以上の整数である。

とおく。
ここで、ｗはソフトウェアからみた処理単位であるワードを示し、ｕはＬ／ｗ以上の最小の整数を意味する。また、Ｅは、ワード単位（ｗビット）で処理可能なＬビット以上の最小ビット数と、Ｌビットとの誤差を意味する（Ｅ＝ｕｗ‐Ｌ）。また、式（１１）のｄ_{ｗｈ＋ｋ‐Ｅ}は、式（１０）のｄ_ｊに対応するものであるが、ｗｈ＋ｋ‐Ｅ＜０の場合にはｄ_{ｗｈ＋ｋ‐Ｅ}＝０とする。また、ｘは、正規化手段１７における正規化処理の際ｘ＝Ｑ^ｗとして取り扱われる値である。 In this embodiment, the modulus n is

far. Here, L (bit) means the number of bits of the value of mod n to be output, and corresponds to, for example, a security bit. Q is an integer of 2 or more.

far.
Here, w indicates a word that is a processing unit viewed from software, and u indicates a minimum integer equal to or greater than L / w. Further, E means an error between the minimum number of L bits or more that can be processed in word units (w bits) and L bits (E = uw−L). Further, d _{wh + k−E} in equation (11) corresponds to d _j in equation (10), but when wh + k−E <0, d _{wh + k−E} = 0. Further, x is a value which is treated as x = Q ^w during the normalization process in normalization means 17.

と表現した場合における、各係数ａ_ｓ及びｂ_ｔの入力を受け付ける（ステップＳ１）。なお、この例で入力されるａ_ｓ及びｂ_ｔは、
０≦ａ_ｓ,ｂ_ｔ＜Ｑ^ｗ （ｓ,ｔ＝０,１,...,ｕ‐２）
０≦ａ_ｕ−１,ｂ_ｕ−１＜Ｑ^ｗ‐Ｅ
を満たすものとする。また、式（１３）,（１４）のような表現を「冗長表現」と呼ぶ。 In addition, _ph (hereinafter referred to as “multiplication coefficient”) calculated by Expression (11) is stored in the multiplication coefficient storage means 15. Here, the storage of the multiplication factor p _h, another case of storing the multiplication factor p _h as data, but also the case of storing a program which the multiplication factor p _h is incorporated.
When performing remainder multiplication using the remainder device 10, first, in the multiplication target input means 11,

In the case of expressing a receives an input of coefficients _{a s} and _{b t} (Step S1). Incidentally, _{a s} and _{b t} are input in this example,
0 ≦ a _s , b _t <Q ^w (s, t = 0, 1,..., U−2)
0 ≦ a _u−1 , b _u−1 <Q ^w−E
Shall be satisfied. Expressions such as equations (13) and (14) are called “redundant expressions”.

とおいた場合における各係数ｃ_ｉを構成する。そして、ステップＳ２で示した「各項間の繰り上がり補正を行うことなく」とは、項ｘ^ｉの係数ｃ_ｉを構成するｃ_ｓ＋ｔ←ｃ_ｓ＋ｔ＋ａ_ｓｂ_ｔの演算結果がｘ以上となった場合でも、この演算結果を項ｘ^ｉ＋１の係数として繰り上げる処理を行わないことを意味する。
次に、剰余対象入力手段１４において、加算手段１３での最終的な演算結果ｃ_ｓ＋ｔの入力を受け付ける（ステップＳ３）。なお、このｃ_ｓ＋ｔは、ｉ＝ｓ＋ｔとし、剰余対象ｃを

と表現した場合における各係数ｃ_ｉに相当する。 Next, the multiplication unit 12 receives the coefficients a _s and b _t from the multiplication target input unit 11 and performs a _s b _t calculation for all integers s and t with 0 ≦ s and t ≦ u−1. . Further, in the adding means 13, c _{s + t} ← using the calculation result in the multiplying means 12 without performing carry correction between the terms for all integers s, t where 0 ≦ s, t ≦ u−1. Calculation of c _{s + t} + a _s b _t is performed (multiplication processing: step S2).
The calculation result of c _{s + t} ← c _{s + t} + a _s b _t is i = s + t,

Each coefficient c _i is configured. Then, “without performing carry correction between each term” shown in step S2 means that the calculation result of c _{s + t} ← c _{s + t} + a _s b _t constituting the coefficient c _i of the term x ⁱ is greater than or _equal to x. This means that the calculation result is not carried up as the coefficient of the term x ^{i + 1} .
Next, the remainder target input unit 14 receives the input of the final calculation result c _{s + t from} the addition unit 13 (step S3). This c _{s + t} is i = s + t, and the remainder object c is

_Is equivalent to each coefficient ci.

を満たす各係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する（縮約処理：ステップＳ４）。つまり、式（１２）から導かれる合同式

を式（１５）に適用することにより得られる式（１６）の左辺の各係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。なお、ここでの「各項間の繰り上がり補正を行うことなく」とは、式（１７）を式（１５）に適用した場合における項ｘ^ｉ（ｉ≦ｕ‐１）の係数ｃ_ｉ’を算出する過程において、演算結果がｘ以上となった場合でも、この演算結果を項ｘ^ｉ＋１の係数として繰り上げる処理を行わないことを意味する。 Then, the contraction means 16, and a coefficient _c i _{= c s + t} which is input in the remainder target input unit 14, a multiplication factor _{p h} extracted from the multiplier coefficient storing means 15 using,

Each coefficient c _i ′ satisfying the above is calculated without performing a carry correction between the terms x ⁱ (contraction processing: step S4). In other words, the congruence derived from equation (12)

Each coefficient c _i ′ on the left side of the equation (16) obtained by applying to the equation (15) is calculated without performing a carry correction between the terms x ⁱ . Here, “without performing carry correction between the terms” means that the coefficient c _i ′ of the term x ⁱ (i ≦ u−1) when Equation (17) is applied to Equation (15). This means that even when the calculation result is equal to or greater than x in the process of calculating, the calculation result is not carried up as a coefficient of the term x ^{i + 1} .

_'After the calculation of each coefficient c _i' all the coefficients c _i is sent to the normalization unit 17, the normalizing unit 17, between each term x ⁱ of the coefficient c _{i 'in} the case where the x = Q ^w Are carried out collectively (step S5), and the L-bit length reduction process is performed to calculate the remainder multiplication result m.
Here, the above-described multiplication coefficient _ph and f (x) defined by using this take into consideration the case where L is not a multiple of w. Then, by using the multiplication coefficient _ph and each coefficient c _i and using each coefficient c _i ′ calculated by the contracting means 16, c mod n can be obtained with a small amount of calculation. That is, even if L is not a multiple of w, c mod n can be obtained at high speed.

となるが、このようなｃ_ｉに対して式（１６）の左辺の各係数ｃ_ｉ’がＱ^２Ｗ未満となるようなｆ（ｘ）に対応するｎを法とする。これにより、演算結果が、ハードウェアが一度に取り扱うことが可能なビット数を超え、その補正処理が必要となるという事態を防止できる。なお、一部の演算結果が、ハードウェアが一度に取り扱うことが可能なビット数を超えることになるｎであっても、他の補正処理との関係で処理が高速化できる場合には、そのようなｎを用いてもよい。 Further, the contracting means 16 uses each coefficient of c ← ab calculated without correcting the coefficient advance between the terms, and further reduces c ′ without correcting the coefficient advance between the terms. Each coefficient c _i ′ is calculated, and finally, the normalizing means 17 collectively performs all carry-up corrections. Therefore, the processing becomes faster than when calculating each coefficient while performing carry correction.
The modulus n in this embodiment is a value that makes the number of bits of each calculation result in the contracting means 16 less than the number of bits (2W bits) that the hardware can handle at a time. That is, in the multiplication target input unit 11, _{a s} and _{b t} is input,
0 ≦ a _s , b _t <Q ^w (s, t = 0, 1,..., U−2)
0 ≦ a _u−1 , b _u−1 <Q ^w−E
When each of the coefficients c _{i in} equation (15) is

However, modulo n corresponding to f (x) such that each coefficient c _i ′ on the left side of the equation (16) is less than Q ^2W with respect to such c _i . As a result, it is possible to prevent a situation in which the calculation result exceeds the number of bits that can be handled by the hardware at one time and the correction process is required. Note that even if some computation results are n that exceeds the number of bits that the hardware can handle at one time, if the processing can be speeded up in relation to other correction processing, Such n may be used.

Such n has 22751 even if only prime numbers when L = 160 and w = 27. And among them, the calculation cost in the contracting means 16 is low, for example,
2 ¹⁶⁰ -2 ^27-2- (2 ⁴ -1)
2 ¹⁶⁰ -2 ⁶ 2 ^27-2 -1
2 ¹⁶⁰ -2 ^{3 ・ 27-2-} (2 ⁴ -1)
Etc. can be illustrated.
<Example 1>
Next, Example 1 in this embodiment will be described.

In this example, Q = 2, L is 160, W is 32, w is 27, u is 6, and modulus n is 2 ¹⁶⁰ -2 ⁷⁹ -15 (= 2 ^160- 2 ^{3 · 27-2-} (2 ⁴ -1)). In this _{^{case, E = 2, p 0 =}} 2 2 (2 4 -1), p 3 = 1, p h = 0 (h = 1,2,4,5), f (x) = x 6 -x 3 −60 (= x ⁶ −x ³ −2 ² (2 ⁴ −1)).
<Configuration of Example 1>
The overall configuration in Example 1 is as described above (FIG. 1). Hereinafter, only detailed configurations of the contracting unit 16 and the normalizing unit 17 in the first embodiment will be described.

FIG. 2 is a block diagram showing the configuration of the contracting means 16 in this embodiment, and FIG. 3 is a block diagram showing the configuration of the normalizing means 17 in this embodiment.
As shown in FIG. 2, the contracting means 16 of the present embodiment includes adding means 16a, 16b, 16d (corresponding to “first to third adding means”) and a multiplying means 16c. As shown in FIG. 3, the contraction means 17 of this embodiment includes carry correction means 17aa, 17ab, 17c and contraction processing means 17ba, 17bb, 17bc, 17bd.
More specifically, for example, the reduction means 16 and the normalization means 17 of this embodiment are realized by a multiplier that obtains a 64-bit product of 64 bits and an adder that obtains the sum of 64 bits. The Here, the adder can also perform subtraction, and the shift of a 64-bit value can be calculated efficiently. An example of such an environment is Intel® SSE2. Of course, when addition of 64 bits cannot be performed directly, there may be a replacement such as executing addition of 64 bits by combining additions of 32 bits (the same applies to Example 2 described later).

<Process of Example 1>
The entire processing in the first embodiment is as described above (FIG. 4). Hereinafter, only the details of the processing in steps S2, S4, and S5 (FIG. 4) in the first embodiment will be described.
<Processing of Step S2 in Embodiment 1>
FIG. 5 is a flowchart for explaining the processing in step S2 of FIG. 4 in the present embodiment.
As shown in FIG. 5, in this process, first, for i = 0, 1,..., 0, 0 is substituted for c _i and 0 is substituted for s and t (step S11). Next, the multiplication unit 12 (FIG. 1) calculates a _s b _t and sends the calculation result to the addition unit 13 (step S12). The adding means 13 calculates c _{s + t} ← c _{s + t} + a _s b _t (step S13). Next, the control means 18 (FIG. 1) determines whether or not s = 5 (= u−1) (step S14). If not s = 5, the calculation of s ← s + 1 is performed and step S12 is performed. Returning to the process, if s = 5, it is determined whether t = 5 (step S15). If t = 5, the process ends. If t = 5, 0 is substituted for s, t ← t + 1 is calculated, and the process returns to step S12.

を満たす係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。すなわち、剰余対象入力手段１４において入力された剰余対象

を複数回適用することにより得られる式（１８）のｃ’の係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。以下この演算を概念的に説明する。 <Processing of Step S4 in Embodiment 1>
As described above, in this embodiment, since u = 6 and f (x) = x ⁶ -x ³ -60, the contracting means 16 of this embodiment is

A coefficient c _i ′ satisfying the above is calculated without performing carry correction between the terms x ⁱ . That is, the remainder target input by the remainder target input means 14

The coefficient c _i ′ of c ′ in the equation (18) obtained by applying a plurality of times is calculated without performing carry correction between the terms x ⁱ . This calculation will be conceptually described below.

FIG. 6 is a conceptual diagram for explaining the relationship between the coefficient c _i of the remainder object c and the coefficient c _i ′ of c ′. Here, x ⁱ (i = 0, 1,..., 10) in FIG. 6 means the terms x ⁱ of c and c ′, and c _i (i = 0, 1,..., 10). Means the coefficient c _i of c, and c _i ′ (i = 0, 1,..., 5) means the coefficient c _i ′ of c ′ in the equation (18). Moreover, c _i and c _i ′ in the same column as x ⁱ (vertical column in FIG. 6) correspond to the coefficient of the term x ⁱ .

FIG. 6A shows the coefficients c _i (i = 0, 1,..., 10) of each term x ⁱ of the residue object c input by the residue object input means 14. Note that, as described above, the remainder object c is obtained by dividing the first multiplication object a expressed by Expression (13) and the second multiplication object b expressed by Expression (14) between the terms x ⁱ . Multiplication is performed without carrying forward correction (step S2). Therefore, the coefficient c _i (i = 0, 1,..., 10) may be greater than or equal to x. In other words, since it corresponds to x = Q ^w = 2 ²⁷ , the coefficient c _i (i = 0, 1,..., 10) may be 27 bits or more.

となるため、各項ｘ^ｉの係数ｃ_ｉは図６の（ｂ）のようになる。なお、この図の「×６０」とは、この「×６０」と同一行（図６における横方向の行）の係数ｃ_ｉを６０倍することを意味する。
さらに、式（２１）に式（２０）を適用すると、

となるため、各項ｘ^ｉの係数ｃ_ｉは図６の（ｃ）のようになる。
そして、図６の（ｃ）に示す各係数ｃ_ｉ或いは６０ｃ_ｉを、各項ｘ^ｉと同一列（図６における縦方向の列）ごとに、桁上がり補正することなく加算した値が、ｃ’における各項ｘ^ｉの係数ｃ_ｉ’となる（図６の（ｄ））。例えば、ｃ_０’＝ｃ_０＋６０ｃ_６＋６０ｃ_９となる。 When the equation (20) is applied once to the equation (19) shown in FIG.

Therefore, the coefficient c _i of each term x ⁱ is as shown in FIG. Note that “× 60” in this figure means that the coefficient c _i of the same row (lateral row in FIG. 6) as this “× 60” is multiplied by 60.
Furthermore, when the formula (20) is applied to the formula (21),

Therefore, the coefficient c _i of each term x ⁱ is as shown in FIG.
A value obtained by adding the coefficients c _i or 60c _i shown in (c) of FIG. 6 for each column x ⁱ in the same column (vertical column in FIG. 6) without carry correction is given as c It becomes the coefficient c _i ′ of each term x ⁱ in “(d) of FIG. 6”. For example, c ₀ ′ = c ₀ + 60c ₆ + 60c ₉

The coefficient c _i ′ is obtained by sequentially calculating c ₀ ′ ← c ₀ +60 c ₆ +60 c ₉ , c ₁ ′ ← c ₁ +60 c ₇ +60 c ₁₀ ,..., C ₅ ′ ← c ₅ + c ₈ However, in this embodiment, this calculation method is devised to further speed up the processing.
FIG. 7 is a flowchart for explaining the processing in step S4 in the present embodiment. Hereinafter, the process of step S4 in the present embodiment will be specifically described with reference to this flowchart.
As shown in FIG. 7, in this process, first, the adding means 16a obtains the coefficients c _i (i = 6, 7, 9, 10) inputted in the remainder target input means 14, and sets i = 6, 7 On the other hand, the calculation of c _i ← c _i + c _{i + 3} is performed (step S21). The coefficient c _i (i = 6, 7), which is the calculation result, is sent to the adding means 16b and the multiple multiplying means 16c.

After the calculation in the adding means 16a, the coefficient c _i (i = 3,4,5,8) inputted in the remainder target input means 14 and the coefficient c _i (i = 6) sent from the adding means 16a in the adding means 16b. , 7) and for i = 3, 4, 5, the calculation of c _i ← c _i + c _{i + 3} is performed (step S22). The coefficient c _i (i = 3,4), which is the calculation result, is sent to the adding means 16d, and c ₅ is output as c ₅ ′. That is, the coefficient c ₅ ′ is the calculation result c ₅ in the adding means 16b.
Thereafter, the multiple multiplication means 16c performs 2 ² (2 ⁴ −1) c _{i + 6} calculation on i = 0, 1,..., 4 and sends the calculation result to the addition means 16d. Further, after the calculation in the adding means 16b and the multiplying means 16c, the adding means 16d obtains the remainder coefficient p ₀ = 2 ² (2 ⁴ −1) from the remainder coefficient storage means 15 (FIG. 1), and i = 0 , 1,..., 4 are subjected to an operation of c _i ← c _i +2 ² (2 ⁴ −1) c _{i + 6} , and the operation result is expressed as c _i ′ (i = 0, 1,... 4) is output (step S23). That is, the coefficient c _i ′ (i = 0, 1,..., 4) is the calculation result c _i (i = 0, 1,..., 4) in the adding means 16d. Note that the processing in the multiplication unit 16c may be performed before the calculation of the addition unit 16b as long as it is after the calculation in the addition unit 16a.

Since the calculation in the contraction means 16 is performed without carrying forward correction, each calculated coefficient c _i ′ (i = 0, 1,..., 5) is 27 (= w) bits or more. In some cases.
<Processing of Step S5 in Embodiment 1>
In the normalization process is performed 160 (= L) performs a contraction process bit length, collectively the carry correction between each term x ⁱ of the coefficient c _{i 'in} the case where the x = 2 ^27. Here, 160-bit length reduction processing refers to performing mod n operation on values exceeding n. In this embodiment, a part of the carry correction is performed before the 160-bit length reduction process, thereby simplifying the normalization process and speeding up the process.

FIG. 8 is a flowchart for explaining the processing in step S5 in the present embodiment. Hereinafter, the process of step S5 in the present embodiment will be specifically described with reference to this flowchart. Note that steps S31, S32 in the flowchart is a carry process from _{c 4} to _{c 5,} step S33~S36 is contraction processing 160-bit length, step S37 is _{c i +} 1 from the _{c i} ( This is a carry-up process to i = 0, 1,..., 4), and steps S38 to S40 are the last adjustment process.

の演算を行い、その演算結果ｃ_５’を縮約処理手段１７ｂａ、１７ｂｂに送る（ステップＳ３１）。
次に、繰り上がり補正手段１７ａｂにおいて、縮約手段１６から出力された係数ｃ_４’を取得してｃ_４’←ｃ_４’ ｍｏｄ ２^２７を演算し、その演算結果ｃ_４’を繰り上がり補正手段１７ｃに送る（ステップＳ３２）。 As illustrated in FIG. 8, first, the carry correction unit 17aa acquires the coefficients c ₄ ′ and c ₅ ′ output from the contraction unit 16,

The calculation result c ₅ ′ is sent to the contraction processing means 17ba and 17bb (step S31).
Next, the carry correction means 17ab obtains the coefficient c ₄ ′ output from the reduction means 16, calculates c ₄ ′ ← c ₄ ′ mod 2 ^27, and carries out the carry correction of the calculation result c ₄ ′. The data is sent to the means 17c (step S32).

の演算を行い、その演算結果ｚを縮約処理手段１７ｂｃ,１７ｂｄに送る（ステップＳ３３）。
次に、縮約処理手段１７ｂｂにおいて、繰り上がり補正手段１７ａａから送られた演算結果ｃ_５’を用い、ｃ_５’←ｃ_５’ ｍｏｄ ２^２５を演算し、その演算結果ｃ_５’を繰り上がり補正手段１７ｃに送る（ステップＳ３４）。 Next, in the contraction processing means 17ba,

The calculation result z is sent to the contraction processing means 17bc and 17bd (step S33).
Next, the reduction processing means 17bb uses the calculation result c ₅ 'sent from the carry correction means 17aa to calculate c ₅ ' ← c ₅ 'mod 2 ^25, and carries the calculation result c ₅ ' up. It sends to the correction means 17c (step S34).

ｃ_ｉ’←ｃ_ｉ’ ｍｏｄ ２^２７
（ｉ＝０,１,２,３,４）
の演算を行い、その演算結果ｃ_ｉ’（ｉ＝０,１,...,５）を減算手段１７ｄに送る（ステップＳ３７）。
次に、減算手段１７ｄにおいて、繰り上がり補正手段１７ｃから送られた演算結果ｃ_ｉ’（ｉ＝０,１,...,５）を取得し、これらによって

のように特定されるｃ’がｎ未満であるか否かを判断する（ステップＳ３８）。ここで、ｃ’＜ｎであった場合には、減算手段１７ｄにおいて、ｃを演算結果ｍとして出力し、処理を終了する（ステップＳ３９）。一方、ｃ’＜ｎでなかった場合には、ｍ←ｃ’‐ｎの演算を行い、その演算結果ｍを出力して処理を終了する（ステップＳ４０）。なお、ステップＳ３８〜Ｓ４０の処理は、ｃ’-nの演算を行い、ｃ’-n＜０であればｃ’を演算結果ｍとして出力し、ｃ’-n≧０であればｍ←ｃ’‐ｎとすることとしてもよい。 Further, the reduction processing unit 17bc obtains the coefficient c ₀ ′ output from the reduction unit 16 and z output from the reduction processing unit 17ba, and c ₀ ′ ← c ₀ ′ + (2 ⁴ −1). z is calculated, and the calculation result c ₀ ′ is sent to the carry correction means 17c (step S35).
Further, in the contraction processing unit 17bd, the coefficient c ₂ ′ output from the contraction unit 16 and z output from the contraction processing unit 17ba are obtained, and c ₂ ′ ← c ₂ ′ +2 ²⁵ z is calculated. The calculation result c ₂ ′ is sent to the carry correction means 17c (step S36).
Thereafter, in the carry correction means 17c, the coefficients c ₁ 'and c ₃ ' output from the reduction means 16, the coefficient c ₄ 'output from the carry correction means 17ab, and the reduction processing means 17bc and 17bd are output. Obtained coefficients c ₀ ′, c ₂ ′,

c _i '← c _i ' mod 2 ²⁷
(I = 0,1,2,3,4)
The calculation result c _i ′ (i = 0, 1,..., 5) is sent to the subtraction means 17d (step S37).
Next, the subtraction means 17d obtains the calculation result c _i ′ (i = 0, 1,..., 5) sent from the carry correction means 17c.

It is determined whether or not c ′ specified as follows is less than n (step S38). Here, if c ′ <n, the subtraction means 17d outputs c as the operation result m, and the process is terminated (step S39). On the other hand, if c ′ <n is not satisfied, the calculation m ← c′−n is performed, the calculation result m is output, and the process ends (step S40). In the processing of steps S38 to S40, c'-n is calculated. If c'-n <0, c 'is output as the calculation result m. If c'-n ≧ 0, m ← c. '-N may be used.

<Example 2>
Next, Example 2 in this embodiment will be described.
In this example, Q = 2, L is 160, W is 32, w is 27, u is 6, and modulus n is 2 ¹⁶⁰ -2 ³¹ -1 (= 2 ^160- 2 ^6.27-2 -1). In this _{^{case, E = 2, p 0 =}} 2 2, p 1 = 2 6, p h = 0 (h = 2,3,4,5), f (x) = x 6 -64x-4 (= x 6 -2 ⁶ x-2 ² ).
<Configuration of Example 2>
The overall configuration in Example 2 is as described above (FIG. 1). Hereinafter, only detailed configurations of the contracting unit 16 and the normalizing unit 17 in the second embodiment will be described.

FIG. 9 is a block diagram showing the configuration of the contracting means 16 in this embodiment, and FIG. 10 is a block diagram showing the configuration of the normalizing means 17 in this embodiment.
As shown in FIG. 9, the contracting means 16 of this embodiment includes multiple multiplying means 116a and 116c (corresponding to "first and second multiple multiplying means") and adding means 116b and 116d ("first first"). , The second adding means ”), and as shown in FIG. 10, the contracting means 17 of this embodiment includes carry correction means 117aa, 117ab, 117c and contraction processing means 117ba, 117bb. 117bc, 117bd.

を満たす係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく算出する。以下この演算を概念的に説明する。 <Process of Example 2>
The entire processing in the second embodiment is as described above (FIG. 4). The processing in step S2 is the same as that in the first embodiment. Hereinafter, only the details of the processing of steps S4 and S5 (FIG. 4) in the second embodiment will be described.
<Processing of Step S4 in Embodiment 2>
As described above, in this embodiment, since u = 6 and f (x) = x ⁶ -64x-4, the contracting means 16 of this embodiment is

A coefficient c _i ′ satisfying the above is calculated without performing carry correction between the terms x ⁱ . This calculation will be conceptually described below.

となるため、各項ｘ^ｉの係数ｃ_ｉは図１１の（ｂ）のようになる。なお、この図の「×４」や「×６４」とは、この「×４」や「×６４」と同一行（図１１における横方向の行）の係数ｃ_ｉを４倍や６４倍することを意味する。
そして、図１１の（ｂ）に示す各係数ｃ_ｉ（ｉ＝０,１,...,５）、４ｃ_ｉ（ｉ＝６,７,...,１０）及び６４ｃ_ｉ（ｉ＝６,７,...,１０）を、各項ｘ^ｉと同一列（図１１における縦方向の列）ごとに、桁上がり補正することなく加算した値が、ｃ’における各項ｘ^ｉの係数ｃ_ｉ’となる（図１１の（ｃ））。例えば、ｃ_０’＝ｃ_０＋４ｃ_６となる。 Figure 11 is a conceptual diagram for explaining the coefficient c _i of the remainder subject c expressed by equation (19), the relationship between the 'coefficients c _{i of'} c of formula (22). Here, x ⁱ (i = 0, 1,..., 10), c _i (i = 0, 1,..., 10), c _i ′ (i = 0, 1,...) In FIG. ., 5) has the same meaning as in FIG.
FIG. 11A shows the coefficients c _i (i = 0, 1,..., 10) of each term x ⁱ of the remainder object c input by the remainder object input means 14.
In equation (19) shown in FIG.

Therefore, the coefficient c _i of each term x ⁱ is as shown in FIG. Note that “× 4” and “× 64” in this figure _mean that the coefficient c _i of the same row (horizontal row in FIG. 11) as this “× 4” or “× 64” is multiplied by 4 or 64 times. Means that.
Then, each coefficient c _i (i = 0, 1,..., 5), 4c _i (i = 6, 7,..., 10) and 64c _i (i = 6) shown in FIG. , 7,..., 10) are added to each term x ⁱ in the same column (vertical column in FIG. 11) without carry correction, and the coefficient of each term x ⁱ in c ′ It becomes c _i '((c) of FIG. 11). For example, c ₀ ′ = c ₀ + 4c ₆ .

FIG. 12 is a flowchart for explaining the processing in step S4 in the present embodiment. Hereinafter, the process of step S4 in the present embodiment will be specifically described with reference to this flowchart.
As shown in FIG. 12, in this process, first, in the multiplication means 116a, the coefficient c _i (i = 6, 7, 8, 9, 10) inputted in the remainder target input means 14 and the multiplication coefficient storage means. multiplication coefficient stored in 15 _p 0 = ^{2 2} acquires, i = 0, 1, ..., against 4 ^performs calculation of the ^{2 2} c _{i + 6,} the operation result ^{2 2} c _{i + 6} The data is sent to the adding means 116b. In addition, in addition means 116b, coefficient c _i (i = 0, 1, 2, 3, 4) input in remainder target input means 14 and calculation in multiple multiplication means 116a sent from multiple multiplication means 116a. Result 2 ² c _{i + 6} is acquired, and c _i ← c _i +2 ² c _{i + 6} (i = 0, 1, 2, 3, 4) is calculated (step S51). The calculation result c _i (i = 1, 2, 3, 4) is sent to the adding means 116d, and the calculation result c ₀ is output as a coefficient c ₀ ′. That is, the coefficient c ₀ ′ is the calculation result c ₀ in the adding unit 116b.

After the calculation in the adding means 116b, the coefficient c _i (i = 1, 2, 3, 4, 5) input in the remainder target input means 14 and the multiplication coefficient storage means 15 are stored in the multiple multiplication means 116c. get the multiplication factor ^{_{p 1 = 2 6, i =}} 1,2, ..., for the 5 ^performs calculation of ² 6 c _{i + 5,} and sends the calculation result ² 6 c _{i + 5} to the adding means 116d . In addition, in addition means 116d, coefficient c ₅ input in remainder target input means 14, calculation result 2 ⁶ c _{i + 5} sent from multiple multiplication means 116c, and calculation result c _i sent from addition means 116b. (I = 1, 2, 3, 4) are obtained and used to calculate c _i ← c _i +2 ⁶ c _{i + 5} for i = 1, 2,..., 5 (step S52). ). The calculation result c _i (i = 1, 2,..., 5) is output as a coefficient c _i ′ (i = 1, 2,..., 5). That is, the coefficient c _i ′ (i = 1, 2,..., 5) is the calculation result c _i ′ (i = 1, 2,..., 5) in the adding unit 116d.

<Processing of Step S5 in Example 2>
In the normalization process is performed 160 (= L) performs a contraction process bit length, collectively the carry correction between each term x ⁱ of the coefficient c _{i 'in} the case where the x = 2 ^27. Also in this embodiment, a part of the carry correction is performed before the 160-bit length reduction process, thereby simplifying the normalization process and speeding up the process.
FIG. 13 is a flowchart for explaining the processing in step S5 in the present embodiment. Hereinafter, the process of step S5 in the present embodiment will be specifically described with reference to this flowchart. Note that steps S61, S62 in the flowchart is a carry process from _{c 4} to _{c 5,} step S63~S66 is contraction processing 160-bit length, step S67 is _{c i +} 1 from the _{c i} ( This is a carry-over process to i = 0, 1,..., 4), and steps S68 to S70 are the last adjustment process.

の演算を行い、その演算結果ｃ_５’を縮約処理手段１１７ｂａ、１１７ｂｂに送る（ステップＳ６１）。
次に、繰り上がり補正手段１１７ａｂにおいて、縮約手段１６から出力された係数ｃ_４’を取得してｃ_４’←ｃ_４’ ｍｏｄ ２^２７を演算し、その演算結果ｃ_４’を繰り上がり補正手段１１７ｃに送る（ステップＳ６２）。 As illustrated in FIG. 13, first, the carry correction unit 117aa acquires the coefficients c ₄ ′ and c ₅ ′ output from the contraction unit 16,

The calculation result c ₅ ′ is sent to the contraction processing means 117ba and 117bb (step S61).
Next, the carry correction means 117ab obtains the coefficient c ₄ ′ output from the contraction means 16, calculates c ₄ ′ ← c ₄ ′ mod 2 ^27, and carries out the carry correction of the calculation result c ₄ ′. The data is sent to the means 117c (step S62).

の演算を行い、その演算結果ｚを縮約処理手段１１７ｂｃ,１１７ｂｄに送る（ステップＳ６３）。
次に、縮約処理手段１１７ｂｂにおいて、繰り上がり補正手段１１７ａａから送られた演算結果ｃ_５’を用い、ｃ_５’←ｃ_５’ ｍｏｄ ２^２５を演算し、その演算結果ｃ_５’を繰り上がり補正手段１１７ｃに送る（ステップＳ６４）。
また、縮約処理手段１１７ｂｃにおいて、縮約手段１６から出力された係数ｃ_０’及び縮約処理手段１１７ｂａから出力されたｚを取得し、ｃ_０’←ｃ_０’＋ｚを演算し、その演算結果ｃ_０’を繰り上がり補正手段１１７ｃに送る（ステップＳ６５）。 Next, in the contraction processing means 117ba,

The calculation result z is sent to the contraction processing means 117bc and 117bd (step S63).
Next, the reduction processing unit 117bb uses the calculation result c ₅ ′ sent from the carry correction unit 117aa, calculates c ₅ ′ ← c ₅ ′ mod 2 ^25, and carries the calculation result c ₅ ′ up. It sends to the correction means 117c (step S64).
Further, the contraction processing means 117bc obtains the coefficient c ₀ ′ output from the contraction means 16 and z output from the contraction processing means 117ba, calculates c ₀ ′ ← c ₀ ′ + z, and calculates The result c ₀ ′ is sent to the carry correction means 117c (step S65).

ｃ_ｉ’←ｃ_ｉ’ ｍｏｄ ２^２７
（ｉ＝０,１,２,３,４）
の演算を行い、その演算結果ｃ_ｉ’（ｉ＝０,１,...,５）を減算手段１１７ｄに送る（ステップＳ６７）。 Further, the contraction processing unit 117bd obtains the coefficient c ₁ ′ output from the contraction unit 16 and z output from the contraction processing unit 117ba, and calculates c ₁ ′ ← c ₁ ′ +2 ⁴ z, The calculation result c ₁ ′ is sent to the carry correction means 117c (step S66).
Thereafter, in the carry correction unit 117c, the coefficients c ₂ ′ and c ₃ ′ output from the reduction unit 16, the coefficient c ₄ ′ output from the carry correction unit 117ab, and the coefficient output from the reduction processing unit 117bb. c ₅ ′, the coefficients c ₀ ′ and c ₁ ′ output from the reduction processing means 117 bc and 117 bd are acquired,

c _i '← c _i ' mod 2 ²⁷
(I = 0,1,2,3,4)
The calculation result c _i ′ (i = 0, 1,..., 5) is sent to the subtraction means 117d (step S67).

Next, in the subtraction unit 117d, the carry correction means operation result transmitted from _{117c c i '(i = 0,1} , ..., 5) acquires, c specified by these' is less than n It is determined whether or not there is (step S68). Here, if c ′ <n, the subtraction means 117d outputs c as the operation result m, and the process is terminated (step S69). On the other hand, if c ′ <n is not satisfied, the calculation m ← c′−n is performed, the calculation result m is output, and the process ends (step S70).
It should be noted that in performing each calculation in the first and second embodiments, the multiplication and truncation division related to the power of 2 is often performed by performing a left shift / right shift calculation.

The present invention is not limited to the above-described embodiment.
For example, the above-described calculation order is not limited to the above, but may be performed within the range where the results are not contradictory or may be performed simultaneously.
Further, the word length multiplication of a and b (step S2) may be performed at high speed by another method such as the Karatsuba method, the Toom-Cook method, or the FFT method instead of the textbook method described above. Normally, when performing multiple-length multiplication, the Karatsuba method is often not effective because the carry-up process becomes complicated with small values such as L = 160 and W = 32. However, in the present invention, the carry is collectively performed at the end, so the Karatsuba method is often effective even with L and W of this size.

Furthermore, of course, omit the initialization of _{c i} in step S11, the _a s _{b t} which has been added to 0 in step S13 described above as the initial value of _{c i,} the addition of a 0 in the step S13 It is good also as not performing a process.
In this embodiment, the multiplication result of a and b calculated by the multiplying unit 12 and the adding unit 13 is set as a residue target c and input to the residue target input unit 14. However, other values may be used as the remainder object c.
[Second Embodiment]
Next, a second embodiment of the present invention will be described.

This form is a form in which the terms are canceled and the amount of calculation is reduced by the Karatsuba process of multiplication and the reduction process using the pseudo Mersenne prime.
In this embodiment, Q = 2, L is 160, W is 32, w is 27, u is 6, and modulus n is 2 ¹⁶⁰ -2 ⁷⁹ -15 (= 2 ¹⁶⁰ -2 ^{3 · 27-2-} (2 ⁴ -1)). In this _{^{case, E = 2, p 0 =}} 2 2 (2 4 -1), p 3 = 1, p h = 0 (h = 1,2,4,5), f (x) = x 6 -x 3 −60 (= x ⁶ −x ³ −2 ² (2 ⁴ −1)).

と表現した場合におけるａｂｍｏｄ ｆ（ｘ）を計算する。
ここで、
Ａ_０＝ａ_２ｘ^２＋ａ_１ｘ＋ａ_０，
Ａ_１＝ａ_５ｘ^２＋ａ_４ｘ＋ａ_３，
Ｂ_０＝ｂ_２ｘ^２＋ｂ_１ｘ＋ｂ_０，
Ｂ_１＝ｂ_５ｘ^２＋ｂ_４ｘ＋ｂ_３，
Ｘ＝ｘ^３，
とおくと、
ａ＝Ａ_１Ｘ＋Ａ_０
ｂ＝Ｂ_１Ｘ＋Ｂ_０
ｆ（Ｘ）＝Ｘ^２‐Ｘ‐２^２（２^４‐１） …(25)
となる。そのため、
ａｂ＝（Ａ_１Ｘ＋Ａ_０）（Ｂ_１Ｘ＋Ｂ_０）
＝Ａ_１Ｂ_１Ｘ^２＋（（Ａ_１＋Ａ_０）（Ｂ_１＋Ｂ_０）‐Ａ_１Ｂ_１‐Ａ_０Ｂ_０）Ｘ＋Ａ_０Ｂ_０
となり、式（２５）より導かれる合同式

となる。ここで、第１式から第２式への変換において、第１式のＡ_１Ｂ_１Ｘ（下線部）の項が打ち消しあっている。これにより、演算数を削減できることが分かる。本形態では、この性質を利用し、縮約の処理の一部を乗算処理に組み込み、剰余乗算全体の演算数を低減させ高速化を図る。 <Principle>
In this form,

Abmod f (x) is calculated.
here,
A ₀ = a ₂ x ² + a ₁ x + a ₀ ,
A ₁ = a ₅ x ² + a ₄ x + a ₃ ,
B ₀ = b ₂ x ² + b ₁ x + b ₀ ,
B ₁ = b ₅ x ² + b ₄ x + b ₃ ,
X = x ³ ,
After all,
a = A ₁ X + A ₀
b = B ₁ X + B ₀
f (X) = X ² -X-2 ² (2 ⁴ -1) (25)
It becomes. for that reason,
ab = (A ₁ X + A ₀ ) (B ₁ X + B ₀ )
= A ₁ B ₁ X ² + ((A ₁ + A ₀ ) (B ₁ + B ₀ ) −A ₁ B ₁ −A ₀ B ₀ ) X + A ₀ B ₀
And the congruence derived from equation (25)

It becomes. Here, in the conversion from the first expression to the second expression, the term A ₁ B ₁ X (underlined portion) in the first expression cancels out. This shows that the number of operations can be reduced. In this embodiment, by utilizing this property, a part of the reduction process is incorporated into the multiplication process, and the number of operations in the entire remainder multiplication is reduced to increase the speed.

<Configuration>
FIG. 14 is a block diagram exemplifying a configuration of the surplus apparatus 200 according to this embodiment, which is realized by causing a known computer to execute a predetermined program.
As illustrated in FIG. 14, the remainder device 200 includes a multiplication target input unit 211, a contraction unit 212, and a normalization unit 213. Further, the contraction unit 212 includes a multiplication term calculation unit 212a, a multiplication term storage unit 212b, and a coefficient calculation unit 212c.
More specifically, the remainder apparatus 200 according to the present embodiment is realized by a multiplier that obtains a product of 32 bits of 64 bits and an adder that obtains a sum of 64 bits. Here, the adder can also perform subtraction, and the shift of a 64-bit value can be calculated efficiently. An example of such an environment is Intel® SSE2. Of course, in the case where 64-bit addition cannot be performed directly, there may be a replacement such as combining 64-bit addition and executing 64-bit addition.

を満たす係数ｃ_ｉ’を、各項ｘ^ｉ間の繰り上がり補正を行うことなく、以下のように算出する（縮約処理）。
すなわち、まず、乗算項算出手段２１２ａにおいて、乗算対象入力手段２１１から各係数ａ_ｓ及びｂ_ｔを取得し、これらを用いて、乗算項Ａ_０Ｂ_０を算出する（ステップＳ８２）。算出された乗算項Ａ_０Ｂ_０は乗算項格納手段２１２ｂに送られ、そこに格納される（ステップＳ８３）。 <Processing>
FIG. 15 is a flowchart for explaining the modular multiplication process in this embodiment. Hereinafter, the remainder multiplication process in this embodiment will be described with reference to this flowchart.
As illustrated in FIG. 15, first, in the multiplication target input unit 211, each coefficient a _s and b _t when the first multiplication target a and the second multiplication target b are expressed by Expressions (23) and (24). Is received (step S81).
The inputted coefficients a _s and b _t are sent to the contracting means 212, which uses these coefficients a _s and b _t ,

The coefficient c _i ′ satisfying the above is calculated as follows (contraction processing) without performing the carry correction between the terms x ⁱ .
That is, first, the multiplication term calculation unit 212a obtains the coefficients a _s and b _t from the multiplication target input unit 211, and uses them to calculate the multiplication term A ₀ B ₀ (step S82). The calculated multiplication term A ₀ B ₀ is sent to the multiplication term storage means 212b and stored therein (step S83).

Thereafter, the coefficient calculation means 212c obtains the coefficients a _s and b _t from the multiplication target input means 211, and further uses the multiplication term A ₀ B ₀ stored in the multiplication term storage means 212b, and c = ((A ₁ + A ₀ ) (B ₁ + B ₀ ) −A ₀ B ₀ ) X + A ₀ B ₀ +2 ² (2 ⁴ −1) A ₁ B ₁
The coefficient c _i ′ for the term x ⁱ of c is calculated (step S85).
Each calculated coefficient c _i ′ is sent to the normalizing means 213, and the normalizing means 213 collectively performs carry correction between the terms of this coefficient (step S85).
Needless to say, the present invention is not limited to the above-described embodiment, and can be appropriately changed without departing from the spirit of the present invention. In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary.

Further, when the configuration in each of the above-described embodiments is realized by a computer, the processing contents of the functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program on the computer.
The program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory. Specifically, for example, the magnetic recording device may be a hard disk device or a flexible Discs, magnetic tapes, etc. as optical disks, DVD (Digital Versatile Disc), DVD-RAM (Random Access Memory), CD-ROM (Compact Disc Read Only Memory), CD-R (Recordable) / RW (ReWritable), etc. As the magneto-optical recording medium, MO (Magneto-Optical disc) or the like can be used, and as the semiconductor memory, EEP-ROM (Electronically Erasable and Programmable-Read Only Memory) or the like can be used.

The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.
A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

  The industrial application field of the present invention includes, for example, public key cryptography based on the difficulty of the discrete logarithm problem and multiple-precision modular multiplication in electronic signatures. By using the present invention for these, processing such as public key cryptography can be speeded up.

The block diagram which illustrated the whole structure of the remainder apparatus in 1st Embodiment. FIG. 3 is a block diagram showing a configuration of contraction means in the first embodiment. FIG. 3 is a block diagram showing a configuration of normalization means in the first embodiment. The flowchart for demonstrating the whole process of the remainder apparatus in 1st Embodiment. 4 is a flowchart for explaining the process of step S2 of FIG. 4 in the first embodiment. Conceptual diagram illustrating the relationship between the 'coefficients c _{i of'} coefficients c _i and c of the remainder subject c in Example 1. 7 is a flowchart for explaining a process of step S4 in the first embodiment. 6 is a flowchart for explaining a process of step S5 in the first embodiment. FIG. 9 is a block diagram showing a configuration of contraction means in the second embodiment. FIG. 6 is a block diagram showing a configuration of normalization means in the second embodiment. Conceptual diagram illustrating the relationship between the 'coefficients c _{i of'} coefficients c _i and c of the remainder subject c in Example 2. 9 is a flowchart for explaining a process of step S4 in the second embodiment. 9 is a flowchart for explaining a process of step S5 in the second embodiment. The block diagram which illustrated the composition of the remainder device in a 2nd embodiment. The flowchart for demonstrating the remainder multiplication process in 2nd Embodiment.

Explanation of symbols

10,200 residue device 11,211 multiplication object input means 12 multiplication means 13 addition means 14 remainder object input means 15 multiplication coefficient storage means 16,212 contraction means 17,213 normalization means

Claims (9)

c mod n is a residue device that performs a residue operation,

Remainder target input means for receiving input of each coefficient c _i ;
The value of mod n is L bits, the number of bits of a word as a processing unit as viewed from software is w, u is the smallest integer greater than or equal to L / w, Q is an integer greater than or equal to 2, and E = uw−L ,

Multiplication coefficient storage means for storing
Using said multiplication factor _{p h} and the coefficient _{c i,}

Contraction means for calculating each coefficient c _i ′ satisfying without performing carry-over correction between the terms x ⁱ ;
After calculating all the coefficients c _i ′, normalization means for collectively performing carry correction between the terms x ⁱ of the coefficient c _i ′ when x = Q ^w
A surplus device characterized by comprising: The surplus device according to claim 1,
The modulus n is
The number of bits of each operation result in the contraction means is a value that is less than the number of bits that can be handled by hardware at one time.
A surplus device characterized by that. The surplus device according to claim 1,
L is 160;
U is 6;
The modulus n is 2 ¹⁶⁰ -2 ⁷⁹ -15,
The contracting means includes
a first adding means for calculating c _i ← c _i + c _{i + 3} for i = 6, 7;
A second adding means for calculating c _i ← c _i + c _{i + 3} for i = 3, 4, 5 after the calculation in the first adding means;
After the calculation in the first addition means, multiple multiplication means for calculating 2 ² (2 ⁴ −1) c _{i + 6} for i = 0, 1,..., 4;
After the calculations in the second adding means and the multiple multiplying means, the calculation of c _i ← c _i +2 ² (2 ⁴ −1) c _{i + 6} is performed for i = 0, 1,. A third adding means,
The coefficient c _i ′ (i = 0, 1,..., 4) is
A calculation result c _i (i = 0, 1,..., 4) in the third adding means;
The coefficient c ₅ ′ is
The calculation result c ₅ in the second addition means.
A surplus device characterized by that. The surplus device according to claim 1,
L is 160;
U is 6;
The modulus n is 2 ¹⁶⁰ -2 ³¹ -1;
The contracting means includes
first multiplicative means for performing 2 ² c _{i + 6} operations for i = 0, 1,..., 4;
First addition means for performing a calculation of c _i ← c _i +2 ² c _{i + 6} using the calculation result in the first multiple multiplication means;
Second arithmetic means for calculating 2 ⁶ c _{i + 5} for i = 1, 2,..., 5 after the operation in the first adding means;
Second addition means for performing a calculation of c _i ← c _i +2 ⁶ c _{i + 5} for i = 1, 2,..., 5 using the calculation result in the second multiple multiplication means. Have
The coefficient c ₀ ′ is
A calculation result c ₀ in the first adding means;
The coefficient c _i ′ (i = 1, 2,..., 5) is
It is the calculation result c _i ′ (i = 1, 2,..., 5) in the second adding means.
A surplus device characterized by that. The surplus device according to any one of claims 1 to 4,

A multiplication target input means for receiving inputs of the coefficients a _s and b _t ;
Multiplication means for calculating a _s b _t for all integers s, t with 0 ≦ s, t ≦ u−1;
Using the calculation result in the multiplication means, c _{s + t} ← c _{s + t} + a _s b _t is applied to all integers s, t with 0 ≦ s, t ≦ u−1 without performing carry correction between the terms. A fourth addition means for performing a calculation,
Each coefficient c _i of the remainder object c is
A final calculation result c _{s + t} in the fourth addition means;
A surplus device characterized by that. a remainder device for calculating ab mod n,
The value of mod n is 160 bits, n = 2 ¹⁶⁰ -2 ⁷⁹ -15, and the minimum integer of 160 / w or more is 6 when the number of bits of a word as a processing unit viewed from software is w. Yes,

A multiplication target input means for receiving inputs of the coefficients a _s and b _t ;
When f (x) = x ⁶ −x ³ −2 ² (2 ⁴ −1),

Contraction means for calculating a coefficient c _i ′ satisfying the above without performing a carry-over correction between the terms x ⁱ ;
After calculating all the coefficients c _i ′, normalization means for collectively performing carry correction between the terms x ⁱ of the coefficient c _i ′ when x = Q ^w
Have
The contracting means includes
A ₀ = a ₂ x ² + a ₁ x + a ₀ ,
A ₁ = a ₅ x ² + a ₄ x + a ₃ ,
B ₀ = b ₂ x ² + b ₁ x + b ₀ ,
B ₁ = b ₅ x ² + b ₄ x + b ₃ ,
X = x ³ ,
Multiplication term calculation means for calculating the multiplication term A ₀ B ₀ using the coefficients a _s and b _t in the case of
Multiplication term storage means for storing the calculated multiplication terms A ₀ B ₀ ;
Using the coefficients a _s and b _t and the multiplication term A ₀ B ₀ stored in the multiplication term storage means,
c = ((A ₁ + A ₀ ) (B ₁ + B ₀ ) −A ₀ B ₀ ) X + A ₀ B ₀ +2 ² (2 ⁴ −1) A ₁ B ₁
Coefficient calculation means for calculating the coefficient c _i ′ for the term x ⁱ of the c,
Having
A surplus device characterized by that. c mod n is a residue method for performing a residue operation,
The value of mod n is L bits, the number of bits of a word as a processing unit as viewed from software is w, u is the smallest integer greater than or equal to L / w, Q is an integer greater than or equal to 2, and E = uw−L ,

Is stored in the multiplication coefficient storage means,
In the remainder object input means,

Accepts input of each coefficient c _i ,
In contraction means, using said multiplication factor p _h and the coefficient c _i,

Each coefficient c _i ′ satisfying the above is calculated without performing carry correction between the terms x ⁱ
After the calculation of all the coefficients c _i ′, the normalization means collectively performs the carry correction between the terms x ⁱ of the coefficient c _i ′ when x = Q ^w .
A remainder method characterized by that.   The program for functioning a computer as a surplus apparatus in any one of Claim 1 to 6.   A computer-readable recording medium storing the program according to claim 8.

Images