Matrix application apparatus, matrix application method and program

Abstract

To reduce the processing amount of a field multiplication. A matrix application apparatus computes a vector b by multiplying a vector a and a matrix A, provided that a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q)), and A denotes a m-by-k Vandennonde matrix. A polynomial multiplication part computes a value b.sub.i. An order reduction part designates g.sub.ih.sub.if as the value b.sub.i by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q.

Claims

1. A matrix application apparatus that computes a vector b by multiplying a vector a and a matrix A, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m1)(k1)qd, a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1 GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1(b.sub.0, . . . , b.sub.m1GF(x.sup.q)), A denotes a m-by-k Vandermonde matrix, and the matrix application apparatus comprising: circuitry configured to: compute a value b.sub.i for i (i{0, . . . , m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j{x}^{\mathrm{ij}};$ and designate g.sub.i-h.sub.if as the value b.sub.i for i (i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q.

2. A matrix application apparatus that computes a vector b by multiplying a vector a and a matrix A, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a.sub.0, . . . ,a.sub.k1 (a.sub.0, . . . a.sub.k1GF(x.sup.q), b denotes an m-th order vector having elements b.sub.0. . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q), A denotes a mby k Vandermonde matrix, denotes a positive integer equal to or smaller than qd, and the matrix application apparatus comprising: circuitry configured to: designate a.sub.j and 0 as a.sub.j and d.sub.j, respectively, (a.sub.j=a.sub.j, d.sub.j=0) for j (j{0, . . . , k1}); compute the value b.sub.i for i (i{0, . . . , m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j^{}{x}^{\mathrm{ij}-d_j};$ designate g.sub.i-h.sub.if as the value b.sub.i for i(i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q; and update a.sub.j and d.sub.j according to a.sub.j:=a.sub.jx.sup. and d.sub.j:=d.sub.j+, respectively, for i (i{0, . . . , m1}) and j (j{0, . . . , k1}) if im1 and (i+1)jdqd.

3. A matrix application method of computing a vector b by multiplying a vector a and a matrix A, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m1)(k1)qd, a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q), A denotes a m-by-k Vandermonde matrix, and the matrix application method comprising: computing, by circuitry of a matrix application apparatus, a value b.sub.i for i(i{0, . . ., m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j{x}^{\mathrm{ij}};$ and designating, by circuitry of the matrix application apparatus, g.sub.i-h.sub.if as the value b.sub.i for i (i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q.

4. A matrix application method of computing a vector b by multiplying a vector a and a matrix A, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2,m denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a.sub.0, . . . a.sub.k1 (a.sub.0, . . . a.sub.k1GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q)), A denotes a m-by-k Vandennonde matrix, denotes a positive integer equal to or smaller than qd, and the matrix application method comprising: designating, by circuitry of a matrix application apparatus a.sub.j and 0 as a.sub.j and d.sub.j, respectively, (a.sub.j=a.sub.j, d.sub.j=0) for j (j{0, . . . , k1}); computing, by circuitry of the matrix application apparatus, the value b.sub.i for i (i{0, . . . , m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j^{}{x}^{\mathrm{ij}-d_j};$ designating, by circuitry of the matrix application apparatus, g.sub.i-h.sub.if as the value b.sub.i for i (i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q; and updating, by circuitry of the matrix application apparatus, a.sub.j and d.sub.j according to a.sub.j:=a.sub.jx.sup. and d.sub.j:=d.sub.j+, respectively, for i (i{0, . . . , m1}) and j(j{0, . . . , k1}) if im1 and (i+1)jdqd.

5. A non-transitory computer readable medium including computer executable instructions that make a matrix application apparatus, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, m denotes an integer equal to or greater than 1, (m1)(k1)qd, a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . ., a.sub.k1GF(x.sup.q)), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0, . . . , b.sub.m1GF(x.sup.q)), A denotes a m-by-k Vandermonde matrix, perform a method comprising: computing, by circuitry of a matrix application apparatus, a value b.sub.i for i (i{0, . . . , m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j{x}^{\mathrm{ij}};$ and designating, by circuitry of the matrix application apparatus, g.sub.i-h.sub.if as the value b.sub.i for i (i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q.

6. A non-transitory computer readable medium including computer executable instructions that make a matrix application apparatus, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x.sup.q), q denotes an extension degree of the extension field GF(x.sup.q), d denotes the order of a term of the highest order of a polynomial f obtained by removing a term of the highest order from the irreducible polynomial f[X], k denotes an integer equal to or greater than 2, in denotes an integer equal to or greater than 1, a denotes a k-th order vector having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q), b denotes an m-th order vector having elements b.sub.0, . . . , b.sub.m1 (b.sub.0. . . , b.sub.m1GF(x.sup.q)), A denotes a m-by-k Vandermonde matrix, denotes a positive integer equal to or smaller than qd, and perform a method comprising: designating a.sub.j and 0 as a.sub.j and d.sub.j, respectively, (a.sub.j=a.sub.j, d.sub.j=0) for j (j{0, . . . , k1})); computing the value b.sub.i for i (i{0, . . . , m1}) according to the following formula: $b_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j^{}{x}^{\mathrm{ij}-d_j};$ designating g.sub.i-h.sub.if as the value b.sub.i for i (i{0, . . . , m1}) by using a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having an order equal to or higher than q by X.sup.q and a polynomial g.sub.i formed by a part of the value b.sub.i having an order lower than q; and updating and a.sub.j and d.sub.j according to a.sub.j:=a.sub.jx.sup. and d.sub.j:=d.sub.j+, respectively, for i (i{0, . . . , m1}) and j (j{0, . . . , k1}) if im1 and (i+1)jdqd.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram illustrating a functional configuration of a matrix application apparatus according to a first embodiment;

(2) FIG. 2 is a diagram illustrating a process flow of a matrix application method according to the first embodiment;

(3) FIG. 3 is a diagram illustrating a functional configuration of a matrix application apparatus according to a second embodiment;

(4) FIG. 4 is a diagram illustrating a process flow of a matrix application method according to the second embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(5) Before describing an embodiment, a principle of the present invention will be described.

(6) The following description will be made on the assumption that x represents an element X of an extension field GF(2.sup.64) expressed by an irreducible polynomial f[X]=X.sup.64+X.sup.4+X.sup.3+X.sup.2+X+1. x is 2 in an integer expression.

(7) GF(2.sup.64) is a set of remainders of a division of a polynomial by a 64-th order polynomial f[X] whose coefficients are integers modulo 2 (division as polynomials). GF(2.sup.64) is a field on which the four arithmetic operations are possible. GF(2.sup.64) may also be regarded as a 64-th order vector of bits with a special arithmetic. GF(2.sup.64) can be expressed by a 64-bit integer, a term x.sup.i of which is expressed as 2.sup.i. For example, 1+x+x.sup.3 is expressed as 2.sup.0+2.sup.1+2.sup.3=11.

(8) Multiplication of a and b (a, bGF(2.sup.64)) is an operation of multiplying two 63-th order polynomials a and b (see the formula (8)) by each other and then dividing the product by the 64-th order polynomial f (see the formula (9)). A coefficient of a -th order term is expressed by the formula (10).

(9) $\begin{array}{cc}a=\underset{1<64}{\overset{}{.Math.}}{a}_i{x}^i,b=\underset{1<64}{\overset{}{.Math.}}{b}_i{x}^i& \left(8\right)\\ \underset{i<64}{\overset{}{.Math.}}\underset{j<64}{\overset{}{.Math.}}{a}_i{b}_j{x}^{i+j}\mathrm{mod}f& \left(9\right)\\ {}_{i+j=}{a}_i{b}_j& \left(10\right)\end{array}$

(10) In the formula (9), a process of taking a modulus f of the 126-th order polynomial to provide a 63-th order polynomial is referred to as reduction. The reduction is achieved by using the equivalence relation expressed by the formula (11).
F=x.sup.64+x.sup.4+x.sup.3+x+1=0 mod f(11)
The formula (11) can be transformed into the formula (12), which represents a relation that reduces the 64-th order teen to a fourth-order formula.
x.sup.64=x.sup.4+x.sup.3+x+1 mod f(12)

(11) As shown by the formula (13), the order of any 64-th or higher order term can be reduced by 60.
x.sup.64+n=x.sup.n(x.sup.4+x.sup.3+X+1)mod f(13)

(12) The 126-th order polynomial can be expressed by a 63-th order polynomial g and a 62-th order polynomial h according to the formula (14).
g+x.sup.64h=g+(x.sup.4+x.sup.3+x+1)h mod f(14)

(13) A multiplication (x+1)a of an arbitrary element a and x+1 can be expressed by the formula (15).
xa+a=xaa.(15)

(14) In addition, since the order of each term of x.sup.na is n higher than the order of the corresponding term of a, each term of x.sup.na is equivalent to 2.sup.n times the term in the integer expression or the term left-shifted by n bits. Thus, x.sup.na can be expressed by the formula (16).
(x.sup.4+x.sup.3+x+1)h=(h4)(h3)(h1)h(16)

(15) Since h is a 62-th order polynomial, the term
(h4)(h3)

(16) in the formula (16) is a 64-th or higher order polynomial, and the order needs to be further reduced. The part of 64-th or higher order is expressed by the formula (17).
x.sup.4(h.sub.62x.sup.62+h.sub.61x.sup.61+h.sub.60x.sup.60)+x.sup.3(h.sub.62x.sup.62+h.sub.61x.sup.61)=x.sup.64((h60)(h61))(17)

(17) Considering that in the case of the 64-bit integer, any number is truncated to 64 bits, computation can be performed according to the formula (18).
X.sup.64(h(h60)(h61))=(x.sup.4+x.sup.3+x+1)(h(h60)(h61))=(x.sup.3+1)(x+1)h(h60)(h6))(18)

(18) In multiplication, if one of the multiplier is a number with 61 bits or a smaller number of bits (more strictly, if the total number of bits of the multipliers is equal to or less than 125), the formula (19) holds, so that the reduction can be made more efficient.
(h60)(h61)=0(19)

(19) Thus, considering the processing amount including the reduction, the multiplication by a 61-bit number with only one bit being 1, that is, 2.sup.i where 0i60 is quick.

(20) For the conventional error correcting code, a parity share is generated by using the Vandermonde matrix. The parity share is computed from k inputs a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)) according to the formula (20). GF(x.sup.q) is an extension field that is generated from an irreducible polynomial f[X] and has an extension degree of q. x denotes an element of the irreducible polynomial fin and f[X]=X.

(21) $\begin{array}{cc}\underset{0j<k}{\overset{}{.Math.}}{a}_j{x}^{\mathrm{ij}}& \left(20\right)\end{array}$

(22) When the field is an extension field, the computation can be made more efficient. It is assumed that a part of the irreducible polynomial f that excludes the term of the highest order is denoted as f. It is also assumed that the order of the term of the highest order of the polynomial f is denoted by d. Then, if a relation (m1)(k1)qd holds, the multiplication is simpler than normal as described below.

(23) If i is smaller than q, x.sup.i=X.sup.i. Assuming that the input a is expressed by the formula (21), the result of the polynomial multiplication is as shown by the formula (22).

(24) $\begin{array}{cc}\underset{j<q}{\overset{}{.Math.}}{a}_j{X}^j& \left(21\right)\\ {\mathrm{aX}}^i=\left(\underset{j<q}{\overset{}{.Math.}}{a}_j{X}^j\right)X^i& \left(22\right)\end{array}$

(25) Since the order is equal to or higher than q, a remainder with respect to f is determined based on f0X.sup.qf. That is, provided that a part of aX.sup.i comprising the terms of orders lower than q is denoted by g, and a polynomial obtained by dividing a part of aX.sup.i comprising the terms of q-th or higher orders by X.sup.q is denoted by h, a relation aX.sup.ighf holds. In extension field multiplication, such order reduction is repeated until the order of ghf is q1. If i is equal to or smaller than qd, the order of aX.sup.i is only q1+qd2qd1, and the order of h is only qd1. Since f is a d-th order polynomial, the order of hf is only q1, and one order reduction suffices.

(26) In the following, embodiments of the present invention will be described in detail. In the drawings, components having the same function are denoted by the same reference numerals, and redundant descriptions thereof will be omitted.

(27) [First Embodiment]

(28) As illustrated in FIG. 1, a matrix application apparatus 1 according to a first embodiment comprises a vector input part 10, a matrix generation part 11, a polynomial multiplication part 12, an order reduction part 13, and a vector output part 14. A matrix application method according to the first embodiment is achieved by the matrix application apparatus 1 performing processings in steps illustrated in FIG. 2.

(29) The matrix application apparatus 1 is a special apparatus formed by a well-known or dedicated computer in which a special program is loaded, the computer having a central processing unit (CPU: Central Processing Unit), a main memory (RAM: Random Access Memory), and other components. The matrix application apparatus 1 performs the processings under the control of the central processing unit. Data input to the matrix application apparatus 1 and data resulting from the processings are stored in the main memory, and the data stored in the main memory is loaded to the central processing unit and used for other processings. At least part of the processing parts of the matrix application apparatus 1 may be formed by hardware, such as an integrated circuit.

(30) With reference to FIG. 2, a procedure of the matrix application method according to the first embodiment will be described.

(31) In step S10, a k-th order vector a=(a.sub.0, . . . , a.sub.k1) having elements a.sub.0, . . . , a.sub.k1 (a.sub.0, . . . , a.sub.k1GF(x.sup.q)) is input to the vector input part 10. The vector a is fed to the polynomial multiplication part 12. The vector a is defined by the formula (23)

(32) 0$\begin{array}{cc}a=\left(\begin{array}{c}{a}_0\\ \mathrm{.Math.}\\ a_{k-1}\end{array}\right)& \left(23\right)\end{array}$

(33) In step S11, the matrix generation part 11 generates an m-by-k Vandermonde matrix A. m and k are values for which a relation (m1)(k1)qd holds. The matrix A is fed to the polynomial multiplication part 12. The matrix A is defined by the formula (24).
A.sub.ij=x.sup.(ik)j(24)
where
i{0, . . . , m1}, j{0, . . . , k1}

(34) That is, the matrix A is an m-by-k matrix expressed by the formula (25).

(35) $\begin{array}{cc}\underset{\underset{k\mathrm{columns}}{}}{\left(\begin{array}{ccccc}1& 1& 1& \mathrm{.Math.}& 1\\ 1& x& x^2& \mathrm{.Math.}& x^{k-1}\\ 1& x^2& x^4& \mathrm{.Math.}& x^{2\left(k-1\right)}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& & \mathrm{.Math.}\\ 1& x^{m-1}& x^{2\left(m-1\right)}& \mathrm{.Math.}& x^{\left(m-1\right)\left(k-1\right)}\end{array}\right)}\}m\mathrm{rows}& \left(25\right)\end{array}$

(36) In step S12, the polynomial multiplication part 12 computes a value b.sub.i for i (i{0, . . . , m1}) according to the formula (26). Values b.sub.0, . . . , b.sub.m1 are fed to the order reduction part 13.

(37) $\begin{array}{cc}{b}_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j{x}^{\mathrm{ij}}& \left(26\right)\end{array}$

(38) In step S13, the order reduction part 13 generates, for i (i{0, . . . , m1}), a polynomial h.sub.i obtained by dividing a part of the value b.sub.i having q-th or higher orders by X.sup.q and a polynomial g.sub.i that is a part of the value b.sub.i having orders lower than q. g.sub.ih.sub.if is computed from the polynomials h.sub.i and g.sub.i, to update the value b.sub.i. Updated values b.sub.0, . . . , b.sub.m1 are fed to the vector output part 14.

(39) The processings in steps S12 and S13 are performed for each i (i{0, . . . , m1}). In this way, the values b.sub.0, . . . , b.sub.m1 are computed. The processings for different values of i can be performed in parallel.

(40) In step S14, the vector output part 14 outputs an m-th vector b (b=(b.sub.0, . . . , b.sub.m1)) having values b.sub.0, . . . , b.sub.m1 as elements.

(41) In the matrix application method according to the first embodiment, a relation (m1)(k1)qd holds, so that one reduction suffices in all field multiplications. Thus, the processing amount of the multiplication including reductions is reduced.

(42) [Second Embodiment]

(43) A second embodiment is an extension in which the processing amount of the field multiplication is reduced even if the relation (m1)(k1)qd does not hold.

(44) As illustrated in FIG. 3, as with the matrix application apparatus 1 according to the first embodiment, a matrix application apparatus 2 according to the second embodiment comprises the vector input part 10, the matrix generation part 11, the polynomial multiplication part 12, the order reduction part 13, and the vector output part 14. The matrix application apparatus 2 further comprises a vector copy part 15 and a vector update part 16. A matrix application method according to the second embodiment is achieved by the matrix application apparatus 2 performing processings in steps illustrated in FIG. 4.

(45) With reference to FIG. 4, a procedure of the matrix application method according to the second embodiment will be described. The following description will be focused mainly on differences from the first embodiment described above.

(46) In step S15, the vector copy part 15 designates a.sub.j as a.sub.i (a.sub.j=a.sub.j) for j (j{0, . . . , k1}). In addition, the vector copy part 15 designates 0 as d.sub.j (d.sub.j=0). A vector a (a=(a.sub.0, . . . , a.sub.k1)) and values d.sub.0, . . . , d.sub.k1 are fed to the polynomial multiplication part 12.

(47) In step S11, the matrix generation part 11 generates an m-by-k Vandelinonde matrix A. Unlike the first embodiment, the relation (m1)(k1)qd may not hold. The matrix A is fed to the polynomial multiplication part 12.

(48) In step S12, the polynomial multiplication part 12 computes the value b.sub.i for i (i{0, . . . , m1}) according to the formula (27). Values b.sub.0, . . . , b.sub.m1 are fed to the order reduction part 13.

(49) $\begin{array}{cc}{b}_i=\underset{0j<k}{\overset{}{.Math.}}{a}_j^{}{x}^{\mathrm{ij}-d_j}& \left(27\right)\end{array}$

(50) In step S16, for j (j{0, . . . , k1}), if im1 and (i+1)jdqd, the vector update part 16 updates a.sub.j: and d.sub.j: according to a.sub.j: =a.sub.jx.sup., and d.sub.j: =d.sub.j+, respectively. denotes a positive integer equal to or smaller than qd. The updated vector a (a=(a.sub.0, a.sub.k1)) and the updated values d.sub.0, . . . , d.sub.k1 are fed to the polynomial multiplication part 12.

(51) Although the second embodiment is inferior to the first embodiment in reduction of the processing amount, the second embodiment is sufficiently effective in quickening the processing if the number of times of update by the vector update part 16 is low (that is, if a is appropriately set).

(52) [Third Embodiment]

(53) In the embodiments described above, if the order of the extension field is a power of 2, the addition is simply an exclusive-OR (XOR) operation. In addition, since X is 2 in an integer expression, the polynomial multiplication (a.sub.ix.sup.ij) is simply an ij bit shift. Thus, the processing is more efficiently performed by a computer.

(54) The present invention is advantageous due to the fact that, with the Vandemionde matrix, x of the right ax of the multiplication is fixed in a simple range. If the order of any of a.sub.iX.sup.j in the polynomial multiplication exceeds 2qd1, one order reduction does not suffice. And the polynomial multiplication of x.sup.ij is simply a bit shift operation because all the elements of the Vandermonde matrix are powers of x.

(55) The present invention is not limited to the embodiments described above, and modifications can be made as required without departing from the spirit of the present invention. The various processings described above with regard to the embodiments are not necessarily sequentially performed in the order described above but also can be performed in parallel with or independently of each other depending on the processing capacity of the apparatus that perfolins the processings or as required.

(56) [Program and Storage Medium]

(57) When a computer carries out the various processing functions of the apparatus according to the embodiments described above, the specific processings of the functions that the apparatus needs to have are described in a program. The various processing functions of the apparatus described above are implemented on the computer by the computer executing the program.

(58) The program that describes the specific processings can be recorded in a computer readable recording medium. Any computer readable recording medium can be used, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory.

(59) The program can be distributed by selling, transferring or lending a portable recording medium, such as a DVD, or a CD-ROM, on which the program is recorded, for example. Furthermore, the program may be distributed by storing the program in a memory of a server computer and transferring the program from the server computer to another computer.

(60) The computer that executes the program first temporarily stores, in a memory thereof, the program recorded on a portable recording medium or transferred from a server computer, for example. When performing the processings, the computer reads the program from the memory of the computer and performs the processings according to the read program. In an alternative implementation, the computer may read the program directly from the portable recording medium and perform the processings according to the program, or the computer may perform the processings according to the program each time the computer receives the program transferred from the server computer. As a further alternative, the processings described above may be performed on an application service provider (ASP) basis, in which the server computer does not transfer the program to the computer, and the processings are implemented only through execution instruction and result acquisition. The program according to the embodiments of the present invention includes a quasi-program, which is information to be processed by a computer (such as data that is not a direct instruction to a computer but has a property that defines the processings performed by the computer).

(61) Although the apparatus according to the embodiments of the present invention have been described as being implemented by a computer executing a predetermined program, at least part of the specific processings may be implemented by hardware.