Finite fields

Basic properties

2.208 Definition Apiite field is a field F which contains a finite number of elements. The order of F is the number of elements in F.

  • 2.209 Fact (existence and uniqueness of finite fields)
  • (i) If F is a finite field, then F contains pm elements for some prime p and integer m > 1.
  • (ii) For every prime power order pm, there is a unique (up to isomorphism) finite field of order pm. This field is denoted by Fpm, or sometimes by GF(pm).

Informally speaking, two fields are isomorphic if they are structurally the same, although the representation of their field elements may be different. Note that if p is a prime then Zp is a field, and hence every field of order p is isomorphic to Zp. Unless otherwise stated, the finite field Fp will henceforth be identified with Zp.

  • 2.210 Fact If Fq is a finite field of order q = pm, p a prime, then the characteristic of F,; is p. Moreover, F(/ contains a copy of Zp as a subfield. Hence F(/ can be viewed as an extension field of Zp of degree m.
  • 2.211 Fact (subfields of a finite field) Let F4 be a finite field of order q = pm. Then every subfield of Fq has order pn, for some n that is a positive divisor of m. Conversely, if n is a positive divisor of m, then there is exactly one subfield of F4 of order pn; an element a € F4 is in the subfield Fp>. if and only if ap" = a.
  • 2.212 Definition The non-zero elements of F9 form a group under multiplication called the multiplicative group of Fq, denoted by F*.
  • 2.213 Fact F* is a cyclic group of order q 1. Hence aq = a for all a e Fq.
  • 2.214 Definition A generator of the cyclic group F* is called a primitive element or generator Of Fq.

2.215 Fact If a, b € F9, a finite field of characteristic p, then

The Euclidean algorithm for polynomials

Let Zp be the finite field of order p. The theory of greatest common divisors and the Euclidean algorithm for integers carries over in a straightforward manner to the polynomial ring Zp[x] (and more generally to the polynomial ring F[x], where F is any field).

  • 2.216 Definition Let g{x), h(x) € Zp[x], where not both are 0. Then the greatest common divisor of g(x) and h(x), denoted gcd(g(x), h(x)), is the monic polynomial of greatest degree in Zp[x] which divides both g(x) and h(x). By definition, gcd(0,0) = 0.
  • 2.217 Fact Zp [x] is a unique factorization domain. That is, every non-zero polynomial /(x) e Zp[x] has a factorization

where the /;(x) are distinct monic irreducible polynomials in Zp[x], the e, are positive integers, and a € Zp. Furthermore, the factorization is unique up to rearrangement of factors.

The following is the polynomial version of the Euclidean algorithm (cf. Algorithm 2.104).

2.218 Algorithm Euclidean algorithm for Zp[x]

INPUT: two polynomials g{x), h(x)Zp[x}.

OUTPUT: the greatest common divisor of g(x) and h(x).

  • 1. While h(x) ф 0 do the following:
  • 1.1 Set r(ar)-t— g(x) mod h(x), g(x)<—h(x), h(x)<—r(x).
  • 2. Retum(g(x)).
  • 2.219 Definition A Zp-operation means either an addition, subtraction, multiplication, inversion, or division in Zp.
  • 2.220 Fact Suppose that deg g(x) < m and deg li(x) < m. Then Algorithm 2.218 has a running time of 0(m2) Zp-operations, or equivalently, 0(ra2(lgp)2) bit operations.

As with the case of the integers (cf. Algorithm 2.107), the Euclidean algorithm can be extended so that it also yields two polynomials s(x) and t(x) satisfying

2.221 Algorithm Extended Euclidean algorithm for Zp[x]

INPUT: two polynomials g{x), h(x)Zp[x].

OUTPUT: d(x) = gcd(g(x),h(x)) and polynomials s(x), t(x)Zp[x] which satisfy

s(x)g(x) + t(x)h(x) = d(x).

  • 1. If h(x) = 0 then set d(x)^g{x), s(a;)<— 1, t(x)0, and remm(d(2:),s(a:),f(a:)).
  • 2. Set S2(x)<—1, si(x)-t—0, f2(x)-t—0, ti(x)-t— 1.
  • 3. While h(x) ф 0 do the following:
  • 3.1 q(x)<^g(x) div h(x), r(x)^g(x)h(x)q(x).
  • 3.2 s(x)2(x)q(x)si(x), <2(2:) q(x)ti(x).
  • 3.3 g(x)^li(x), /i(x)-<—r(x).
  • 3.4 S2(x)<—si(x), si(x)<—s(x), f2(x)<— ti(x), and t(x)-<— t(x).
  • 4. Set d(x)2{x), t(x)<—t2{x).
  • 5. Retum(d(x),s(z),t(a:)). [1] [2]

Iteration 1

q(x) + 1, a;8 + x7 + x6 + x2 + x,

s(x)1, t(x)<— x + 1,

g(x)t + x6 + x5 + x3 + x2 + 1, h(x)*—x& + x7 + x6 + x2 + 1,

S2(x)<— 0, si(a;)-<— 1, 12(x)<—l, ti(x)<—x+l.

Iteration 2

q(x)<— x + 1, r(x)-t— x5 + x2 + x + 1, s(x)<—x + 1, t(x)<—x2,

g(x)<—x& + x‘ + xG + x2 + 1, h(x)<—x5 + x2 + x + 1,

S2(x)1, Si(x) 1, t2(x)^X + 1, ti(x)^x2.

Iteration 3

q(x)-^x3 + x2 + x + 1, r(x)3 + x + 1, s(a;)<— x4, t(x)b + x4 + a:3 + x2 + x + 1, g(x)<—x5 + x2 + x + 1, h(x)^x3 + x + 1,

S2{x) 1, Si(x)<^x4, t2{x)-^x2, ti(x)3 + X4 + X3 + X2 + X + 1.

Iteration 4

q[x)ix2 + 1, r(x)^r-0,

s(a;)<— x6 + x4 + x + 1, t(x)<—x7 + x6 + x2 + x + 1, g(x)<—x3 + x + 1, h(x)<— 0,

S2{x)4, si(x)-^x6 + x4 + x + 1,

t2{x)^xb + x4 + a;3 + x2 + x + 1, t(x)^x‘ + x6 + x2 + x + 1.

Hence gcd((/(:c), h(x)) = x3 + x + 1 and

(x4)g(x) + (a:5 + x4 + a:3 + x2 + x + l)/i(a;) = ar3 + x + 1. □

  • [1] 2.222 Fact (running time of Algorithm 2.221) (i) The polynomials s(x) and t(x) given by Algorithm 2.221 have small degree; that is,they satisfy deg «(ж) < deg h(x) and deg t(x) < deg g(x).
  • [2] Suppose that deg g(x) < m and deg h(x) < m. Then Algorithm 2.221 has a runningtime of 0(m2) Zp-operations, or equivalently, 0(m2([gp)2) bit operations. 2.223 Example (extended Euclidean algorithm for polynomials) The following are the steps ofAlgorithm 2.221 with inputs g(x) = a;10 + a;9 + x8 + x6 + xb + x4 + 1 and h(x) =a:9 + a:6 + a:5 + a;3 + x2 + 1 in Z2[a;]. Initialization S2{x)
 
Source
< Prev   CONTENTS   Source   Next >