Modulo arithmetic device, memory system, and method

A memory system comprising:

• a nonvolatile memory in which firmware is stored;
• and
• a controller configured to control the nonvolatile memory and perform signature verification processing for the firmware, the signature verification processing including calculation of a remainder based on a bitwise operation using a dividend a and a divisor q, wherein
• the controller is configured to, in the calculation of the remainder,
• acquire a first intermediate value by shifting right the dividend a by a shift amount w correlated with a bit length of the divisor q, the shift amount w taking a value equal to or less than the bit length of the divisor q,
• acquire a second intermediate value by multiplying the first intermediate value by a value m,
• acquire a third intermediate value by shifting right the second intermediate value by a shift amount (2k−w), k being a parameter value and taking a value equal to or larger than the bit length of the divisor q,
• acquire a fourth intermediate value by multiplying the third intermediate value by the divisor q,
• acquire a fifth intermediate value by subtracting the fourth intermediate value from the dividend a, and
• calculate the remainder by subtracting a value n-times the divisor q from the fifth intermediate value, n being an integer of 0 or more.