# What are some applications of binary finite fields in CS?

I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F_2}$, are used in CS in some places such as circuit theory .

What are some key applications of finite fields in CS?

I am also looking for uses of $\mathbb{F_{2}^n}$ which Mathworld shows can be represented as binary vectors.

• notation. does $\mathbb{F_{2^n} = F_2^n}$? also the pages do not describe the vector algebra much, any links? do the binary vectors (which can be seen as coefficients of polynomials) operate like addition/multiplication in binary over mod $2^n$? – vzn Oct 27 '12 at 15:43
• What does “binary finite field” mean? – Tsuyoshi Ito Oct 27 '12 at 15:56
• it seems $\mathbb{F_{2^n} \ne F_2^n}$ as in the edit on this post? iirc the latter is a "bitwise" addition/multiplication & the former is not. just found this nice example for $\mathbb{F_{2^8}}$ wrt AES crypto by neal wagner – vzn Oct 27 '12 at 16:54
• $\mathbb{F}_2^n$ is the $n$-dimensional vector space over $\mathbb{F}_2$, which is not a finite field. $\mathbb{F}_{2^n}$ is the finite field with $2^n$ elements. The difference between them is that $\mathbb{F}_{2^n}$ has a multiplicative structure that $\mathbb{F}_2^n$ does not. The mathematical term for the fields $\mathbb{F}_{2^n}$ is finite fields of characteristic 2. – Peter Shor Oct 27 '12 at 23:16

Finite fields come up in many places. Here are just a few examples:

1. The Razborov-Smolensky polynomial method.
2. Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication.
3. List decoding - codes like Reed-Muller are algebraic codes.
4. Algebraization, the method used to prove IP=PSPACE.
5. Elliptic curves over finite fields are used in cryptography.

For one example, it shows up in the analysis of approximation algorithms for Feedback Vertex Set.

The characteristic vector of a simple cycle $C$ in a graph $G = (V, E)$ is a vector in $\mathbb{GF}^m, m = |E|$. A vector over this field has 1s in components correspond to edges of $C$ and 0s in the other components.

We can use this to describe the cycle space of $G$. That is, a subspace of $\mathbb{GF}^m$ that is spanned by the characteristic vector of all simple cycles of $G$. The cyclomatic number of $G$, $\text{cyc}(G)$, is the dimension of this space. Using $\text{comps}(G)$ to denote the number of connected components in a graph we have $$\text{cyc}(G) = |E| - |V| + \text{comps}(G).$$

The vectors of $\mathbb{GF}^m$ correspond to cut vectors of $G$ where a 1 corresponds to a component that has an edge in the cut, and 0 otherwise.

Using this fact, you can derive results giving an upper bound of $2 \text{OPT}$ for an approximation algorithm using a local-ratio scheme.