Finite field multiplication is a key operation in such areas as cryptography and error correction coding by block codes. The operation is far from trivial, since it involves a modulo operation with a primitive polynomial. This paper provides insight into the structure and design of finite field multipliers.
The paper introduces relevant concepts from field theory using vector-matrix notation and corresponding operations. A decomposition theorem and a corresponding algorithm are then presented that permit building a Mastrovito multiplier in the general case. An example is given to show how to perform every step in the algorithm. This could for example be used to build constant multiplier Galois field multipliers. Such multipliers are of great value in particular applications of Reed-Solomon codecs, such as xDSL.
Next it is shown that an efficient multiplier architecture can be obtained even for high Hamming weight irreducible polynomials, a valuable development, since it is traditionally known that complexity grows with such polynomials. The last section is concerned with building efficient multipliers for some special irreducible polynomials: specific types of trinomials and pentanomials, as well as the so-called equally-spaced polynomials. Proofs of the decomposition theorem that permits the building of modular general purpose Mastrovito multipliers is given in the appendix. In a subsequent appendix the theorem for building the matrix needed to compute the Galois field multiplication in the case of high Hamming weight irreducible polynomials is proved. This is one of the few papers available that, besides its theoretical value, also has a direct implementational value.