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 is a field if and only if there exists an element such that for every , there exists an element such that
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.
Formally, a field is a set equipped with two binary operations and satisfying the following properties:
- is an abelian group under addition; that is,
- F is closed under addition, meaning that
- There is an identity element so that for every , , and there exists an element such that
- Addition is both commutative and associative: for , , and .
- (not including 0) is an abelian group under multiplication as well. Its identity element is 1, meaning that , and there exists an such that .
- Distributivity holds: .
- 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 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, , and , so that the distributive property holds.
Many "usual" number systems are examples of fields. For instance,
- The rational numbers form a field, because for any , is also in .
- The real numbers form a field, for the same reason as above.
There are several number system examples that are not fields; for example,
- integers (since the only integers with multiplicative inverses are -1 and 1)
- integers modulo for composite (for a similar reason)
- odd or even numbers (for the same reason)
- Roman numerals (since there is no zero)
- irrational numbers (since, again, there is no zero).
There are also non-infinite examples of fields, known as finite fields. A simple example is the field for any prime number , consisting of the set and operations defined by modulo . Note that is necessarily prime for this construction to work, else an element will not have an inverse; for instance, 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 despite the above note. It consists of four elements: so that is the additive identity (i.e. 0) and is the multiplicative identity (i.e. 1). The rest of the relations are determined by the following table:
which can be derived from direct logic; e.g. note that , and if , one would have , which is impossible, and hence , so for any . Then cannot be , because , which is impossible as . The rest of the table 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 ; i.e. is a generator. Details on why such a field belongs to the area of finite fields.
Fields, especially finite fields, have a number of major applications in cryptography and error correction; one major example is in cyclic redundancy checking which implicitly uses finite fields for error detection, as follows:
- Choose an -bit number to be used as the redundancy check. It is fixed.
- When transmitting a message , calculate the exclusive or of and , applied to the leftmost digits of . Repeat this process (removing leading zeros as necessary) until no longer possible (when has more digits than the result of the xor calculation). The result of the final xor calculation is the check value.
- Transmit both and the check value.
- When receiving a message , calculate the check value as detailed above, and 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 was (all in base 2 numbers), and one wanted to transmit the message . So one would calculate
So the result is 1001001. This process is then applied again:
and a final time:
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 --the polynomials with coefficients equal to either 0 or 1--and calculating the coset representative of the message in the quotient ring formed by , where is the polynomial corresponding to the redundancy check 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 is always used due to its natural relation with the binary architecture of computers.