# 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([[                  α^2 + 2,                   α^2 + α,
2α^4 + α^3 + 2α^2 + α + 2,      α^4 + 2α^3 + α^2 + 2,
α^4 + α^3 + α + 2],
[                α^3 + α^2,                2α^3 + α^2,
2α^4 + 1,      2α^4 + α^3 + α^2 + 1,
α^4 + 2],
[      2α^4 + α^2 + 2α + 2,                  2α^2 + 1,
2α^4 + 2α^3 + 2α^2 + 2α,          2α^4 + 2α^2 + 2α,
α^4 + α^3 + α^2 + 2],
[     2α^4 + 2α^3 + 2α + 1,                 α^4 + α^3,
2α^4 + α^3 + 2α^2 + α + 2,      2α^3 + 2α^2 + 2α + 1,
α^4 + 1],
[                 2α^3 + 1,             α^4 + α^3 + α,
α^4 + α^3 + 2α^2 + 2α,            α^4 + 2α^3 + 1,
2α^4 + 2]], 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([[                  α^2 + 2,                   α^2 + α, 2α^4 + α^3 + 2α^2 + α + 2,      α^4 + 2α^3 + α^2 + 2,         α^4 + α^3 + α + 2],
[                α^3 + α^2,                2α^3 + α^2,                  2α^4 + 1,      2α^4 + α^3 + α^2 + 1,                   α^4 + 2],
[      2α^4 + α^2 + 2α + 2,                  2α^2 + 1,   2α^4 + 2α^3 + 2α^2 + 2α,          2α^4 + 2α^2 + 2α,       α^4 + α^3 + α^2 + 2],
[     2α^4 + 2α^3 + 2α + 1,                 α^4 + α^3, 2α^4 + α^3 + 2α^2 + α + 2,      2α^3 + 2α^2 + 2α + 1,                   α^4 + 1],
[                 2α^3 + 1,             α^4 + α^3 + α,     α^4 + α^3 + 2α^2 + 2α,            α^4 + 2α^3 + 1,                  2α^4 + 2]],
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: Jul 12, 2022