Arithmetic of polynomials

A commonly used representation for the elements of a finite field F(/, where q = pm and p is a prime, is a polynomial basis representation. If m = 1, then F9 is just Zp and arithmetic is performed modulo p. Since these operations have already been studied in Section 2.4.2, it is henceforth assumed that m > 2. The representation is based on Fact 2.198.

2.224 Fact Let f(x)Zp[x be an irreducible polynomial of degree m. ThenZP[x]/(f{x)) is a finite field of order pm. Addition and multiplication of polynomials is performed modulo

f{x).

The following fact assures that all finite fields can be represented in this manner.

2.225 Fact For each m > 1, there exists a monic irreducible polynomial of degree m over Zp. Hence, ever}' finite field has a polynomial basis representation.

An efficient algorithm for finding irreducible polynomials over finite fields is presented in §4.5.1. Tables 4.6 and 4.7 list some irreducible polynomials over the finite field Z2.

Henceforth, the elements of the finite field Fp». will be represented by polynomials in Zp[x of degree < m. If g(x), h(x) e Fpm, then addition is the usual addition of polynomials in Zp[x. The product g(x)h(x) can be formed by first multiplying g(x) and h(x) as polynomials by the ordinary method, and then taking the remainder after polynomial division by f(x). Multiplicative inverses in Fpm can be computed by using the extended Euclidean algorithm for the polynomial ring Zp[a:].

2.226 Algorithm Computing multiplicative inverses in Fp

INPUT: a non-zero polynomial r/(x) e Fpm. (The elements of the field Fpm are represented as Zp[x]/(f(x)), where f(x)Zp[x] is an irreducible polynomial of degree m over Zp.) OUTPUT: g{x)~l 6 Fp™.

  • 1. Use the extended Euclidean algorithm for polynomials (Algorithm 2.221) to find two polynomials s(x) and t(x)Zp[x such that s(x)g(x) + t(x)f(x) = 1.
  • 2. Retum(.s(.x')).

Exponentiation in Fpm can be done efficiently by the repeated square-and-multiply algorithm (cf. Algorithm 2.143).

2.227 Algorithm Repeated square-and-multiply algorithm for exponentiation in Fp»<

INPUT: g(x) e Fp». and an integer 0 < k < pm - 1 whose binary representation is к = Xa=o (The field Fpm is represented as Zp[x]/(f(x)), where f(x) e Zp[x] is an irreducible polynomial of degree m over Zp.)

OUTPUT: g{x)k mod f{x).

  • 1. Set s(x)'*-l. If к = 0 then retum(s(x)).
  • 2. Set G(x)-t— g(x).
  • 3. If k0 = 1 then set s(x)-^g(x).
  • 4. For i from 1 to t do the followmg:
  • 4.1 Set G(x)<—G(x)2 mod f(x).
  • 4.2 If ki = 1 then set s(x)<— G{x) ■ s(x) mod f(x).
  • 5. Retum(.s(.x')).

The number of Zp-operations for the basic operations in Fpm is summarized in Table 2.8.

Operation

Number of Zp-operations

Addition

g(x) + h(x)

О (in)

Subtraction

g(x) - h(x)

О (in)

Multiplication

g(x) ■ h(x)

О (in2)

Inversion

а&у1

0(m2)

Exponentiation

g(x)k, к < pm

0((lgp)m3)

Table 2.8: Complexity of basic operations in Fpm.

In some applications (cf. §4.5.3), it may be preferable to use a primitive polynomial to define a finite field.

2.228 Definition An irreducible polynomial f(x) € Zp[x] of degree m is called a primitive polynomial if x is a generator of Fp..«, the multiplicative group of all the non-zero elements

in Fpm = Zp[x]/(/(x)).

2.229 Fact The irreducible polynomial f(x) e Zp[x] of degree m is a primitive polynomial if and only if f(x) divides xk 1 for к = pm 1 and for no smaller positive mteger k.

  • 2.230 Fact For each m > 1, there exists a moiiic primitive polynomial of degree m over Zp. In fact, there are precisely ф(рт - 1 )/m such polynomials.
  • 2.231 Example {the finite field F2j of order 16) It can be verified (Algorithm 4.69) that the polynomial f(x) = x4 + x + 1 is irreducible over Z2. Hence the finite field F2i can be represented as the set of all polynomials over F2 of degree less than 4. That is,

For convenience, the polynomial 03a;3 + a2x2 + ax + a0 is represented by the vector

(озо2а.1ао) of length 4, and

The following are some examples of field arithmetic.

  • (i) Field elements are simply added componentwise: for example, (1011) -l- (1001) =
  • (0010).
  • (ii) To multiply the field elements (1101) and (1001), multiply them as polynomials and then take the remainder when this product is divided by fix):

Hence (1101) • (1001) = (1111).

  • (iii) Tlie multiplicative identity of F24 is (0001).
  • (iv) The diverse of (1011) is (0101). To verify this, observe that

whence (1011) • (0101) = (0001).

f(x) is a primitive polynomial, or, equivalently, the field element x = (0010) is a generator of F24. This may be checked by verifying that all the non-zero elements in F24 can be obtained as a powers of x. The computations are summarized in Table 2.9. □

A list of some primitive polynomials over finite fields of characteristic two is given in Table 4.8.

 
Source
< Prev   CONTENTS   Source   Next >