PineWikiRecall that a field is an algebra F (see AlgebraicStructures) with operations + and × such that (F,+) is an abelian group with identity 0, (F-{0},×} is an Abelian group with identity 1, and the distributive law a(b+c) = ab+ac holds.
The finite fields or Galois fields consist precisely of the fields GF(p) = ℤp for each prime p, and the fields GF(pn) for each prime p and each n > 1 constructed by taking the quotient ring of ℤp[x] by some degree-n polynomial (see Polynomials for a high-level description of this construction and AlgebraicStructures for a specific example of constructing GF(4)). For n > 1, GF(pn) will not in general be isomorphic to the ring ℤp^n.
1. The additive group of a finite field
The additive group of a finite field of order pn is always isomorphic to (ℤp)n, i.e. to adding vectors of n elements of ℤp element by element. A proof of this fact is given in BiggsBook §23.2. The essential idea of the proof is that given a finite field F we can first identify p by looking for the characteristic χ(F) of F, the smallest positive integer n such that n⋅1 = ∑i=1 to n 1 = 0. The characteristic must be prime because if mn⋅1 = 0 then (m⋅1)(n⋅1) = 0 and one of m⋅1 or n⋅1 must be zero (since a field has no zero divisors). Furthermore, χ(F)⋅a = 0 for any a in F, since χ(F)⋅a = (χ(F)⋅1)a = 0a = 0, and we can use Lagrange's theorem to show that n⋅a = 0 if and only if χ(F)∣n. We can now go hunting for a basis a1, a2, a3, ..., an for F where every a∈F can be expressed as ∑ ni⋅ai, and no subset of the basis has this property. With some further argument we can show that the representation of each a as (n1...,nn) is unique, which gives exactly pn elements corresponding to the pn vectors.
2. The multiplicative group of a finite field
The primitive element theorem says that any finite field has primitive element or generator, an element g such that for every x ≠ 0 there exists some y such that x = gy. This implies that the multiplicative group F* is cyclic and thus isomorphic to ℤ|F|-1.
Finding a generator is not always easy. If we are very careful in choosing our irreducible polynomial when constructing GF(pn), the polynomial x will be a primitive element; this happens if the irreducible polynomial is primitive irreducible, which is equivalent to dividing x^|F| - 1.
Some consequences:
Fermat's Little Theorem generalizes to finite fields: if a∈F is not equal to zero, then a|F|-1 = 1.
Every nonzero element x of a finite field has a unique discrete logarithm y in { 0 ... |F| - 2} such that x = gy. This fact is popular in cryptography because (a) given g and y it's usually not too hard to compute x, but (b) given g and most values of x it seems to be very hard to compute y. This means for example that I can prove (once) that I generated x in the first place by showing you y such that g^x = y; if I hadn't picked y first, it's unlikely I could have found it later.
Note that except for GF(p), the behavior of multiplication in GF(pn) is often very different from multiplication in ℤ,,pn (which for n > 1 is not a field since among other things every multiple of p is a zero divisor).