Apparatus for solving system of equations on finite field and apparatus for inverting element of extension field

[0001] This application is based on applications Nos. 11-203055 and 2000-140886 filed in Japan, the contents of which are hereby incorporated by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates to cryptographic and error correction techniques for information security, and in particular relates to computation techniques which use extension fields and systems of equations.

[0004] 2. Description of the Prior Art

[0005] Secret communication or digital signature techniques have increasingly been used in data communication in recent years.

[0006] Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable the recipient to verify whether the communicated content is valid or whether the information is from the stated sender. Such secret communication or digital signature techniques use a cryptosystem called public key cryptography. Public key cryptography provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users.

[0007] In the public key cryptography, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Here, one of the founding principles for the security of public key cryptography is the so-called discrete logarithm problem. Representative examples of the discrete logarithm problem are problems based on finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz (1987), A Course in Number Theory and Cryptography, Springer-Verlag.

(Elliptic Curve Discrete Logarithm Problem)

[0008] The elliptic curve discrete logarithm problem is the following.

[0009] Let E be an elliptic curve defined over a finite field GF(q) (q=pⁿ, p a prime, n a positive integer), with a point G on the elliptic curve E, given when the order of E is divisible by a large prime, being set as a base point. This being so, the problem is to find an integer x such that
Y=x*G

• • [0010] where Y is a given point on E, if such an integer x exists.

[0011] In this specification, the operator * represents elliptic curve exponentiation, so that x*G means G is added to itself x times on E. Also, GF(q) is an extension field of a finite field GF(p). For details about extension fields, see T. Okamoto & H. Yamamoto (1997), Modern Encryption, Mathematics of Information Sciences Series, Sangyo Tosho, pp. 26–28.

(Prior Art 1: ElGamal Signature Scheme which Uses the Elliptic Curve Discrete Logarithm Problem)

[0012] The ElGamal signature scheme using the elliptic curve discrete logarithm problem is described below with reference to FIG. 9.

[0013] In the figure, a device 310 used by a user A (hereafter, “user A 310”), a management center 320, and a device 330 used by a user B (hereafter, “user B 330”) are connected via a network.

[0014] Let p be a prime, q=pⁿ, n be a positive integer, and E be an elliptic curve over a finite field GF(q), with G being a base point of E and r being the order of G. Which is to say, r is the smallest positive integer that satisfies
r*G=0

• • [0015] where 0 is the zero element in the additive group on the elliptic curve E.
    (1) Public Key Generation by the Management Center 320

[0016] First, the management center 320 generates a public key Y_A of the user A 310 using the user A's secret key x_A which has been informed beforehand, according to the equation
Y_A=x_A*G

• • [0017] (S1, S2).

[0018] The management center 320 announces the finite field GF(q), the elliptic curve E, and the base point G as system parameters, and reveals the public key Y_A of the user A 310 to the user B 330 (S3, S4).

(2) Signature Generation by the User A 310

[0019] The user A 310 generates a random number k (S5), calculates
R₁=(r_x,r_y)=k*G

• • [0020] (S6), and finds s satisfying
    s×k=m+r_x×x_Amod r
  • [0021] (S7) where m is a message to be sent from the user A 310 to the user B 330.

[0022] The user A 310 sends the message m and the signature (R₁,s) to the user B 330 (S8).

(3) Signature Verification by the User B 330

[0023] The user B 330 verifies the authenticity of the user A 310 by judging whether
s*R₁=m*G+r_x*Y_A

• • [0024] is true (S9).

[0025] This equation is derived from

[0026] $\begin{array}{c}s*R_1=\left[\left(\left(m+r_x\times x_A\right)/k\right)\times k\right]*G\\ =\left(m+r_x\times x_A\right)*G\\ =m*G+\left(r_x\times x_A\right)*G\\ =m*G+r_x*Y_A\end{array}$

[0027] In this ElGamal digital signature scheme using the elliptic curve discrete logarithm problem, elliptic curve exponentiation is repeatedly performed to generate the public key and the signature and to verify the signature.

[0028] For details on elliptic curve exponentiation, see “Efficient Elliptic Curve Exponentiation” in Miyaji, Ono & Cohen (1997), Advances in Cryptology-Proceedings of ICICS'97, Lecture Notes in Computer Science, Springer-Verlag, pp. 282–290 (hereafter “document 1”).

[0029] Let an elliptic curve be defined by an equation of the form
y²=x³+a×x+b

• • [0030] with some point P on the elliptic curve being represented by 2-tuple coordinates (x₁,y₁) called affine coordinates.

[0031] Elliptic curve exponentiation in the 2-tuple coordinate is known to involve inverse operations on the finite field GF(q).

[0032] Document 1 makes brief mention of a 3-tuple coordinate called projective coordinate. 2-tuple coordinates can be transformed into corresponding 3-tuple coordinates as shown by
(x₁,y₁)→(x₁,y₁,1)

[0033] Elliptic curve exponentiation in the 3-tuple coordinate involves no inverse operations on the finite field GF(q). Since inverting a finite field element generally takes considerable computation time, the 3-tuple coordinate is often used in elliptic curve exponentiation.

[0034] However, when transforming 3-tuple coordinates into corresponding 2-tuple coordinates as shown by
(X,Y,Z)→(X/Z, Y/Z)

• • [0035] inversion on the finite field GF(q) is necessary.

[0036] In step S6 in FIG. 9, for instance, after 2-tuple coordinates are transformed into 3-tuple coordinates, elliptic curve exponentiation is performed on the 3-tuple coordinates, and the resulting 3-tuple coordinates are transformed into corresponding 2-tuple coordinates. Inversion is needed in this transformation of the 3-tuple coordinates to the 2-tuple coordinates.

(Prior Art 2: Inversion in an Extension Field)

[0037] A conventional inverse operation on an extension field GF(q) (q=pⁿ, p a prime, n a positive integer) is performed in the following way.

[0038] For simplicity's sake, a generator polynomial of the extension field GF(q) is set as f(g)=gⁿ−β whose root is α, and an element of GF(q) to be inputted in the generator polynomial is set as
x=x₀+x₁×α+ . . . +x_n−1×αⁿ⁻¹
(1) Step 1

[0039] Based on the element x of GF(q), a system of equations for y_i (i=0, 1, . . . , n−1)

[0040] $x_0{y}_0+\beta x_{n-1}{y}_1+\beta x_{n-2}{y}_2+\dots +\beta x_1{y}_{n-1}=1$ $x_1{y}_0+x_0{y}_1+\beta x_{n-1}{y}_2+\dots +\beta x_2{y}_{n-1}=0$ $x_2{y}_0+x_1{y}_1+x_0{y}_2+\dots +\beta x_3{y}_{n-1}=0$ $⋮$ $x_{n-2}{y}_0+x_{n-3}{y}_1+x_{n-4}{y}_2+\dots +\beta x_{n-1}{y}_{n-1}=0$ $x_{n-1}{y}_0+x_{n-2}{y}_1+x_{n-3}{y}_2+\dots +x_0{y}_{n-1}=0$

• • [0041] is formed.
    (2) Step 2

[0042] The solutions y_k (k=0,1, . . . ,n−1) of the system of equations are sought.

(3) Step 3

[0043] From the solutions y_k (k=0,1, . . . ,n−1), the inverse
I=y₀+y₁α+ . . . y_n−1αⁿ⁻¹

• • [0044] is calculated. Hence the inverse of the element x in the extension field GF(q) is obtained.

[0045] The validity of this inverse operation is shown below.

[0046] If the inverse I and the element x satisfy the relationship
xI=1 mod f(g)

• • [0047] then

[0048] $\begin{array}{c}\mathrm{xI}=x_0\left(y_0+y_1\alpha +\dots +y_{n-1}{\alpha }^{n-1}\right)+\\ x_1\alpha \left(y_0+y_1\alpha +\dots +y_{n-1}{\alpha }^{n-1}\right)+\\ x_2{\alpha }^2\left(y_0+y_1\alpha +\dots +y_{n-1}{\alpha }^{n-1}\right)+⋮x_{n-1}{\alpha }^{n-1}\left(y_0+y_1\alpha +\dots +y_{n-1}{\alpha }^{n-1}\right)\end{array}$

• • [0049] and also
    αⁿβmod f(g)

[0050] Accordingly,

[0051] $\begin{array}{c}\mathrm{xI}=x_0\left(y_0+y_1\alpha +\dots +y_{n-1}{\alpha }^{n-1}\right)+\\ x_1\left(y_0\alpha +y_1{\alpha }^2+\dots +y_{n-1}\beta \right)+\\ x_2\left(y_0{\alpha }^2+y_1{\alpha }^3+\dots +y_{n-1}\mathrm{\alpha \beta }\right)+\\ ⋮\\ x_{n-1}\left(y_0{\alpha }^{n-1}+y_1\beta +\dots +y_{n-1}{\alpha }^{n-2}\beta \right)\end{array}$

• • [0052] which can be rearranged in ascending order of power of α into

[0053] $\begin{array}{c}\mathrm{xI}=x_0{y}_0+\beta \times x_{n-1}\times y_1+\dots +\beta x_1{y}_{n-1}+\\ \alpha \left(x_1{y}_0+x_0\times y_1+\dots +{\mathrm{\beta x}}_2{y}_{n-1}\right)+\\ {\alpha }^2\left(x_2{y}_0+x_1{y}_1+\dots +\beta x_3{y}_{n-1}\right)+\\ ⋮\\ {\alpha }^{n-1}\left(x_{n-1}{y}_0+x_{n-2}{y}_1+\dots +x_0{y}_{n-1}\right)\end{array}$

[0054] From this equation and the relationship xI=1, the system of equations in step 1 is derived.

[0055] Therefore, calculating an inverse in the extension field GF(q) is equivalent to solving a system of equations on the basic field GF(p).

[0056] Though the foregoing example uses the generator polynomial of the form gⁿ−β for simplicity's sake, a system of equations can be formed by the same procedure for a generator polynomial of ordinary form.

(Prior Art 3: Solution of a System of Equations on the Basic Field GF(p))

[0057] A conventional method for solving a system of equations on the basic field GF(p) is described below. This method is called Gaussian elimination. For details on Gaussian elimination, see K. Mizugam_i (1985), Mathematical Calculations by Computers, Introduction to Programming Series, Asakura Shoten, pp. 76˜82 (hereafter “document 2”).

[0058] A system of equations for x_k (k=0, 1, 2, . . . , n−1)

[0059] $\begin{array}{c}{a}_{11}{x}_0+a_{12}{x}_1+\dots +a_{1n}{x}_{n-1}=b_1\\ a_{21}{x}_0+a_{22}{x}_1+\dots +a_{2n}{x}_{n-1}=b_2\\ ⋮\\ a_{\mathrm{n1}}{x}_0+a_{\mathrm{n2}}{x}_1+\dots +a_{\mathrm{nn}}{x}_{n-1}=b_n\end{array}$

• • [0060] is solved by Gaussian elimination in the following manner.
    (Step 1)

[0061] A matrix M and a vector v are given respectively as

[0062] $M=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& ⋮& ⋮& ⋮\\ a_{\mathrm{n1}}& a_{\mathrm{n2}}& \dots & a_{\mathrm{nn}}\end{array}\right)$ $v=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right)$

[0063] Meanwhile, a vector X is given as

[0064] $X=\left(\begin{array}{c}{x}_0\\ x_1\\ •\\ •\\ x_{n-1}\end{array}\right)$

[0065] Then the above system of equations can be simply written as
MX=v

[0066] The matrix M an d the vector v are triangular transformed so as to put the matrix M into upper triangular form, as a result of which a matrix M′ and a vector v′ are generated. Here, the triangular transformation is such a transformation that changes all elements beneath the diagonal elements of a matrix to 0, and such a transformed matrix is called an upper triangular matrix.

[0067] The procedure of this conventional triangular transformation is explained below with reference to FIG. 10.

[0068] First, counter j is set at 1 (S21). Next, the inverse I_j of a_jj is computed (S22), 1 is assigned to a_jj (S23), and a_jk=a_jk×I_j and b_j=b_j×I_j are set for j+1≦k≦n (S24). Then counter i is set at j+1 (S25).

[0069] Following this, 0 is assigned to a_ij (S26), a_ik=a_ik−a_jj×a_jk is set for j+1≦k≦n (S27), and also b_i=b_i−a_ij×b_j is set (S28). Then it is judged whether i=n (S29). If i≠n, counter i is incremented by 1 (S31) and the procedure returns to step S26. If i=n, it is judged whether j=n (S30). If j≠n, counter j is incremented by 1 and the procedure returns to step S22. If j=n, the procedure ends.

[0070] As a result, the matrix M′ and the vector v′ are obtained. The matrix M′ is a matrix whose diagonal elements are all 1 and whose elements beneath the diagonal elements are all 0.

[0071] The system of equations M′X=v′ and the system of equations MX=v have an equivalence relation.

[0072] Let the matrix M′ and the vector v′ be written respectively as

[0073] $M^{\prime }=\left(\begin{array}{cccc}{c}_{11}& c_{12}& \dots & c_{1n}\\ c_{21}& c_{22}& \dots & c_{2n}\\ •& •& •& •\\ •& •& •& •\\ c_{\mathrm{n1}}& c_{\mathrm{n2}}& \dots & c_{\mathrm{nn}}\end{array}\right)$ $v^{\prime }=\left(\begin{array}{c}{d}_1\\ d_2\\ •\\ •\\ d_n\end{array}\right)$
(Step 2)

[0074] The system of equations M′X=v′ is solved using the generated matrix M′ and vector v′, in the following way.

[0075] The values n−1, . . . , 1, 0 are set one by one in counter c in this order. For counter c,
y_c=d_c+1

• • [0076] is calculated when c=n−1, and

[0077] $y_c=d_{c+1}-\sum _{i=c+1}^{n-1}\left(c_{c+1i+1}\times y_{i-1}\right)$

• • [0078] is calculated when c≠n−1.

[0079] A concrete example of applying the prior art 3 is presented below.

[0080] Note that this example is provided here only for facilitating the understanding of the triangular transformation, and is not an example of practical use in cryptographic communication or digital signature systems.

[0081] When a prime p=31, a generator polynomial f(g)=g⁵−2, and an element x=5α⁴+29α³+6α²+19α+17 of GF(q) are given, the calculations

[0082] $\begin{array}{c}x\times \alpha =5{\alpha }^5+29{\alpha }^4+6{\alpha }^3+19{\alpha }^2+17\alpha \\ =29{\alpha }^4+6{\alpha }^3+19{\alpha }^2+17\alpha +5\times 2\end{array}$ $\begin{array}{c}x\times {\alpha }^2=29{\alpha }^5+6{\alpha }^4+19{\alpha }^3+17{\alpha }^2+10\alpha \\ =6{\alpha }^4+19{\alpha }^3+17{\alpha }^2+10\alpha +29\times 2\end{array}$ $\begin{array}{c}x\times {\alpha }^3=6{\alpha }^5+19{\alpha }^4+17{\alpha }^3+10{\alpha }^2+27\alpha \\ =19{\alpha }^4+17{\alpha }^3+10{\alpha }^2+27\alpha +6\times 2\end{array}$ $\begin{array}{c}x\times a^4=19{\alpha }^5+17{\alpha }^4+10{\alpha }^3+27{\alpha }^2+12\alpha \\ =17{\alpha }^4+10{\alpha }^3+27{\alpha }^2+12\alpha +19\times 2\end{array}$

• • [0083] lead to a system of equations shown in FIG. 11(a), where a coefficient matrix 301 consists of 5 rows and 5 columns and a constant vector 302 consists of 5 elements.

[0084] In the system of equations in FIG. 11(a), a linear equation
17x₀+10x₁+27x₂+12x₃+7x₄=1

• • [0085] is called a pivotal equation that serves as the pivot of transformation, and the other linear equations are called object equations that are to be transformed.

[0086] First, the inverse operation
1/17 mod 31=11

• • [0087] is performed, and then
    10×11 mod 31=17
    27×11 mod 31=18
    12×11 mod 31=8
    7×11 mod 31=15
    1×11 mod 31=11
  • [0088] are calculated. As a result, the system of equations is transformed as shown in FIG. 11(b), where the element in the first column and row has become 1 in a coefficient matrix 311. The elements enclosed with the boxes in the coefficient matrix 311 and constant vector 312 in FIG. 11(b) are those which have changed from the coefficient matrix 301 and constant vector 302 in FIG. 11(a). The same goes for the rest of FIG. 11.

[0089] Here, the above inverse operation 1/17 mod 31=11 is carried out by first seeking a which satisfies
a×17+b×31=1

• • [0090] by means of the extended GCD (Greatest Common Divisor), and then setting a as the inversion result.

[0091] In general, the extended GCD takes considerable computational complexity, as it involves repeated multiplications and additions. For details on the extended GCD, see H. Cohen (1996) “A Course in Computational Algebraic Number Theory” in Graduate Texts in Mathematics 138, Springer-Verlag, pp. 16˜19.

[0092] Next,
17−17×19=4 mod 31
10−18×19=9 mod 31
27−8×19=30 mod 31
12−15×19=6 mod 31
0−11×19=8 mod 31

• • [0093] are calculated to convert the element in the first column and second row in the coefficient matrix 311 to 0, and in a like manner the elements in the first column and third to fifth rows in the coefficient matrix 311 are converted to 0, thereby transforming the coefficient matrix 311 in FIG. 11(b) into a coefficient matrix 321 shown in FIG. 11(c). The constant vector 312 is also transformed into a constant vector 322, as a result of which a system of equations shown in FIG. 11(c) is obtained.

[0094] Next, the coefficient matrix 321 is transformed into a coefficient matrix 331 so that the element in the second column and row becomes 1, and the constant vector 322 is transformed into a constant vector 332. Hence a system of equations shown in FIG. 11(d) is obtained. Further, the coefficient matrix 331 is transformed into a coefficient matrix 341 so that the elements in the second column and third to fifth rows become 0, and the constant vector 332 is transformed into a constant vector 342. Hence a system of equations shown in FIG. 11(e) is obtained.

[0095] Likewise, the element in the third column and row is converted to 1 in a coefficient matrix 351 in FIG. 11(f), and the elements in the third column and fourth to fifth rows are converted to 0 in a coefficient matrix 361 in FIG. 11(g). After this, the element in the fourth column and row is converted to 1 in a coefficient matrix 371 in FIG. 11(h), and the element in the fourth column and fifth row is converted to 0 in a coefficient matrix 381 in FIG. 11(i). Lastly, the element in the fifth column and row is converted to 1 in a coefficient matrix 391 in FIG. 11(j).

[0096] Thus, the coefficient matrix 301 is transformed into the upper triangular matrix 391.

[0097] Following this,

[0098] $y_4=29$ $\begin{array}{c}{y}_3=15-21\times 29\\ =26\mathrm{mod}31\end{array}$ $\begin{array}{c}{y}_2=11-4\times 26-28\times 29\\ =25\mathrm{mod}31\end{array}$ $\begin{array}{c}{y}_1=2-10\times 25-23\times 26-17\times 29\\ =25\mathrm{mod}31\end{array}$ $\begin{array}{c}{y}_0=11-17\times 25-18\times 25-8\times 26-15\times 29\\ =12\mathrm{mod}31\end{array}$

• • [0099] are computed.
    (Computational Complexity)

[0100] The total computational complexity of the prior art 3 is evaluated below. Here, computational complexity of one multiplication on a basic field is measured as 1Mul and computational complexity of one inversion on the basic field is measured as 1Inv.

[0101] In step 1 in the prior art 3, computational complexity for one value of counter j can be broken down as follows.

• • [0102] (a) Step S22 involves one inversion, so that computational complexity is 1Inv.
  • [0103] (b) Step S24 involves ((n−(j+1)+1)+1)=(n−j+1) multiplications, so that computational complexity is (n−j+1)Mul.
  • [0104] (c) For one value of counter i, step S27 involves (n−(j+1)+1) multiplications and so computational complexity is (n−j)Mul (c1), and step S28 involves one multiplication and so computational complexity is 1Mul (c2). Since counter i changes from j+1 to n, (c1) and (c2) are repeated (n−(j+1)+1)=(n−j) times, which makes the computational complexity of for all values of counter c at ((n−j)(n−j+1))Mul.

[0105] Summing (a), (b), and (c) together results in computational complexity of ((n−j+1)(n−j+1))Mul+1Inv.

[0106] Since counter j changes from 1 to n, the total computational complexity of step 1 is

[0107] $\sum _{j=1}^n\left(\left(\left(n-j+1\right)\left(n-j+1\right)\right)\mathrm{Mul}+1\mathrm{Inv}\right)=\sum _{j=1}^n\left(\left(n-j+1\right)\left(n-j+1\right)\right)\mathrm{Mul}+\sum _{j=1}^{n}1\mathrm{Inv}=\sum _{j=1}^n{j}^2\mathrm{Mul}+n\mathrm{Inv}=\left(1/6\times n\left(n+1\right)\left(2n+1\right)\right)\mathrm{Mul}+n\mathrm{Inv}$

[0108] On the other hand, computational complexity of step 2 in the prior art 3 is as follows.

[0109] For one value of counter c, (n−(c+1)+1)=(n−c) multiplications are necessary, so that computational complexity is (n−c)Mul.

[0110] Since counter c changes from 1 to n, the total computational complexity of step 2 is

[0111] $\begin{array}{c}\sum _{c=1}^n\left(n-c\right)\mathrm{Mul}=\sum _{c=1}^n\left(c-1\right)\mathrm{Mul}\\ =\left(\sum _{c=1}^{n}c-\sum _{c=1}^{n}1\right)\mathrm{Mul}\\ =\left(1/2\times n\left(n+1\right)-n\right)\mathrm{Mul}\\ =\left(1/2\times n\left(n-1\right)\right)\mathrm{Mul}\end{array}$

[0112] Therefore, the overall computational complexity of the prior art 3 is
(1/6×n(n+1)(2n+1)+1/2×n(n−1))Mul+nInv=1/3×n×(n²+3n−1)Mul+nInv

[0113] It is known that in a general-purpose computer 1Inv=40Mul when n=5 and |q|=160 (|q| is the bit size of q). Accordingly, the overall computational complexity of the prior art 3 is 265Mul.

[0114] As described above, an inverse of an element in an extension field can be computed by solving a system of equations on a finite field. Nevertheless, given that computational complexity of inversion needed in solving the system of equations is generally large, there still remains the demand to further reduce computational complexity of solving a system of equations on a finite field, and to thereby reduce computational complexity of inverting an extension field element.

[0115] In view of the stated demand, the present invention aims to provide an apparatus, method, and storage medium storing a program for solving a system of equations on a finite field with reduced computational complexity, an apparatus, method, and storage medium storing a program for inverting an element in an extension field with reduced computational complexity, and a communication system and a record medium reproducing apparatus that utilize these apparatuses and methods.

[0116] The above object can be achieved by an apparatus for use in encryption or decryption, for solving a system of linear equations Ax=b in n unknowns on a finite field GF(p), where p is a prime, n is a positive integer, A is a coefficient matrix consisting of elements of n rows and n columns, x is a vector of unknowns consisting of n elements, and b is a constant vector consisting of n elements, the apparatus including: a parameter storing unit for storing the coefficient matrix A and the constant vector b; a triangular transforming unit for reading the coefficient matrix A and the constant vector b from the parameter storing unit, and transforming the read coefficient matrix A and constant vector b to generate a coefficient matrix C and a constant vector d for a system of linear equations Cx=d in n unknowns that is equivalent to the system of linear equations Ax=b, the coefficient matrix C consisting of elements of n rows and n columns and the constant vector d consisting of n elements, wherein the coefficient matrix A is triangular transformed into the coefficient matrix C of upper triangular form without diagonal elements of the coefficient matrix A being changed to 1; a diagonal element inverting unit for calculating inverses of diagonal elements of the generated coefficient matrix C on the finite field GF(p); and an equation computing unit for solving the system of linear equations Cx=d using the coefficient matrix C, the constant vector d, and the inverses of the diagonal elements of the coefficient matrix C, to thereby solve the system of linear equations Ax=b.

[0117] With this construction, the system of linear equations can be solved with reduced computational complexity.

[0118] Here, the triangular transforming unit may perform one or more successive transformation processes to generate the coefficient matrix C and the constant vector d of the system of linear equations Cx=d from the coefficient matrix A and the constant vector b of the system of linear equations Ax=b, wherein in each transformation process the triangular transforming unit transforms a coefficient matrix and a constant vector of a system of linear equations in n unknowns, into a coefficient matrix and a constant vector of a system of linear equations in n unknowns that is equivalent to the system of linear equations before the transformation, where the system of linear equations Ax=b is subjected to the first transformation process and the system of linear equations Cx=d is generated as a result of the last transformation process, wherein in each transformation process the system of linear equations in n unknowns that is subjected to the transformation includes one pivotal equation which is a linear equation serving as a pivot for the transformation and one or more object equations which are linear equations to be transformed, and the triangular transforming unit transforms each of the object equations into an equation equivalent to the object equation by defining a first coefficient group containing at least one value related to the pivotal equation and a second coefficient group containing n+1 values related to the pivotal equation, changing a nonzero coefficient in the object equation to 0, multiplying each of a constant and n coefficients in the object equation by the value in the first coefficient group, and subtracting the n+1 values in the second coefficient group respectively from the n+1 multiplication results.

[0119] With this construction, the triangular transformation is carried out without the diagonal elements of the coefficient matrix of the system of linear equations being converted to 1.

[0120] Here, each transformation process may have transformation subprocesses each for transforming a separate one of the object equations, wherein in each transformation subprocess the triangular transforming unit (a) chooses a nonzero coefficient from the pivotal equation and sets the chosen nonzero coefficient into the first coefficient group, (b) chooses a nonzero coefficient from the object equation, multiplies each of a constant and n coefficients in the pivotal equation by the nonzero coefficient chosen from the object equation, and sets n+1 values obtained by the multiplications into the second coefficient group, (c) changes the chosen nonzero coefficient in the object equation to 0, and (d) multiplies each of a constant and n coefficients in the object equation by the nonzero coefficient in the first coefficient group, and subtracts the n+1 values in the second coefficient group respectively from the n+1 multiplication results.

[0121] Here, each transformation process may have a coefficient group calculation process and transformation subprocesses, performed following the coefficient group calculation process, each for transforming a separate one of the object equations, wherein in the coefficient group calculation process the triangular transforming unit (a) chooses m nonzero coefficients by taking one nonzero coefficient from each of the pivotal equation and the object equations, multiplies each combination of (m−1) of the chosen nonzero coefficients, and sets the m multiplication results into the first coefficient group, m being a positive integer no smaller than 2, and (b) multiplies each of a constant and n coefficients in the pivotal equation by a multiplication result in the first coefficient group for a combination of nonzero coefficients that does not include a nonzero coefficient chosen from the pivotal equation, and sets n+1 values obtained by the multiplications into the second coefficient group, and wherein in each of the transformation subprocesses following the coefficient group calculation process, the triangular transforming unit (a) changes a nonzero coefficient chosen from the object equation in the coefficient group calculation process, to 0 in the object equation, and (b) multiplies each of a constant and n coefficients in the object equation by a multiplication result in the first coefficient group for a combination of nonzero coefficients that does not include the nonzero coefficient chosen from the object equation, and subtracts the n+1 values in the second coefficient group respectively from the n+1 multiplication results.

[0122] With these constructions, the equivalent system of linear equations can be obtained through the triangular transformation.

[0123] Here, when the diagonal elements of the coefficient matrix C are denoted by m_i (i=1,2, . . . , n) and the inverses of the diagonal elements m_i (i=1,2, . . . , n) in the finite field GF(p) are denoted by I_i (i=1,2, . . . , n), the diagonal element inverting unit may include (a) a multiplying unit for computing

[0124] $t_i=\prod _{k=1}^n{m}_k\left(\mathrm{except}{m}_i\right)\mathrm{mod}p\left(i=1,2,\dots ,n\right)$
and

[0125] $t=\prod _{k=1}^n{m}_k\mathrm{mod}p$
(b) a first inverting unit for computing
u=1/t mod p
and (c) a second inverting unit for computing
I_i=u×t_i mod p (i=1,2, . . . ,n)
to find the inverses I₁ (i=1,2, . . . ,n).

[0126] Here, the multiplying unit may calculate

[0127] $\begin{array}{c}{s}_1=m_1\times m_2\mathrm{mod}p\\ s_2=s_1\times m_3\mathrm{mod}p\\ ⋮\\ s_{n-3}=s_{n-4}\times m_{n-2}\mathrm{mod}p\end{array}$

• • [0128] in the stated order, then calculate

[0129] $\begin{array}{c}{t}_n=s_{n-3}\times m_{n-1}\mathrm{mod}p\\ t_{n-1}=s_{n-3}\times m_n\mathrm{mod}p\\ s_n=m_{n-1}\times m_n\mathrm{mod}p\\ t_{n-2}=s_{n-4}\times s_n\mathrm{mod}p\\ s_{n-1}=m_{n-2}\times s_n\mathrm{mod}p\\ t_{n-3}=s_{n-5}\times s_{n-1}\mathrm{mod}p\\ s_{n-2}=s_{n-3}\times s_{n-1}\mathrm{mod}p\\ t_{n-4}=s_{n-6}\times s_{n-2}\mathrm{mod}p\\ s_5=m_4\times s_6\mathrm{mod}p\\ t_3=s_1\times s_5\mathrm{mod}p\\ s_4=m_3\times s_5\mathrm{mod}p\\ t_2=m_1\times s_4\mathrm{mod}p\\ t_1=m_2\times s_4\mathrm{mod}p\end{array}$

• • [0130] in the stated order, and lastly calculate
    t=t_j×m_j
  • [0131] for a value j chosen from a set of positive integers {1,2, . . . ,n}.

[0132] With these constructions, the number of inverse operations needed to compute the inverses of the diagonal elements can be reduced.

[0133] As a result, overall computational complexity of the apparatus for solving a system of equations on a finite field is reduced. Such an apparatus bears high practical value, as it enables high-speed cryptographic or digital signature processing.

[0134] The above object can also be achieved by an apparatus for use in encryption or decryption, for computing an inverse I of an element y in GF(q) which is an extension field of a finite field GF(p), where p is a prime, q=pⁿ, and n is a positive integer, the apparatus including: an equation generating unit for generating a coefficient matrix A and a constant vector b for a system of linear equations Ax=b in n unknowns, using the element y and all coefficients of a generator polynomial of GF(q) whose root is α; an equation solving unit for finding solutions of the system of linear equations Ax=b, the equation solving unit including the above apparatus for solving the system of linear equations Ax=b; and an inverse computing unit for computing the inverse I using the root α and the solutions found by the equation solving unit.

[0135] With this construction, the inverse of the extension field element can be computed with reduced computational complexity.

[0136] The above object can also be achieved by a record medium reproducing apparatus for computing, when copyrighted digital content has been encrypted using a discrete logarithm problem on an elliptic curve E over GF(q) as a basis for security and recorded on a record medium, an inverse I of an element y in GF(q) to decrypt the encrypted digital content recorded on the record medium, where GF(q) is an extension field of a finite field GF(p), p is a prime, q=pⁿ, n is a positive integer, and G is a base point of the elliptic curve E, the record medium reproducing apparatus including: an equation generating unit for generating a coefficient matrix A and a constant vector b for a system of linear equations Ax=b in n unknowns, using the element y and all coefficients of a generator polynomial of GF(q) whose root is α; an equation solving unit for finding solutions of the system of linear equations Ax=b, the equation solving unit including the above apparatus for solving the system of linear equations Ax=b; and an inverse computing unit for computing the inverse I using the root α and the solutions found by the equation solving unit.

[0137] With this construction, the record medium reproducing apparatus can compute the inverse of the extension field element with reduced computational complexity.

[0150] The following is a description of an inversion apparatus 100 according to an embodiment of the present invention.

1.1. Construction of the Inversion Apparatus 100

[0151] The inversion apparatus 100 computes the inverse I of an element x on GF(q) (q=pⁿ, p a prime, n a positive integer) which is an extension field of a predetermined finite field GF(p). In this embodiment, a generator polynomial of the extension field GF(q) is gⁿ−β whose root is α, and the element x is such that x=x₀+x₁α+ . . . +x_n−1αⁿ⁻¹, where α is an element of GF(q) and β, x₀, x₁, . . . x_n−1 are elements of GF(p).

[0152] As shown in FIG. 1, the inversion apparatus 100 is roughly made up of a parameter storing unit 200, an equation generating unit 201, an equation salving unit 202, an inverse computing unit 203, and an inverse storing unit 204.

[0153] Specifically, the inversion apparatus 100 is implemented by a computer system equipped with a microprocessor, a ROM, a RAM, a hard disk, and the like. Through execution of a computer program stored in the hard disk by the microprocessor, the equation generating unit 201, the equation solving unit 202, and the inverse computing unit 203 are realized.

(1) Parameter Storing Unit 200

[0154] The parameter storing unit 200 is implemented by the hard disk. The parameter β of the generator polynomial, the root α, and the elements x₀, x₁, . . . , x_n−1 are stored in the parameter storing unit 200 beforehand.

(2) Equation Generating Unit 201

[0155] The equation generating unit 201 reads β, α, x₀, x₁, . . . , x_n−1 from the parameter storing unit 200, and generates parameters of the following system of equations of y_i (i=0,1,2, . . . ,n−1)

[0156] $\begin{array}{c}{x}_0{y}_0+\beta x_{n-1}{y}_1+\beta x_{n-2}{y}_2+\dots +\beta x_1{y}_{n-1}=1\\ x_1{y}_0+x_0{y}_1+\beta x_{n-1}{y}_2+\dots +\beta x_2{y}_{n-1}=0\\ x_2{y}_0+x_1{y}_1+x_0{y}_2+\dots +\beta x_3{y}_{n-1}=0\\ ⋮\mathrm{ }\\ x_{n-1}{y}_0+x_{n-2}{y}_1+x_{n-3}{y}_2+\dots +x_0{y}_{n-1}=0\end{array}$

• • [0157] using the read values.

[0158] This system of equations can be written simply as
AY=B

• • [0159] where A is a matrix and Y and B are vectors such that

[0160] $A=\left(\begin{array}{ccccc}{x}_0& \beta x_{n-1}& \beta x_{n-2}& \dots & \beta x_1\\ x_1& x_0& \beta x_{n-1}& \dots & \beta x_2\\ x_2& x_1& x_0& \dots & \beta x_3\\ ⋮& ⋮& ⋮& \cdots & ⋮\\ x_{n-1}& x_{n-2}& x_{n-3}& \dots & x_0\end{array}\right)$ $Y=\left(\begin{array}{c}{y}_0\\ y_1\\ y_2\\ ⋮\\ Y_{n-1}\end{array}\right)$ $B=\left(\begin{array}{c}1\\ 0\\ 0\\ ⋮\\ 0\end{array}\right)$

[0161] The parameters of the system of equations generated by the equation generating unit 201 are the matrix A and the vector B. The equation generating unit 201 outputs the generated matrix A and vector B to the equation solving unit 202.

[0162] The equation generating unit 201 also outputs α read from the parameter storing unit 200, to the inverse computing unit 203.

(3) Equation Solving Unit 202

[0163] The equation solving unit 202, when given parameters a_ij (i,j=1,2, . . . ,n) and b_k (k=1,2, . . . ,n) of the following system of linear equations in n unknowns for x_i (i=1,2, . . . ,n) on a predetermined finite field GF(p) (p a prime), solves the system of linear equations in n unknowns on GF(p).

[0164] $\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n=b_2\\ ⋮\mathrm{ }\\ a_{\mathrm{n1}}{x}_1+a_{\mathrm{n2}}{x}_2+\dots +a_{\mathrm{nn}}{x}_n=b_n\end{array}$

[0165] The equation solving unit 202 includes a constant storing unit 101, an equation transforming unit 102, an inverting unit 103, and an equation computing unit 104, as shown in FIG. 1.

(Constant Storing Unit 101)

[0166] The constant storing unit 101 is implemented by the RAM. The constant storing unit 101 receives a matrix M and a vector v from the equation generating unit 201 and stores them. Here, the matrix M and the vector v are respectively

[0167] $M=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ •& •& •& •\\ •& •& •& •\\ a_{\mathrm{n1}}& a_{\mathrm{n2}}& \dots & a_{\mathrm{nn}}\end{array}\right)$ $v=\left(\begin{array}{c}{b}_1\\ b_2\\ •\\ •\\ b_n\end{array}\right).$

[0168] For example, the matrix M is the matrix A and the vector v is the vector B.

(Equation Transforming Unit 102)

[0169] The equation transforming unit 102 reads the matrix M and the vector v from the constant storing unit 101 and triangular transforms the read matrix M and vector v, to generate a matrix M′ (a coefficient matrix consisting of n rows and n columns) and a vector v′ (a constant vector consisting of n elements) for a system of linear equations M′x=v′ in n unknowns that is equivalent to a system of linear equations Mx=v in n unknowns.

[0170] In the triangular transformation, the equation transforming unit 102 transforms the matrix M into an upper triangular matrix without changing each diagonal element of the matrix M to 1.

[0171] Such generated matrix M′ and vector v′ are

[0172] $M^{\prime }=\left(\begin{array}{cccc}{c}_{11}& c_{12}& \dots & c_{1n}\\ c_{21}& c_{22}& \dots & c_{2n}\\ •& •& •& •\\ •& •& •& •\\ c_{\mathrm{n1}}& c_{\mathrm{n2}}& \dots & c_{\mathrm{nn}}\end{array}\right)$ $v^{\prime }=\left(\begin{array}{c}{d}_1\\ d_2\\ •\\ •\\ d_n\end{array}\right)$

[0173] This triangular transformation is carried out in the following way.

[0174] In the triangular transformation, one or more successive transformation processes are performed to generate the matrix M′ and vector v′ of the system of linear equations M′x=v′ from the system of linear equations Mx=v.

[0175] In each transformation process, the equation transforming unit 102 generates, from a system of linear equations in n unknowns, a coefficient matrix and a constant vector for a system of linear equations in n unknowns that is equivalent to the system of linear equations before the transformation. In this embodiment, a system of linear equations in n unknowns that is subjected to the initial transformation process is the system of linear equations Mx=v, whereas a system of linear equations in n unknowns that is obtained as a result of the last transformation process is the system of linear equations M′x=v′.

[0176] In each transformation process, a system of linear equations in n unknowns before the transformation includes one linear equation as a pivotal equation serving as the transformation pivot and one or more linear equations as object equations to be transformed.

[0177] Each transformation process has transformation subprocesses as many as the object equations in the system of linear equations, each for transforming a separate one of the object equations to an equation equivalent to the object equation. Before transforming the object equation to the equivalent equation, a first coefficient group and a second coefficient group are defined in each transformation subprocess.

[0178] The first and second coefficient groups are each a group that contains at least one value related to the pivotal equation. To be more specific, the equation transforming unit 102 sets one nonzero coefficient of the pivotal equation into the first coefficient group. Also, the equation transforming unit 102 multiplies each of a constant and n coefficients of the pivotal equation by one nonzero coefficient of the object equation, and sets n+1 values obtained as a result into the second coefficient group.

[0179] Following this, the equation transforming unit 102 changes the nonzero coefficient of the object equation to 0. The equation transforming unit 102 then multiplies each of a constant and n coefficients of the object equation by the value in the first coefficient group, and subtracts the n+1 values in the second coefficient group respectively from the n+1 multiplication results. In so doing, the object equation is transformed into the equivalent equation where one of its nonzero coefficients has become 0.

[0180] This triangular transformation will be explained in greater detail later.

[0181] The equation transforming unit 102 outputs the generated matrix M′ and vector v′ to the equation computing unit 104, and outputs the diagonal elements c_ii (i=1,2, . . . ,n) of the matrix M′to the inverting unit 103.

[0182] As described earlier, when transforming the matrix M into upper triangular form, the equation transforming unit 102 also transforms the vector v so as not to alter the solutions of the system of linear equations Mx=v. The difference with the conventional triangular transformation lies in that the diagonal elements of the matrix M are not converted to 1.

(Inverting Unit 103)

[0183] The inverting unit 103 receives the diagonal elements c_ii (i=1,2, . . . ,n) of the matrix M′ from the equation transforming unit 102.

[0184] For simplicity's sake, the diagonal elements c_ii (i=1,2, . . . ,n) of the matrix M′ are expressed as m_i (i=1,2, . . . ,n) here.

[0185] The inverting unit 103 solves

[0186] $t_i=\prod _{k=1}^n{m}_k\left(\mathrm{except}{m}_i\right)\mathrm{mod}p\left(i=1,2,\dots ,n\right)$

• • [0187] by first calculating

[0188] $\begin{array}{cc}{s}_1=m_1\times m_2\mathrm{mod}p& \\ s_2=s_1\times m_3\mathrm{mod}p& \\ ⋮& \\ s_{n-3}=s_{n-4}\times m_{n-2}\mathrm{mod}p& \\ t_n=s_{n-3}\times m_{n-1}\mathrm{mod}p& \\ t_{n-1}=s_{n-3}\times m_n\mathrm{mod}p& \\ s_n=m_{n-1}\times m_n\mathrm{mod}p,& t_{n-2}=s_{n-4}\times s_n\mathrm{mod}p\\ s_{n-1}=m_{n-2}\times s_n\mathrm{mod}p,& t_{n-3}=s_{n-5}\times s_{n-1}\mathrm{mod}p\\ s_{n-2}=m_{n-3}\times s_{n-1}\mathrm{mod}p,& t_{n-4}=s_{n-6}\times s_{n-2}\mathrm{mod}p\\ ⋮& \\ s_5=m_4\times s_6\mathrm{mod}p,& t_3=s_1\times s_5\mathrm{mod}p\\ s_4=m_3\times s_5\mathrm{mod}p,& t_2=m_1\times s_4\mathrm{mod}p\\ t_1=m_2\times s_4\mathrm{mod}p& \end{array}$

• • [0189] in this order. The inverting unit 103 then calculates
    t=t_k×m_k mod p
  • [0190] using a predetermined value k (chosen from a set of positive integers {1, 2, . . . , n}), and thereby solves

[0191] $t=\prod _{i=1}^n{m}_i\mathrm{mod}p$

[0192] The inverting unit 103 next computes
u=1/t mod p

• • [0193] and finally obtains the inverses I_i (i=1,2, . . . , n) by
    I_i=u×t_i mod p (i=1,2, . . . n)

[0194] The inverting unit 103 outputs the inverses I_i (i=1,2, . . . n) to the equation computing unit 104.

[0195] Thus, the inverting unit 103 computes, on GF(p), the inverses I_i (i=1,2, . . . , n) of the diagonal elements c_ii (i=1,2, . . . , n) of the matrix M′ which are given from the equation transforming unit 102.

(Equation Computing Unit 104)

[0196] The equation computing unit 104 receives the matrix M′ and the vector v′ from the equation transforming unit 102, and also receives the inverses I_i (i=1,2, . . . ,n) from the inverting unit 103.

[0197] The equation computing unit 104 sets the values n−1, n−2, . . . , 2, 1, 0 in counter j one at a time. For counter j, the equation computing unit 104 uses the matrix M′, the vector v′, and the inverses I_i (i=1,2, . . . ,n) to compute
y_j=I_j+1×d_j+1 mod p

• • [0198] when j=n−1, and compute

[0199] $y_j=I_{j+1}\times \left(d_{j+1}-\sum _{i=j+1}^{n-1}{c}_{j+1i+1}\times y_i\right)\mathrm{mod}p$

• • [0200] when j≠n−1.

[0201] The equation computing unit 104 then outputs the solutions y_j (j=0,1,2, . . . ,n−1) to the inverse computing unit 203.

[0202] The reason that the solutions of the system of linear equations in n unknowns can be found by the equation computing unit 104 is shown below.

[0203] Since the matrix M′ received from the equation transforming unit 102 is an upper triangular matrix, the system of linear equations M′x=v′ can be written as

[0204] $\begin{array}{c}{c}_{11}{x}_0+c_{12}{x}_1+c_{13}{x}_2+\dots +c_{1n}{x}_{n-1}=d_1\\ c_{22}{x}_1+c_{23}{x}_2+\dots +c_{2n}{x}_{n-1}=d_2\\ ⋮\mathrm{ }\\ c_{\mathrm{nn}}{x}_{n-1}=d_n\end{array}$

• • [0205] with the inverses of the diagonal elements c_ii (i=1,2, . . . ,n) of the matrix M′ being I_i (i=1,2, . . . ,n).

[0206] Accordingly, the solution y_n−1 of x_n-1 is
y_n-1=I_nd_n−1 mod p

• • [0207] the solution y_n−2 of x_n−2 is
    y_n−2=I_n−1(d_n−1−c_{n−1 n}y_n−1) mod p
  • [0208] and the solutions y_j (j=n−3,n−4, . . . ,0) of x_j are

[0209] $y_j=I_{j+1}\times \left(d_{j+1}-\sum _{i=j+1}^{n-1}{c}_{j+1i+1}{y}_i\right)\mathrm{mod}p$
(4) Inverse Computing Unit 203

[0210] The inverse computing unit 203 receives the solutions y_j (j=0,1,2, . . . ,n−1) from the equation computing unit 104 in the equation solving unit 202, and receives the root α from the equation generating unit 201. The inverse computing unit 203 calculates the inverse I according to the equation
I=y₀+y₁α+ . . . +y_n−1αⁿ⁻¹

• • [0211] using the received solutions y_j (j=0,1,2, . . . ,n−1) and root α. The inverse computing unit 203 writes the calculated inverse I into the inverse storing unit 204.

[0212] Hence the inverse I of the element x in the extension field GF(q) is obtained.

(5) Inverse Storing Unit 204

[0213] The inverse storing unit 204 is implemented by the hard disk and stores the inverse I of the element x of the extension field GF(q).

1.2. Operation of the Inversion Apparatus 100

[0214] The following is a description on the operation of the above constructed inversion apparatus 100.

(1) General Operation of the Inversion Apparatus 100

[0215] The general operation of the inversion apparatus 100 is explained below with reference to FIG. 2.

[0216] The equation generating unit 201 reads the parameter β, the root α, and x₀, x₁, . . . , x_n−1 from the parameter storing unit 200, and uses them to generate the matrix A and the vector B as the parameters of the system of linear equations AY=B in n unknowns for y_i (i=0,1,2, . . . ,n−1). The equation generating unit 201 outputs the generated matrix A and vector B to the constant storing unit 101 in the equation solving unit 202, and outputs the root α to the inverse computing unit 203 (S101).

[0217] The equation transforming unit 102 in the equation solving unit 202 reads the matrix M and the vector v from the constant storing unit 101 and triangular transforms the read matrix M and vector v, as a result of which the matrix M′ and the vector v′ for the system of linear equations M′x=v′ in n unknowns, that is equivalent to the system of linear equations M′x=v, are generated (S102).

[0218] The inverting unit 103 in the equation solving unit 202 calculates the inverses I_i (i=1,2, . . . ,n) of the diagonal elements c_ii (i=1,2, . . . ,n) of the matrix M′ (S103).

[0219] The equation computing unit 104 in the equation solving unit 202, through the use of the matrix M′, the vector v′, and the inverses I_i (i=1,2, . . . ,n), seeks the solutions y_j (j=0,1,2, . . . , n−1) of the system of linear equations M′x=v′, and outputs the solutions y_j (j=0,1,2, . . . ,n−1) to the inverse computing unit 203 (S104).

[0220] The inverse computing unit 203 receives the solutions y_j (j=0,1,2, . . . ,n−1) from the equation computing unit 104 and the root α from the equation generating unit 201, finds the inverse I of the element x in the extension field GF(q) using the received solutions and root, and writes the inverse I into the inverse storing unit 204 (S105).

(2) Operation of Triangular Transformation by the Equation Transforming Unit 102

[0221] The operation of the triangular transformation by the equation transforming unit 102 is explained in detail below with reference to FIG. 3.

[0222] The equation transforming unit 102 reads the matrix M and the vector v from the constant storing unit 101 (S111), and sets counter j at 1 (S112).

[0223] The equation transforming unit 102 searches the jth column of the matrix M from the jth to nth rows for an element which is not 0 on GF(p), and sets the row number of a nonzero element found first as k (S113). Here, if k≠j (S114), the equation transforming unit 102 changes places between the kth row and the jth row in the matrix M (S115), and changes places between the kth row and the jth row in the vector v (S116).

[0224] The equation transforming unit 102 sets counter i at j+1 (S117), and makes the following settings using a_jj (the element in the jth row and jth column of the matrix M) and a_ij:
a_ij=0
a_ik=a_jja_ik−a_ija_jk for j+1≦k≦n (k=j+1,j+2, . . . ,n)
b_i=a_jjb_i−a_ijb_j

• • [0225] (S118).

[0226] The equation transforming unit 102 then judges whether i=n (S119). If i≠n, the equation transforming unit 102 increments counter i by 1 (S122) and returns to step S118. If i=n, the equation transforming unit 102 judges whether j=n−1 (S120). If j≠n−1, the equation transforming unit 102 increments counter j by 1 (S123) and returns to step S113. If j=n−1, the equation transforming unit 102 sets the matrix M as the matrix M′ and the vector v as the vector v′, and completes the operation.

[0227] As described above, this triangular transformation includes transformation processes which correspond to the separate values of counter j, and each of the transformation processes includes transformation subprocesses which correspond to the separate values of counter i.

(Reason for Equivalence Between Mx=V and M′X=V′)

[0228] The reason why the system of linear equations M′x=v′ generated as a result of the triangular transformation by the equation transforming unit 102 is equivalent to the system of linear equations Mx=v is given below.

[0229] In each transformation process of the triangular transformation, let M_in and v_in be a matrix and a vector before the transformation, M_out and v_out be a matrix and a vector after the transformation, and L_i and L_j be the ith and jth row vectors of the matrix M_in.

[0230] The equation transforming unit 102 calculates
a_jj×L_i−a_ij×L_j

• • [0231] and, having set the resulting row vector as the ith row of the matrix M_out, calculates
    a_jj×b_i−a_ij×b_j
  • [0232] the outcome of which is set as the ith row of the vector v_out. The other elements of M_out and the other elements of v_out are respectively equal to the other elements of M_in and the other elements of v_in. This being the case, the system of linear equations
    M_in·x=v_in
  • [0233] and the system of linear equations
    M_out·x=v_out
  • [0234] have the same solutions, as demonstrated in document 2.

[0235] Also, the equation transforming unit 102 defines a_ij=0 for every i that satisfies j+1≦i≦n. Repeating this process from j=1 to j=n renders all elements in the lower triangle of the matrix 0. Thus, the matrix can be triangular transformed without the solutions of the system of linear equations being altered.

(3) Operation of the Inverting Unit 103

[0236] The operation of the inverting unit 103 is explained in detail below with reference to FIG. 4.

[0237] The inverting unit 103 receives the diagonal elements m_i (i=1,2, . . . ,n) of the matrix M′ from the equation transforming unit 102 (S141), and computes

[0238] $t_i=\prod _{k=1}^n{m}_k\left(\mathrm{except}{m}_i\right)\mathrm{mod}p\left(i=1,2,\dots ,n\right)$

• • [0239] (S142). The inverting unit 103 then computes
    t=t_k×m_k mod p
  • [0240] using the predetermined value k (S143), and also computes
    u=1/t mod p
  • [0241] (S144). The inverting unit 103 finally finds the inverses
    I_i=u×t_i mod p (i=1,2, . . . ,n)
  • [0242] (S145), and outputs the inverses I_i (i=1,2, . . . ,n) to the equation computing unit 104 (S146).
    (4) Operation of the Equation Computing Unit 104

[0243] The operation of the equation computing unit 104 is explained in detail below with reference to FIG. 5.

[0244] The equation computing unit 104 receives the matrix M′ and the vector v′ from the equation transforming unit 102, and receives the inverses I_i (i=1,2, . . . ,n) from the inverting unit 103 (S161). Having set counter j at n−1 (S162), the equation computing unit 104 computes
y_j=I_j+1×d_j+1 mod p

• • [0245] when j=n−1, and computes

[0246] $y_j=I_{j+1}\times \left(d_{j+1}-\sum _{i=j+1}^{n-1}{c}_{j+1i+1}\times y_i\right)\mathrm{mod}p$

• • [0247] when j≠n−1 (S163)

[0248] The equation computing unit 104 judges whether j=0 (S164). If j=0, the equation computing unit 104 outputs the solutions y_j(j=0,1,2, . . . ,n−1) to the inverse computing unit 203 (S166). Otherwise, the equation computing unit 104 decrements counter j by 1 (S165) and returns to step S163.

1.3. Computational Complexity

[0249] The computational complexity of the equation solving unit 202 is evaluated below.

(1) Computational Complexity of the Equation Transforming Unit 102

[0250] In the equation transforming unit 102, computational complexity for one value of counter j (steps S113˜S119 in FIG. 3) is the following.

[0251] First, computational complexity for one value of counter i (step S118) is broken down as shown below.

[0252] (a) In step S118, the calculation a_ik=a_jj×a_ik−a_ij×a_jk is performed for j+1≦k≦n (k=j+1,j+2, . . . ,n). This means two multiplications are repeated (n−(j+1)+1)=(n−j) times, so that computational complexity is (2×(n−j))Mul.

[0253] (b) In step S118, the calculation b_i=a_jj×b_i−a_ij×b_j involves two multiplications, so that computational complexity is 2Mul.

[0254] Since counter i changes from j+1 to n, the computational complexity of steps S113˜S119 for one value of counter j is
(2×(n−j+1))Mul×(n+(j+1)+1)=(2×(n−j)×(n−j+1))Mul

[0255] In steps S112˜S120, counter j changes from 1 to n−1, so that the overall computational complexity of the equation transforming unit 102 is

[0256] $\sum _{j=1}^{n-1}\left(2\times \left(n-j\right)\times \left(n-j+1\right)\right)\mathrm{Mu1}=2\mathrm{Mu1}\times \sum _{j=1}^{n-1}j\left(j+1\right)=2\mathrm{Mu1}\times \left(\sum _{j=1}^{n-1}{j}^2+\sum _{j=1}^{n-1}j\right)=2\mathrm{Mu1}\times \left(1\text{/}6\times n\left(n-1\right)\left(2n-1\right)+1\text{/}2\times n\left(n-1\right)\right)=2\mathrm{Mul}\times 1\text{/}6\times n\left(n-1\right)\left(2n-1+3\right)=1\text{/}3\mathrm{Mu1}\times n\left(n-1\right)\left(2n+2\right)=\left(2\text{/}3\times n\left(n-1\right)\left(n+1\right)\right)\mathrm{Mu1}$
(2) Computational Complexity of the Inverting Unit 103

[0257] The computational complexity of the inverting unit 103 can be broken down as follows.

[0258] (a) Finding s₁˜s_n−3 t_n requires n−2 multiplications, so that computational complexity is (n−2)Mul.

[0259] (b) Finding t_n−1 requires one multiplication, so that computational complexity is 1Mul.

[0260] (c) Finding s_n and t_n−1, s_n−1 and t_n−3, . . . , and s₄ and t₂ requires 2×(n−3) multiplications, so that computational complexity is (2×(n−3))Mul.

[0261] (d) Finding t₁ requires one multiplication, so that computational complexity is 1Mul.

[0262] (e) Finding t requires one multiplication, so that computational complexity is 1Mul.

[0263] (f) Finding u=1/t mod p requires one inversion, so that computational complexity is 1Inv.

[0264] (g) Finding I_i=u×t_i mod p (i=1,2, . . . ,n) requires n multiplications, so that computational complexity is nMul.

[0265] Summing these computational complexity gives the total computational complexity of the inverting unit 103 as
((n−2)+1+2 (n−3)+1+1+n)Mul+1Inv=(4n−5)Mul+1Inv
(3) Computational Complexity of the Equation Computing Unit 104

[0266] In the equation computing unit 104, computational complexity for one value of counter j (steps S163˜S165 in FIG. 5) is as follows.

[0267] To compute
y_j=I_j+1×d_j+1 mod p

• • [0268] when j=n−1 and

[0269] $y_j=I_{j+1}\times \left(d_{j+1}-\sum _{i=j+1}^{n-1}{c}_{j+1i+1}{y}_i\right)\mathrm{mod}p$
when j≠n−1, one multiplication and (n−(j+1)+1) multiplications are needed, which makes the computational complexity of (n−j+1)Mul.

[0270] Since counter j changes from 1 to n, the total computational complexity of the equation computing unit 104 is

[0271] $\sum _{j=1}^n\left(n-j+1\right)\mathrm{Mu1}=\sum _{j=1}^{n}j\mathrm{Mu1}=\left(1\text{/}2\times n\left(n+1\right)\right)\mathrm{Mu1}$
(4) Total Computational Complexity of the Equation Solving Unit 202

[0272] From the foregoing description, the total computational complexity of the equation solving unit 202 is given by
(2/3×n(n−1)(n+1))Mul+(4n−5)Mul+1Inv+(1/2×n(n+1))Mul=(1/6(4n³+3n²+23n−30))Mul+1Inv

[0273] Supposing 1Inv=40Mul in a general-purpose computer when n=5 and |q|=160 (|q| is the bit size of q), the total computational complexity of the equation solving unit 202 can be estimated at 150Mul.

[0274] Thus, the computational complexity of the equation solving unit 202 of the invention is much smaller than that of the prior art. Such an equation solving unit bears huge practical value, as it enables an apparatus to solve a system of equations on a finite field with reduced computational complexity.

[0275] Also, such an equation solving unit enables an apparatus to compute an inverse I of an element x in an extension field GF(q) of a predetermined finite field GF(p) with reduced computational complexity.

1.4. Concrete Example

[0276] The following is a concrete example of the operation of the equation solving unit 202.

[0277] As with the prior art 3, a prime p=31, a generator polynomial f(g)=g⁵−2, and an element x=5α⁴+29α³+6α²+19α+17 of GF(q) are given. A system of equations to be solved is the same as that in the prior art 3, as shown in FIG. 6(a).

[0278] The following calculations are performed:
a₂₁=0
a₂₂=17×17−19×10=6 mod 31
a₂₃=17×10−19×27=29 mod 31
a₂₄=17×27−19×12=14 mod 31
a₂₅=17×12−19×7=9 mod 31
b₂=17×0−19×1=12 mod 31

[0279] When j=1 (i=2), the system of equations is transformed as shown in FIG. 6(b). Here, the element in the first column and second row has become 0 in a coefficient matrix 411.

[0280] As a result of the transformation process for j=1, the system of equations has become as shown in FIG. 6(c), where the elements in the first column and third to fifth rows are 0 in a coefficient matrix 421.

[0281] As a result of the transformation process for j=2, the system of equations has become as shown in FIG. 6(d), where the elements in the second column and third to fifth rows are 0 in a coefficient matrix 431.

[0282] As a result of the transformation process for j=3, the system of equations has become as shown in FIG. 6(e), where the elements in the third column and fourth to fifth rows are 0 in a coefficient matrix 441.

[0283] As a result of the transformation process for j=4, the system of equations has become as shown in FIG. 6(f), where the element in the fourth column and fifth row is 0 in a coefficient matrix 451.

[0284] Next, the diagonal elements in the coefficient matrix 451 are inverted by calculating
s_i=m₁×m₂=17×6=9 mod 31
s₂=s₁×m₃=9×17=29 mod 31
t₅=s₂×m₄=29×6=19 mod 31
t₄=s₂×m₅=29×30=2 mod 31
s₅=m₄×m₅=6×30=25 mod 31
t₃=s₁×s₅=9×25=8 mod 31
s₄=m₃×s₅=17×25=22 mod 31
t₂=m₁×s₄=17×22=2 mod 31
t₁=m₂×s₄=6×22=8 mod 31
t=m₁×t₁=17×8=12 mod 31
u=1/t=1/12=13 mod 31
I₁=u×t₁=13×8=11 mod 31
I₂=u×t₂=13×2=26 mod 31
I₃=u×t₃=13×8=11 mod 31
I₄=u×t₄=13×2=26 mod 31
I₅=u×t₅=13×19=30 mod 31

[0285] Notice that u=1/t=1/12=13 mod 31 is the only inverse operation here.

[0286] Lastly, the system of equations is solved in the following way:

[0287] $\begin{array}{c}{y}_4=I_5\times d_5=30\times 2=29\mathrm{mod}31\\ y_3=I_4\times \left(d_4-c_{45}\times y_4\right)\\ =26\times \left(28-2\times 29\right)=26\mathrm{mod}31\\ y_2=I_3\times \left(d_3-c_{34}\times y_3-c_{35}\times y_4\right)\\ =11\times \left(1-6\times 26-11\times 29\right)=25\mathrm{mod}31\\ y_1=I_2\times \left(d_2-c_{23}\times y_2-c_{24}\times y_3-c_{25}\times y_4\right)\\ =26\times \left(12-29\times 25-14\times 26-9\times 29\right)\\ =25\mathrm{mod}31\\ y_0=I_1\times \left(d_1-c_{12}\times y_1-c_{13}\times y_2-c_{14}\times y_3-c_{15}\times y_4\right)\\ =11\times \left(1-10\times 25-27\times 25-12\times 26-7\times 29\right)\\ =12\mathrm{mod}31\end{array}$
1.5. Applications

[0288] In application of the present invention to an actual communication system such as a cryptographic communication system, a digital signature communication system, or an error correction communication system, parameters such as follows are used.

[0289] For a prime p=2³¹−1, q=pⁿ, n=5, a generator polynomial f(g)=g⁵−g−8, and an element x=x₀+x₁×α+x₂×α²+x₃×α³+x₄×α⁴ of GF(q), a system of equations is defined as

[0290] $(\begin{array}{ccccc}{x}_0& 8x_4& 8x_3& 8x_2& 8x_1\\ x_1& x_0+x_4& x_3+8x_4& x_2+8x_3& x_1+8x_2\\ x_2& x_1& x_0+x_4& x_3+8x_4& x_2+8x_3\\ x_3& x_2& x_1& x_0+x_4& x_3+8x_4\\ x_4& x_3& x_2& x_1& x_0+x_4\end{array})(\begin{array}{c}{y}_0\\ y_1\\ y_2\\ y_3\\ y_4\end{array})=(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\end{array})$
where p, x₀, . . . , x₄, and y₀, . . . , y₄ are each 31 bits long, and q and x are each 155 bits long.
2. Modifications
2.1. Variant

[0291] As a variant of the equation transforming unit 102 in the equation solving unit 202, an equation transforming unit 102a is explained below.

[0292] In the equation transforming unit 102a, each transformation process has one coefficient group calculation process and subsequent transformation subprocesses as many as object equations, each for transforming a separate one of the object equations.

[0293] In the coefficient group calculation process, the equation transforming unit 102a chooses m nonzero coefficients by taking one nonzero coefficient from each of the pivotal equation and the object equations in the coefficient matrix consisting of n rows and n columns, multiplies each combination of (m−1) of the chosen nonzero coefficients, and sets the m multiplication results into a first coefficient group. The equation transforming unit 102a then multiplies each of a constant and n coefficients of the pivotal equation by the multiplication result in the first coefficient group for a combination of nonzero coefficients that does not include the nonzero coefficient of the pivotal equation, and sets n+1 values obtained as a result into a second coefficient group.

[0294] Following this, in each of the transformation subprocesses the equation transforming unit 102a changes a nonzero coefficient chosen from an object equation to 0, multiplies each of a constant and n coefficients of the object equation by the multiplication result in the first coefficient group for a combination of nonzero coefficients that does not include the nonzero coefficient of the object equation, and subtracts the n+1 values in the second coefficient group respectively from the n+1 multiplication results.

[0295] The operation of the equation transforming unit 102a is explained below with reference to FIG. 7. The flowchart in FIG. 7 includes steps S118a˜S118c instead of step S118 in FIG. 3.

[0296] Since the other steps are the same as those in FIG. 3, the following explanation will focus on steps S118a˜S118c.

[0297] In step S118a, the equation transforming unit 102a computes

[0298] $h_k=\prod _{m=j}^n{a}_{\mathrm{mj}}\left(\mathrm{except}{a}_{\mathrm{kj}}\right)$

• • [0299] for each k that satisfies j≦k≦n (k=j, j+1, . . . ,n). In step S118b, the equation transforming unit 102a computes
    w_k=h_j×a_jk
    e=h_j×b_j
  • [0300] for each k that satisfies j+1≦k≦n (k=j+1,j+2, . . . ,n). In step S118c, having set a_ij=0, the equation transforming unit 102a computes
    a_ik=h_i×a_ik−w_k
    b_i=h_i×b_i−e
  • [0301] for each k that satisfies j+1≦k≦n (k=j+1,j+2, . . . ,n).

[0302] An example of the operation of the equation transforming unit 102a is shown below.

[0303] As with the prior art 3, a prime p=31, a generator polynomial f(g)=g⁵⁻², and an element x=5α⁴+29α³+6α²19α17 of GF(q) are given. A system of equations to be solved is the same as that in the prior art 3, as shown in FIG. 8(a).

[0304] When j=1, the equation transforming unit 102a calculates
s₁=a₁₁×a₂₁=17×19=13 mod 31
s₂=s×a₃₁=13×6=16 mod 31
h₅=s₂×a₄₁=16×29=30 mod 31
h₄=s₂×a₅₁=16×5=18 mod 31
s₅=a₄₁×a₅₁=29×5=21 mod 31
h₃=s₁×s₅=13×21=25 mod 31
s₄=a₃₁×s₅=6×21=2 mod 31
h₂=a₁₁×s₄=17×2=3 mod 31
h₁=a₂₁×s₄=19×2=7 mod 31

• • [0305] and then calculates
    w₂=h₁×a₁₂=7×10=8 mod 31
    w₃=h₁×a₁₃=7×27=3 mod 31
    w₄=h₁×a₁₄=7×12=22 mod 31
    w₅=h₁×a₁₅=7×7=18 mod 31
    e=h₁×b₁=7×1=7 mod 31

[0306] When i=2 (j=1), the equation transforming unit 102a calculates
a₂₁=0
a₂₂=h₂×a₂₂−w₂=3×17−8=12 mod 31
a₂₃=h₂×a₂₃−w₃=3×10−3=27 mod 31
a₂₄=h₂×a₂₄−w₄=3×27−22=28 mod 31
a₂₅=h₂×a₂₅−w₅=3×12−18=18 mod 31
b₂=h₂×b₂−e=3×0−7=24 mod 31

[0307] According to this method, only one multiplication is needed to find a_ik unlike the first embodiment which needs two multiplications, so that computational complexity is further reduced.

[0308] With the above computations, the system of equations is transformed as shown in FIG. 8(b), where the element in the first column and second row has become 0 in a coefficient matrix 511.

[0309] As a result of the transformation process for j=1, the system of equations has become as shown in FIG. 8(c), where the elements in the first column and third to fifth rows are 0 in a coefficient matrix 521.

[0310] Next, when j=2, the equation transforming unit 102a calculates
s₁=a₂₂×a₃₂=12×2=24 mod 31
h₅=s₁×a₄₂=24×7=13 mod 31
h₄=s₁×a₅₂=24×25=11 mod 31
s₄=a₄₂×a₅₂=7×25=20 mod 31
h₃=a₂₂×s₄=12×20=23 mod 31
h₂=a₃₂×s₄=2×20=9 mod 31

• • [0311] and then calculates
    w₃=h₂×a₂₃=9×27=26 mod 31
    w₄=h₂×a₂₄=9×28=4 mod 31
    w₅=h₂×a₂₅=9×18=7 mod 31
    e=h₂×b₂=9×24=30 mod 31