To reduce the processing amount of a field multiplication. A matrix application apparatus 1 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 0 , ..., a k-1 (a 0 , ..., a k-1 ˆˆGF(x q )), b denotes an m-th order vector having elements b 0 , ..., b m-1 (b 0 ,..., b m-1 ˆˆGF(x q )), and A denotes a m-by-k Vandermonde matrix. A polynomial multiplication part 12 computes a value b i . An order reduction part 13 designates g i -h i f' as the value b i 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.
