Element Representation¶
The 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 element 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 element representation¶
The field element representation can be set during FieldArray subclass creation by passing the repr keyword
argument to the GF() class factory.
In [1]: GF = galois.GF(3**5, repr="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]
The current element representation is accessed with the element_repr class property.
In [5]: GF.element_repr
Out[5]: 'poly'
The element representation can be temporarily changed using the repr() classmethod as a context manager.
# Inside the context manager, x prints using the power representation
In [6]: with GF.repr("power"):
...: print(x)
...:
[α^222 α^69]
# Outside the context manager, x prints using the previous representation
In [7]: print(x)
[α^2 + 2α + 2 α + 1]
The element representation can be permanently changed using the repr() classmethod (not as a context manager).
# The old polynomial representation
In [8]: x
Out[8]: GF([α^2 + 2α + 2, α + 1], order=3^5)
In [9]: GF.repr("int");
# The new integer representation
In [10]: x
Out[10]: GF([17, 4], order=3^5)
Integer representation¶
The integer representation (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 an 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("x^2 + 2x + 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 representation displays all finite field elements as polynomials over their prime subfield with degree less than \(m\).
In prime fields \(m = 1\), therefore the polynomial representation is equivalent to the integer representation because the polynomials all have degree 0.
In [17]: GF = galois.GF(31, repr="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, repr="poly")
In [20]: GF(17)
Out[20]: GF(α^2 + 2α + 2, order=3^5)
In [21]: GF("x^2 + 2x + 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 representation displays all finite field elements as powers of the field’s primitive element \(\alpha\).
Slower performance
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 representation is just as fast as
the others.
In prime fields, the elements are displayed as \(\{0, 1, \alpha, \alpha^2, \dots, \alpha^{p-2}\}\).
In [23]: GF = galois.GF(31, repr="power")
In [24]: GF(11)
Out[24]: GF(α^23, order=31)
In [25]: GF.repr("int");
In [26]: alpha = GF.primitive_element; alpha
Out[26]: GF(3, order=31)
In [27]: alpha ** 23
Out[27]: GF(11, order=31)
In extension fields, the elements are displayed as \(\{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}\).
In [28]: GF = galois.GF(3**5, repr="power")
In [29]: GF(17)
Out[29]: GF(α^222, order=3^5)
In [30]: GF.repr("int");
In [31]: alpha = GF.primitive_element; alpha
Out[31]: GF(3, order=3^5)
In [32]: alpha ** 222
Out[32]: GF(17, order=3^5)
Vector representation¶
The vector representation, while not a valid input to repr(), 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, repr="poly")
In [34]: GF("x^2 + 2x + 2")
Out[34]: GF(α^2 + 2α + 2, order=3^5)
In [35]: GF("x^2 + 2x + 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(["x^2 + 2x + 2", "2x^4 + x"])
Out[36]: GF([α^2 + 2α + 2, 2α^4 + α], order=3^5)
In [37]: GF(["x^2 + 2x + 2", "2x^4 + x"]).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, repr="poly")
In [40]: x = GF.Random((5, 5)); x
Out[40]:
GF([[ α^3 + 2α^2 + 2α + 1, α^4 + α^3 + 2α^2 + α,
2α^4 + α^3 + 2α^2 + α + 1, 2α^4 + α^3 + 2α^2 + 2,
α^4 + 2α^2 + 2α + 2],
[ α^3 + 2, 2α^4 + 1,
α^4 + 2α^3 + 2α^2, 2α^4 + α^2 + 2α + 1,
2α^3 + α^2 + 2],
[ α^4 + 2, 2α^4 + α^3 + α + 1,
α^4 + α^3 + 2α^2 + α, α^4 + 2α^3 + 2α^2 + α + 1,
2α^4 + 2α^2 + 2α + 2],
[ 2α^4 + 2α^3 + α^2 + α + 1, α^2,
α^3 + α^2 + α, 2α + 2,
α^4 + 2α^3 + α^2 + 2α + 1],
[ α^4 + α^2 + 2, 2α^4 + 2α^2 + 1,
α^4 + 2α^3 + 2, 2α^4 + 2α^3 + 2α^2 + 2α + 1,
2α^4 + 2α^3 + α + 1]], order=3^5)
The readability is improved by increasing the line width using numpy.set_printoptions().
In [41]: np.set_printoptions(linewidth=200)
In [42]: x
Out[42]:
GF([[ α^3 + 2α^2 + 2α + 1, α^4 + α^3 + 2α^2 + α, 2α^4 + α^3 + 2α^2 + α + 1, 2α^4 + α^3 + 2α^2 + 2, α^4 + 2α^2 + 2α + 2],
[ α^3 + 2, 2α^4 + 1, α^4 + 2α^3 + 2α^2, 2α^4 + α^2 + 2α + 1, 2α^3 + α^2 + 2],
[ α^4 + 2, 2α^4 + α^3 + α + 1, α^4 + α^3 + 2α^2 + α, α^4 + 2α^3 + 2α^2 + α + 1, 2α^4 + 2α^2 + 2α + 2],
[ 2α^4 + 2α^3 + α^2 + α + 1, α^2, α^3 + α^2 + α, 2α + 2, α^4 + 2α^3 + α^2 + 2α + 1],
[ α^4 + α^2 + 2, 2α^4 + 2α^2 + 1, α^4 + 2α^3 + 2, 2α^4 + 2α^3 + 2α^2 + 2α + 1, 2α^4 + 2α^3 + α + 1]], order=3^5)
Representation comparisons¶
For any finite field, each of the four element 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