GF(2)
Encyclopedia
GF (also F2 or Z/2Z) is the Galois field
of two elements. It is the smallest finite field
.
and multiplicative identities, respectively. The field's addition operation is given by the table
and its multiplication operation by the following table.
As a consequence of modular arithmetic
which forms the basis of finite fields, these two elements and these two operations constitute a system with many of the important properties of familiar number systems: addition and multiplication are commutative and associative, multiplication is distributive over addition, addition has an identity element
(0) and an inverse for every element, and multiplication has an identity element (1) and an inverse for every element but 0.
s and real number
s. Since modern computer
s also represent data in binary code
, GF(2) is an important tool for studying algorithm
s on these machines that can be defined by a series of bitwise operation
s. For example, many techniques of matrix algebra apply to matrices of elements in GF(2) (see matrix ring
), including matrix inversion, which is important in the analysis of many binary algorithms . Properties of LFSR
s, checksum
s and some cipher
s can be studied mathematically by expressing them as operations in GF(2).
Galois theory
In mathematics, more specifically in abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory and group theory...
of two elements. It is the smallest finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
.
Definition
The two elements are nearly always called 0 and 1, being the additiveAdditive identity
In mathematics the additive identity of a set which is equipped with the operation of addition is an element which, when added to any element x in the set, yields x...
and multiplicative identities, respectively. The field's addition operation is given by the table
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
and its multiplication operation by the following table.
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Properties
As a consequence of modular arithmetic
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
which forms the basis of finite fields, these two elements and these two operations constitute a system with many of the important properties of familiar number systems: addition and multiplication are commutative and associative, multiplication is distributive over addition, addition has an identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
(0) and an inverse for every element, and multiplication has an identity element (1) and an inverse for every element but 0.
Bitwise operations
The addition and multiplication operations in GF(2) are also the bitwise operators XOR and AND, respectively.Applications
Many familiar and powerful tools of mathematics work in GF(2) just as well as in the integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s and real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. Since modern computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s also represent data in binary code
Binary code
A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...
, GF(2) is an important tool for studying algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s on these machines that can be defined by a series of bitwise operation
Bitwise operation
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
s. For example, many techniques of matrix algebra apply to matrices of elements in GF(2) (see matrix ring
Matrix ring
In abstract algebra, a matrix ring is any collection of matrices forming a ring under matrix addition and matrix multiplication. The set of n×n matrices with entries from another ring is a matrix ring, as well as some subsets of infinite matrices which form infinite matrix rings...
), including matrix inversion, which is important in the analysis of many binary algorithms . Properties of LFSR
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
s, checksum
Error detection and correction
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...
s and some cipher
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...
s can be studied mathematically by expressing them as operations in GF(2).