A matrix application apparatus that encodes a vector a into a vector b as a Reed-Solomon code sequence by computing the vector b by multiplying the vector a and a matrix A, wherein x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x q ), q denotes an extension degree of the extension field GF(x 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, n ≥ 2k-1, m = n-k, a denotes a k-th order vector corresponding to a data share having elements a 0 , ..., a k-1 , where a 0 , ..., a k-1 ∈GF(x q ), b denotes an m-th order vector corresponding to a parity share having elements b 0 , ..., b m-1 , where b 0 , ..., b m-1 ∈GF(x q ), A denotes a m-by-k Vandermonde matrix, and the matrix application apparatus comprising: a polynomial multiplication part that computes a value b i for i, where i∈{0, ..., m-1}, according to the following formula: b i = ∑ 0 ≤ j < k a j x ij ; and an order reduction part that designates g i -h i f' as the value b i for i, where i∈{0, ..., m-1}, by using a polynomial h i obtained by dividing a part of the value b i having an order equal to or higher than q by X q and a polynomial g i formed by a part of the value b i having an order lower than q, characterized in that m is set as satisfying (m-1)(k-1) ≤ q-d. x denotes an element of an irreducible polynomial f[X] that generates an extension field GF(x q ), q denotes an extension degree of the extension field GF(x 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, n ≥ 2k-1, m = n-k, a denotes a k-th order vector corresponding to a data share having elements a 0 , ..., a k-1 , where a 0 , ..., a k-1 ∈GF(x q ), b denotes an m-th order vector corresponding to a parity share having elements b 0 , ..., b m-1 , where b 0 , ..., b m-1 ∈GF(x q ), A denotes a m-by-k Vandermonde matrix, and the matrix application apparatus comprising: a polynomial multiplication part that computes a value b i for i, where i∈{0, ..., m-1}, according to the following formula: b i = ∑ 0 ≤ j < k a j x ij ; and an order reduction part that designates g i -h i f' as the value b i for i, where i∈{0, ..., m-1}, by using a polynomial h i obtained by dividing a part of the value b i having an order equal to or higher than q by X q and a polynomial g i formed by a part of the value b i having an order lower than q, characterized in that m is set as satisfying (m-1)(k-1) ≤ q-d. a polynomial multiplication part that computes a value b i for i, where i∈{0, ..., m-1}, according to the following formula: b i = ∑ 0 ≤ j < k a j x ij ; and an order reduction part that designates g i -h i f' as the value b i for i, where i∈{0, ..., m-1}, by using a polynomial h i obtained by dividing a part of the value b i having an order equal to or higher than q by X q and a polynomial g i formed by a part of the value b i having an order lower than q, characterized in that m is set as satisfying (m-1)(k-1) ≤ q-d. <EOS>