Bit-parallel finite field multipliers for irreducible trinomials
Citations Over TimeTop 10% of 2006 papers
Abstract
A new formulation for the canonical basis multiplication in the finite fields GF(2/sup m/) based on the use of a triangular basis and on the decomposition of a product matrix is presented. From this algorithm, a new method for multiplication (named transpositional) applicable to general irreducible polynomials is deduced. The transpositional method is based on the computation of 1-cycles and 2-cycles given by a permutation defined by the coordinate of the product to be computed and by the cardinality of the field GF(2/sup m/). The obtained cycles define groups corresponding to subexpressions that can be shared among the different product coordinates. This new multiplication method is applied to five types of irreducible trinomials. These polynomials have been widely studied due to their low-complexity implementations. The theoretical complexity analysis of the corresponding bit-parallel multipliers shows that the space complexities of our multipliers match the best results known to date for similar canonical GF(2/sup m/) multipliers. The most important new result is the reduction, in two of the five studied trinomials, of the time complexity with respect to the best known results.
Related Papers
- → Hybrid multiplier for GF (2 m ) defined by some irreducible trinomials(2004)8 cited
- → Area-Efficient Systolic Multipliers for Finite Field GF(2m) Based on Irreducible Trinomial(2011)3 cited
- → Montgomery Multiplier and Squarer in GF(2m)(2000)9 cited
- GF(2^m)상의 기약 3 항식을 이용한 승산기 설계 ( A Design of Multiplier Over GF(2^m) using the Irreducible Trinomial )(2001)
- Low Space Complexity Bit Parallel Multiplier For Irreducible Trinomial over GF($2^n$)(2008)