Finite field multiple bit multiplier

Claim 1

A method of computing the product D of two elements B,C of the finite field GF(2 nm ) where n and m are integers greater than 1, the field having components that constitute a normal basis for GF2 nm as an extension of GF2 n , comprising the steps a) representing the element B as a vector of subfield elements b i , where b i is the coefficient of in said normal basis representation of B, b) representing the element C as a vector of subfield elements c i , where c i is the coefficient of in said normal basis representation of C, c) converting the representation of elements B and C to vectors of m subfield elements with each subfield element represented as a n-tuple, d) storing in successive cells of a first m cell recirculating shift register the n-tuples representing the element B, e) storing in successive cells of a second m cell recirculating shift register the n-tuples representing the element C, f) establishing logical connections between the m cells of the first and second shift registers and a m cell product register to provide a m subfield element finite field multiplier in which grouped terms representing the subfield elements of the product D are generated in the respective ones of the m cells of the product register as the contents of said shift registers and product registers are cyclically shifted, said logical connections performing arithmetic operations bit wise on the n-tuples as determined by a grouped term and subfield arithmetic inherent in the subfield elements to provide an n-tuple subfield element in each of the m cells of the product register, and g) continuing cyclic shifting of said registers until all grouped terms are generated.

Claim 9

A method of generating the square of an element x in the finite field GF2 mn and represented as a vector of mn subfield elements which are the coefficients of components of GF2 mn that constitute a normal basis for GF2 mn comprising the steps of arranging in a first register said vector as m subfield elements repr3senting coefficients in the normal basis representation of GF2 m with each of said m subfield elements comprising an n-tuple of n binary digits in respective subcells representing coefficients of a normal basis representation in GF2 n , mapping the permutation of said binary digits resulting from a cyclic shift of the vector as represented in a product normal basis that is the product of said normal bases GF2 m and GF2 n , establishing connections between said one register and another register to replicate said mapping and shifting said binary digits from said one register to another to obtain a representation x 2 as coefficients of the product normal basis.