Finite field

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains a finite number of elements, called its order (the size of the underlying set). As with any field, a finite field is a set on which the operations of commutative multiplication, addition, subtraction and division (by anything except zero) have been defined. Common, but not the only, examples of finite fields are given by the integers modulo a prime, that is, the integers mod n where n is a prime number, such as ℤ/3ℤ or ℤ/7ℤ.

Finite fields only exist when the order (size) is a prime power pk (where p is a prime number and k is a positive integer). For each prime power, there is a finite field with this size, and all fields of a given order are isomorphic. The characteristic of a field of order pk is p (this means that adding p copies of any element always results in zero). ℤ/2ℤ (the integers mod 2) has characteristic 2 since, as 1 + 1 \equiv 0 \pmod 2, we have 1+1=0 in this field. Similarly, ℤ/5ℤ has characteristic 5 since 0 = 1 + 1 + 1 + 1 + 1 = 2 + 2 + 2 + 2 + 2 = \cdots in this field.

In a finite field of order q, the polynomial XqX has all the elements of the finite field as roots, and so, is the product of q different linear factors. Just considering multiplication, the non-zero elements of any finite field form a multiplicative group that is a cyclic group. Therefore, the non-zero elements can be expressed as the powers of a single element called a primitive element of the field (in general there will be several primitive elements for a given field.)

A field has, by definition, a commutative multiplication operation. A more general algebraic structure that satisfies all the other axioms of a field but isn't required to have a commutative multiplication is called a division ring (or sometimes skewfield). A finite division ring is a finite field by Wedderburn's little theorem. This result shows that the finiteness condition in the definition of a finite field can have algebraic consequences.

Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.

Classification[edit]

Statement[edit]

The finite fields are classified as follows (Jacobson 2009, §4.13, p. 287):

  • The number of elements in a finite field is of the form pn, where p is a prime number called the characteristic of the field, and n is a positive integer.
  • For every prime number p and positive integer n, there exists a finite field with pn elements.
  • Any two finite fields with the same number of elements are isomorphic. That is, under some renaming of the elements of one of these, both its addition and multiplication tables become identical to the corresponding tables of the other one.

This classification justifies using a naming scheme for finite fields that specifies only the order of the field. One notation for a finite field is \mathbb{F}_{p^n} or Fpn. Another notation is GF(pn), where the letters GF stand for "Galois field".[1]

A prime power field with p = 2 is also called a binary field.

First we consider fields where the size is prime, i.e., with n = 1. Such a field is called a prime field, and is canonically isomorphic to the ring Z/pZ, the set of integers modulo p. It is sometimes denoted Zp, but within some areas of mathematics, particularly number theory, this may be confused with the same notation for the ring of p-adic integers. The ring Z/pZ is a field since it contains a multiplicative inverse for each element other than zero (an integer that, multiplied by the element modulo p yields 1), and it has a finite number of elements (being p), making it a finite field.

Even though all fields of size p are isomorphic to Z/pZ, for n ≥ 2 the ring of integers modulo pn, Z/pnZ, is not a field. The element p is nonzero and has no multiplicative inverse modulo pn. By comparison with the ring Z/4Z of size 4, the underlying additive group of the field (Z/2Z)[T]/(T2 + T + 1) of size 4 is not cyclic, but is isomorphic to the Klein four-group.

No fields exist for which the size is not a prime power. For example, there is no field with 6 elements. Given a prime power q = pn, we may explicitly construct a finite field with q elements as follows. Select a monic irreducible polynomial f (T) of degree n in Fp[T]. (Such a polynomial is guaranteed to exist, once we know that a finite field of size q exists: just take the minimal polynomial of any primitive element for that field over the subfield Fp.) Then Fp[T]/(f (T)) is a field of size q. Here, Fp[T] denotes the ring of all polynomials in T with coefficients in Fp, (f (T)) denotes the ideal generated by f (T), and the quotient is meant in the sense of quotient rings — the set of polynomials in T with coefficients in Fp mod (f (T)).

Proof[edit]

Outline[edit]

The characteristic of a finite field is a prime p (since a field has no zero divisors), and the field is a vector space of some finite dimension, say n, over Z/pZ, hence the field has pn elements. A field of order p exists, because Fp = Z/pZ is a field, where primality is required for the nonzero elements to have multiplicative inverses.

For any prime power q = pn, Fq is the splitting field of the polynomial f (T) = TqTFp[T]. This field exists and is unique up to isomorphism by the construction of splitting fields. The set of roots is a field, the fixed field of the n-th iterate of the Frobenius endomorphism, so the splitting field is exactly the q roots of this polynomial, which are distinct because the polynomial TqT is separable over Fp: its derivative is −1, which has no roots.

Size[edit]

The cardinality of a finite field is a prime-power.

Let F be a finite field. Write its additive identity as 0 and its multiplicative identity as 1. The characteristic of F is a prime number p as the characteristic of a finite ring is positive and must be prime or else the ring would have zero divisors. The p distinct elements 0, 1, 2, ..., p − 1 (where 2 means 1 + 1, and all the elements can be deduced by induction) form a subfield Fp of F that is isomorphic to Z/pZ. F is a vector space over Z/pZ, and it must have a finite dimension over Z/pZ. Call the dimension n, so each element of F is specified uniquely by n coordinates in Z/pZ. There are p possibilities for each coordinate, with no dependencies among different coordinates, so the number of elements in F is pn. This proves the first statement, and does a little more: it shows that, additively, F is a direct sum of copies of Z/pZ.

E. H. Moore's 1893 paper,[2] that (for the first time) classified all finite fields, gave a longer proof that is no longer used in textbooks.

Existence[edit]

For any prime p, and any positive integer n, there exists a finite field of size q = pn.

For n = 1 take Fp = Z/pZ.

For n > 1, let f (T) = TqTFp[T]. It is possible to construct a field F (called the splitting field of f (T) over Fp), which contains Fp and which is large enough for f (T) to split completely into linear factors:

f (T) = (Tr1)(Tr2) ... (Trq)

in F[T]. The existence of splitting fields in general is discussed in construction of splitting fields. These q roots are distinct, because TqT is a polynomial of degree q which has no repeated roots in F: its derivative is qTq−1 − 1, which is −1 (because q = 0 in F) and therefore the derivative has no roots in common with f (T). Furthermore, setting R to be the set of these roots,

R = {r1, ..., rq} = {roots of Tq = T}.

one sees that R itself forms a field, as follows. Both 0 and 1 are in R, because 0q = 0 and 1q = 1. If r and s are in R, then

(r + s)q = rq + sq = r + s

so that r + sR. The first equality above follows by induction on n for q = pn, from the binomial theorem, the fact that for n = 1 all binomial coefficients except first and last are divisible by p, and the fact that F has characteristic p. Therefore R is closed under addition. Similarly, R is closed under multiplication and taking inverses, because

(rs)q = rq sq = rs

and

(r−1)q = (rq)−1 = r−1.

Therefore R is a field with q elements, proving the second statement.

We also sketch the ideas for a second proof: we will give a combinatorial argument that a monic irreducible f (T) of degree n exists in Fp[T]. Then the quotient ring Fp[T]/(f (T)) is a field of size q. Because TqT has no repeated irreducible factors (it is a separable polynomial in Fp[T]), it is a product of distinct monic irreducibles. We ask: which monic irreducibles occur in the factorization? Using some group theory, one can show that a monic irreducible in Fp[T] is a factor precisely when its degree divides n. Writing Np(d) for the number of monic irreducibles of degree d in Fp[T], computing the degree of the irreducible factorization of TqT shows q = pn is the sum of dNp(d) over all d dividing n. This holds for all n, so by Moebius inversion one can get a formula for Np(n) for all n, and a simple lower bound estimate using this formula shows Np(n) is positive. Thus a (monic) irreducible of degree n in Fp[T] exists, for any n.

Uniqueness[edit]

Two finite fields of the same size are isomorphic.

A field of size q = pn is the splitting field of TqT over its subfield of size p, and for any field K, two splitting fields of a polynomial in K[T] are unique up to isomorphism over K. That is, the two splitting fields are isomorphic by an isomorphism extending the identification of the copies of K inside the two splitting fields. Since a field of size p can be embedded in a field of characteristic p in a unique way (the multiplicative identity 1 in the field is unique, then 2 = 1 + 1, and so on up to p − 1), the condition of two fields of size q being isomorphic over their subfields of size p is the same as just being isomorphic fields.

Warning: it is not the case that two finite fields of the same size are isomorphic in a unique way, unless the fields have size p. Two fields of size pn are isomorphic to each other in n ways (because a field of size pn is isomorphic to itself in n ways, from Galois theory for finite fields).

Explicit constructions of finite fields[edit]

F4[edit]

The field with 4 elements is isomorphic to:

(\mathbf{Z}/2\mathbf{Z})[T]/\left(T^2+T+1 \right) =\mathbf{Z}[T]/\left ( 2,T^2+T+1 \right )

Here (Z/2Z)[T] is the polynomial ring of Z/2Z and (Z/2Z)[T]/(T2 + T + 1) are the equivalence classes of these polynomials modulo T2 + T + 1. The polynomial f (T) = T 2 + T + 1 is irreducible over Z/2Z, and (Z/2Z)[T]/(T 2 + T + 1) has size 4. Roughly T2 + T + 1 = 0 so that T2 = T + 1 (since −1 = 1 in Z/2Z) and hence the elements of (Z/2Z)[T]/(T2 + T + 1) are the polynomials of degree up to 1 with coefficients in Z/2Z, i.e. the set {0, 1, T, T + 1}, where the multiplication is carried out by using the relation T 2 + T + 1 = 0, or equivalently: T 2 = −T − 1. However in Z/2Z (or any field of characteristic 2), we have: −1 = 1 and therefore we may write this as T 2 = T + 1. For example we can compute T 3 as follows:

T 3 = TT 2 = T (T + 1) = T 2 + T = (T + 1) + T = 2T + 1 = 1.

In order to find the multiplicative inverse of T in this field, we have to find a polynomial p(T) such that Tp(T) = 1 mod T 2 + T + 1. The polynomial p(T) = T + 1 works, and hence T−1 = T + 1.

Remark 1. (Z/2Z)[T]/(T2 + 1) is not a field since it admits a zero divisor (T + 1)2 = T2 + 1 = 0 (since in Z/2Z, 2 = 0).

Remark 2. One can interpret F4 as Z[φ]/(2Z[φ]) where φ is the golden ratio (φ2 = φ + 1).[3]

F27[edit]

To construct a field of size 27, we could start for example with the irreducible polynomial T 3 + T 2 + T + 2 over Z/3Z. The field (Z/3Z)[T]/(T 3 + T 2 + T + 2) has size 27. Its elements have the form aT 2 + bT + c where a, b, and c lie in Z/3Z and the multiplication is defined by T 3 + T 2 + T + 2 = 0, or by rearranging this equation, T 3 = 2T 2 + 2T + 1.

F8[edit]

A field with 8 elements is (Z/2Z)[T]/(T3 + T + 1).

F9[edit]

Two isomorphic constructions of the field with 9 elements are (Z/3Z)[T]/(T2 + 1) and Z[i]/(3Z[i]).

Fp2 (via quadratic residues modulo p)[edit]

Definition. A number x in Z/pZ is called a quadratic residue (resp. quadratic non-residue) if x modulo p is (resp. is not) the square of any integer in Z/pZ. There are exactly (p − 1)/2 nonzero quadratic residues and nonresidues each, for any prime other than 2.
Quadratic Residue Multiplication Rule.
The product of two quadratic residues modulo p is a quadratic residue.
The product of a residue and non-residue is a non-residue.
The product of two quadratic non-residues is a quadratic residue.

Now consider the numbers of the form:

a+b\sqrt c,

where a, bZ/pZ and c is a quadratic non-residue.

Notice that the sum and product of any two is done in the obvious way.

\begin{align}
\left (a+b\sqrt c \right ) + \left (j+k\sqrt c \right ) &=(a+j)+(b+k)\sqrt c \\
\left (a+b\sqrt c \right ) \left (j+k\sqrt c \right ) &=(aj+cbk)+(ak+bj)\sqrt c
\end{align}

The multiplication rule for quadratic residue implies that when c is a non-residue, then:

a^2 -c b^2 \ne 0,

provided that a and b are not both 0. Now,

\frac{\left (a+b\sqrt c \right ) \left (a - b\sqrt c \right )}{a^2 - cb^2} = \frac{a^2 - cb^2}{a^2 - c b^2} = 1, \qquad a+b\sqrt c \neq 0.

This means the numbers a+b\sqrt c, as described at the start, are a field and so Fp2.

Fp2 (via 2 × 2 matrices in integers modulo p)[edit]

Consider the following 2 × 2 matrix over the integers modulo p, where p is a prime number:

A =\begin{bmatrix} 0 & b \\ 1 & 1 \end{bmatrix} \in \text{M}(2, \mathbf{Z}/p\mathbf{Z})

The following set:

 \mathbf{F} = \left \{ uI + vA  \ : \ I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, u, v \in \mathbf{Z}/p\mathbf{Z} \right \},

forms an additive group with p2 elements. It is easily seen to be closed with respect to multiplication since A satisfies its characteristic polynomial equation x2xb = 0. Simple inspection of the product shows multiplication is associative, commutative, and distributive. It is only left to determine what conditions on b imply that every nonzero element of F has a multiplicative inverse in F. Elements of F which are of the form xI + A have an inverse:

(x2 + xb)−1 ((x + 1)IA),

provided that x2 + xb ≠ 0 for any x in Z/pZ. This can be verified by direct multiplication and making use of the equation A2AbI = 0.

The number of b for which x2 + xb is irreducible over Z/pZ is quite numerous, being (p − 1)/2. It is only left to observe that v((u/v)I + A) = uI + vA.

Determining for which b that A is a primitive element for F is not as easy to analyze. For p, not too large for brute calculation of all B ∈ M(2, Z/pZ) such that Bp2−1 = I and BkI, for k = 1, 2, ..., p2 − 2, showed many cases. Such a matrix B is a primitive element for F. To see this notice that Bp2−2 = B−1 and so, if Bk = Br for 0 < r < k < p2 − 1, then Bkr = I, which is assumed not to be the case. As noted before, since B satisfies its characteristic equation, the powers of B must lie in the span of uI + vB. Since there are p2 − 1 of them distinct together with 0 they are F.

More generally:

Proposition. Let A ∈ M(2, Z/pZ) with characteristic polynomial x2 + bx + c. Then F, as defined above, is a field if and only if x2 + bx + c is irreducible over Z/pZ. Assume A is independent of I over Z/pZ.

Proof: 0, IF and is closed with respect to associative, commutative, and distributive addition and multiplication. Consider any element of F of the sort xI + A and consider the following calculation:

(xI + A)((xb)IA) = x2IA2bxIbA = x2I + (bA + cI) − bxIbA = (x2bx + c)I

The polynomial x2bx + c is the same as x2 + bx + c after substituting x for x so their irreducibilities are the same. In the case that x2 + bx + c is irreducible (x2bx + c)−1((xb)IA) is a multiplicative inverse for xI + A and F is a field. In the case that x2bx + c has a root x in Z/pZ then xI + A is a zero divisor and F is not a field.

Fpn (via n × n matrices in integers modulo p)[edit]

To clarify notation, it is the usual convention when P(x) = u0 + u1x + ... + ukxk is a polynomial and A is a matrix P(A) = u0I + u1A + ... + ukAk.

A monic polynomial P(x) is said to be minimal for A if P(A) = 0 and there is no non-zero polynomial of less degree for which A is a zero.

The characteristic polynomial of a n × n matrix A is given by P(x) = det(xIA), and has degree n.

By the Cayley–Hamilton theorem, a matrix A satisfies its characteristic equation, that is P(A) = 0.

If A has the characteristic polynomial

P(x) = a0 + a1x + ... + an−1xn−1 + xn,

then it satisfies the relation

An = −a0Ia1A − ... − an−1An−1.

Expressions of the kind u0I + u1A + u2A2 ... + un−1An−1, are closed with respect to multiplication besides addition. Since powers of a matrix commute with one another as do polynomials, the multiplication will be commutative, as well as associative and distributive (these last two being properties of matrix algebra).

Lemma. If P(x) is irreducible, then P(x) is also the minimal polynomial for A.

Proof: Suppose Q(x) is of positive degree less than n and the minimal polynomial for A instead. By the division algorithm:

P(x) = T(x)Q(x) + R(x), deg(R) < deg(Q),

R(x) ≠ 0 since P(x) is irreducible. But, Q(A) = 0, and P(A) = T(A)Q(A) + R(A) = 0, meaning R(A) = 0 too, which would be that Q(x) is not minimal for A.

Theorem. Let A ∈ M(n, Z/pZ) with characteristic polynomial P(x), and define F to be the span of {u0I + u1A + u2A2 ... + un−1An−1}, with u0, u1, ..., un−1Z/pZ. Then F is a field with pn elements if and only if P(x) is irreducible over Z/pZ.

Proof: Suppose P(x) is reducible, then there exist nontrivial polynomials Q(x), T(x) such that P(A) = T(A)Q(A) = 0, in which case F has zero divisors and is not a field.

Now, assume P(x) is irreducible. Then we apply the Remainder Theorem to uZ/pZ and we get P(x) = T(x)(xu) + P(u), where deg(T) = n − 1.

Then, P(A) = T(A)(AuI) + P(u)I = 0. Since P(x) is irreducible, P(u) ≠ 0 and it follows −(P(u))−1 T(A)(AuI) = I. So (AuI)−1 exists and is in F.

Now, let an induction hypothesis be that for any polynomial R(x) = u0 + u1x + ... + ukxk with k < m < n, (R(A))−1 exists and is in F.

Consider Q(x) = u0 + u1x + ... + umxm. By the division algorithm

P(x) = T(x)Q(x) + R(x), deg(R) < m

So, P(A) = T(A)Q(A) + R(A) = 0, −(R(A))−1T(A)Q(A) = I, and (Q(A))−1 = −(R(A))−1 T(A) exists and is in F. The induction proceeds until m = n − 1, and it is seen that F is a field.

Remark. In the above argument, the variable x can replace A, in the first place. The polynomials with their coefficients in Z/pZ having xn resolved by an irreducible monic polynomial of degree n, in the same manner, is a field.

Properties and facts[edit]

Wedderburn's little theorem[edit]

A division ring is a generalization of field. Division rings are not assumed to be commutative. There are no non-commutative finite division rings: Wedderburn's little theorem states that all finite division rings are commutative, hence finite fields. The result holds even if we relax associativity and consider alternative rings, by the Artin–Zorn theorem.

Ordering[edit]

Finite fields can not be ordered.

In an ordered field the elements

0 < 1 < 1 + 1 < 1 + 1 + 1 < ...

are all different, so that an ordered field necessarily contains infinitely many elements.

Frobenius automorphisms[edit]

If F is a finite field with q = pn elements, then, for all x in F we have: xq = x (see Analog of Fermat's little theorem below). Furthermore, the map

\begin{cases} f: \mathbf{F} \to \mathbf{F} \\ f(x) = x^p \end{cases}

is bijective and a homomorphism, and is therefore an automorphism on the field F which fixes the subfield with p elements. It is called the Frobenius automorphism, after Ferdinand Georg Frobenius. The fact that the Frobenius map is surjective implies that a finite field is perfect.

The Frobenius automorphism of a field of size pn has order n, and the cyclic group it generates is the full group of automorphisms of the field.

Containment[edit]

The field Fpn contains a copy of Fpm if and only if m divides n.

Suppose FpnFpm, then we can consider Fpn as a vector space over Fpm, of some finite dimension, say d. Therefore Fpn must have size (pm)d = pmd, so m divides n. And if m | n then there exist irreducible polynomials of every degree over Fpm.

Algebraic closure[edit]

A finite field F can not be algebraically closed.

Consider the polynomial:

f(T)=1+\prod_{\alpha \in \mathbf{F}} (T-\alpha)

f has no roots over F, as f (α) = 1 for all α in F.

The direct limit of the system:

{Fp, Fp2, ..., Fpn, ...},

with inclusion, is an infinite field. It is the algebraic closure of all the fields in the system, and is denoted by: \overline{\mathbf{F}_p}.

The inclusions commute with the Frobenius map, as it is defined the same way on each field (xx p), so the Frobenius map defines an automorphism of \overline{\mathbf{F}_p}, which carries all subfields back to themselves. In fact Fpn can be recovered as the fixed points of the n-th iterate of the Frobenius map.

However unlike the case of finite fields, the Frobenius automorphism on \overline{\mathbf{F}_p} has infinite order, and it does not generate the full group of automorphisms of this field. That is, there are automorphisms of \overline{\mathbf{F}_p} which are not a power of the Frobenius map. However, the group generated by the Frobenius map is a dense subgroup of the automorphism group in the Krull topology. Algebraically, this corresponds to the additive group Z being dense in the profinite integers (direct product of the p-adic integers over all primes p, with the product topology).

If we actually construct our finite fields in such a fashion that Fpn is contained in Fpm whenever n divides m, then this direct limit can be constructed as the union of all these fields. Even if we do not construct our fields this way, we can still speak of the algebraic closure, but some more delicacy is required in its construction.

Irreducibility of polynomials[edit]

If F is a finite field, a polynomial f (X) with coefficients in F is said to be irreducible over F if and only if f (X) is irreducible as an element of F[X].

Since F[X] is a unique factorization domain, a polynomial f (X) is irreducible if and only if it is prime as an element of F[X].

Number of monic irreducible polynomials of a given degree over a finite field[edit]

If Fq denotes the finite field of order q, then the number N of monic irreducible polynomials of degree n over Fq is given by:[4]

N(q,n)=\frac{1}{n}\sum_{d|n} \mu(d)q^{\frac{n}{d}},

where μ is the Möbius function. By the above formula, the number of irreducible polynomials of degree n over Fq is given by (q − 1)N(q, n). A (slightly simpler) lower bound on N also exists, and is given by:

N\geq\frac{1}{n} \left(q^n-\sum_{p|n, \ p \text{ prime}} q^{\frac{n}{p}}\right).

Algorithm for computing the irreducible factors of a given polynomial over a finite field[edit]

Multiplicative structure[edit]

In what follows F is a finite field with q elements, and F× = F\{0}.

Cyclic[edit]

The multiplicative group of every finite field is cyclic, a special case of a theorem mentioned in Fields. A generator for F× is called a primitive element, i.e. there exists an element x in F such that

F = {0, 1, x, x2, ..., xq−2}.

Unless q = 2, 3, the primitive element x is not unique. The set of generators has size φ(q − 1) where φ is Euler's totient function. If we fix a generator, then for any non-zero element a in F, there is a unique integer n with 0 ≤ nq − 2 such that

a = xn.

For a given a, n is called the discrete log of a in F, to the base x.

Analog of Fermat's little theorem[edit]

Theorem. Every element of a finite field of size q satisfies aq = a.

Proof: Since F× is a multiplicative group of order q − 1, Lagrange's theorem implies that aq−1 = 1 for all aF×. Hence aq = a for all aF×. Finally note that this also holds for 0.

Remark. When q is prime, this is just Fermat's little theorem, which states that apa (mod p) for any integer a and prime p.

Roots of unity[edit]

Let n > 0 be an integer, a n-th root of unity in F is a solution of the equation xn = 1, a n-th primitive root of unity is a solution of the equation xn = 1 that is not a solution of the equation xm = 1 for any positive integer m < n.

Unlike the n-th roots of unity in C, the number of n-th roots of unity in F is not n, it is equal to gcd(n, q − 1). Thus if nq − 1 then F has no primitive n-roots of unity, while if n | q − 1 then the number of primitive n-th roots of unity in F is φ(n).

Applications[edit]

Discrete exponentiation, also known as calculating a = xn from x and n, can be computed quickly using techniques of fast exponentiation such as binary exponentiation, which takes only O(log n) field operations. No fast way of computing the discrete logarithm n given a and x is known, and this has many applications in cryptography, such as the Diffie-Hellman protocol.

Finite fields also find applications in coding theory: many codes are constructed as subspaces of vector spaces over finite fields.

Within number theory, the significance of finite fields is their role in the definition of the Frobenius element (or, more accurately, Frobenius conjugacy class) attached to a prime ideal in a Galois extension of number fields, which in turn is needed to understand Artin L-functions of representations of the Galois group, the non-abelian generalization of Dirichlet L-functions.

Counting solutions to equations over finite fields leads into deep questions in algebraic geometry, the Weil conjectures, and in fact was the motivation for Grothendieck's development of modern algebraic geometry.

Some small finite fields[edit]

F2[edit]

+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1

F3[edit]

+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
× 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1

F4[edit]

+ 0 1 A B
0 0 1 A B
1 1 0 B A
A A B 0 1
B B A 1 0
× 0 1 A B
0 0 0 0 0
1 0 1 A B
A 0 A B 1
B 0 B 1 A

F8[edit]

Field of 8 elements represented as matrices
integers are modulo 2

element (0)     element (1)     element (2)     element (3)

  0  0  0         1  0  0         0  1  0         0  0  1
  0  0  0         0  1  0         0  0  1         1  1  0
  0  0  0         0  0  1         1  1  0         0  1  1

element (4)     element (5)     element (6)     element (7)

  1  1  0         0  1  1         1  1  1         1  0  1
  0  1  1         1  1  1         1  0  1         1  0  0
  1  1  1         1  0  1         1  0  0         0  1  0

+/  (0) (1) (2) (3) (4) (5) (6) (7)
(0)  0   1   2   3   4   5   6   7
(1)  1   0   4   7   2   6   5   3
(2)  2   4   0   5   1   3   7   6
(3)  3   7   5   0   6   2   4   1
(4)  4   2   1   6   0   7   3   5
(5)  5   6   3   2   7   0   1   4
(6)  6   5   7   4   3   1   0   2
(7)  7   3   6   1   5   4   2   0

x/  (0) (1) (2) (3) (4) (5) (6) (7)
(0)  0   0   0   0   0   0   0   0
(1)  0   1   2   3   4   5   6   7
(2)  0   2   3   4   5   6   7   1
(3)  0   3   4   5   6   7   1   2
(4)  0   4   5   6   7   1   2   3
(5)  0   5   6   7   1   2   3   4
(6)  0   6   7   1   2   3   4   5
(7)  0   7   1   2   3   4   5   6

F9[edit]

Field of 9 elements represented as matrices
integers are modulo 3

element (0)     element (1)     element (2)

  0  0            1  0            0  1
  0  0            0  1            1  1

element (3)     element (4)     element (5)

  1  1            1  2            2  0
  1  2            2  0            0  2

element (6)     element (7)     element (8)

  0  2            2  2            2  1
  2  2            2  1            1  0

+/  (0) (1) (2) (3) (4) (5) (6) (7) (8)
(0)  0   1   2   3   4   5   6   7   8
(1)  1   5   3   8   7   0   4   6   2
(2)  2   3   6   4   1   8   0   5   7
(3)  3   8   4   7   5   2   1   0   6
(4)  4   7   1   5   8   6   3   2   0
(5)  5   0   8   2   6   1   7   4   3
(6)  6   4   0   1   3   7   2   8   5
(7)  7   6   5   0   2   4   8   3   1
(8)  8   2   7   6   0   3   5   1   4

x/  (0) (1) (2) (3) (4) (5) (6) (7) (8)
(0)  0   0   0   0   0   0   0   0   0
(1)  0   1   2   3   4   5   6   7   8
(2)  0   2   3   4   5   6   7   8   1
(3)  0   3   4   5   6   7   8   1   2
(4)  0   4   5   6   7   8   1   2   3
(5)  0   5   6   7   8   1   2   3   4
(6)  0   6   7   8   1   2   3   4   5
(7)  0   7   8   1   2   3   4   5   6
(8)  0   8   1   2   3   4   5   6   7

F16[edit]

F16 is represented by the polynomials a + b x + c x2 + d x3.
a, b, c, and d are integers modulo 2
The polynomials are generated by the powers of x using the rule

x4 = 1 + x

e ( 0)        e ( 1)        e ( 2)        e ( 3)
[ 0  0  0  0] [ 1  0  0  0] [ 0  1  0  0] [ 0  0  1  0]

e ( 4)        e ( 5)        e ( 6)        e ( 7)
[ 0  0  0  1] [ 1  1  0  0] [ 0  1  1  0] [ 0  0  1  1]

e ( 8)        e ( 9)        e (10)        e (11)
[ 1  1  0  1] [ 1  0  1  0] [ 0  1  0  1] [ 1  1  1  0]

e (12)        e (13)        e (14)        e (15)
[ 0  1  1  1] [ 1  1  1  1] [ 1  0  1  1] [ 1  0  0  1]

+/   0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ 8_ 9_10_11_12_13_14_15_
 0_  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
 1_  1  0  5  9 15  2 11 14 10  3  8  6 13 12  7  4
 2_  2  5  0  6 10  1  3 12 15 11  4  9  7 14 13  8
 3_  3  9  6  0  7 11  2  4 13  1 12  5 10  8 15 14
 4_  4 15 10  7  0  8 12  3  5 14  2 13  6 11  9  1
 5_  5  2  1 11  8  0  9 13  4  6 15  3 14  7 12 10
 6_  6 11  3  2 12  9  0 10 14  5  7  1  4 15  8 13
 7_  7 14 12  4  3 13 10  0 11 15  6  8  2  5  1  9
 8_  8 10 15 13  5  4 14 11  0 12  1  7  9  3  6  2
 9_  9  3 11  1 14  6  5 15 12  0 13  2  8 10  4  7
10_ 10  8  4 12  2 15  7  6  1 13  0 14  3  9 11  5
11_ 11  6  9  5 13  3  1  8  7  2 14  0 15  4 10 12
12_ 12 13  7 10  6 14  4  2  9  8  3 15  0  1  5 11
13_ 13 12 14  8 11  7 15  5  3 10  9  4  1  0  2  6
14_ 14  7 13 15  9 12  8  1  6  4 11 10  5  2  0  3
15_ 15  4  8 14  1 10 13  9  2  7  5 12 11  6  3  0

x/   0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ 8_ 9_10_11_12_13_14_15_
 0_  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 1_  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
 2_  0  2  3  4  5  6  7  8  9 10 11 12 13 14 15  1
 3_  0  3  4  5  6  7  8  9 10 11 12 13 14 15  1  2
 4_  0  4  5  6  7  8  9 10 11 12 13 14 15  1  2  3
 5_  0  5  6  7  8  9 10 11 12 13 14 15  1  2  3  4
 6_  0  6  7  8  9 10 11 12 13 14 15  1  2  3  4  5
 7_  0  7  8  9 10 11 12 13 14 15  1  2  3  4  5  6
 8_  0  8  9 10 11 12 13 14 15  1  2  3  4  5  6  7
 9_  0  9 10 11 12 13 14 15  1  2  3  4  5  6  7  8
10_  0 10 11 12 13 14 15  1  2  3  4  5  6  7  8  9
11_  0 11 12 13 14 15  1  2  3  4  5  6  7  8  9 10
12_  0 12 13 14 15  1  2  3  4  5  6  7  8  9 10 11
13_  0 13 14 15  1  2  3  4  5  6  7  8  9 10 11 12
14_  0 14 15  1  2  3  4  5  6  7  8  9 10 11 12 13
15_  0 15  1  2  3  4  5  6  7  8  9 10 11 12 13 14

F25[edit]

F25 represented by the numbers a + b√2, a and b are integers modulo 5
generated by powers of  2 + √2

e ( 0) e ( 1) e ( 2) e ( 3) e ( 4)
0 + 0√2 1 + 0√2 2 + 1√2 1 + 4√2 0 + 4√2
e ( 5) e ( 6) e ( 7) e ( 8) e ( 9)
3 + 3√2 2 + 4√2 2 + 0√2 4 + 2√2 2 + 3√2
e (10) e (11) e (12) e (13) e (14)
0 + 3√2 1 + 1√2 4 + 3√2 4 + 0√2 3 + 4√2
e (15) e (16) e (17) e (18) e (19)
4 + 1√2 0 + 1√2 2 + 2√2 3 + 1√2 3 + 0√2
e (20) e (21) e (22) e (23) e (24)
1 + 3√2 3 + 2√2 0 + 2√2 4 + 4√2 1 + 2√2
+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 7 18 6 3 12 14 19 22 5 20 2 10 0 23 16 11 21 15 13 9 8 24 4 17
2 2 18 8 19 7 4 13 15 20 23 6 21 3 11 0 24 17 12 22 16 14 10 9 1 5
3 3 6 19 9 20 8 5 14 16 21 24 7 22 4 12 0 1 18 13 23 17 15 11 10 2
4 4 3 7 20 10 21 9 6 15 17 22 1 8 23 5 13 0 2 19 14 24 18 16 12 11
5 5 12 4 8 21 11 22 10 7 16 18 23 2 9 24 6 14 0 3 20 15 1 19 17 13
6 6 14 13 5 9 22 12 23 11 8 17 19 24 3 10 1 7 15 0 4 21 16 2 20 18
7 7 19 15 14 6 10 23 13 24 12 9 18 20 1 4 11 2 8 16 0 5 22 17 3 21
8 8 22 20 16 15 7 11 24 14 1 13 10 19 21 2 5 12 3 9 17 0 6 23 18 4
9 9 5 23 21 17 16 8 12 1 15 2 14 11 20 22 3 6 13 4 10 18 0 7 24 19
10 10 20 6 24 22 18 17 9 13 2 16 3 15 12 21 23 4 7 14 5 11 19 0 8 1
11 11 2 21 7 1 23 19 18 10 14 3 17 4 16 13 22 24 5 8 15 6 12 20 0 9
12 12 10 3 22 8 2 24 20 19 11 15 4 18 5 17 14 23 1 6 9 16 7 13 21 0
13 13 0 11 4 23 9 3 1 21 20 12 16 5 19 6 18 15 24 2 7 10 17 8 14 22
14 14 23 0 12 5 24 10 4 2 22 21 13 17 6 20 7 19 16 1 3 8 11 18 9 15
15 15 16 24 0 13 6 1 11 5 3 23 22 14 18 7 21 8 20 17 2 4 9 12 19 10
16 16 11 17 1 0 14 7 2 12 6 4 24 23 15 19 8 22 9 21 18 3 5 10 13 20
17 17 21 12 18 2 0 15 8 3 13 7 5 1 24 16 20 9 23 10 22 19 4 6 11 14
18 18 15 22 13 19 3 0 16 9 4 14 8 6 2 1 17 21 10 24 11 23 20 5 7 12
19 19 13 16 23 14 20 4 0 17 10 5 15 9 7 3 2 18 22 11 1 12 24 21 6 8
20 20 9 14 17 24 15 21 5 0 18 11 6 16 10 8 4 3 19 23 12 2 13 1 22 7
21 21 8 10 15 18 1 16 22 6 0 19 12 7 17 11 9 5 4 20 24 13 3 14 2 23
22 22 24 9 11 16 19 2 17 23 7 0 20 13 8 18 12 10 6 5 21 1 14 4 15 3
23 23 4 1 10 12 17 20 3 18 24 8 0 21 14 9 19 13 11 7 6 22 2 15 5 16
24 24 17 5 2 11 13 18 21 4 19 1 9 0 22 15 10 20 14 12 8 7 23 3 16 6
× 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
2 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1
3 0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2
4 0 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3
5 0 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4
6 0 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5
7 0 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6
8 0 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7
9 0 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8
10 0 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9
11 0 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10
12 0 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11
13 0 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12
14 0 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13
15 0 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14
16 0 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
17 0 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
18 0 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
19 0 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
20 0 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
21 0 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
22 0 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
23 0 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
24 0 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

See also[edit]

Notes[edit]

  1. ^ This notation was introduced by E. H. Moore in an address given in 1893 at the International Mathematical Congress held in Chicago Mullen & Panario 2013, p. 10.
  2. ^ Moore, E. H. (1896), "A doubly-infinite system of simple groups", in E. H. Moore, et. al., Mathematical Papers Read at the International Mathematics Congress Held in Connection with the World's Columbian Exposition, Macmillan & Co., pp. 208–242 
  3. ^ A Solitaire Game and Its Relation to a Finite Field http://alexandria.tue.nl/repository/freearticles/598441.pdf
  4. ^ Jacobson 2009, §4.13

References[edit]

External links[edit]