5
$\begingroup$

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the multiplication factor has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

$\endgroup$
7
$\begingroup$

Fix a finite field $k$ of $q$ elements, with additive identity $0_k$ and multiplicative identity $1_k$.

  1. For any integer $n$, let $[n]$ be the $n$-fold sum of $1_k$. Clearly $[a + b] = [a] + [b]$ and $[a\cdot b] = [a] \cdot [b]$. Since $k$ is finite, for any $n$, in the sequence $[a]$, $[a + 1]$, $[a + 2]$, etc., there must be a repeat; let $p$ be the smallest integer so that $[a] = [a + p] = [a] + [p]$. Then $[p] = 0_k$, and in the sequence $[1], [2], [3], \ldots, [p]$, the element $[p]$ is the first zero element.

  2. $p$ is called the characteristic of the field. Suppose $p$ were composite, with factors $1 < a \leq b < p$ so that $p = a\cdot b$. Then $0_k = [p] = [a\cdot b] = [a] \cdot [b]$, but $[a]$ and $[b]$ are nonzero because $[p]$ was the first zero element in the sequence $[1], [2], [3], \ldots, [p]$. This is impossible in a field, so $p$ must be prime.

  3. The set $\{[0],[1],[2],\ldots,[p-1]\}$ forms a subfield $k_p$ of $k$, since it is by construction closed under addition and multiplication. Thus the extension field $k$ forms a vector space over the subfield $k_p$. Being finite, this vector space is necessarily finite-dimensional, of dimension $n$, and thus has exactly $p^n$ elements. Hence $q = p^n$ for some $n$.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I don't understand that proof. How is $[p]$ nonzero if it's equal to $0_k$? How are the elements $[1],[2],[3]...$ equal to zero? $\endgroup$ – Zen Hacker May 27 '18 at 16:26
  • 1
    $\begingroup$ I don't understand that proof. How is $[p]$ nonzero if it's equal to $0_k$? How are the elements $[1],[2],[3]...$ equal to zero? $\endgroup$ – Zen Hacker May 27 '18 at 16:26
  • 1
    $\begingroup$ @ZenHacker Typo! Fixed. $\endgroup$ – Squeamish Ossifrage May 27 '18 at 16:26
  • $\begingroup$ Okay, now it makes sense. $\endgroup$ – Zen Hacker May 27 '18 at 16:28
  • $\begingroup$ What about composite fields where a = b and p = a ⋅ b, such as GF(2^8) mapped to GF(16^2) = GF((2^4)^2), where a = b = 16? (For this to work, map(x) + map(y) = map(x + y) and map(x) ⋅ map(y) = map(x ⋅ y) ). I assume that for both fields, the characteristic is still 2. $\endgroup$ – rcgldr May 27 '18 at 20:00

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.