# Fields

In abstract algebra, a **field** is a type of commutative ring in which every nonzero element has a multiplicative inverse; in other words, a ring \(F\) is a field if and only if there exists an element \(e\) such that for every \(a \in F\), there exists an element \(a^{-1} \in F\) such that
\[a \cdot a^{-1} = a^{-1} \cdot a = e\]

Fields are useful in forming the scalars in a given vector space; for instance, polynomials can draw coefficients from the field of real numbers, but also may be restricted to the rationals. Finite Fields, or fields with a finite number of elements, are extensively applied to cryptography and error correction, along with more theoretical areas such as Galois Theory.

## Formal definition

Formally, a **field** \(F\) is a set equipped with two binary operations \(+\) and \(\times\) satisfying the following properties:

- \(F\) is an abelian group under addition; that is,

- F is closed under addition, meaning that \(a,b \in F \implies a+b \in F\)
- There is an identity element \(0 \in F\) so that for every \(a \in F\), \(a + 0 = 0 + a = a\), and there exists an element \(-a \in F\) such that \(a + (-a) = (-a) + a = 0\)
- Addition is both commutative and associative: for \(a,b,c \in F\), \((a + b) + c = a + (b + c)\), and \(a + b = b + a\).
- \(F\) (not including 0) is an abelian group under multiplication as well. Its identity element is 1, meaning that \(a \cdot 1 = 1 \cdot a = a\), and there exists an \(a^{-1} \in F\) such that \(a \cdot a^{-1} = a^{-1} \cdot a = 1\).
- Distributivity holds: \(a \cdot (b + c) = a \cdot b + a \cdot c\).
- 0 and 1 are distinct (this is necessary to exclude the trivial ring consisting of one element).

The definition of a field differs from the definition of a ring only in the criterion that \(F\) has a multiplicative inverse; thus, a field can be viewed as a special case of a ring. More intuitively speaking, a field can be viewed as a set equipped with *four* binary operations, \(+, -, \cdot\), and \(\div\), so that the distributive property holds.

## Examples

Many "usual" number systems are examples of fields. For instance,

The rational numbers \(\mathbb{Q}\) form a field, because for any \(r \in \mathbb{Q}\), \(r^{-1} = \frac{1}{r}\) is also in \(\mathbb{Q}\).

The real numbers \(\mathbb{R}\) form a field, for the same reason as above.

There are also non-infinite examples of fields, known as finite fields. A simple example is the field \(F_p\) for any prime number \(p\), consisting of the set \(\{0, 1, \ldots, p-1\}\) and operations defined by modulo \(p\). Note that \(p\) is necessarily prime for this construction to work, else an element will not have an inverse; for instance, \(F_6\) is not a field because 2 (and 3, and 4) have no multiplicative inverse.

Another canonical example is the **field with four elements**, sometimes called \(F_4\) despite the above note. It consists of four elements: \(O, I, A, B\), so that \(O\) is the additive identity (i.e. 0) and \(I\) is the multiplicative identity (i.e. 1). The rest of the relations are determined by the following tables:

\(\cdot\) | O | I | A | B | + | O | I | A | B | |

O | O | O | O | O | O | O | I | A | B | |

I | O | I | A | B | I | I | O | B | A | |

A | O | A | B | I | A | A | B | O | I | |

B | O | B | I | A | B | B | A | I | O |

which can be derived from direct logic; e.g. note that \(I + I + I + I = O\), and if \(I + I \neq O\), one would have \((I + I) \cdot (I + I) = O, I + I \neq O\), which is impossible, hence \(I + I = O\), and so \(X + X = O\) for any \(X\). Then \(A \cdot A\) cannot be \(I\), because \(A \cdot A = I \implies (A - I) * (A - I) = 0\), which is impossible as \(A \neq I\). The rest of the tables are filled in similarly.

It is somewhat surprising that such an ad-hoc method actually results in a field and not in, for example, a direct contradiction. This is due in part to the fact that every nonzero element is a power of \(A: A^1 = A, A^2 = B, A^3 = I\); i.e. \(A\) is a **generator**. Details on *why* such a field belongs to the area of finite fields.

## Field extensions

## Applications

Fields, especially finite fields, have a number of major applications in cryptography and error correction; one major example is in **cyclic redundancy check**ing which implicitly uses finite fields for error detection, as follows:

- Choose an \(n\) bit number to be used as the redundancy check. It is fixed.
- When transmitting a message \(m\), calculate the exclusive or of \(m\) and \(n\), applied to the leftmost digits of \(m\). Repeat this process (removing leading zeros as necessary) until no longer possible (when \(n\) has more digits than the result of the xor calculation). The result of the final xor calculation is the
**check value** - Transmit both \(m\) and the check value.
- When receiving a message \(m\), calculate the check value as detailed above, then compare it to the received check value. If they differ, the transmission was corrupted in some place.

For example, suppose the chosen redundancy check \(n\) was \(1011\) (all in base 2 numbers), and one wanted to transmit the message \(11111001\). So one would calculate:

1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |

xor | 1 | 0 | 1 | 1 | ||||

0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |

So the result is 1001001. This process is then applied again:

1 | 0 | 0 | 1 | 0 | 0 | 1 | |

xor | 1 | 0 | 1 | 1 | |||

0 | 0 | 1 | 0 | 0 | 0 | 1 |

and a final time:

1 | 0 | 0 | 0 | 1 | |

xor | 1 | 0 | 1 | 1 | |

0 | 0 | 1 | 1 | 1 |

at which point the algorithm stops, because the redundancy check 1011 has more digits than the result 111. This makes the check value 111.

Mathematically speaking, the algorithm is viewing binary strings as being elements of \(\mathbb{F}_2[X]\) -- the polynomials with coefficients equal to either 0 or 1 -- and calculating the coset representative of the message in the quotient ring formed by \(\mathbb{F}_2[X] / P_{\text{check}}[X]\), where \(P_{\text{check}}[X]\) is the polynomial corresponding to the redundancy check (\(x^3 + x +1\) in the above example). Thus field theory allows for analysis of the algorithm and for choosing an appropriate redundancy check. It is even possible to perform the calculations over a different field, but in practice \(\mathbb{F}_2[X]\) is always used due to its natural relation with the binary architecture of computers.