Is $x$ always a primitive element of $\text{GF}(2^m)$?

727 Views Asked by At

I checked using MATLAB that $x$ is a primitive element of $\text{GF}(2^m)$ for $m\le 16$. Is the statement true for $m > 16$?

EDIT: In this question, we represent an element of $\text{GF}(2^m)$ as a polynomial of $x$ with degree at most $m-1$ with coefficients drawn from $\text{GF}(2)$. I used the default primitive polynomials (see https://www.mathworks.com/help/comm/ref/gf.html ).

1

There are 1 best solutions below

0
On BEST ANSWER

Short answer: if the irreducible polynomial used to generate the binary extension field $\mathrm{GF}(2^m)$ is primitive, then yes $x$ is always a primitive element. Although, the irreducible polynomial need not be primitive. Matlab always uses a primitive polynomial as its default irreducible polynomial.

A Galois extension field $\mathrm{GF}(p^m)$ is created using an irreducible polynomial over $\mathrm{GF}(p)$ of degree $m$. If the irreducible polynomial is primitive, then the field element $x$ is a primitive element $\alpha$ of the field, meaning the field elements can be represented by its powers $\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m - 2}\}$. When the irreducible polynomial is primitive, the polynomial representation of field elements use $\alpha$ as the polynomial indeterminate (since $x = \alpha$), $c_{m-1}\alpha^{m-1} + \dots + c_1\alpha + c_0 \in \mathrm{GF}(p^m)$ for $c_i \in \mathrm{GF}(p)$.

Definition: A polynomial $f(x) \in \mathrm{GF}(p)[x]$ is reducible over $\mathrm{GF}(p)$ if it can be represented as $f(x) = g(x)h(x)$ for some non-constant $g(x), h(x) \in \mathrm{GF}(p)[x]$ of strictly lower degree. If $f(x)$ is not reducible, it is said to be irreducible. Since Galois fields are not algebraically closed, such irreducible polynomials exist.

Definition: A degree-$m$ polynomial $f(x)$ over $\mathrm{GF}(p)$ is primitive if it is irreducible and $f(x)\ |\ (x^k - 1)$ for $k = p^m - 1$ and no $k$ less than $p^m - 1$.

I created a python package galois that extends numpy arrays for Galois fields. It mimics a lot of functionality of Matlab's finite field functions. Here are some examples using the library.

In $\mathrm{GF}(2^4)$, which I'm using because it's a small field, $x^4 + x + 1$ and $x^4 + x^3 + 1$ are primitive polynomials of degree 4. Matlab and my library's default irreducible polynomial is $x^4 + x + 1$ (which is primitive). My library contains a repr_table() method to display all field element representations as powers of a primitive element and as polynomials over $\mathrm{GF}(p)$. Since the irreducible polynomial is primitive, notice the polynomial $x$ = $\alpha$ and all the powers of $\alpha$ uniquely generate the field.

In [1]: import galois

In [2]: galois.primitive_polys(2, 4)
Out[2]: [Poly(x^4 + x + 1, GF(2)), Poly(x^4 + x^3 + 1, GF(2))]

In [3]: galois.matlab_primitive_poly(2, 4)
Out[3]: Poly(x^4 + x + 1, GF(2))

In [4]: GF = galois.GF(2**4)

In [5]: print(GF.properties)
GF(2^4):
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: Poly(x^4 + x + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^4)

In [6]: print(GF.repr_table())
╔════════╦═══════════════════╦══════════════╦═════════╗
║ Power  │     Polynomial    │    Vector    │ Integer ║
║════════╬═══════════════════╬══════════════╬═════════║
║   0    │         0         │ [0, 0, 0, 0] │    0    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^0   │         1         │ [0, 0, 0, 1] │    1    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^1   │         α         │ [0, 0, 1, 0] │    2    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^2   │        α^2        │ [0, 1, 0, 0] │    4    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^3   │        α^3        │ [1, 0, 0, 0] │    8    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^4   │       α + 1       │ [0, 0, 1, 1] │    3    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^5   │      α^2 + α      │ [0, 1, 1, 0] │    6    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^6   │     α^3 + α^2     │ [1, 1, 0, 0] │    12   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^7   │    α^3 + α + 1    │ [1, 0, 1, 1] │    11   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^8   │      α^2 + 1      │ [0, 1, 0, 1] │    5    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^9   │      α^3 + α      │ [1, 0, 1, 0] │    10   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^10  │    α^2 + α + 1    │ [0, 1, 1, 1] │    7    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^11  │   α^3 + α^2 + α   │ [1, 1, 1, 0] │    14   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^12  │ α^3 + α^2 + α + 1 │ [1, 1, 1, 1] │    15   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^13  │   α^3 + α^2 + 1   │ [1, 1, 0, 1] │    13   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  α^14  │      α^3 + 1      │ [1, 0, 0, 1] │    9    ║
╚════════╩═══════════════════╩══════════════╩═════════╝

However, there are irreducible polynomials of degree 4 over $\mathrm{GF}(2)$ that are not primitive, namely $x^4 + x^3 + x^2 + x + 1$. Constructing $\mathrm{GF}(2^4)$ using a non-primitive polynomial does not result in $x$ being a primitive element. In this case, $\alpha = x + 1$ is the minimal primitive element of $\mathrm{GF}(2^4)$, although there are others. Notice that the polynomial $x = \alpha^{12}$.

In [8]: galois.irreducible_polys(2, 4)
Out[8]:
[Poly(x^4 + x + 1, GF(2)),
 Poly(x^4 + x^3 + 1, GF(2)),
 Poly(x^4 + x^3 + x^2 + x + 1, GF(2))]

In [9]: p = galois.irreducible_polys(2, 4)[2]; p
Out[9]: Poly(x^4 + x^3 + x^2 + x + 1, GF(2))

In [10]: GF = galois.GF(2**4, irreducible_poly=p)

In [11]: print(GF.properties)
GF(2^4):
  characteristic: 2
  degree: 4
  order: 16
  irreducible_poly: Poly(x^4 + x^3 + x^2 + x + 1, GF(2))
  is_primitive_poly: False
  primitive_element: GF(3, order=2^4)

In [12]: print(GF.repr_table())
╔════════════╦═══════════════════╦══════════════╦═════════╗
║   Power    │     Polynomial    │    Vector    │ Integer ║
║════════════╬═══════════════════╬══════════════╬═════════║
║     0      │         0         │ [0, 0, 0, 0] │    0    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^0  │         1         │ [0, 0, 0, 1] │    1    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^1  │       x + 1       │ [0, 0, 1, 1] │    3    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^2  │      x^2 + 1      │ [0, 1, 0, 1] │    5    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^3  │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │    15   ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^4  │   x^3 + x^2 + x   │ [1, 1, 1, 0] │    14   ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^5  │   x^3 + x^2 + 1   │ [1, 1, 0, 1] │    13   ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^6  │        x^3        │ [1, 0, 0, 0] │    8    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^7  │    x^2 + x + 1    │ [0, 1, 1, 1] │    7    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^8  │      x^3 + 1      │ [1, 0, 0, 1] │    9    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^9  │        x^2        │ [0, 1, 0, 0] │    4    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^10 │     x^3 + x^2     │ [1, 1, 0, 0] │    12   ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^11 │    x^3 + x + 1    │ [1, 0, 1, 1] │    11   ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^12 │         x         │ [0, 0, 1, 0] │    2    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^13 │      x^2 + x      │ [0, 1, 1, 0] │    6    ║
╟────────────┼───────────────────┼──────────────┼─────────╢
║ (x + 1)^14 │      x^3 + x      │ [1, 0, 1, 0] │    10   ║
╚════════════╩═══════════════════╩══════════════╩═════════╝

We can also display all the powers of the element $\beta = x$ and see that $\beta$ does not generate the field. Specifically, $\textrm{ord}(\beta) = 5 \ne 2^4 - 1$.

In [16]: beta = GF("x"); beta
Out[16]: GF(x, order=2^4)

In [17]: print(GF.repr_table(beta))
╔════════╦═══════════════════╦══════════════╦═════════╗
║ Power  │     Polynomial    │    Vector    │ Integer ║
║════════╬═══════════════════╬══════════════╬═════════║
║   0    │         0         │ [0, 0, 0, 0] │    0    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^0   │         1         │ [0, 0, 0, 1] │    1    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^1   │         x         │ [0, 0, 1, 0] │    2    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^2   │        x^2        │ [0, 1, 0, 0] │    4    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^3   │        x^3        │ [1, 0, 0, 0] │    8    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^4   │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │    15   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^5   │         1         │ [0, 0, 0, 1] │    1    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^6   │         x         │ [0, 0, 1, 0] │    2    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^7   │        x^2        │ [0, 1, 0, 0] │    4    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^8   │        x^3        │ [1, 0, 0, 0] │    8    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^9   │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │    15   ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^10  │         1         │ [0, 0, 0, 1] │    1    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^11  │         x         │ [0, 0, 1, 0] │    2    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^12  │        x^2        │ [0, 1, 0, 0] │    4    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^13  │        x^3        │ [1, 0, 0, 0] │    8    ║
╟────────┼───────────────────┼──────────────┼─────────╢
║  x^14  │ x^3 + x^2 + x + 1 │ [1, 1, 1, 1] │    15   ║
╚════════╩═══════════════════╩══════════════╩═════════╝

The most common example of a Galois field that does not use a primitive polynomial is the Galois field used in AES. AES uses $\mathrm{GF}(2^8)$ with irreducible polynomial $x^8 + x^4 + x^3 + x + 1$, which is not primitive.

In [20]: p = galois.Poly.Degrees([8,4,3,1,0]); p
Out[20]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))

In [21]: galois.is_irreducible(p)
Out[21]: True

In [22]: galois.is_primitive(p)
Out[22]: False

Hope this helps!