We show that the step “modulo the degree-n field generating irreducible polynomial” in the classical definition of the GF (2n) multiplication operation can be avoided. This leads to an alternative representation of the finite field multiplication operation. Combining this representation and the Chinese Remainder Theorem, we design bit-parallel GF (2n) multipliers for irreducible trinomials un+ uk+ 1 on GF (2) where 12k+ uk+ 1 for example, the space complexity of the proposed design is reduced by about 1/8, while the time complexity matches the best result. Our experimental results show that among the 539 values of n such that 4n+ xk+ 1 is irreducible over GF(2) for some k in the range 1 <; k ≤ n=2, the proposed multipliers beat the current fastest parallel multipliers for 290 values of n when (n - 1)/3 ≤ k ≤ n/2: they have the same time complexity, but the space complexities are reduced by 8:4 percent on average.

Besides Karatsuba’s algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design$GF(2^n)$subquadratic multipliers. However, when$GF(2^n)$elements are represented using a polynomial basis or its generalization—shifted polynomial basis—this approach is currently appliable only to fields$GF(2^n)$generated by an irreducible trinomial or a special type of irreducible pentanomials, but not to a general irreducible pentanomial. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial.

The aim of this study is to find more Karatsuba-like formulae for a fixed set of moduli polynomials in GF(2)[x]. To this end, a theoretical framework is established. The authors first generalise the division algorithm, and then present a generalised definition of the remainder of integer division. Finally, a generalised Chinese remainder theorem is used to achieve their initial goal. As a by-product of the generalised remainder of integer division, the authors rediscover Montgomery's N-residue and present a systematic interpretation of definitions of Montgomery's multiplication and addition operations.

The authors describe how a simple way to split input operands allows for fast VLSI implementations of subquadratic GF(2)[x] Karatsuba–Ofman multipliers. The theoretical XOR gate delay of the resulting multipliers is reduced significantly. For example, it is reduced by about 33 and 25% for n = 2t and n = 3t (t > 1), respectively. To the best of our knowledge, this parameter has never been improved since the original Karatsuba–Ofman algorithm was first used to design GF(2n) multipliers in 1990.

A new approach to subquadratic space complexity GF(2n) multipliers has been proposed recently. The corresponding algorithm for software implementations is developed. While its recursive implementation is as simple as that of the Karatsuba algorithm, it requires much less memory to store the look-up table. Therefore it is quite suitable for memory-constrained applications, for example smart cards.

Based on Toeplitz matrix-vector products and coordinate transformation techniques, we present a new scheme for subquadratic space complexity parallel multiplication in GF(2n) using the shifted polynomial basis. Both the space complexity and the asymptotic gate delay of the proposed multiplier are better than those of the best existing subquadratic space complexity parallel multipliers. For example, with n being a power of 2, the space complexity is about 8 percent better, while the asymptotic gate delay is about 33 percent better, respectively. Another advantage of the proposed matrix-vector product approach is that it can also be used to design subquadratic space complexity polynomial, dual, weakly dual, and triangular basis parallel multipliers. To the best of our knowledge, this is the first time that subquadratic space complexity parallel multipliers are proposed for dual, weakly dual, and triangular bases. A recursive design algorithm is also proposed for efficient construction of the proposed subquadratic space complexity multipliers. This design algorithm can be modified for the construction of most of the subquadratic space complexity multipliers previously reported in the literature

For original paper see P.L. Montgomery, ibid., vol.54, no.3, p.362-369, (2005). We show that multiplication complexities of n-term Karatsuba-Like formulae of GF(2)[x] (7w

Based on a recently proposed Toeplitz matrix-vector product approach, a subquadratic computational complexity scheme is presented for multiplications in binary extended finite fields using type I and II optimal normal bases.

Applying the matrix-vector product idea of the Mastrovito multiplier to the GF(2^{m}) Montgomery multiplication algorithm, we present a new parallel multiplier for irreducible trinomials. This multiplier and the corresponding shifted polynomial basis (SPB) multiplier have the same circuit structure for the same set of parameters. Furthermore, by establishing isomorphisms between the Montgomery and the SPB constructions of GF(2^{m}), we show that the Montgomery algorithm can be used to perform the SPB multiplication without any changes and vice versa.

Based on a new representation of GF(2/sup n/), we present two multipliers for all irreducible trinomials. Space complexities of the multipliers match the best results. The time complexity of one multiplier is T/sub A/ + (1 + [log/sub 2/ n])T/sub X/ for all irreducible trinomials, where T/sub A/ and T/sub X/ are the delay of one 2-input AND and XOR gates, respectively.