JP5403982B2 - COMPUTER DEVICE, METHOD, AND PROGRAM - Google Patents

Description

  The present invention relates to a calculation apparatus, method, and program for performing a power calculation in a finite field expansion field.

  Conventionally, there is a method using encryption in order to protect information flowing through a communication path. As a method using encryption, there is a common key encryption method in which a key is shared in advance with a communication partner. This method requires a great deal of time for key sharing and management. On the other hand, in the public key cryptosystem, secure communication can be realized without sharing a key in advance. For this reason, it is widely used as a basic technology for network security. In addition, with the diversification of information terminals, various schemes and protocols using public keys have been used even in small devices by devising methods and implementations. However, the public key cryptosystem has a higher cost for the calculation process than the common key cryptosystem, and a higher speed than the calculation process is required. Various speedups have been made for the calculation methods used in the public key cryptosystem. As a method applicable to a high-speed power calculation method, there is a cyclic window method (see Patent Document 1 and Non-Patent Document 1).

  Here, the circulation window method will be described. The cyclic window method is a calculation method for obtaining a scalar k (εZ) times a point P on an elliptic curve E (GF (p ^ m)). Unless otherwise specified, the symbols used in paragraphs 0003 to 0010 are described in conformity with Patent Document 1, and therefore have different meanings from symbols used in other portions.

[Explanation of terms]
φ is a Frobenius map and is expressed as φ (x, y) = (x ^ p, y ^ p). For a point P on the elliptic curve, φ ^ i (P) can be calculated at high speed using the Frobenius map.

For b which is a non-negative integer, the vector v _b is represented by B + 2 elements as follows, and each element v _{b, h} is v _{b, 0} = 1 when b = 0 and b ≠ 0. v _{b, h} = ([b / 3 ^ (h-1) +1] mod3) -1.
v _b = (v _{b, 0} , v _{b, 1} ,..., v _{b, B} , v _{b, B + 1} )
Here, B = [log ₃ b]. Note that [a] is obtained by discarding the decimal part of a. W _H (v _b ) represents the number of non-zero elements of the vector v _b ,
w _H (v _b ) = Σ _{h = 0} ^{B + 1} | v _{b, h} |
It is.

Step1:
[Create table with appropriate length w]
Several b are selected, and for each b, Qb = Σ _{i = 0} ^B−1 v _{b, i} φ ^ i (P)
Is calculated and stored as a table.

Step 2:
[P-adic and d-ary expansion + initialization]
k is expanded as follows to obtain c _{i, j} (ε {−1, 0, 1}), and R = O and j = n′−1 are set. However, O represents the unit element of E (GF (p ^ m)).
k = Σ _{i = 0} ^n′−1 Σ _{j = 0} ^m′−1 c _{i, j} d ^ j φ ^ i

Step3:
[matching]
Among the selected _b, w H _(v b) for all the non-zero elements to _c i + h of _{v b} in descending order, j = (- 1) ^ e v b, a _h b, e, i And execute c _{i + h, j} = c _{i + h, j} − (− 1) ^ e v _{b, h} for each h of 0 ≦ h ≦ B + 1, and R = R + (− 1) ^ ev v _{, h} The process of φ ^ i is executed while changing b until c _{i, j} of 0 ≦ i <m ′ is all 0. However, e = {0, 1}.

Step 4:
[A & D]
j = j−1, R = R × d,
Step 3 and Step 4 are repeated until j = 0.

Japanese Patent No. 3604126 Application of the Cyclic Window Method to Elliptic Curve Cryptography Kazutaro Aoki, Tetsuro Kobayashi, Literary Hoshino September 2000 ISEC2000-75 p.147-p.154

However, the methods described in Patent Document 1 and Non-Patent Document 1 have the following problems.
(1) Since it is devised assuming scalar multiplication of points on an elliptic curve, it cannot be applied as it is to power multiplication of a finite field. (2) Although it is advantageous in terms of table creation cost, it reduces the number of tables. Therefore, it is necessary to repeatedly search for each j. (3) Since an operation using an inverse element uses a special point on an elliptic curve, it can be calculated at high speed. For (2), the table search cost can be small while the expansion order m is small. However, when the expansion order m is large, the search cost cannot be ignored. For (3), the point P on the elliptic curve that is “(1 + φ + φ ^ 2 +... Φ ^ (m−1)) (P) = O ′ (m is the expansion order) is used. The same is not true for any element of. For this reason, the same method as that for realizing scalar multiplication by adding and subtracting a value obtained by multiplying the table Qb by “−1” cannot be performed. In addition, all the tables including negative values may be held. However, as the expansion order m increases, the table size suitable for it increases, so the number of tables to be stored explosively (2 ^ B To 3 ^ B (B is the table size).

  The present invention has been made in view of the above, and an object of the present invention is to provide a calculation device, method, and program capable of reducing the amount of power calculation to be performed in a finite field expansion field.

The present invention solves the above-described problem, and the present invention is a computing device that calculates the power of an element of a finite field, and the element a of the finite field (a∈Fp ^ m, m is a natural number, and `^ 'represents a power) Is a computing device for calculating a power of n and q = Σ _{i = 0} ^w−1 q _i × s ^ i (0 ≦ q _i <s)
And the s-adic expansion unit for determining each coefficient _{q i} made, each coefficient _{q i} expand r adic ^{_{q i = Σ j = 0 h}} -1 q ij × r ^ j (0 <r <s, 0 ≦ q _ij <r)
And formed by using the r-adic expansion unit for obtaining the coefficients q _ij, each coefficient q _ij, should a power calculation unit for calculating the original power of the exponent q, wherein r adic expansion unit after s Decimal expansion For the coefficients q _y and q _{(y + 1)} (0 ≦ y ≦ w−2), a part s times the value of the coefficient q _{(y + 1)} is added to the coefficient q _y to obtain each coefficient q _y , q _{(y + 1)} Is expanded in r notation .

In addition, the present invention includes an s-adic expansion unit, an r-adic expansion unit, and a power calculation unit, and a finite field element a (aεFp ^ m, m is a natural number, and '^' represents a power). In the calculation method executed by a computing device that calculates a power, the s-adic expansion unit expands a power exponent q for each s by s-adic and q = Σ _{i = 0} ^w−1 q _i × s ^ i (0 ≦ q _i <s)
Each coefficient q _i is obtained, and the r-adic expansion unit expands each coefficient q _i into an r-adic number to obtain q _i = Σ _{j = 0} ^h−1 q _ij × r ^ j (0 <r <s, − r <q _ij <r)
Obtains the coefficients q _ij to be, the power calculation unit, by using the coefficients q _ij, the original power of the exponent q is computed should the r-adic expansion, coefficient after s-adic expansion q _y, q for _{(y + 1) (0 ≦} y ≦ w-2), added s times of some of the values of the coefficients _{q (y + 1)} to the coefficient _{q y,} that each coefficient _{q y, q} and _{(y + 1)} expand r adic It is characterized by.

  According to the present invention, it is possible to reduce the amount of power calculation to be performed in a finite field expansion field.

  Exemplary embodiments of a computing device, a method, and a program according to the present invention will be described below in detail with reference to the accompanying drawings.

[First embodiment]
(1) Configuration First, the hardware configuration of the computing device of this embodiment will be described. The computing device of this embodiment includes a control device such as a CPU (Central Processing Unit) that controls the entire device, and a storage such as a ROM (Read Only Memory) and a RAM (Random Access Memory) that store various data and various programs. Device, an external storage device such as an HDD (Hard Disk Drive) or a CD (Compact Disk) drive device for storing various data and various programs, and a bus for connecting them, and a hardware using an ordinary computer The hardware configuration. Also, the computing device includes a display device for displaying information, an input device such as a keyboard and a mouse for accepting user instruction input, and a communication I / F (interface) for controlling communication with an external device by wire or wirelessly. Each is connected. In such a hardware configuration, various functions realized by executing various programs stored in a storage device or an external storage device by a CPU included in the calculation device will be described. FIG. 1 is a diagram illustrating a functional configuration of a computing device. The calculation apparatus includes a p-adic expansion unit 51, an r-adic expansion unit 52, a calculated value storage table 53, a first calculation unit 54, and a second calculation unit 55. Each of these units is generated on a storage device such as a RAM when the CPU program is executed. The calculated value storage table 53 is stored in an external storage device such as an HDD.

First, the calculation principle used in this embodiment will be described. The power b ^ p of the element b, which is an element of the extension field Fp ^ m of the finite field Fp and expressed by the following Expression 1, is expressed by Expression 2 using the Frobenius map.
_{b = b 0 + b 1 ×} z + b 2 × z ^ 2 + b 3 z ^ 3 + ··· + b (m-1) × z ^ {m-1} ··· (1)
_{b ^ p = b 0 + b} 1 z ^ p + b 2 z ^ {2p} + ··· + b (m-1) z ^ {p (m-1)} ··· (2)
By dividing this by the binomial modulo polynomial g _m expressed by the following Equation 3, b ^ p can be easily obtained. In this case, z ^ m may be sequentially replaced with “−α”.
g _m (z) = z ^ {m} + α (3)

For example, consider an algebraic torus element as a power element. Since the element T6 (Fp ^ m) of the algebraic torus is a subgroup of Fp ^ m ^ 6, it is an element of an extension field of a finite field. Note that in the case of an algebraic torus element, the original element b _n of Fp does not become b _n even _if it is raised to the power of p, so it must be set as b _n ^ p. And about such an element, it becomes possible to perform the exponentiation calculation at high speed using the above-mentioned method.

Here, it is assumed that the computing device performs a to the qth power with a (aεFp ^ m) as an element of an extension field of a finite field. The p-adic expansion unit 51 expands the exponent q to a p-adic number. A power exponent q expanded by p-adic numbers is expressed by the following Equation 4.
_{q = q 0 + q 1 ×} p + q 2 × p ^ 2 + ··· + q (w-1) × p ^ {w-1} ··· (4)
Note that q _i (0 ≦ i ≦ w−1) is a coefficient, and “q _i <p”.

The r-adic expansion unit 52 expands the coefficient q _i in r-adic. When 'r = 2', the coefficient q _i expanded in r-adic is expressed by the following Equation 5.
q _i = q _i0 + q _i1 × 2 + q _i2 × 2 ^ 2 +... + q _{i (h−1)} × 2 ^ {h−1} (5)

At this time, q _ij ε {0, 1} (0 ≦ i ≦ w−1, 0 ≦ j ≦ h−1). Here, for simplicity, it is assumed that “w = d × n” (w is a multiple of d). d will be described later in the description of the calculated value storage table 53. If w is not a multiple of d, padding may be performed as 'q _w = 0, q _{(w + 1)} = 0, ...'.

FIG. 2 is a diagram showing a two-dimensional table format for visually expressing a ^ q, which is the qth power of the element a. In the figure, for each vertical column, a value obtained by multiplying the power of 2 shown in each horizontal row represents the coefficient q _i . On the other hand, for each horizontal row, a value obtained by multiplying the power value of p indicated in each vertical column is S _j . S _j is expressed by Equation 6 below.
_{S j = a ^ {q 0j} + q 1j × p + q 2j × p ^ 2 + ··· + q (w-1) j × p ^ {w-1}} ··· (6)

The first calculator 54 refers to the calculated value storage table 53 and calculates S _j for each j. The calculated value storage table 53 is used for calculating the value of S _j , and is a combination of d bits (b ₀ , b ₁ , b ₂ ,..., B when r = 2). _(D-1) ) The values of T (k) represented by the following expression 7 are stored for all.
_{T (k) = a ^ {} b 0 + b 1 × p + b 2 × p ^ 2 + b 3 × p ^ 3 + ··· + b (d-1) × p ^ {d-1}} ··· (7)

  Hereinafter, d is referred to as a window width. Further, kε {0,1} ^ d, and k represents an ordered combination of d bits in binary notation. An ordered combination of bits is called a bit string.

The value of T (k) is calculated (pre-calculated) in advance and stored in the calculated value storage table 53. When a power of a ^ p or a ^ {p ^ 2} is calculated in the prior calculation of T (k), it can be easily calculated by using the Frobenius map. FIG. 3 is a diagram visually showing the calculated value storage table 53 when “d = 4”. In the figure, it is shown that T (k) is calculated for each of all combinations of (b ₀ , b ₁ , b ₂ , b ₃ ) for p ^ _{0 to} p ^ 3. Has been. In this calculated value storage table 53, only the value of T (k) corresponding to the combination of p ^ 0 to p ^ 3 is stored, but it corresponds to the combination of d bits after p ^ 4. The value to be calculated can be easily calculated using the value of T (k). For example, each value corresponding to the combination of p ^ 4 to p ^ 7 is obtained by multiplying T (k) corresponding to the combination of p ^ 0 to p ^ 3 by p ^ 4, respectively. , P ^ 4 can be easily calculated using the Frobenius map. Therefore, it is possible to apply T (k) a plurality of times to all S _j calculations, which greatly contributes to speeding up the calculation.

The first calculation unit 54 calculates S _j for each j using the value of T (k). As a result, S _j represented by Expression 6 is represented by Expression 8 below.
_{S j = T (q (d} -1) j q (d-2) j ··· q 0j) × T (q (2d-1) j q (2d-2) j ··· q dj) ^ { p ^ d} * T (q _(3d-1) jq _{(3d-2) j} ... q _{(2d) j} ) ^ {p ^ (2d)} * ... * T (q _{(nd-1 ) J} q _{(nd-2) j} ... q _{((n-1) d) j} ) ^ {p ^ {d (n-1)}} (8)

When the first calculation unit 54 calculates the S _j for all j, the second calculating unit 55 uses the respective S _j, the equation 9 below, computes the multiplication q of a.
S = a ^ q = (( (((S (h-1)) ^ 2 × S (h-2)) ^ 2 × S (h-3)) ^ 2 × ···) ^ 2 × S 1 ) ^ 2 × S ₀ (9)

(2) Operation Next, a procedure of power calculation processing to be performed by the calculation apparatus according to the present embodiment will be described with reference to FIG. Here, it is assumed that the computing device performs the qth power of the element a (aεFp ^ m) of the finite field expansion field. The computing device expands the power exponent q into p-adic numbers (step S1). FIG. 5 is a flowchart showing a detailed procedure of p-adic number expansion processing. First, the computing device sets 'i = 0' and 't ₀ = q' (step S10), obtains the coefficient q _i as 'q _i = t _i mod p', and sets 't _{i + 1} = t _i / p'. Obtained (step S11). Next, the computing device increments i to 'i = i + 1' (step S12), and then determines whether 't _i = 0' (step S13). If the determination result of step S13 is negative, the process proceeds to step S11. If the determination result of step S13 is positive, the process ends. As described above, the coefficient q _i satisfying “q _i <p” is obtained for all i (0 ≦ i ≦ w−1), and the exponent q is expressed by p as expressed by the above-described equation 4. Expands to a decimal number.

Returning to FIG. 4, the computing device then expands the coefficient q _i in r-adic. (Step S2). FIG. 6 is a flowchart showing a detailed procedure of r-adic expansion processing. First, the computing device obtains the coefficient q _i as “q _ij = t _i mod r” by setting “j = 0” and “t ₀ = q _i ” (step S20), and “t _{i + 1} = t _i / r”. Is obtained (step S21). Next, the computing device increments j to “j = j + 1” (step S22), and then determines whether or not “t _j = 0” (step S23). If the determination result of step S23 is negative, the process proceeds to step S21. If the determination result of step S23 is positive, the process ends. As described above, the coefficient _{q i, q ij ∈ {0,1} , ···, r-1} obtained for all j the coefficients _{q ij} is (0 ≦ j ≦ h-1 ). When 'r = 2', the coefficient q _i expanded in r notation is expressed by the above-described Expression 5. The calculation device obtains the coefficient q _ij for the coefficient q _i for all i (0 ≦ i ≦ w−1).

Returning to FIG. 4, the calculation device then refers to the calculated value storage table 53 and obtains S _j obtained by calculating the product for the same j in the coefficient q _ij (step S _< b> 3). FIG. 7 is a flowchart showing a detailed procedure of a process for calculating S _j . First, the computing device sets S _j as a unit element to “S _j = 1”, “l = 0” (step S30), and “v = d−1” (step S31). Next, the computing device sets “k = 0” (step S32), and obtains “k = k + q _{(1 × d + v) j} × 2 ^ v” as a new value of k (step S33). d is the window width described above. Next, the computing device sets “v = v−1” (step S34), and determines whether “v = 0” (step S35). If the determination result of step S35 is negative, the process proceeds to step S33. When the determination result of step S35 is affirmative, the calculation device refers to the value of T (k) stored in the calculation value storage table 53 using the value of k obtained in step S33, and performs the calculation of S _j Is obtained as 'S _j = S _j × T (k) ^ (l × d)' (step S36). Then, the computing device increments l to “l = 1 + 1” (step S37), and determines whether “l = n” (step S38). 'n = w / d'. If the determination result in step S38 is negative, the process proceeds to step S31. If the determination result in step S38 is positive, the process ends. As described above, the calculation apparatus obtains the value of each T (k) with reference to the calculation value storage table 53, and performs the multiplication and power calculation using T (k), thereby obtaining S _j . .

FIG. 8 is a diagram schematically showing each S _j obtained using T (k) stored in the calculated value storage table 53 shown in FIG. 3 in the table of FIG. 2 showing a ^ q. It is. As shown in the figure, for each j, the product of the combinations of exponents to be consecutive with respect to p by 4 is calculated using T (k).

Then, when S _j is calculated for all j, the processing returns to FIG. 4 and the calculation device calculates a to the qth power by the above-described equation 9 using each S _j (step S4). FIG. 9 is a flowchart showing a detailed procedure of a process of calculating S that is a to the power of q. The computing device first obtains the minimum value of v such that “p <r ^ v” (step S40), and then sets “S = S _v−1 ” and “v = v−1” (step S41). ). Further, the computing device sets “v = v−1” (step S42) and sets “S = S ^ {r} × S _v ” (step S43). Next, the computing device determines whether or not “v> 0” (step S44). If the determination result is affirmative, the calculation device proceeds to step S42. If the determination result of step S44 is negative, the computing device ends the process. As described above, the calculation apparatus performs power calculation and multiplication using S _j obtained in step S3 to obtain a to the qth power.

Next, a procedure of processing in which the calculation device pre-calculates the value of T (k) stored in the calculated value storage table 53 before performing the above power calculation will be described with reference to FIG. First, the computing device sets “T (0) = 1” as a unit element, sets “T (1) = a” (step S50), and sets “k = 10 ₂ ” (step S51). “10 ₂ ” is a bit string indicating an ordered combination of “1” and “0” in binary notation. Next, the computing device determines whether or not “k mod 2 = 1” (step S52). If the determination result in step S52 is negative, the computing device sets 'T (k) = T (k / 2) ^ p' (step S53), and if the determination result in step S52 is positive, T (k) = T ((k−1) / 2) ^ p × a ′ is set (step S54).

Here, the calculation device obtains T (k) using the Frobenius map. For example, in the case of “d = 4”, the following expressions 10 to 11 hold.
T (110 ₂ ) = T (1100 ₂ ) ^ p (10)
T (1110 ₂ ) = T (110 ₂ ) × a (11)
For this reason, it is not necessary to obtain all the values of T (k) only by multiplication. Accordingly, in step S53 or step S54, the computing device obtains a new value of T (k) using the values of T (k / 2) and T ((k-1) / 2) that have already been obtained. Thus, the value of each T (k) can be obtained at high speed.

  Thereafter, in either case, the process proceeds to step S55, where the computing device sets ‘k = k + 1’ (step S55), and then determines whether ‘k <2 ^ d’ (step S56). When the determination result of step S56 is affirmative, the process proceeds to step S52, and when the determination result of step S56 is negative, the computing device ends the process. As described above, the calculation apparatus obtains T (k) for all combinations of d bits with respect to the window width d and stores them in the calculated value storage table 53.

As described above, the p-th power of an extension field of a finite field in a special case can be obtained by calculating the Frobenius map at high speed, expanding the power exponent q in p-adic with characteristic p, An r-adic expansion is performed for each coefficient q _i . Then, it is possible to reduce the amount of calculation by pre-calculating and storing a power calculation value for all combinations of d bits and calculating S _j using the stored value. Such a power calculation method is suitable, for example, for public key cryptography.

[Second Embodiment]
Next, a second embodiment of the computing device will be described. In addition, about the part which is common in the above-mentioned 1st Embodiment, it demonstrates using the same code | symbol or abbreviate | omits description.

(1) Configuration The configurations of the p-adic expansion unit 51 and the r-adic expansion unit 52 included in the computing device are the same as those in the first embodiment. The method of creating the calculated value storage table 53 and the configuration of the first calculation unit 54 are different from those in the first embodiment. In the first embodiment described above, the calculated value storage table 53 is created in advance by calculating the value of T (k) in advance and storing it in the calculated value storage table 53. The first calculating unit 54 S _j was calculated with reference to the calculated value storage table 53. In the present embodiment, the value of T (k) is not calculated in advance, but the value of T (k) is calculated at any time during the process in which the first calculation unit 54 calculates S _j. S _j is calculated for each j while creating the calculated value storage table 53 by storing it in the value storage table 53 as needed. In order to distinguish from T (k) according to the first embodiment described above, hereinafter, it is denoted as T ′ (k).

(2) Operation Next, a procedure of power calculation processing performed by the calculation apparatus according to the present embodiment will be described with reference to FIG. Steps S1 and S2 are the same as those in the first embodiment. In step S3 ′, the calculation device calculates S _j for each j while creating the calculated value storage table 53. FIG. 12 is a flowchart showing a detailed procedure of the process in step S3 ′. Here, b is a bit string of the maximum length w, and lower bits are stored in b sequentially from the left, and 'b = b || {0}' (|| is a concatenation of bits). . First, the computing device sets “T” (1) = a ”,“ t = 0 ”, and“ S _j = 1 ”(step S60). Next, the computing device determines whether or not “q _tj = 1” (step S61). If the determination result is affirmative (step S61: YES), “b = 1” and “s = T '(step S62). Then, the computing device sets “t = t + 1” (step S63), and then determines whether or not “t <w” (step S64). If the determination result is affirmative (step S64: YES), the computing device determines whether or not “q _tj = 1” (step S65). If the determination result is affirmative (step S65: YES), the calculation apparatus determines whether T ′ (b || 1) is stored in the calculated value storage table 53 (step S66). When the determination result is negative (step S66: NO), the calculation device calculates T ′ (b || 1) by the following expression 12 and stores it in the calculated value storage table 53 (step) S67).
T ′ (b || 1) = T ′ (b) × a ^ {p ^ (ts)} (12)
Next, the calculation device calculates S _j by the following equation 13 (step S68).
S _j = S _j × T ′ (b || 1) ^ {p ^ s} (13)
The computing device increments t to “t = t + 1” (step S71), and then determines whether or not “t <w” (step S72). If the determination result is affirmative, the process returns to step S61. If the determination result of step S72 is negative, the process ends.

If the determination result in step S66 is affirmative, the computing device concatenates the bit q _tj to b by setting 'b = b || q _tj ' (step S70), and proceeds to step S63 described above. That is, when 'q _tj = 0', the process proceeds to the next bit string to be processed.

When the determination result of step S64 is negative, the calculation apparatus calculates S _j by the following expression 13 (step S69) and ends the process.
S _j = S _j × T ′ (b || 1) ^ {p ^ s} (13)

As described above, when the calculation device calculates S _j for all j in step S3 ′, the calculation device calculates a to the qth power in the same manner as in the first embodiment described above in step S4.

As described above, the value of T ′ (k) obtained in the process of calculating each S _j is reused and stored in the new T ′ (k) calculated value storage table 53 as needed, so that the prior calculation is performed. It is possible to calculate a to the qth power at high speed.

[Third embodiment]
Next, a third embodiment of the computing device will be described. In addition, about the part which is common in the above-mentioned 1st Embodiment or 2nd Embodiment, it demonstrates using the same code | symbol or abbreviate | omits description.

In the present embodiment, the same concept as the sliding window method is used. In this case, a combination of d bits is selected so that the leading value does not become “0”. d is the window width described above. This is because when the value of the coefficient q _ij in the power exponent is “0”, the result of multiplication with the coefficient is “0”, so there is no need for multiplication. For this reason, when “0” is at the head, this value is skipped and a combination of bits with the head at “1” is selected, whereby the number n using T (k) when calculating S _j Can be made smaller than 'w / d', and the amount of calculation can be further reduced.

The procedure of the whole power calculation process according to the present embodiment is as shown in FIG. 4 and is the same as that of the first embodiment. In the present embodiment, the detailed procedure of the process of calculating S _j in step S3 is different from that of the first embodiment. FIG. 13 is a flowchart showing a detailed procedure of the process of calculating S _j in the present embodiment. First, the computing device sets “S _j = 1” and “l = 0” using S _j as a unit element (step S80), and then determines whether “q _ij = 0” (step S81). When the determination result is negative, the computing device sets “t = 1”, sets “k = 1” (step S82), and then sets “k = k + q _{(l + t) j} × 2 as a new value of k. ^ T 'is obtained (step S83). Next, the computing device sets “t = t + 1” (step S84), and determines whether or not “l + t = n” (step S85). If the determination result in step S85 is affirmative, the process proceeds to step S87. If the determination result in step S85 is negative, the calculation device then determines whether or not 't = d' (step S86). . If the determination result of step S86 is affirmative, the process proceeds to step S83, and if the determination result of step S86 is negative, the process proceeds to step S87. In step S87, the computing device, using the value of k obtained in step S83, the with reference to the value of the calculated value storage table 53 in the stored T (k), _S the value of _{j 'S j} = _{S It is obtained as j} × T (k) ^ l ′ (step S87). Then, the computing device sets “l = l + d” (step S88), and determines whether “l <n” (step S89). 'n = w / d'. If the determination result in step S89 is negative, the process proceeds to step S81. If the determination result in step S89 is affirmative, the process ends. If the determination result in step S81 is affirmative, the computing device sets “l = 1 + 1” (step S90) and proceeds to step S81. As described above, the computing device selects a combination of d bits so that the leading value does not become “0” for the bit string when using T (k), and T (corresponding to the selected bit string). The value of k) is referred to in the calculated value storage table 53, and S _j is obtained.

FIG. 14 is a diagram schematically showing each S _j obtained by using T (k) stored in the calculated value storage table 53 shown in FIG. 3 in the table of FIG. 2 showing a ^ q. It is. As shown in the figure, for each j, a combination of four bits that does not start with “0” is selected for a combination of exponents that should be consecutive four for p, and T ( k).

Next, a procedure of processing for precalculating the value of T (k) stored in the calculated value storage table 53 before the calculation device performs the above power calculation will be described with reference to FIG. Computing device, first, a 'T (1) = a' ( step S100), and 'k = 11 _2' (step S101). Next, the computing device sets “T (k) = T ((k−1) / 2) ^ p × a” (step S102). Thereafter, the computing device sets “k = k + 2” (step S103), and then determines whether or not “k <2 ^ d” (step S104). When the determination result of step S104 is affirmative, the process proceeds to step S102, and when the determination result of step S104 is negative, the calculation apparatus ends the process. As described above, the calculation apparatus obtains T (k) for a combination whose leading bit is not “0” among the combinations of d bits, and stores this in the calculated value storage table 53.

  According to the configuration as described above, it is possible to more effectively reduce the amount of calculation of the power calculation performed by the computing device in the finite field expansion field.

[Fourth embodiment]
Next, a fourth embodiment of the computing device will be described. In addition, about the part which is common in the above-mentioned 1st Embodiment thru | or 3rd Embodiment, it demonstrates using the same code | symbol or abbreviate | omits description.

(1) Configuration In this embodiment, the r-adic expansion unit 52 of the computing device uses the low-order bits of the coefficient q _{y + 1} for the coefficients q _y and q _{y + 1} (0 ≦ y ≦ w−2) after the p-adic expansion. It distributes the minute term of the coefficient _{q y,} i.e., the addition of p times the part of coefficient _{q y + 1} value for the coefficient _{q y,} the coefficient _{q y,} the _{q y + 1} expand r Decimal.

When p satisfies 'p ≠ r ^ n (r ^ {n-1} ≦ p <r ^ n, n is a natural number)', a coefficient q _i (see Equation 4) after q is expanded to a p-adic number is “q _i <r ^ n” is satisfied. Here, for the sake of convenience, the description will be made assuming that “r = 2”. Even when “r ≠ 2”, the concept is the same. For example, 'p = 9' and 'q = 48'. At this time, when q is expanded to the p-adic number, the following Expression 15 is established.
q = q ₀ + q ₁ × p = 3 + 5 × 9 (= 3 × p ^ 0 + 5 × p ^ 1) (15)
At this time, 'q ₀ = 3' and 'q ₁ = 5'. When q ₀ and q ₁ are expressed in binary notation, respectively, “q ₀ = (11 ₂ )” and “q ₁ = (101 ₂ )” are obtained. Since 'q _i <p', there is usually no q _i such as '11 = (1011 ₂ ) 'or '14 = (1110 ₂ )'. Here, the expression of q _i , such as (1110 ₂ ), is allowed to be expressed as “q _i ≧ p”, so that the range of expression of the coefficient q _i is increased, and as a result, the number of calculations is reduced. by selecting the representation of the coefficients q _i, the coefficient q _i expand r Decimal.

In the above example, even if 'q ₀ = 12 = (1100 ₂ )' and 'q ₁ = 4 = (100 ₂ )', 'q = q ₀ × p ^ 0 + q ₁ × p ^ 1' is satisfied, There is no increase in bit length. 16, 'i = 4', when the 'r = 2' and 'h = 14', the coefficient _q 4, _{q 5,} the coefficient _{q 5 (0)} when the expansion coefficients _{q 5} 2 binary numbers' It is the figure which showed a ^ q in the case of 1 'in the two-dimensional table format. In the figure, the coefficient _{q 4 (0)} when the expansion coefficients _{q 4} 2 binary, q _{4 (13)} are each '0'. Figure 17 is distributed to the coefficients of the coefficient _{q 5 (0)} the coefficient _{q 4} in FIG. 4, the coefficient _{q 4 (0),} q _{4 (13)} to each '1', the coefficient _{q 5 (0)} '0 It is a figure which shows the state made into '. As described above, even when a part of the value of the coefficient q _{i + 1} is added to the coefficient q _i , the calculation result of a ^ p is the same between the case shown in FIG. 16 and the case shown in FIG. . Using this calculation principle, in the present embodiment, the r-adic expansion unit 52 determines that “q _i ≧” only when the appearance frequency of “1” can be reduced for the coefficient q _i after the p-adic expansion. The coefficient q _i is optimized so as to be p ′, and r-adic expansion is performed.

FIG. 18 is a flowchart showing a procedure of coefficient optimization processing according to the present embodiment. The computing device sets 'k = 0' (step S110), and determines whether or not 'q _k + p <r ^ n' (step S111). If the determination result is affirmative, the computing device determines whether or not 'q _{(k + 1) 0} = 1' (step S112). If the determination result is positive, then the computing device compares the number and the number of '1' appears in the case of q _k, which is the case of 'q _{k +} p''1' appears, It is determined whether the former is greater than or equal to the latter (step S113). That is, by setting “q _k + p”, the calculation device determines whether the number of occurrences of “1” increases as compared to the case of q _k . If the determination result in step S113 is affirmative, that is, if the number of occurrences of “1” does not increase, the computing device sets “q _k = q _k + p”, and “q _{(k + 1) 0} = q _{(K + 1) 0} −1 ′ is set (step S114), and the process proceeds to step S115. If the determination result in step S111, S112 or S113 is negative, the process proceeds to step S115. In step S115, the computing device increments k to “k = k + 1”. Then, the computing device determines whether or not “k <n” (step S116). If the determination result in step S116 is affirmative, the process proceeds to step S111. If the determination result in step S116 is negative, the coefficient optimization process ends. As described above, when the number of occurrences of “1” does not increase by setting “q _k + p” as compared with the case of q _k , the calculation device sets each of “q _k = q _k + p” as Recalculate q _ij . As described above, the computing device searches for i where 'q _i + p <r ^ n' and 'q _{(i + 1) 0} = 1', and optimizes the coefficient q _i .

After the above optimization processing, the computing device may perform the processing after step S2 described in the first embodiment or the second embodiment. When such a configuration in the present embodiment is combined with the first embodiment or the second embodiment, '1' existing at the head or tail of the window width when referring to the calculated value storage table 53 Can be converted to '0', there is a high possibility that the number of multiplications can be reduced by reducing the appearance frequency of '1'. Therefore, when attention is paid to easily coefficient becomes the first or tail of the Window width q _d and coefficient q _(2d) can be expected more effective. Therefore, the configuration in this embodiment optimizes the bit arrangement after p-adic expansion and r-adic expansion so as to reduce the calculation amount without changing the exponent value, thereby effectively reducing the calculation amount. It becomes possible to do.

In the above description, the processing is performed so as not to increase the bit length. However, if the increase in the bit length is allowed, '(q ₀ , q ₁ ) = (21, 3), (30, 2), ( 39,1) 'etc. can also be taken as expressions.

As another example, a case where 'p = 19' and 'q = 216' will be described. At this time, since “q = 7 + 11 × 19”, it is “(q ₀ , q ₁ ) = (7, 11)”, but if “(q ₀ , q ₁ ) = (64, 8)”, the coefficient is The number of occurrences of “1” decreases from 6 to 2. However p whereas can be represented by 5 bits, the 7 bits are required to represent q _0. For this reason, when the expression is converted in this way, it is necessary to repeat the process of step 5 in the first embodiment twice more than before the expression is converted. However, since the final purpose is to reduce the processing amount of the whole power calculation process, it is only necessary to perform such conversion a plurality of times so that the number of multiplications can be reduced as a whole. When “(q ₀ , q ₁ ) = (64, 8)”, the number of multiplications can be reduced by four or more as the whole power calculation process. Whether the number of multiplications can be reduced can be determined experimentally. For example, in an environment where power exponents are given in advance and offline pre-calculation is possible, if the conversion with such a long bit length can be performed, the amount of calculation of the whole power calculation process can be reduced. it can.

[Fifth embodiment]
Next, a fifth embodiment of the computing device will be described. In addition, about the part which is common in the above-mentioned 1st Embodiment thru | or 4th Embodiment, it demonstrates using the same code | symbol or abbreviate | omits description.

The procedure of the whole power calculation process according to the present embodiment is as shown in FIG. 4 and is the same as that of the first embodiment. In the present embodiment, the detailed procedure of the process of calculating S _j in step S3 is the same as that of the third embodiment. What is different from the third embodiment is a method of creating a calculated value storage table. Here, a method of creating a calculated value storage table will be described.

  The calculation value storage table used here uses a concept similar to the BPE method used in data compression or the like. The concept of the BPE method is to repeat an operation of replacing a 2-byte character string having a high appearance frequency with an unused 1-byte character.

  In the power calculation, if multiplication results corresponding to repeated coefficient sequences are stored in advance as a table, the total number of multiplications can be reduced. However, the difference from data compression is that the coefficient should be multiplied when the coefficient is ‘1’, and therefore there is a case where it is not necessary to handle when the coefficient is ‘0’. For this reason, here, a sequence that starts with a value other than “0” and ends with a value other than “0” is regarded as one “character string”, and the multiplication result corresponding to the series in which this “character string” appears multiple times is stored. The calculation device creates a value storage table. The longer the data length of the value stored in the calculated value storage table, the more the number of multiplications can be reduced. However, the concept of the BPE method is applied to create a calculated value storage table for storing a long data length value. To do. That is, a coefficient other than “0” or “character” starts with a coefficient other than “0” or “character” (for example, (1, 1), (1, 0, 0, 1), (C, 0, 1) etc.) is treated as one “character string”, and the calculation device creates a calculated value storage table by repeatedly replacing “character string” that appears multiple times with another “character” for convenience. To do. This is the creation policy in this embodiment. Here, “character” represents a coefficient string or a combination of coefficient strings and “characters”, and “character string” is a coefficient string or a combination of “characters”.

FIG. 19 is a flowchart of a process procedure for creating a calculated value storage table according to the present embodiment. Here, as a specific example, consider the case of 'h = 1', 'w = 10', and 'r = 2'. If '(q ₀₀ ,..., Q ₉₀ ) = (1,1,0,1,0,0,1,1,0,1)', this is calculated by the computing device according to the above-mentioned creation policy. Convert. First, the computing device searches for a coefficient sequence having a high frequency in the coefficient sequence (step S201). As a result, a coefficient sequence (“character string”) of (1,1) is found here. The computer replaces this with a new “character” “A” (step S202).
(Q ₀₀ ,..., Q ₉₀ ) = (A, 0, 1, 0, 0, A, 0, 1)

Next, when the computing device searches for a frequently-used “character string” in the converted coefficient string (step S203), here, (A, 0, 1) is found (step S203: Yes). In addition, since there is no other “character string” other than the above, the process proceeds from step S201 to step S202, and “B” is replaced with “B”. As a result,
(Q ₀₀ ,..., Q ₉₀ ) = (B, 0, 1, 0, 0, B)
It becomes. Here, the same “character string” does not appear twice or more (step S203: No). Therefore, when “character string” is represented by a coefficient string, A: (1, 1)
B: (A, 0, 1) (= (1, 1, 0, 1))
It becomes. When this is converted into a table expression like the calculated value storage table shown in the third embodiment,
A: T (11) = a ^ (1 + p)
B: T (1101) = a ^ (1 + p ^ 2 + p ^ 3)
It becomes. The calculation device obtains this and stores it in the calculated value storage table 53 (step S204).

  According to the configuration as described above, it is possible to more effectively reduce the amount of calculation of the power calculation performed by the computing device in the finite field expansion field.

[Modification]
Note that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Moreover, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the embodiment. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined. Further, various modifications as exemplified below are possible.

<Modification 1>
In each of the above-described embodiments, various programs executed by the computing device may be provided by being stored on a computer connected to a network such as the Internet and downloaded via the network. The various programs are recorded in a computer-readable recording medium such as a CD-ROM, a flexible disk (FD), a CD-R, and a DVD (Digital Versatile Disk) in an installable or executable format file. You may comprise so that it may provide.

<Modification 2>
In the first embodiment or the third embodiment described above, the value of T (k) is preliminarily calculated and stored in the calculated value storage table 53 in advance. However, the calculation apparatus may acquire the value of T (k) calculated by another information processing apparatus and store it in the calculation value storage table 53. Acquisition of the value of T (k) may be performed by communication via the communication I / F, or may be performed by reading from a computer-readable recording medium or the like.

  In the first embodiment or the third embodiment described above, the window width is set to “4”. However, the present invention is not limited to this, and the window width is not less than “2” and not more than “w”. good.

<Modification 3>
In the first embodiment or the second embodiment described above, when a plurality of power calculations with the same power exponent are performed, the result of the p-adic expansion and the r-adic expansion performed in the previous power calculation are performed. At least one of the results may be reused to perform the later power calculation. In this case, for example, if the values of the coefficients q _ij after p-adic expansion and after r-adic expansion are stored in an external storage device such as an HDD as shown in FIG. Can be reused.

  In addition, when a plurality of power calculations that should have the same element are performed, some or all of the calculation results obtained in the process of the previous power calculation may be reused to perform the subsequent power calculation. In this case, for example, the calculated value storage table 53 can be reused in the later power calculation.

  As described above, if power exponents or elements in a plurality of power multiplications are the same, the amount of calculation can be effectively reduced by sharing a common calculation result.

<Modification 4>
In the second embodiment described above, an upper limit of the value of b may be determined. According to such a configuration, storage in the calculated value storage table 53 and calculation of each S _j can be performed more effectively.

<Modification 5>
In each of the above-described embodiments, the Frobenius map is used as a calculation method capable of calculating the power at a high speed. However, the present invention is not limited to this.

It is a figure which illustrates the functional structure of the calculation apparatus concerning 1st Embodiment. It is the figure shown in the two-dimensional tabular form in order to express a ^ q which is the qth power of the former a visually. It is the figure which showed visually the calculation value storage table 53 in case of 'd = 4'. It is a flowchart which shows the procedure of the power calculation process concerning the embodiment. It is a flowchart which shows the detailed procedure of the process of p-adic number expansion concerning the embodiment. It is a flowchart which shows the detailed procedure of the r-adic number expansion process concerning the embodiment. It is a flowchart which shows the detailed procedure of the process which calculates _{Sj concerning} the embodiment. In the table of FIG. 2 showing a ^ q according to the same embodiment, each S _j obtained using T (k) stored in the calculated value storage table 53 shown in FIG. 3 is schematically shown. It is a figure. It is a flowchart which shows the detailed procedure of the process which calculates S which is the q power of a concerning the embodiment. It is a flowchart which shows the procedure of the process which pre-calculates the value of T (k) memorize | stored in the calculation value storage table 53 concerning the embodiment. It is a flowchart which shows the procedure of the power calculation process concerning 2nd Embodiment. It is a flowchart which shows the detailed procedure of the process of step S3 'concerning the embodiment. It is a flowchart which shows the detailed procedure of the process which calculates _{Sj concerning} 3rd Embodiment. In the table of FIG. 2 showing a ^ q according to the same embodiment, each S _j obtained using T (k) stored in the calculated value storage table 53 shown in FIG. 3 is schematically shown. It is a figure. It is a flowchart which shows the procedure of the process which pre-calculates the value of T (k) memorize | stored in the calculation value storage table 53 concerning the embodiment. It is the figure which showed a ^ q concerning 4th Embodiment in the two-dimensional table format. It is the figure which showed a ^ q concerning the embodiment in the two-dimensional table format, and is a figure which shows the state after conversion of a coefficient. It is a flowchart which shows the procedure of the coefficient optimization process concerning the embodiment. It is a flowchart which shows the procedure of the process which produces the calculation value storage table concerning 5th Embodiment.

Explanation of symbols

51 p-adic expansion unit 52 r-adic expansion unit 53 calculated value storage table 54 first calculation unit 55 second calculation unit

Claims (15)

A computing device for calculating a power of a finite element a (a∈Fp ^ m, m is a natural number, and `^ 'is a power),
Q = Σ <sub>i = 0</sub> <sup>w−1</sup> q <sub>i</sub> × s ^ i (0 ≦ q <sub>i</sub> <s)
An s-adic expansion unit for obtaining each coefficient q <sub>i</sub>
Each coefficient <sub>q i</sub> expand r adic <sup><sub>q i = Σ j = 0 h</sub></sup> -1 q ij × r ^ j (0 <r <s, 0 ≦ q ij <r)
An r-adic expansion unit for <sub>obtaining</sub> each coefficient q <sub>ij such</sub> that
A power calculator that calculates a power using each coefficient q <sub>ij</sub> ,
Wherein r adic number expansion unit, coefficient after s-adic expansion <sub>q y, q (y + 1</sub> ) for (0 ≦ y ≦ w-2 ), added s times of some of the values of the coefficients <sub>q (y + 1)</sub> to the coefficient <sub>q y</sub> And calculating each coefficient q <sub>y</sub> , q <sub>(y + 1)</sub> by r-adic number. The power calculator is
For each j
S <sub>j</sub> = Π <sub>i = 0</sub> <sup>w−1</sup> a ^ {q <sub>ij</sub> × s ^ i}
A first calculation unit for calculating
Using S <sub>j</sub> calculated for each j, a ^ q = (((((((S <sub>(h-1)</sub> )) ^ r * S <sub>(h-2)</sub> ) ^ r * <sub>S (h-3)) ^</sub> r × ···) ^ r × S 1) ^ r × S 0
The calculation apparatus according to claim 1, further comprising: a second calculation unit that calculates.   D consecutive coefficients q for the same j <sub>0j</sub> , q <sub>1j</sub> , ..., q <sub>(d-1) j</sub> 'A ^ (q each calculated for all possible combinations of values for (2 ≦ d ≦ w) <sub>0j</sub> + Q <sub>1j</sub> Xs + ... + q <sub>(d-1) j</sub> × s ^ {d−1}) ′
  The first calculation unit uses the value stored in the storage unit to calculate S for each j. <sub>j</sub> Calculate
The computing apparatus according to claim 2, wherein:   Non-zero q for the same j <sub>ij</sub> U (2 ≦ u ≦ d, 2 ≦ d ≦ w) consecutive coefficient sequences q starting with (0 ≦ i <(w−1)) <sub>ij</sub> , ..., q <sub>(I + u-1) j</sub> Q <sub>(I + u-1) j</sub> U taking a non-zero value and the coefficient sequence q <sub>ij</sub> , ..., q <sub>(I + u-1) j</sub> ‘A ^ (q <sub>ij</sub> + Q <sub>(I + 1) j</sub> Xs + ... + q <sub>(I + u-1) j</sub> × s ^ {i + u−1}) ′ and the coefficient sequence q used in the calculation <sub>ij</sub> , ..., q <sub>(I + u-1) j</sub> Storage means for storing each coefficient value of
  The first calculation unit performs S for each j. <sub>j</sub> When u are calculated, u consecutive coefficient sequences q <sub>kj</sub> , ..., q <sub>(K + u-1) j</sub> The value of each coefficient (0 ≦ k <(w−1)) and the coefficient sequence q stored in the storage means <sub>ij</sub> , ..., q <sub>(I + u-1) j</sub> When the values of the respective coefficients match, the ‘a ^ (q <sub>ij</sub> + Q <sub>(I + 1) j</sub> Xs + ... + q <sub>(I + u-1) j</sub> Xs ^ {i + u-1}) 'value is used
The computing apparatus according to claim 2, wherein:   ‘A ^ (q <sub>uj</sub> + Q <sub>(U + 1) j</sub> × s + q <sub>(U + 2) j</sub> × s ^ 2 + ... + q <sub>(U + d-1) j</sub> Xs {d-1}) 'is further stored in advance,
  The first calculation unit calculates a coefficient q that is not 0 for d ≧ 2. <sub>uj</sub> And non-zero coefficient q <sub>(U + d-1) j</sub> D consecutive coefficient sequences q for the same j including <sub>uj</sub> , ..., q <sub>(U + d-1) j</sub> And d consecutive coefficient sequences q having the same value of each coefficient <sub>(U + t) (j + v)</sub> , ..., q <sub>(U + t + d-1) (j + v)</sub> Is calculated for each j using the value stored in the storage means
The computing apparatus according to claim 2, wherein: s in the s-adic expansion is the characteristic p of the element a of the finite field,
The s-adic expansion unit expands a power exponent q to a p-adic number, and q = Σ <sub>i = 0</sub> <sup>w−1</sup> q <sub>i</sub> × p ^ i (0 ≦ q <sub>i</sub> <p)
Become computing device according to any one of claims 1 to 5, characterized in that determining the coefficients q <sub>i.</sub> The power calculation unit uses the Frobenius map and each said coefficient q <sub>ij,</sub> computing device according to any one of claims 1 to 6, wherein the calculating the power of said source. The finite field is an expanded field expanded by a binomial expression,
The power calculation unit uses each of said coefficients q <sub>ij,</sub> computing device according to any one of claims 1 to 7, characterized in that to calculate the original power of the extension field. The finite field is an expanded field expanded by a circular polynomial,
The power calculation unit uses each of said coefficients q <sub>ij,</sub> computing device according to any one of claims 1 to 7, characterized in that to calculate the original power of the extension field. Wherein r adic number expansion unit, for each coefficient q <sub>i,</sub> computing device according to any one of claims 1 to 9, characterized in that the binary expansion. When calculating a plurality of powers that should have the same power exponent, the s-adic expansion unit uses a part or all of the result of the s-adic expansion when calculating the previous power, when calculating the subsequent power. The computing device according to claim 1, wherein the power exponent q is expanded to an s-adic number. In the case of calculating a plurality of powers that should have the same power exponent, the r-adic expansion unit uses a part or all of the result of the r-adic expansion in the previous power calculation in the subsequent power calculation. 12. The calculation apparatus according to claim 1, wherein each coefficient q <sub>i</sub> is expanded to an r-adic number. If the original is a plurality calculates the power is the same, the power calculation unit that uses a part or all of the calculation results obtained during the previous power calculations, calculating the power of pre Kimoto The computing device according to claim 1, wherein A computing device that includes an s-adic expansion unit, an r-adic expansion unit, and a power calculation unit, and calculates a power of a finite field element a (a∈Fp ^ m, m represents a natural number, and `^ 'represents a power) A calculation method executed in
The s-adic expansion unit expands a power exponent q into an s-adic number and q = Σ _{i = 0} ^w−1 q _i × s ^ i (0 ≦ q _i <s)
Find each coefficient q _i
The r-adic expansion unit expands each coefficient q _i into an r-adic number, and q _i = Σ _{j = 0} ^h−1 q _ij × r ^ j (0 <r <s, 0 ≦ q _ij <r)
_Find each coefficient q _{ij such} that
The power calculation unit calculates an original power of a power exponent q using each coefficient q _ij ,
In the r-adic expansion, for the coefficients q _y , q _{(y + 1)} (0 ≦ y ≦ w−2) after the s-adic expansion, a part s times the value of the coefficient q _{(y + 1)} is added to the coefficient q _y. A calculation method characterized by expanding each coefficient q _y , q _{(y + 1)} to an r-adic number.   A program for causing a computer to execute the calculation method according to claim 14.

Images