5
$\begingroup$

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 [1].

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.


[1] Noga Alon and Gil Cohen. On Rigid Matrices and Subspace Polynomials. Electronic Colloquium on Computational Complexity, Report No. 133 (2012).

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – vzn Oct 27 '12 at 15:43
  • $\begingroup$ What does “binary finite field” mean? $\endgroup$ – Tsuyoshi Ito Oct 27 '12 at 15:56
  • $\begingroup$ 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 $\endgroup$ – vzn Oct 27 '12 at 16:54
  • 3
    $\begingroup$ $\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. $\endgroup$ – Peter Shor Oct 27 '12 at 23:16
7
$\begingroup$

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.
$\endgroup$
4
$\begingroup$

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}[2]^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}[2]^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}[2]^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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.