# Element Representation¶

The display representation of finite field elements can be set to either their integer ("int"), polynomial ("poly"), or power ("power") representation.

In prime fields $$\mathrm{GF}(p)$$, elements are integers in $$\{0, 1, \dots, p-1\}$$. Their two useful representations are the integer and power representation.

In extension fields $$\mathrm{GF}(p^m)$$, elements are polynomials over $$\mathrm{GF}(p)$$ with degree less than $$m$$. All display representations are useful. The polynomial representation allows proper representation of the element as a polynomial over its prime subfield. However, the integer representation is more compact for displaying large arrays.

## Set the display mode¶

The field element display mode can be set during FieldArray subclass creation by passing the display keyword argument to the GF() class factory.

In [1]: GF = galois.GF(3**5, display="poly")

In [2]: x = GF([17, 4])

In [3]: x
Out[3]: GF([α^2 + 2α + 2,        α + 1], order=3^5)

In [4]: print(x)
[α^2 + 2α + 2,        α + 1]


Note

Notice __repr__() displays GF([...], order=p^m) where __str__() only displays [...]. This is designed to be consistent with NumPy’s use of repr() and str().

The current display mode is accessed with the display_mode class property.

In [5]: GF.display_mode
Out[5]: 'poly'


The display mode can be temporarily changed using the display() classmethod as a context manager.

# Inside the context manager, x prints using the power representation
In [6]: with GF.display("power"):
...:     print(x)
...:
[α^222,  α^69]

# Outside the context manager, x prints using the previous representation
In [7]: print(x)
[α^2 + 2α + 2,        α + 1]


The display mode can be permanently changed using the display() method.

# The old polynomial display mode
In [8]: x
Out[8]: GF([α^2 + 2α + 2,        α + 1], order=3^5)

In [9]: GF.display("int");

# The new integer display mode
In [10]: x
Out[10]: GF([17,  4], order=3^5)


## Integer representation¶

The integer display mode (the default) displays all finite field elements as integers in $$\{0, 1, \dots, p^m-1\}$$.

In prime fields, the integer representation is simply the integer element in $$\{0, 1, \dots, p-1\}$$.

In [11]: GF = galois.GF(31)

In [12]: GF(11)
Out[12]: GF(11, order=31)


In extension fields, the integer representation converts and element’s degree-$$m-1$$ polynomial over $$\mathrm{GF}(p)$$ into its integer equivalent. The integer equivalent of a polynomial is a radix-$$p$$ integer of its coefficients, with the highest-degree coefficient as the most-significant digit and zero-degree coefficient as the least-significant digit.

In [13]: GF = galois.GF(3**5)

In [14]: GF(17)
Out[14]: GF(17, order=3^5)

In [15]: GF("α^2 + 2α + 2")
Out[15]: GF(17, order=3^5)

# Integer/polynomial equivalence
In [16]: p = 3; p**2 + 2*p + 2 == 17
Out[16]: True


## Polynomial representation¶

The polynomial display mode displays all finite field elements as polynomials over their prime subfield with degree less than $$m$$.

In prime fields, $$m = 1$$ and, therefore, the polynomial representation is equivalent to the integer representation because the polynomials all have degree $$0$$.

In [17]: GF = galois.GF(31, display="poly")

In [18]: GF(11)
Out[18]: GF(11, order=31)


In extension fields, the polynomial representation displays the elements naturally as polynomials over their prime subfield. This is useful, however it can become cluttered for large arrays.

In [19]: GF = galois.GF(3**5, display="poly")

In [20]: GF(17)
Out[20]: GF(α^2 + 2α + 2, order=3^5)

In [21]: GF("α^2 + 2α + 2")
Out[21]: GF(α^2 + 2α + 2, order=3^5)

# Integer/polynomial equivalence
In [22]: p = 3; p**2 + 2*p + 2 == 17
Out[22]: True


Tip

Use set_printoptions() to display the polynomial coefficients in degree-ascending order.

Use numpy.set_printoptions() to increase the line width to display large arrays more clearly. See NumPy print options for more details.

## Power representation¶

The power display mode represents the elements as powers of the finite field’s primitive element $$\alpha$$.

Warning

To display elements in the power representation, galois must compute the discrete logarithm of each element displayed. For large fields (or fields using explicit calculation), this process can take a while. However, when using lookup tables this display mode is just as fast as the others.

In prime fields, the elements are displayed as $$\{0, \alpha, \alpha^2, \dots, \alpha^{p-2}\}$$.

In [23]: GF = galois.GF(31, display="power")

In [24]: GF(11)
Out[24]: GF(α^23, order=31)

In [25]: GF.display("int");

In [26]: α = GF.primitive_element; α
Out[26]: GF(3, order=31)

In [27]: α**23
Out[27]: GF(11, order=31)


In extension fields, the elements are displayed as $$\{0, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}$$.

In [28]: GF = galois.GF(3**5, display="power")

In [29]: GF(17)
Out[29]: GF(α^222, order=3^5)

In [30]: GF.display("int");

In [31]: α = GF.primitive_element; α
Out[31]: GF(3, order=3^5)

In [32]: α**222
Out[32]: GF(17, order=3^5)


## Vector representation¶

The vector representation, while not a proper display mode of display(), represents finite field elements as vectors of their polynomial coefficients.

The vector representation is accessed using the vector() method.

In [33]: GF = galois.GF(3**5, display="poly")

In [34]: GF("α^2 + 2α + 2")
Out[34]: GF(α^2 + 2α + 2, order=3^5)

In [35]: GF("α^2 + 2α + 2").vector()
Out[35]: GF([0, 0, 1, 2, 2], order=3)


An N-D array over $$\mathrm{GF}(p^m)$$ is converted to a (N + 1)-D array over $$\mathrm{GF}(p)$$ with the added dimension having size $$m$$. The first value of the vector is the highest-degree coefficient.

In [36]: GF(["α^2 + 2α + 2", "2α^4 + α"])
Out[36]: GF([α^2 + 2α + 2,     2α^4 + α], order=3^5)

In [37]: GF(["α^2 + 2α + 2", "2α^4 + α"]).vector()
Out[37]:
GF([[0, 0, 1, 2, 2],
[2, 0, 0, 1, 0]], order=3)


Arrays can be created from the vector representation using the Vector() classmethod.

In [38]: GF.Vector([[0, 0, 1, 2, 2], [2, 0, 0, 1, 0]])
Out[38]: GF([α^2 + 2α + 2,     2α^4 + α], order=3^5)


## NumPy print options¶

NumPy displays arrays with a default line width of 75 characters. This is problematic for large arrays. It is especially problematic for arrays using the polynomial representation, where each element occupies a lot of space. This can be changed by modifying NumPy’s print options.

For example, below is a $$5 \times 5$$ matrix over $$\mathrm{GF}(3^5)$$ displayed in the polynomial representation. With the default line width, the array is quite difficult to read.

In [39]: GF = galois.GF(3**5, display="poly")

In [40]: x = GF.Random((5, 5)); x
Out[40]:
GF([[                  α^4 + α^3,              2α^4 + α^2 + 1,
α^4 + 2,    2α^4 + α^3 + α^2 + α + 2,
α^4 + α^3 + α^2 + α + 2],
[       2α^4 + 2α^3 + 2α + 2,               α^4 + α^3 + 1,
α^4 + α^3 + 2α^2 + 2, 2α^4 + 2α^3 + 2α^2 + 2α + 2,
α^4 + α^3 + 1],
[                          1,          α^4 + α^2 + 2α + 1,
2α^4 + α^2 + α,              α^3 + 2α^2 + 2,
α + 2],
[         α^3 + α^2 + 2α + 2,            2α^4 + α^3 + α^2,
α^3 + α,       2α^4 + α^3 + 2α^2 + 2,
2α^4 + α^3 + α],
[               2α^2 + α + 1,                     α^4 + α,
2α^4 + 2α^3 + 2α^2 + α + 1,        α^4 + α^3 + 2α^2 + 2,
2α^4 + 2α^3 + α^2 + 1]], order=3^5)


The readability is improved by increasing the line width using numpy.set_printoptions().

In [41]: np.set_printoptions(linewidth=150)

In [42]: x
Out[42]:
GF([[                  α^4 + α^3,              2α^4 + α^2 + 1,                     α^4 + 2,    2α^4 + α^3 + α^2 + α + 2,
α^4 + α^3 + α^2 + α + 2],
[       2α^4 + 2α^3 + 2α + 2,               α^4 + α^3 + 1,        α^4 + α^3 + 2α^2 + 2, 2α^4 + 2α^3 + 2α^2 + 2α + 2,
α^4 + α^3 + 1],
[                          1,          α^4 + α^2 + 2α + 1,              2α^4 + α^2 + α,              α^3 + 2α^2 + 2,
α + 2],
[         α^3 + α^2 + 2α + 2,            2α^4 + α^3 + α^2,                     α^3 + α,       2α^4 + α^3 + 2α^2 + 2,
2α^4 + α^3 + α],
[               2α^2 + α + 1,                     α^4 + α,  2α^4 + 2α^3 + 2α^2 + α + 1,        α^4 + α^3 + 2α^2 + 2,
2α^4 + 2α^3 + α^2 + 1]], order=3^5)


## Representation comparisons¶

For any finite field, each of the four representations can be easily compared using the repr_table() classmethod.

In [43]: GF = galois.GF(3**3)

In [44]: print(GF.repr_table())
+-------+---------------+-----------+---------+
| Power |   Polynomial  |   Vector  | Integer |
+-------+---------------+-----------+---------+
|   0   |       0       | [0, 0, 0] |    0    |
+-------+---------------+-----------+---------+
|  x^0  |       1       | [0, 0, 1] |    1    |
+-------+---------------+-----------+---------+
|  x^1  |       x       | [0, 1, 0] |    3    |
+-------+---------------+-----------+---------+
|  x^2  |      x^2      | [1, 0, 0] |    9    |
+-------+---------------+-----------+---------+
|  x^3  |     x + 2     | [0, 1, 2] |    5    |
+-------+---------------+-----------+---------+
|  x^4  |    x^2 + 2x   | [1, 2, 0] |    15   |
+-------+---------------+-----------+---------+
|  x^5  |  2x^2 + x + 2 | [2, 1, 2] |    23   |
+-------+---------------+-----------+---------+
|  x^6  |  x^2 + x + 1  | [1, 1, 1] |    13   |
+-------+---------------+-----------+---------+
|  x^7  |  x^2 + 2x + 2 | [1, 2, 2] |    17   |
+-------+---------------+-----------+---------+
|  x^8  |    2x^2 + 2   | [2, 0, 2] |    20   |
+-------+---------------+-----------+---------+
|  x^9  |     x + 1     | [0, 1, 1] |    4    |
+-------+---------------+-----------+---------+
|  x^10 |    x^2 + x    | [1, 1, 0] |    12   |
+-------+---------------+-----------+---------+
|  x^11 |  x^2 + x + 2  | [1, 1, 2] |    14   |
+-------+---------------+-----------+---------+
|  x^12 |    x^2 + 2    | [1, 0, 2] |    11   |
+-------+---------------+-----------+---------+
|  x^13 |       2       | [0, 0, 2] |    2    |
+-------+---------------+-----------+---------+
|  x^14 |       2x      | [0, 2, 0] |    6    |
+-------+---------------+-----------+---------+
|  x^15 |      2x^2     | [2, 0, 0] |    18   |
+-------+---------------+-----------+---------+
|  x^16 |     2x + 1    | [0, 2, 1] |    7    |
+-------+---------------+-----------+---------+
|  x^17 |    2x^2 + x   | [2, 1, 0] |    21   |
+-------+---------------+-----------+---------+
|  x^18 |  x^2 + 2x + 1 | [1, 2, 1] |    16   |
+-------+---------------+-----------+---------+
|  x^19 | 2x^2 + 2x + 2 | [2, 2, 2] |    26   |
+-------+---------------+-----------+---------+
|  x^20 |  2x^2 + x + 1 | [2, 1, 1] |    22   |
+-------+---------------+-----------+---------+
|  x^21 |    x^2 + 1    | [1, 0, 1] |    10   |
+-------+---------------+-----------+---------+
|  x^22 |     2x + 2    | [0, 2, 2] |    8    |
+-------+---------------+-----------+---------+
|  x^23 |   2x^2 + 2x   | [2, 2, 0] |    24   |
+-------+---------------+-----------+---------+
|  x^24 | 2x^2 + 2x + 1 | [2, 2, 1] |    25   |
+-------+---------------+-----------+---------+
|  x^25 |    2x^2 + 1   | [2, 0, 1] |    19   |
+-------+---------------+-----------+---------+


Last update: May 18, 2022