2.4.1 Finite Fields

2.4.1 Finite Fields

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

Theorem 2.4.3 (existence and uniqueness of finite fields)

1. If F is a finite field, then F contains p^m elements for some prie p and integer

m ≥ 1.

2. For every prime power order p^m, there is a unique (up to isomorphism) finite field of order p^m . This field is denoted F_p^m , or sometimes by GF(p^m).

Theorem 2.4.4 if F_q is a finite field of order q = p^m,p is a prime, then the characteristic of F_q is p. Moreover, F_q contains a copy of Z_p as a subfield. Hence F_q can be viewed as an extension field of Z_p of degree m.

Theorem 2.4.5 (subfields of a finite field) Let F_q be a finite field of order q = p^m. Then every subfield of F_q has order p^n, for some n that is a positive divisor of m. Conversely, if n is positive divisor of m, then there is exactly one subfield of F_q of order p^n; an element a Є F_q is in the subfield F_p^n if and only if a^p_n = a.

Definition 2.4.3 The non-zero elements of F_q from a group under multiplication called the multiplicative group of F_q, denoted F*_q .

Theorem 2.4.6 F*_q is a cyclic group of order q - 1. Hence a^q = a for all a ЄF_q .

Proposition 2.4.1 The order of any a F*_q devides q - 1.

Proof. Fo r a^(q-1) = 1 let d be the order of a, i.e., the smallest positive power which gives 1. If d

did not divide q - 1, we could find a smaller positive number r- namely, the remainder

when

q - 1=bd + r, where 1≤ r

is divided by d- such that

a^r. a^(bd) = a^(q-1) =1.

But this contradicts the minimality of d. This concludes the proof.

Definition 2.4.4 A generator of the cyclic group F*_q is called a primitive element or

generator of F_q .

Theorem 2.4.7 If a, b Є F_q, a finite field of characteristic p, then

(a + b)^(p^t) = a^(p^t) + b^(p^t) for all t ≥ 0.

2.2 Groups

2.2 Groups

This section provides an overview of basic algebra objects and their properties.

Definition 2.2.1 A binary operation * on a set S is a mapping from S x S to S. That

is, * is a rule which assigns to each order pair of elements from S an element of S.

Definition 2.2.2 A group operation (G, *) consists of a set G with a binary operation *

on G satisfying the following three axioms.

1. The group is a associative. That is, a * (b * c)=(a * b) * c for all a, b, c Є G.

2. There is an element 1 Є G, called the identity element, such that a * 1=1* a = a

for all a Є G.

3. For each a Є G there exists an element a^(-1) Є G, called the inverse of a, such that

a * a^(-1) = a^(-1) * a =1.

A group G is abelian (or commutative) if, furthermore,

4. a * b = b * a for all a, b Є G.

Definition 2.2.3 A group G is a finite if |G| is finite. The number of elements in a finite

group is called its order.

Definition 2.2.4 A group G is a cyclic if there is an element g Є G such that for each

b Є G there is an integer i with b = g^i. Such an element g is called a generator of G.

Euler’s Theorem-Fermat’s Theorem

Theorem 2.1.13 Let n ≥ 2 be an integer.

1. (Euler’s Theorem)If a Є Z*n, then a^φ(n)≡1 (mod n).

2. If n is a pro duct of distinct primes, and if r ≡ s (mod φ(n)), then a^r ≡ a^s (mod n)

for all integers a. In other words, when working modulo such an n exponents can

be reduced modulo φ(n).

Definition 2.1.12 Let a, b Є Zn. The multiplicative inverse of a modulo n is an integer

x Є Zn such that ax ≡ 1(mod n). If such an x exists, then it is unique, and a is said to

be invertible,or a unit; the inverse of a is denoted by a^-1.

Theorem 2.1.14 Let a Є Zn. Then a is invertible if and only if gcd(a, n)=1.

Proof First, if gcd(a, n) were greater than 1, we could not have ab =1(mod n) for any b,

because that would imply that d divides ab - 1 and hence divides 1.

A special case of Euler’s theorem is Fermat’s (little) theorem.

Theorem 2.1.15 Let p be a prime.

1. (Fermat’s Theorem) If gcd(a, p) = 1, then a^p-1 ≡ 1(mod p).

2. In particular, a^p ≡ a (mod p) for all integers a.

Definition 2.1.13 Let a Є Z*n. The order of a, is denoted ord(a), is the least positive

integer t such that a^t ≡ 1(mod n).

Theorem 2.1.16 If the order of a Є Z*n is t, and a^s ≡ 1(mod n), then t divides s.In

particular, t| φ(n).

Definition 2.1.14 Let a Є Z*n. If the order of g is φ(n), then g is said to be a generator

or a primitive element of Z*n.If Z*n has a generator, then Z* is said to be cyclic.