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α^4 + 2α^3 + 2α^2, 2α^4 + 2α^2,
2α^4 + 2α, α^3 + 2α^2 + 2,
α^4 + α^2 + α + 1],
[ 2α^4, 2α^4 + α^3 + 1,
α^3 + α^2 + 2α + 1, 2α^2,
2α^2 + α],
[ α^3 + 2α, α^4 + α^3 + α^2 + 2,
2α^4 + 2α^2 + α, 2α^4 + α^3 + 2α^2 + 2α + 1,
α^4 + α^3 + 2α^2 + 2α],
[ 2α^4 + α^3 + α^2, 2α^4 + α + 2,
2α^4 + α^3 + 2α^2 + 2α, α^4 + 2α^3 + 2,
1],
[ α^4 + α^3 + 2α, α^3 + α^2 + α,
2α^4 + α^3 + α^2 + 2, α^4 + 2α^3 + α^2 + α + 2,
α^4 + 2α^3 + α]], 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α^4 + 2α^3 + 2α^2, 2α^4 + 2α^2, 2α^4 + 2α, α^3 + 2α^2 + 2, α^4 + α^2 + α + 1],
[ 2α^4, 2α^4 + α^3 + 1, α^3 + α^2 + 2α + 1, 2α^2, 2α^2 + α],
[ α^3 + 2α, α^4 + α^3 + α^2 + 2, 2α^4 + 2α^2 + α, 2α^4 + α^3 + 2α^2 + 2α + 1, α^4 + α^3 + 2α^2 + 2α],
[ 2α^4 + α^3 + α^2, 2α^4 + α + 2, 2α^4 + α^3 + 2α^2 + 2α, α^4 + 2α^3 + 2, 1],
[ α^4 + α^3 + 2α, α^3 + α^2 + α, 2α^4 + α^3 + α^2 + 2, α^4 + 2α^3 + α^2 + α + 2, α^4 + 2α^3 + α]],
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 |
+-------+---------------+-----------+---------+