resented by a one-byte word. The modulus m(x) = =x8tx4tx3. + X + 1, which is used in the AES cryptosystem, meets such a requirement. This specific polynomial is also irreducible, meaning that it has no dividers other than 1 and itself. It is the conceptual equivalent of a prime number in the polynomial field. The polynomial dividers of m(x) are any numbers u(x), v(x) that verify u(x) X v(x) = m(x), where X is the usual algebraic multiplication. Let us look now at how multiplications X and work through a simple example. Take u(x) = x3 1 and v(x) = Following usual algebra, we first get the product v(x)=(x3x2+1)(x2x = =x5+x3+x2+ Polynomial byte representation and modular multiplication To obtain this result, we use + to perform the addition between the polynomial coef- ficients of the same order, since this is the operation used in the corresponding binary representation. The second task is to reduce the above result modulo a given polynomial, say, m(x) = x4 + 1. By definition, we have for any polynomial p(x), p(x)=q(x)xm(x)+r(x), = where q(x) is the quotient and r(x) is the remainder, also noted p(x) mod m(x). Note that the degree of the remainder must be lower than that of m(x), otherwise it could divide it. Taking the previous example, we must find the polynomials q(x) and r(x) that satisfy From the above relation, we must conclude that p(x) = ax +b and q(x) = cx3 dx2 + ex + f, where a, b, C, d, e, f are the unknowns. Substituting these two definitions into the right-hand side yields a = c=d = 1, b=e=f=0, which gives p(x) = x and q(x) =x3+x2.Thus, which illustrates how modulus reduction is performed. With the modulus-reduction tool in hand, we can now consider an example that uses the irreducible polynomial m(x) = =x8tx4tx3+ + 1. Take, for instance, the two numbers {4A} and {18}. What is p(x) = {4A} {19}? The conversion into polynomial representation gives p(x) = {01001010} {00011001} = m(x) = mod m(x) = mod m(x) = {11100000} {E0}, which is the result of the operation. Since we have defined a multiplication law f