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 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, 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 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, 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.