RSA Laboratories

A.4 Fields and rings

One interesting observation from the examples in the previous section is that each of the sets Zp, R, Q, and C contains two different abelian group structures: the set itself under addition and the set of nonzero elements under multiplication. Structures satisfying this property together with an axiom about multiplication ``distributing'' over addition are called fields.

Formally, a field consists of a set F together with two operations + : F ×F ® F and ·: F ×F ® F called addition and multiplication, respectively, such that the following axioms are satisfied.

  1. F forms an abelian group under addition.
  2. F \{0} forms an abelian group under multiplication, where 0 is the identity in the additive abelian group áF, + ñ.
  3. Multiplication distributes over addition, that is, a ·(b+c) = a ·b + a ·c.

For an integer n and a field element x, n ·x denotes the element obtained by adding x to itself n times; for example, 3·x = x+x+x. The characteristic of a field is the smallest positive integer p such that p ·1 = 0. If no such p exists, then the characteristic of the field is defined to be 0. The characteristic of a field is either a prime number or 0. If the characteristic of a field is 0, then the field is infinite. However, a field with nonzero characteristic might be either finite or infinite.

The fields Q, R, and C of rational, real, and complex numbers, respectively, are fields of characteristic 0. The finite field Zp is a field of characteristic p.

The number of elements in a finite field must be a power of a prime number. A classification theorem of the finite fields states that there is exactly one finite field (up to isomorphism; see [Fra98]) of size q for each prime power number q. Thus it makes sense talking about the field with q elements, which is traditionally denoted GF(q) (GF = Galois Field) or Fq.

A ring R satisfies axioms (1) and (3), but instead of (2), multiplication in R is only required to be associative. If multiplication is commutative, then the ring is commutative. A nonzero element a in a ring is a zero divisor if there is a nonzero element b such that ab = 0. There are two main classes of commutative rings:

  • Rings with no zero divisors. All fields and the ring Z of integers are of this kind.
  • Rings with zero divisors. The ring Zn contains zero divisors if and only if n is composite.

A polynomial in a ring R is a function f : R ® R of the form

f(x) = a0 + a1 x + a2 x2 + ¼+ an xn,

where a0, ¼, an are elements in the ring. A root of a polynomial is an element r such that f(r) = 0.

Top of the page