GF(2)

GF(2)

GF(2) (also F2 or Z/2Z) is the Galois field of two elements. It is the smallest nontrivial finite field, a consequence of the fact that 2 is a prime number.

Definition

The two elements are nearly always called 0 and 1, being the additive and multiplicative identities, respectively. The field's addition operation is given by the table

and its multiplication operation by the following table.

Properties

:main|finite fieldAs 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.

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 integers and real numbers. Since modern computers also represent data in binary code, GF(2) is an important tool for studying algorithms on these machines that can be defined by a series of bitwise operations. 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 vague|date=August 2008. Properties of LFSRs, checksums and some ciphers can be studied mathematically by expressing them as operations in GF(2).


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”