MathWiki - finite_fields

What are rings and fields?

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:12:47+00:00

What are rings and fields? 1. Introduction In high school you probably have studied many arithmetic laws of real numbers and how to apply them in order to compute or solve equations: $ab = ba$, $(a + b) + c = a + (b+c)$, $(a+b)^2 = a^2 + 2ab + b^2$ and so on. In computational algorithms, it is often the case that variables are not real numbers but some other objects, but we still apply some operations to them: e. g. one can add and multiply matrices, one can add and multiply 32-bit integers…

Long division of polynomials

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:13:33+00:00

Long division of polynomials In the next section, where we will construct finite fields other than $\mathbb Z_n$, we will need to calculate the remainder when one polynomial is divided with another. It might come as a surprise that you can do such thing with polynomials — but actually this is very much like the division of integers.$a$$b$$(q, r)$$a = qb + r$$0 \leq r < b$$q$$r$$a$$b$$a$$b$$\mathbb R$$\mathbb Z_p$$p$$b$$(q, r)$$a = qb + r$$r$$b$$q$$r$$a$$b$$a(X) = 4X^3 + 5X^2 + X + 5$$b(X) = 2X…

The general way of constructing finite fields

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:14:47+00:00

The general way of constructing finite fields 1. Yet another finite field We know that $\mathbb Z_n$ is a finite field if $n$ is a prime. Do there exist other examples of finite fields? Let us try to construct one. A way how one could try to construct a finite field would be to start with a data structure for which addition is already defined and then try to define multiplication so that the resulting structure would satisfy all field axioms. Let us consider, for instance, the set of two bi…

Isomorphisms, homomorphisms, automorphisms. Classification of all finite fields

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:16:26+00:00

Isomorphisms, homomorphisms, automorphisms. Classification of all finite fields 1. What is an isomorphism? The word isomorphic means in mathematics that one can identify two structures by relabeling the elements of one structure. For example, consider the residue class field $\mathbb Z_2$$+$$\times$$S = \{$$, $$\}$$+$$\times$$0$$1$$\mathbb Z_2$$(S; +, \times)$$S$$\mathbb Z_2$$S$$\mathbb Z_2$$S$$\mathbb Z_2$$f : S \to \mathbb Z_2$$f($$) = 1$$f($$) = 0$$S$$Z_2$$\mathcal{F}$$\mathcal{G}$$\mat…

Computations in finite fields

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:19:28+00:00

Computations in finite fields 1. Addition and multiplication For clarity, let us consider the $8$-element finite field which is defined by the irreducible polynomial $\alpha^3+\alpha+ 1$. Then any computation is just arithmetic with polynomials with the exception that the end result must be reduced modulo $\alpha^3+\alpha+ 1$. For instance, \[\begin{align*} (\alpha^2+ \alpha+ 1)(\alpha^2+ 1) % &= \alpha^4+ \alpha^3+ \alpha^2 + \alpha^2+ \alpha+ 1\\ &= \alpha^4+ \alpha^3+ \alpha+ 1 …

What is a group?

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:22:36+00:00

What is a group? In lesson What are rings and fields?, we learned the definitions of ring and field. In the next lesson we'll need one more algebraic concept — group. This lesson gives some basic facts about groups. 1. An introductory example Before giving the definition of group, let us start with an example of a group that will also be useful later in this topic. Let $\mathcal F$$a$$S = \{ a^k\ |\ k \in \mathbb Z \} = \{\ldots,\ a^{-3}, a^{-2}, a^{-1}, 1, a, a^2, a^3, \ldots \}$$a$$a^{-n…

Multiplicative group in finite fields

Anonymous (anonymous@undisclosed.example.com) — 2016-02-23T23:10:34+00:00

Multiplicative group in finite fields In this lesson we shall prove the following theorem and study its consequences. Theorem. Let $\mathbb{F}_{p^k}$ be finite field. Then there exists an element $a\in\mathbb{F}_{p^k}$ that generates the entire multiplicative group. In other words, the theorem says that there exists an element $a \in \mathbb F_{p^k}^*$$\mathbb F_{p^k}$$a^n$$n$$\mathbb{F}_8^*$$\alpha^3+\alpha+ 1$$7$$\mathbb{F}_8^*$$1$$7$\[\begin{align*} &\begin{aligned} \alpha^3 &=\alph…

Subfields

Anonymous (anonymous@undisclosed.example.com) — 2014-01-08T13:47:21+00:00

Subfields 1. What is a subfield? A large field can contain a smaller field. For instance, $\mathbb{F}_{2^k}$ always contains as a sub-field the 2-element subset $\mathcal{S} = \left\{0,1\right\}$ consisting of constant polynomials — it is easy to check that this subset satisfies the definition of field (it is closed under addition and multiplication; it contains a zero element and an identity element; every element has an opposite element in $\mathcal{S}$$-0 = 0$$-1 = 1$$\mathbb{F}_{2^k}$$\…