Patent ID: 6618483
Filing Date: 2003-09-09
Classification: G06F,H04L

Abstract:
A method of computing an inverse of a number x with a finite field multiplier operating in the finite field GF(2M) and having elements A2i (o&lE;ia) representing the number x as a vector of binary digits xi where xi is the coefficient of A2i in the normal basis representation of x, b) loading in to each of said shift registers the vector of binary digits xi representing the normal basis representation of x2, c) cyclically shifting the binary digits of a first of said registers one cell to provide in said first register a vector representing x4, d) rotating said vectors in said shift registers and cojointly rotating said accumulating register with a m fold cyclic shift to generate in the cells of said accumulating register the m grouped terms representing the vector of the product of x2 and x4, e) loading the vector from the accumulating register to a second of said shift registers, f) repeating the steps of (c), (d), and (e) (gâˆ’2) times where g is a factor of mâˆ’1 to provide in said accumulating register a vector &ggr; which is the normal basis representation of the exponentiation of x&Sum;j=0g-1&it;2j,g) loading the vector representing the normal basis representation of &ggr; in each of said shift registers, h) performing a g-fold cyclic shift the binary digits of the vector in one of said shift registers where g is a factor of mâˆ’1 and g.h=mâˆ’1 to provide a vector representing y2e in said one register, i) rotating said bit elements in said shift registers and said accumulating register to generate grouped terms of the vector representing the product of &ggr; and y2e, j) loading the vector from the accumulating register to the other of said shift registers, k) repeating steps h), i), and j) a total of g(hâˆ’1)-1 times to provide in said accumulating cell a vector of binary digits of the coefficients of the normal basis representation of the inverse of x.