Arithmetic circuit, memory system, and method of controlling nonvolatile memory

An arithmetic circuit comprising:

• a first substitution circuit configured to calculate p/2 first evaluation values by substituting p/2 check values into a first input polynomial, p being an even integer satisfying 2≤p<n, n being an integer of 2 or more, the first input polynomial being represented by first-order to s-th-order coefficients of an error locator polynomial for an error correction code, s being the minimum integer greater than or equal to t/2 or the maximum integer less than or equal to t/2, t being an integer of 2 or more, the error correction code having a code length of n bits to correct an error of t bits or less;
• and
• a second substitution circuit configured to calculate p/2 second evaluation values,
• wherein the arithmetic circuit is configured to, when the number of errors is t/2 or less, output p pieces of error position information including
• p/2 pieces of error position information calculated based on the first evaluation values calculated by the first substitution circuit by substituting p/2 first check values from the first to the p/2-th among the p check values, and
• p/2 pieces of error position information calculated based on the second evaluation values calculated by the second substitution circuit by substituting the first check values into a second input polynomial, the second input polynomial being represented by coefficients obtained by converting the coefficients of the first input polynomial, and
• wherein the arithmetic circuit is configured to, when the number of errors is larger than t/2,
• convert the second evaluation values into third evaluation values, the second evaluation values being calculated by the second substitution circuit by substituting the first check values into a third input polynomial represented by (s+1)-th-order to t-th-order coefficients of the error locator polynomial, and
• output p/2 pieces of error position information calculated based on the first evaluation values, the first evaluation values being calculated by the first substitution circuit by substituting the first check values and the third evaluation values.