Finding the Multiplicative Inverse

Finding the Multiplicative Inverse

Just as the Euclidean algorithm can be adapted to find the greatest common divisor of two polynomials, the extended Euclidean algorithm can be adapted to find the multiplicative inverse of a polynomial. Specifically, the algorithm will find the multiplicative inverse of b(x) modulo m(x) if the degree of b(x) is less than the degree of m(x) and gcd[m(x), b(x)] = 1. If m(x) is an irreducible polynomial, then it has no factor other than itself or 1, so that gcd[m(x), b(x)] = 1. The algorithm is as follows:

EXTENDED EUCLID[m(x), b(x)]
1. [A1(x), A2(x), A3(x)]  [1, 0, m(x)]; [B1(x), B2(x),
   B3(x)]  [0, 1, b(x)]
2. if B3(x) = 0   return  A3(x) = gcd[m(x), b(x)]; no
   inverse
3. if B3(x) = 1   return  B3(x) = gcd[m(x), b(x)];
   B2(x) = b(x)1 mod m(x)
4. Q(x) = quotient of A3(x)/B3(x)
5. [T1(x), T2(x), T3(x)]  [A1(x)  Q(x)B1(x), A2(x) 
   Q(x)B2(x), A3(x)  QB3(x)]
6. [A1(x), A2(x), A3(x)]  [B1(x), B2(x), B3(x)]
7. [B1(x), B2(x), B3(x)]  [T1(x), T2(x), T3(x)]
8. goto 2

Table 4.7 shows the calculation of the multiplicative inverse of (x7 + x + 1) mod (x8 + x4 + x3 + x + 1). The result is that (x7 + x + 1)1 = (x7). That is, (x7 + x + 1)(x7) 1 (mod (x8 + x4 + x3 + x + 1)). Table 4.7. Extended Euclid [(x8 + x4 + x3 + x + 1), (x7 + x + 1)] (This item is displayed on page 125 in the print version) Initialization A1(x) = 1; A2(x) = 0; A3(x) = x8 + x4 + x3 + x + 1 B1(x) = 0; B2(x) = 1; B3(x) = x7 + x + 1 Iteration 1 Q(x) = x A1(x) = 0; A2(x) = 1; A3(x) = x7 + x + 1 B1(x) = 1; B2(x) = x; B3(x) = x4 + x3 + x2 + 1 Iteration 2 Q(x) = x3 + x2 + 1 A1(x) = 1; A2(x) = x; A3(x) = x4 + x3 + x2 + 1 B1(x) = x3 + x2 + 1; B2(x) = x4 + x3 + x + 1; B3(x) = x Iteration 3 Q(x) = x3 + x2 + x A1(x) = x3 + x2 + 1; A2(x) = x4 + x3 + x + 1; A3(x) = x B1(x) = x6 + x2 + x + 1; B2(x) = x7; B3(x) = 1 Iteration 4 B3(x) = gcd[(x7 + x + 1), (x8 + x4 + x3 + x + 1)] = 1 B2(x) = (x7 + x + 1)1 mod (x8 + x4 + x3 + x + 1) = x7

Computational Considerations

A polynomial f(x) in GF(2ⁿ)

can be uniquely represented by its n binary coefficients (a_n1a_n2...a₀). Thus, every polynomial in GF(2ⁿ) can be represented by an n-bit number.

---

[Page 125]

Tables 4.5 and 4.6 show the addition and multiplication tables for GF(23) modulo m(x) = (x3 + x + 1). Table 4.5 uses the binary representation, and Table 4.6 uses the polynomial representation.

Addition

We have seen that addition of polynomials is performed by adding corresponding coefficients, and, in the case of polynomials over Z₂ addition is just the XOR operation. So, addition of two polynomials in GF(2ⁿ) corresponds to a bitwise XOR operation.

Consider the two polynomials in GF(28) from our earlier example: f(x) = x6 + x4 + x2 + x + 1 and g(x) = x7 + x + 1. (x6 + x4 + x2 + x + 1) + (x7+ x + 1) = x7 + x6 + x6 + x4 + x2 (polynomial notation) (01010111) (10000011) = (11010100) (binary notation) {57} {83} = {D4} (hexadecimal notation)[7] [7] A basic refresher on number systems (decimal, binary, hexadecimal) can be found at the Computer Science Student Resource Site at WilliamStallings.com/StudentSupport.html. Here each of two groups of 4 bits in a byte is denoted by a single hexadecimal character, the two characters enclosed in brackets.

Multiplication

There is no simple XOR operation that will accomplish multiplication in GF(2ⁿ) However, a reasonably straightforward, easily implemented technique is available. We will discuss the technique with reference to GF(2⁸) using m(x) = x⁸ + x⁴ + x³ + x + 1, which is the finite field used in AES. The technique readily generalizes to GF(2ⁿ).

The technique is based on the observation that

Equation 4-8

---

[Page 126]

A moment's thought should convince you that Equation (4.8) is true; if not, divide it out. In general, in GF(2ⁿ) with an nth-degree polynomial p(x), we have xⁿ mod p(x) = [p(x) xⁿ].

Now, consider a polynomial in GF(2⁸), which has the form f(x) = b₇x⁷ + b₆x⁶ + b₅x⁵ + b₄x⁴ + b₃x³ + b₂x² + b₁x + b₀. If we multiply by x, we have

Equation 4-9

If b₇ = 0, then the result is a polynomial of degree less than 8, which is already in reduced form, and no further computation is necessary. If b₇ = 1, then reduction modulo m(x) is achieved using Equation (4.8):

x x f(x) = (b₆x⁷ + b₅x⁶ + b₄x⁵ + b₃x⁴ + b₂x³ +

b₁x² + b₀x) + (x⁴ + x³ + x + 1)

It follows that multiplication by x (i.e., 00000010) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (00011011), which represents (x⁴ + x³ + x + 1). To summarize,

Equation 4-10

Multiplication by a higher power of x can be achieved by repeated application of Equation (4.10). By adding intermediate results, multiplication by any constant in GF(2⁸) can be achieved.

In an earlier example, we showed that for f(x) = x6 + x4 + x2 + x + 1, g(x) = x7 + x + 1, and m(x) = x8 + x4 + x3 + x + 1, f(x) x g(x) mod m(x) = x7 + x6 + 1. Redoing this in binary arithmetic, we need to compute (01010111) x (10000011). First, we determine the results of multiplication by powers of x: (01010111) x (00000001) = (10101110) (01010111) x (00000100) = (01011100) (00011011) = (01000111) (01010111) x (00001000) = (10001110) (01010111) x (00010000) = (00011100) (00011011) = (00000111) (01010111) x (00100000) = (00001110) (01010111) x (01000000) = (00011100) (01010111) x (10000000) = (00111000) So, (01010111) x (10000011) = (01010111) x [(00000001) x (00000010) x (10000000)] = (01010111) (10101110) (00111000) = (11000001) which is equivalent to x7 + x6 + 1.