Electronics Guide

Polynomial Representation

An element of GF(2^m) is represented as a polynomial of degree less than m whose coefficients are drawn from GF(2). A polynomial such as x³ + x + 1 therefore corresponds to the coefficient vector (1, 0, 1, 1), which is stored in hardware as the m-bit word 1011. There are exactly 2^m such polynomials, matching the field's order. This correspondence between polynomials and bit vectors is the foundation of every hardware implementation: a register holding m bits holds one field element, and the bit positions correspond to ascending powers of x.

• Degree bound: Valid elements have degree at most m − 1, so an m-bit register represents every element exactly once.
• Coefficient field: Each coefficient is a single bit, an element of GF(2).
• Zero and one: The additive identity is the all-zero word, and the multiplicative identity is the polynomial 1.
• Bit ordering: A consistent convention must be fixed so that hardware and software agree on which bit carries which power of x; the common choice maps the least significant bit to the constant term x⁰ and the most significant bit to x^m−1. The convention is arbitrary, and at least one widely deployed standard reverses it, so interoperating code must state which end it uses.

Alternative Bases

The polynomial representation described above uses the standard, or polynomial, basis, in which the basis elements are the powers 1, x, x², and so on up to x^m−1. This basis is the most common because multiplication and reduction are straightforward. Two other bases appear in specialized designs and offer different trade-offs.

• Normal basis: Uses the set of successive squares of a single element, so squaring becomes a simple cyclic shift of the coefficient word, which benefits exponentiation-heavy computations such as inversion.
• Dual basis: Defined relative to a trace function; it simplifies certain serial multiplier structures such as the Berlekamp multiplier.
• Basis conversion: Changing basis is a linear transformation over GF(2) and can be realized as a fixed matrix of XOR gates when interoperation is required.

Choosing the Reduction Polynomial

For any given m there are several irreducible polynomials, and the choice affects the cost of reduction hardware. Designers prefer polynomials with few nonzero terms because each nonzero term in the reduction polynomial contributes XOR gates to the reduction network.

• Trinomials: Polynomials of the form x^m + x^k + 1 minimize reduction hardware and exist for many but not all values of m. Degrees 8 and 128 are two of the exceptions: no irreducible trinomial exists at either degree, which is why the two best-known standardized binary fields both settle for five terms.
• Pentanomials: Polynomials with five terms are used when no suitable trinomial exists for a given degree.
• Standardized choices: The Advanced Encryption Standard fixes GF(2⁸) with the pentanomial x⁸ + x⁴ + x³ + x + 1, written 0x11B, while Galois/Counter Mode operates in GF(2¹²⁸) modulo x¹²⁸ + x⁷ + x² + x + 1. Standardizing the reduction polynomial is what guarantees interoperability between independent implementations, and the bit-ordering convention has to be standardized with it: Galois/Counter Mode reverses the mapping given above, placing the constant term in the leftmost bit of a block rather than the rightmost, so its multiplicative identity is the block 0x80 followed by fifteen zero bytes.

Primitivity and Field Generators

A primitive polynomial is an irreducible polynomial whose root generates the entire multiplicative group of the field. The multiplicative group of GF(2^m) contains the 2^m − 1 nonzero elements, and when the root, conventionally denoted by the symbol α, is a generator, every nonzero element can be written as a power of α. The successive powers α⁰, α¹, α², and so on cycle through all nonzero elements before returning to α⁰.

Primitivity is a strictly stronger condition than irreducibility, and treating the two as interchangeable is a durable source of implementation errors. Every irreducible polynomial of degree m defines a valid field, but only some of them make x itself a generator. The Advanced Encryption Standard supplies the cautionary example. Its reduction polynomial is irreducible, so GF(2⁸) modulo 0x11B is a genuine field, yet the element x has multiplicative order 51 rather than 255: its powers close on a subgroup of 51 elements and never reach the remaining 204. That field does have generators, 128 of them, and the smallest is 0x03, the element x + 1; x simply is not one. A design that needs a generator must test for primitivity, not merely confirm irreducibility.

• Generator element: When the reduction polynomial is primitive, the element α = x is a generator of the multiplicative group. When the polynomial is irreducible but not primitive, some other element has to play that part.
• Cyclic structure: The powers of a generator repeat with period 2^m − 1, which is precisely the structure exploited by the log and antilog tables described below.
• Order divides the group: The order of any element divides 2^m − 1, so a non-generator produces a proper subgroup. For m = 8 the group order factors as 3 × 5 × 17, which is why the order 51 seen above is possible at all.
• Maximal-length sequences: The same primitivity condition that makes α a generator makes a linear feedback shift register with the corresponding feedback taps produce a maximal-length sequence.

Shift-and-XOR Multiplication

The bit-serial multiplication algorithm mirrors the shift-and-add method for integers but replaces addition with XOR and discards carries. The algorithm scans the bits of one operand, conditionally accumulating shifted copies of the other operand, and reduces each shifted copy whenever a shift carries it to degree m.

• Conditional accumulation: For each bit of the multiplier that equals one, the current shifted multiplicand is XORed into the product.
• Shift and reduce: After each step the multiplicand is shifted left by one position; if the shift sets the bit at position m, the reduction polynomial is XORed in to bring the value back into range.
• Latency: The serial algorithm completes in m iterations, trading throughput for a very small circuit.

The xtime Operation

Multiplication by the element x, often called the xtime operation in the context of the Advanced Encryption Standard, is the elementary building block of field multiplication. It shifts the coefficient word left by one bit and, if the shifted-out bit was set, XORs in the reduction polynomial. Repeated application of xtime, combined with XOR accumulation, expresses multiplication by any constant.

• Single-step reduction: Multiplying by x can raise the degree by at most one, so at most one conditional reduction is required per step.
• Constant decomposition: A constant multiplier such as multiplication by the element 0x03 is computed as xtime of the operand XORed with the operand itself, because 0x03 is the polynomial x + 1.
• Reuse: Because xtime is small and fast, iterated xtime underlies both the MixColumns transform of block ciphers and the syndrome evaluation of cyclic codes.
• Not a generator by default: Iterating xtime walks the powers of x, so it enumerates the whole multiplicative group only when the reduction polynomial is primitive. Under the AES polynomial the walk closes after 51 steps.

Table Construction

The antilog table is built by starting from α⁰ = 1 and repeatedly multiplying by the generator, which advances from αⁱ to αⁱ⁺¹. Each value is stored at its exponent index. The log table is then the inverse mapping, filled by walking the antilog table and writing each exponent at the index of the element it produced.

When the reduction polynomial is primitive, α = x and the step is exactly the xtime operation described above, which makes the construction a three-line loop. When it is not primitive, that loop silently fails: applied in the AES field, repeated xtime fills only 51 of the 255 entries before returning to 1, leaving four fifths of the table empty and every subsequent lookup wrong. Reed-Solomon implementations therefore select a primitive reduction polynomial so that α = x remains available. The QR Code specification, for example, works in GF(2⁸) modulo x⁸ + x⁴ + x³ + x² + 1, written 0x11D, which is primitive and admits α = x. AES needs no generator anywhere in its definition and is free to choose a polynomial that is merely irreducible.

• Antilog table: Maps an exponent i to the field element αⁱ; for GF(2⁸) it holds 255 entries indexed by exponent, one for each nonzero element.
• Log table: Maps a nonzero field element to its exponent; the zero element has no logarithm and is handled as a special case.
• Period wraparound: Exponents are taken modulo 2^m − 1, so the sum of two exponents that exceeds the period wraps around to the start of the cycle.

Multiplication, Division, and Inversion by Table

With the two tables in place, multiplication of nonzero elements a and b is computed as the antilog of the sum of their logarithms, taken modulo 2^m − 1. Division subtracts the logarithms, and the multiplicative inverse of an element is the antilog of the negation of its logarithm. Every one of these expressions needs its own reduction modulo 2^m − 1, including the inverse, where the omission is easy to miss because it costs nothing until the operand happens to be 1. These reductions are why table-based field arithmetic dominates software implementations of Reed-Solomon coding.

• Multiplication: The product ab equals antilog((log a + log b) mod (2^m − 1)), with a zero operand short-circuited to a zero result.
• Division: a divided by b equals antilog((log a − log b) mod (2^m − 1)).
• Inversion: The inverse of b equals antilog((2^m − 1 − log b) mod (2^m − 1)), giving a constant-time inverse for small fields. The outer modulo is not decoration: for b = 1 the logarithm is zero, and without it the index becomes 2^m − 1, one past the end of a table that holds exactly 2^m − 1 entries.
• Memory cost: Each table grows as roughly 2^m entries, and implementations commonly store the antilog table at double length so that the wraparound modulo can be dropped from the inner loop. In GF(2⁸) that pair costs under a kilobyte. In GF(2¹⁶), at two bytes per entry, it costs about 384 kilobytes, which already overflows the cache levels that made the lookup fast in the first place. In GF(2²⁴) it approaches 200 megabytes, so the practical ceiling does sit near GF(2¹⁶), beyond which algorithmic methods are preferred.

Inversion Algorithms

Two families of algorithms dominate. The extended Euclidean algorithm computes inverses directly through polynomial greatest-common-divisor steps, while exponentiation-based methods exploit the group structure to express the inverse as a power of the element.

• Extended Euclidean algorithm: Computes the inverse through iterated polynomial division and is well suited to variable field sizes.
• Fermat-based inversion: In GF(2^m), every nonzero element b satisfies b^2m−1 = 1, so the inverse equals b^2m−2, computed by repeated squaring and multiplication. Done naively this costs m − 1 squarings and m − 2 multiplications.
• Itoh-Tsujii algorithm: Reorganizes the same exponentiation around the quantities b^2k−1, built by an addition chain on m − 1. The squaring count stays at m − 1, but the number of full multiplications falls to the base-2 logarithm of m − 1 rounded down, plus the Hamming weight of m − 1, less one. For m = 8 that is 4 multiplications rather than 6, a modest gain; for the m = 163 field of the binary elliptic-curve standards it is 9 rather than 161, which is why the algorithm is worth the bookkeeping only as m grows. Calling what remains inexpensive is fair in a normal basis, where a squaring is a free cyclic shift, and nearly fair in a polynomial basis, where it is a fixed XOR network.

Squaring as a Special Case

Squaring is far cheaper than general multiplication in GF(2^m). Because the cross terms of a polynomial squared over GF(2) cancel in pairs, squaring a polynomial simply interleaves zeros between its coefficients, after which the result is reduced. A coefficient at position i moves to position 2i and nothing else survives, so the unreduced square of an m-bit word is fully determined before any gate is evaluated. The interleaving is pure wiring with no logic, so squaring reduces to a fixed linear reduction network, and inversion algorithms built from chains of squarings exploit this heavily.

Linear Feedback Shift Registers

The linear feedback shift register (LFSR) is the canonical sequential structure for field computation. An LFSR is a chain of flip-flops with XOR feedback taps positioned according to a feedback polynomial. When the polynomial is primitive, the register cycles through all nonzero field elements and produces a maximal-length pseudorandom sequence. In its Galois configuration the register is multiplication by α made literal: one clock edge takes the field element held in the flip-flops to x times that element, reduction included, which is the xtime operation built from wires and a handful of gates. The same structure evaluates the remainder of a polynomial division, and it forms the heart of cyclic-code encoders and many stream ciphers.

• Feedback taps: The XOR taps correspond to the nonzero terms of the feedback polynomial.
• Two configurations: The Fibonacci, or external-XOR, form gathers the tapped stages into one XOR tree ahead of the register input, so its critical path deepens as taps are added. The Galois, or internal-XOR, form distributes those gates between stages, leaving at most one XOR between consecutive flip-flops and holding the critical path to a single gate whatever the tap count.
• Division by feedback: Loading data serially into a Galois LFSR computes the polynomial remainder, which is exactly the syndrome or check computation in coding.

Bit-Serial Multipliers

A bit-serial multiplier processes one bit of an operand per clock cycle, interleaving conditional accumulation with reduction. It minimizes silicon area at the cost of m clock cycles per multiplication, which makes it attractive for resource-constrained devices and for very large fields where a fully parallel multiplier would be prohibitively large.

• Compact datapath: A single accumulation register and a small XOR network suffice.
• Latency: One multiplication requires m cycles, so throughput is inversely proportional to field size.
• Use cases: Preferred in compact cryptographic accelerators and embedded controllers with tight area budgets.

Bit-Parallel Multipliers

A bit-parallel multiplier computes the full product and reduction in combinational logic, delivering one result per clock cycle. The Mastrovito multiplier folds the reduction into the partial-product matrix, while Karatsuba decomposition reduces the number of subproducts at the cost of additional XOR gates and is widely used in high-throughput GF(2¹²⁸) units for authenticated encryption.

• Mastrovito multiplier: Generates a reduced product matrix directly, balancing gate count against logic depth.
• Karatsuba decomposition: Splitting each operand in half turns four half-size products into three, so applying the split recursively lowers the coefficient-multiplication count from m² to about m^1.58, paid for in extra XOR gates. The crossover favors Karatsuba only once m is large, which is why it appears in GF(2¹²⁸) units and not in GF(2⁸) ones.
• Composite-field techniques: Representing GF(2⁸) as GF((2⁴)²), and the subfield in turn as GF((2²)²), replaces one inversion in GF(2⁸) with a short sequence of operations in fields small enough to invert with a few gates. This is the tower-field construction of Satoh and colleagues, refined by Canright, whose merged substitution box and its inverse measure 234 NAND-gate equivalents against 294 for the earlier design. The cost is a basis-change matrix at the input, another at the output, and a deeper combinational path than a stored table, so the technique buys area rather than speed and belongs in area-constrained cipher cores.

Error-Control Coding

Reed-Solomon and BCH codes treat data symbols as elements of GF(2^m) and define codewords as polynomials over the field. Encoders in practice work systematically: they shift the message polynomial up by the number of parity symbols, divide by the generator polynomial, and append the remainder, so the original symbols survive unchanged in the codeword. Decoding computes syndromes, locates errors, and corrects them, all through field arithmetic. These codes protect optical discs, deep-space links, QR codes, and the data paths of storage and memory systems.

• Reed-Solomon codes: Operate on m-bit symbols in GF(2^m) and correct up to half as many symbol errors as there are parity symbols. The RS(255, 239) code widely used in transport and broadcast adds 16 parity symbols to correct any 8 symbol errors, and because an error is counted per symbol rather than per bit, a burst that ruins all 8 bits of a symbol still costs only one of that budget.
• Cyclic redundancy checks: Compute a polynomial remainder over GF(2) using exactly the LFSR division described above. What a given CRC guarantees follows from how its generator factors: it catches every error pattern touching an odd number of bits only when x + 1 divides the generator, which holds for CRC-32C and CRC-16 but not for the CRC-32 that Ethernet uses.
• Syndrome evaluation: Reduces to evaluating the received polynomial at successive powers of α, an operation tailor-made for field hardware, and one that presumes α really is a generator.

Cryptographic Use

Block ciphers and message-authentication schemes lean on field arithmetic for their nonlinear and mixing layers. The Advanced Encryption Standard computes its substitution box as a multiplicative inverse in GF(2⁸) followed by an affine map, and its MixColumns step is a matrix product over the same field. Galois/Counter Mode authenticates data by multiplying message blocks in GF(2¹²⁸), and elliptic-curve cryptosystems perform point arithmetic over fields that may be binary extension fields.

• Substitution boxes: Built from field inversion to obtain strong nonlinearity with a compact algebraic description. The table is fully determined by the field: taking the inverse of each byte modulo 0x11B and applying the standard's affine map reproduces all 256 published entries, while the same map over a different reduction polynomial of the same degree reproduces almost none of them. The 256-byte table and the algebraic definition are two views of one object, which is what makes the composite-field implementations above possible.
• Authentication: GF(2¹²⁸) multiplication accumulates an authentication tag across the message in Galois/Counter Mode. The mode multiplies each block into a running value by a hash subkey derived from the block cipher, so a single field multiplier, iterated, is the whole of the authentication path.
• Elliptic curves: Binary-field curves perform point addition and doubling through chains of field multiplications, squarings, and inversions.