The present invention reduces the computational cost of field multiplication. A matrix operation device 1 calculates a vector b by multiplying a vector a and a matrix A with one another, given that a represents a k-order vector having a0,..., ak-1∈GF(xq) as elements, b represents an m-order vector having b0,..., bm-1∈GF(xq) as elements, and A represents a Vandermonde's matrix having m number of rows and k number of columns. A polynomial multiplication unit 12 calculates a value bi. An order reduction unit 13 sets gi-hif' as the value bi, using a polynomial expression hi obtained by dividing a section of the value bi that is equal to or greater than the order q by Xq, and a polynomial expression gi, which is the section of the value bi that is less than the q order.
