A linear feedback shift calculation apparatus, into which input data is input, and which outputs output data, including: an L generation unit which generates q values of q0 to qN−2 represented by: q k = { p 0 ( k = 0 ) p k + ∑ i = 0 k - 1 ⁢ q k - 1 - i × p i ( 1 ≤ k ≤ N - 2 ) Equation ⁢ ⁢ 1 (where, p0, p1, . . . , pN−1, q0, q1, . . . , qN−2 belong to Galois field GF(2)) from coefficients p0 to pN−2 among inputted coefficients p−1 to pN−1 (wherein, N is a natural number of 2 or more); and a matrix calculation unit which outputs the output data calculated from the output data b0 to bN−1 represented by: ( b N - 1 b N - 2 ⋮ b o ) = L × ( U × ( a N - 1 a N - 2 ⋮ a 0 ) + p - 1 × ( a - 1 a - 2 ⋮ a - N ) ) Equation ⁢ ⁢ 2 and L = ( 1 0 … 0 0 0 q 0 1 0 … 0 0 q 1 q 0 1 0 … 0 ⋮ ⋱ ⋱ ⋱ ⋮ q N - 3 q N - 4 … q 0 1 0 q N - 2 q N - 3 … q 1 q 0 1 ) Equation ⁢ ⁢ 3 U = ( p N - 1 p N - 2 … p 2 p 1 p 0 0 p N - 1 p N - 2 … p 2 p 1 0 0 p N - 1 p N - 2 … p 2 ⋮ ⋱ ⋱ ⋱ ⋮ 0 0 … 0 p N - 1 p N - 2 0 0 … 0 0 p N - 1 ) ⁢ from the q values q0 to qN−2, the coefficients p−1 to pN−1 and the input data a−N to a−1, a0 to aN−1.