Inverse element arithmetic apparatus and memory system

An inverse element arithmetic apparatus comprising:

• an initial setting unit that receives input of X and Y and that generates m, n, a number-of-times threshold and f, X and Y representing relatively prime integers, X and Y being used for inverse element arithmetic process, the inverse element arithmetic process being a process of finding U and V satisfying UX+VY=1, m and n indicating effective bit lengths of X and Y, the number-of-times threshold being a threshold determined in accordance with a sum of m and n, f indicating positive/negative of X and Y;
• a word unit processing unit that receives input of X, Y, m, n, and f, that generates r, s, a and b in accordance with m and n when w and t are predetermined integers, that performs correction process, that, as an approximate calculation loop for extended binary GCD process, iterates a first loop in a case where a value of |r−s| is greater than a first threshold and a second loop instead of the first loop in a case where the value of |r−s| is smaller than the first threshold, and that terminates the loop of the extended binary GCD process in a case where a total loop number of times of the first loop and the second loop reaches w, m, n, f being generated in the initial setting unit, r and s indicating high-order w+t bits of X and Y, a and b indicating low-order w bits of X and Y, correction process being a process of updating r, s, a, b, and M so that the values of r, s, a, and b are non-negative based on f, in the first loop values of r, s, a, b, m, and n being updated and an update matrix M being generated or updated, the first threshold being a threshold where high-order bit of |r−s| becomes 0, in the second loop the values of m and n being updated without updating the values of r, s, a, and b as well as the update matrix M;
• a first multiple precision arithmetic unit that receives input of X and Y, receives input of f used in the word unit processing unit and the update matrix M updated by the word unit processing unit, updates the values of X and Y based on the update matrix M, and updates f based on positive/negative of X and Y;
• a second multiple precision arithmetic unit that receives input of the update matrix M updated by the word unit processing unit and that updates the values of U and V based on the update matrix M;
• a control unit that receives input of the number-of-times threshold generated by the initial setting unit, iterates a loop of the inverse element arithmetic process that sequentially operates the word unit processing unit, the first multiple precision arithmetic unit, and the second multiple precision arithmetic unit, and terminates the loop of the inverse element arithmetic process in a case where a loop number of times of the inverse element arithmetic process reaches the number-of-times threshold;
• and
• an output unit that outputs V=Y−1 mod X as an inverse element on a quotient ring Z/XZ in response to the termination of the loop of the inverse element arithmetic process.