19.1 Arithmetic with Polynomials

Addition of polynomials proceeds by adding the coefficients in : If f ( x ) := x ² + x and g ( x ) := x ² + x + 1, then f ( x ) + g ( x ) = 2 x ² + 2 x + 1 = 1, since 1 + 1 = 0 in . We can carry out addition of 3-tuples in column by column. We see, then, for example, that the sum of (1 1 0) and (1 1 1) is (0 0 1):

The addition of digits takes place in and is not to be confused with binary addition, which can involve a carry. This process is reminiscent of our XOR function in Section 7.2, which executes the same operation in for large n .

Multiplication in is accomplished by multiplying each term of the first polynomial by each term of the second and then summing the partial products. The sum is then reduced by an irreducible polynomial of degree 3 (in our example modulo m ( x ) := x ³ + x + 1): ^[3]

This corresponds to the product of 3-tuples (1 1 0) • (1 1 1) = (1 0 1), or, expressed in hexadecimal notation, '06' • '07' = '05'.

The abelian group laws hold in with respect to addition and in \ {0} with respect to multiplication (cf. Chapter 5). The distributive law holds as well.

The structure and arithmetic of can be carried over directly to the field , which is the field that is actually of interest in studying Rijndael. Addition and multiplication are carried out as in our above example, the only differences being that has 256 elements and that an irreducible polynomial of degree 8 will be used for reduction. For Rijndael this polynomial is m ( x ) := x ⁸ + x ⁴ + x ³ + x + 1, which in tuple representation is (1 0 0 0 1 1 0 1 1), corresponding to the hexadecimal number '011B'.

Multiplication of a polynomial

by x (corresponding to a multiplication • '02') is particularly simple:

where the reduction modulo m ( x ) is required only in the case a ₇ ≠ 0, and then it can be carried out by subtracting m ( x ), that is, by a simple XOR of the coefficients.

For programming one therefore regards the coefficients of a polynomial as binary digits of integers and executes a multiplication by x by a left shift of one bit, followed by, if a ₇ = 1, a reduction by an XOR operation with the eight least-significant digits '1B' of the number '011B' corresponding to m ( x ) (whereby a ₇ is simply "forgotten"). The operation a • '02' for a polynomial f , or its numerical value a , is denoted by Daemen and Rijmen by b = xtime(a) . Multiplication by powers of x can be executed by successive applications of xtime .

For example, multiplication of f ( x ) by x + 1 (or '03') is carried out by shifting the binary digits of the numerical value a of f one place to the left and XOR-ing the result with a . Reduction modulo m ( x ) proceeds exactly as with xtime . Two lines of C code demonstrate the procedure:

f ^= f << 1; /* multiplication of f by (x + 1) */ if (f & 0×100) f ^= 0×11B; /* reduction modulo m(x) */

Multiplication of two polynomials f and h in can be speeded up by using logarithms: Let g ( x ) be a generating polynomial ^[4] of \ {0}. Then there exist m and n such that f ≡ g ^m and h ≡ g ⁿ . Thus f · h ≡ g ^{m + n} mod m ( x ).

From a programming point of view this can be transposed with the help of two tables, into one of which we place the 255 powers of the generator polynomial g ( x ) := x + 1 and into the other the logarithms to the base g ( x ) (see Tables 19.2 and 19.3). The product f · h is now determined by three accesses to these tables: From the logarithm table are taken values m and n for which g ^m = f and g ⁿ = h . From the table of powers the value g ^{(( n + m )mod255)} is taken (note that g ^{ord( g )} = 1).

With the help of this mechanism we can also carry out polynomial division in . That is,

We now ratchet the complexity level up one notch and consider arithmetic with polynomials of the form f ( x ) = f ₃ x ³ + f ₂ x ² + f ₁ x + f with coefficients f _i in , that is, coefficients that are themselves polynomials. The coefficients of such polynomials can be represented as fields of four bytes each. Now things begin to get interesting: While addition of such polynomials f ( x ) and g ( x ) again takes place by means of a bitwise XOR of the coefficients, the product h ( x ) = f ( x ) g ( x ) is calculated to be

with coefficients h _k := f _i • g _j , where the summation sign indicates addition in .

After reduction of h ( x ) by a polynomial of degree 4, one again obtains a polynomial of degree 3 over .

For this Rijndael uses the polynomial M ( x ) := x ⁴ + 1. Usefully, x ^j mod M ( x ) = x ^{j mod4} , so that h ( x ) mod M ( x ) can be easily computed as

with

From this one concludes that the coefficients d _i can be computed by matrix multiplication over :

It is precisely this operation with the constant, invertible modulo M ( x ), polynomial a ( x ) := a ₃ x ³ + a ₂ x ² + a ₁ x + a over , with coefficients a ( x ) = x , a ₁ ( x ) = 1, a ₂ ( x ) = 1, and a ₃ ( x ) = x + 1, that is executed in the so-called MixColumn transformation, which constitutes a principal component of the round transformations of Rijndael.

^[3] A polynomial is said to be irreducible if it divisible (without remainder) only by itself and 1.

^[4] g generates \ {0} if g has order 255. That is, is the powers of g run through all the elements of \ {0}.

---

Team-Fly