1. Galois Field

1.1. Definition

“Galois Field is a Field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number.” – From Wikipedia

Usually, multiplication, addition and subtraction can easily been checked that modulo p is a field. But in order to satisfy division, or say inverse, p should be a prime number or an exponential of a prime number.

We will show that every element \(x \in \{1, 2, \cdots, p-1\}\) has an inverse in \(GF(p)\) where \(p\) is a prime number. Indeed, for a given \(x\) take all the products of the form \(x \times y = (x \cdot y)~mod~p\) for \(y \in GF(p)\). These are unique, otherwise, if \((x \cdot y_1)~mod~p = (x \cdot y_2)~mod~p`then :math:`x(y_1 - y_2)~mod~p=0\), i.e., \(p\) divides \(x(y_1 - y_2)\). Thus, \(p\) divides one of the factors \(x\), or \(y_1 - y_2\), which is a contradiction since both \(x\) and \(y_1 - y_2\) are smaller than p. Since \(x\times y\) are unique, and since there are exactly \(p\) of them, they have to go through all numbers \(\{0, 1, \cdots, p-1\}\), thus one of them, say, \(x\times y_0\) equals to 1. Thus x has an inverse and is \(x^{-1}=y_0\).

The modulo can also extend to polynomials.

1.2. Terminology, Properties, Theorems

1.2.1. Polynomials on GF(p^m)

Polynomial of degree \(m\) defined on \(GF(p)\) looks like

\[g(X) = g_0 + g_1 X + g_2 X^2 + \cdots + g_m X^m.\]

\(g_i\) for \(0 \leq i \leq m\) are elements in \(GF(p)\).

If \(g_m\) is 1, the corresponding polynomial is call monic.

If a polynomial of degree \(m\) over \(GF(p)\) cannot be written as a multiplication of two other polynomials over the same field, this polynomial is called irreducible polynomial.

E.g. Since \(X^2 + 1 = (X + 1)^2 = X^2 + 2 % 2 X + 1 = X^2 + 1\), \(X^2 + 1\) is NOT irreducible over \(GF(2)\).

1.2.2. Properties for GF

For \(GF(p)\) where \(p\) is a prime, \(GF(p^m)\) is also a field where \(m\) is a positive integer.

\(GF(p^m)\) is the extension field of \(GF(p)\), and \(GF(p)\) is the ground field of \(GF(p^m)\).

1.2.3. Abelian Group

Abelian Group is also called Commutative Group. If the result of operation doesn’t depend of the order the two involved elements chosen from the group, this group is called Abelian Group.

1.2.4. Modular Arithmetic

Integer \(a\) is congruent to integer \(b\) modulo integer \(m\) and it is written as \(a \equiv b~mod~m\)

For example:

\[\begin{split} &4 \equiv 1~mod~3\\ &-12~mod~7 \equiv -2~mod~7\end{split}\]

• If \(a \equiv b~mod~m\) and \(c > 0\), then \(ac \equiv bc ~mod~m\) and \(a^c \equiv b^c ~mod~m\).

• If \(a \equiv b~mod~m_1\), \(a \equiv b~mod~m_2\), \(\cdots\), \(a \equiv b~mod~m_k\), then \(a \equiv b~mod~LCM(m_1, m_2, \cdots, m_k)\)

• If \(k\) is a positive divisor of \(m\), i.e. \(gcd(m, k) = k\), then \(a \equiv b~mod~m \Rightarrow a \equiv b~mod~k\)

• If \(ac \equiv bc~mod~m\) and \(gcd(c, m) = 1\), then \(a \equiv c ~mod~m\)

  If \(gcd(c, m) \neq 1\), e.g. \(c = m\), then \(ac \equiv am~mod~m = 0\). We cannot conclude that \(a \equiv 0 ~mod~m\)

1.2.5. Cyclic Group

A group is cyclic if every inside element is a power of some fixed element.

For example, by changing \(k\), \(a^k ~mod~p\) can generate every element in a set. \(a\) is a generator of the group.

See the following example.

\[\begin{split}3^1 ~mod~ 7 = 3\\ 3^2 ~mod~ 7 = 2\\ 3^3 ~mod~ 7 = 6\\ 3^4 ~mod~ 7 = 4\\ 3^5 ~mod~ 7 = 5\\ 3^6 ~mod~ 7 = 1\\ 3^7 ~mod~ 7 = 3\end{split}\]

We see that the period of \(3^i mod 7\) is 6 and the modulo result contains 1, 2, 3, 4, 5, 6 which is a rearrangement of all non-zero reminders (not always from 1 to modular number) modulo 7. So 3 is a primitive root modulo 7.

1.2.6. Reduced Residue Set

Set \(R\) for modulus \(m\) is called complete residue set modulus m if \(R=\{0, 1, 2, \cdots, m-1\}\). If elements that are not co-prime to \(m\) are removed from \(R\), the new set \(Q\) is called reduced residue set

For example: For modules 10, number 1, 3, 7, 9 are co-prime to 10, and 2, 4, 5, 6, 8, 10 share a gcd greater than 1 with 10. So the reduced residue set \(Q\) is

\[Q = \{1, 3, 7, 9\}\]

1.2.7. Euler’s Totient Function

Euler’s Totient Function is often denoted as \(\phi(n)\). It counts the positive integers up to a given integer \(n\) that are relatively prime to \(n\). It is the cardinality of the reduced residue set.

For example: For modules 10, \(Q = \{1, 3, 7, 9\}\). Then \(\phi(10)=\|Q\| = 4\)

Euler’s Totient Function has the following properties:

• \(\phi(p) = p-1\) if \(p\) is a prime number

• \(\phi(p^k) = p^{k-1}(p-1)\) if \(p\) is a prime number and \(k \geq 1\) For numbers from 1 to \(p^k-1\), the possible values for \(gcd(m, p^k)\) can only be \(1, p, p^2, p^3, \cdots, p^k\). So the numbers that can share a common divider with \(p^k\) which is not 1 has to be a multiple of \(p, p^2, p^3, \cdots, p^{k-1}\) say \(p, 2p, 3p, \cdots, p^{k-1}p\) There are \(p^{k-1}\) of them. So \(\phi(p^k) = p^k - p^{k-1}\).

• \(\phi(ab) = \phi(a)\phi(b)\)

1.2.8. Fermat’s Little Theorem

\[a^p \equiv a~mod~p\]

I find that the proof using modulo properties is very interesting. For sequence

\[a, 2a, 3a, \cdots, (p-1)a\]

if we apply modulo \(p\) on each of them we have a rearrangement of

\[1, 2, 3, \cdots, p-1\]

Now we multiply them and have

\[\begin{split} &a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots \times (p-1)~mod~p\\ &\Rightarrow a^{p-1}(p-1)! \equiv (p-1)! ~mod~p\\ &\Rightarrow a^{p-1} \equiv 1~mod~p\end{split}\]

1.2.9. Euler’s Theorem

Euler’s Theorem is a generalization of Fermat’s little theorem.

\[a^{\phi(n)} \equiv 1~mod~n ~~if~a~is~coprime~to~n\]

\(a\) and \(n\) are coprime to each other means \(gcd(a, n)=1\).