Matrix application apparatus, matrix application method and program

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(xq), q denotes an extension degree of the extension field GF(xq), 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 a0, . . . ,ak−1 (a0, . . . ak−1∈GF(xq), b denotes an m-th order vector having elements b0. . . , bm−1 (b0, . . . , bm−1∈GF(xq), A denotes a m−by −k Vandermonde matrix, α denotes a positive integer equal to or smaller than q−d, and
• the matrix application apparatus comprising:
• circuitry configured to:
• designate aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1});
• compute the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
• b
• i
• =
• ∑
• 0
• ≤
• j
• <
• k
• ⁢
• a
• j
• ′
• ⁢
• x
• ij
• -
• d
• j
• ;
• designate gi-hif′ as the value bi for i(i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q;
• and
• update a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j (j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.

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(xq), q denotes an extension degree of the extension field GF(xq), 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, (m−1)(k−1)≥q−d, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . . , ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq), A denotes a m-by-k Vandermonde matrix, and
• the matrix application method comprising:
• computing, by circuitry of a matrix application apparatus, a value bi for i(i∈{0, . . ., m−1}) according to the following formula:
• b
• i
• =
• ∑
• 0
• ≤
• j
• <
• k
• ⁢
• a
• j
• ⁢
• x
• ij
• ;
• and
• designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

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(xq), q denotes an extension degree of the extension field GF(xq), 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 a0, . . . ak−1 (a0, . . . ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq)), A denotes a m-by-k Vandennonde matrix, α denotes a positive integer equal to or smaller than q−d, and
• the matrix application method comprising:
• designating, by circuitry of a matrix application apparatus aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1});
• computing, by circuitry of the matrix application apparatus, the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
• b
• i
• =
• ∑
• 0
• ≤
• j
• <
• k
• ⁢
• a
• j
• ′
• ⁢
• x
• ij
• -
• d
• j
• ;
• designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q;
• and
• updating, by circuitry of the matrix application apparatus, a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j(j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.

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(xq), q denotes an extension degree of the extension field GF(xq), 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, (m−1)(k−1)≥q−d, a denotes a k-th order vector having elements a0, . . . , ak−1 (a0, . . ., ak−1∈GF(xq)), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0, . . . , bm−1∈GF(xq)), A denotes a m-by-k Vandermonde matrix,
• perform a method comprising:
• computing, by circuitry of a matrix application apparatus, a value bi for i (i∈{0, . . . , m−1}) according to the following formula:
• b
• i
• =
• ∑
• 0
• ≤
• j
• <
• k
• ⁢
• a
• j
• ⁢
• x
• ij
• ;
• and
• designating, by circuitry of the matrix application apparatus, gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q.

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(xq), q denotes an extension degree of the extension field GF(xq), 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 a0, . . . , ak−1 (a0, . . . , ak−1∈GF(xq), b denotes an m-th order vector having elements b0, . . . , bm−1 (b0. . . , bm−1∈GF(xq)), A denotes a m-by-k Vandermonde matrix, α denotes a positive integer equal to or smaller than q−d, and
• perform a method comprising:
• designating aj and 0 as a′j and dj, respectively, (a′j=aj, dj=0) for j (j∈{0, . . . , k−1}));
• computing the value bi for i (i∈{0, . . . , m−1}) according to the following formula:
• b
• i
• =
• ∑
• 0
• ≤
• j
• <
• k
• ⁢
• a
• j
• ′
• ⁢
• x
• ij
• -
• d
• j
• ;
• designating gi-hif′ as the value bi for i (i∈{0, . . . , m−1}) by using a polynomial hi obtained by dividing a part of the value bi having an order equal to or higher than q by Xq and a polynomial gi formed by a part of the value bi having an order lower than q;
• and
• updating and a′j and dj according to a′j:=a′jxα and dj:=dj+α, respectively, for i (i∈{0, . . . , m−1}) and j (j∈{0, . . . , k−1}) if i≠m−1 and (i+1)j−d≥q−d.