Array Creation¶
This page discusses the multiple ways to create arrays over finite fields. For this discussion, we are working in the finite field \(\mathrm{GF}(3^5)\).
In [1]: GF = galois.GF(3**5)
In [2]: print(GF.properties)
Galois Field:
name: GF(3^5)
characteristic: 3
degree: 5
order: 243
irreducible_poly: x^5 + 2x + 1
is_primitive_poly: True
primitive_element: x
In [3]: alpha = GF.primitive_element; alpha
Out[3]: GF(3, order=3^5)
In [4]: GF = galois.GF(3**5, repr="poly")
In [5]: print(GF.properties)
Galois Field:
name: GF(3^5)
characteristic: 3
degree: 5
order: 243
irreducible_poly: x^5 + 2x + 1
is_primitive_poly: True
primitive_element: x
In [6]: alpha = GF.primitive_element; alpha
Out[6]: GF(α, order=3^5)
In [7]: GF = galois.GF(3**5, repr="power")
In [8]: print(GF.properties)
Galois Field:
name: GF(3^5)
characteristic: 3
degree: 5
order: 243
irreducible_poly: x^5 + 2x + 1
is_primitive_poly: True
primitive_element: x
In [9]: alpha = GF.primitive_element; alpha
Out[9]: GF(α, order=3^5)
Create a scalar¶
A single finite field element (a scalar) is a 0-D FieldArray. They are created by passing a single
ElementLike object to GF’s constructor. A finite field scalar may also be created by exponentiating
the primitive element to a scalar power.
In [10]: GF(17)
Out[10]: GF(17, order=3^5)
In [11]: GF("x^2 + 2x + 2")
Out[11]: GF(17, order=3^5)
In [12]: alpha ** 222
Out[12]: GF(17, order=3^5)
In [13]: GF(17)
Out[13]: GF(α^2 + 2α + 2, order=3^5)
In [14]: GF("x^2 + 2x + 2")
Out[14]: GF(α^2 + 2α + 2, order=3^5)
In [15]: alpha ** 222
Out[15]: GF(α^2 + 2α + 2, order=3^5)
In [16]: GF(17)
Out[16]: GF(α^222, order=3^5)
In [17]: GF("x^2 + 2x + 2")
Out[17]: GF(α^222, order=3^5)
In [18]: alpha ** 222
Out[18]: GF(α^222, order=3^5)
Create a new array¶
Array-like objects¶
A FieldArray can be created from various ArrayLike objects.
A finite field array may also be created by exponentiating the primitive element to a an array of powers.
In [19]: GF([17, 4, 148, 205])
Out[19]: GF([ 17, 4, 148, 205], order=3^5)
In [20]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[20]:
GF([[ 17, 4],
[148, 205]], order=3^5)
In [21]: alpha ** np.array([[222, 69], [54, 24]])
Out[21]:
GF([[ 17, 4],
[148, 205]], order=3^5)
In [22]: GF([17, 4, 148, 205])
Out[22]:
GF([ α^2 + 2α + 2, α + 1,
α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1], order=3^5)
In [23]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[23]:
GF([[ α^2 + 2α + 2, α + 1],
[ α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1]], order=3^5)
In [24]: alpha ** np.array([[222, 69], [54, 24]])
Out[24]:
GF([[ α^2 + 2α + 2, α + 1],
[ α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1]], order=3^5)
In [25]: GF([17, 4, 148, 205])
Out[25]: GF([α^222, α^69, α^54, α^24], order=3^5)
In [26]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[26]:
GF([[α^222, α^69],
[ α^54, α^24]], order=3^5)
In [27]: alpha ** np.array([[222, 69], [54, 24]])
Out[27]:
GF([[α^222, α^69],
[ α^54, α^24]], order=3^5)
Polynomial coefficients¶
Rather than strings, the polynomial coefficients may be passed into GF’s constructor as length-\(m\) vectors using
the Vector() classmethod.
In [28]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[28]: GF([17, 4], order=3^5)
In [29]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[29]: GF([α^2 + 2α + 2, α + 1], order=3^5)
In [30]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[30]: GF([α^222, α^69], order=3^5)
The vector() method is the opposite operation. It converts extension field elements from \(\mathrm{GF}(p^m)\)
into length-\(m\) vectors over \(\mathrm{GF}(p)\).
In [31]: GF([17, 4]).vector()
Out[31]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
In [32]: GF([17, 4]).vector()
Out[32]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
In [33]: GF([17, 4]).vector()
Out[33]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
NumPy array¶
An integer NumPy array may also be passed into GF. The default keyword argument copy=True of the FieldArray
constructor will create a copy of the array.
In [34]: x_np = np.array([213, 167, 4, 214, 209]); x_np
Out[34]: array([213, 167, 4, 214, 209])
In [35]: x = GF(x_np); x
Out[35]: GF([213, 167, 4, 214, 209], order=3^5)
# Modifying x does not modify x_np
In [36]: x[0] = 0; x_np
Out[36]: array([213, 167, 4, 214, 209])
In [37]: x_np = np.array([213, 167, 4, 214, 209]); x_np
Out[37]: array([213, 167, 4, 214, 209])
In [38]: x = GF(x_np); x
Out[38]:
GF([ 2α^4 + α^3 + 2α^2 + 2α, 2α^4 + α + 2,
α + 1, 2α^4 + α^3 + 2α^2 + 2α + 1,
2α^4 + α^3 + 2α^2 + 2], order=3^5)
# Modifying x does not modify x_np
In [39]: x[0] = 0; x_np
Out[39]: array([213, 167, 4, 214, 209])
In [40]: x_np = np.array([213, 167, 4, 214, 209]); x_np
Out[40]: array([213, 167, 4, 214, 209])
In [41]: x = GF(x_np); x
Out[41]: GF([α^183, α^9, α^69, α^153, α^58], order=3^5)
# Modifying x does not modify x_np
In [42]: x[0] = 0; x_np
Out[42]: array([213, 167, 4, 214, 209])
View an existing array¶
Instead of creating a FieldArray explicitly, you can convert an existing NumPy array into a FieldArray
temporarily and work with it in-place.
Simply call .view(GF) to view the NumPy array as a FieldArray. When finished working in the
finite field, call .view(np.ndarray) to view it back to a NumPy array.
In [43]: x_np = np.array([213, 167, 4, 214, 209], dtype=int); x_np
Out[43]: array([213, 167, 4, 214, 209])
In [44]: x = x_np.view(GF); x
Out[44]: GF([213, 167, 4, 214, 209], order=3^5)
# Modifying x does modify x_np!
In [45]: x[0] = 0; x_np
Out[45]: array([ 0, 167, 4, 214, 209])
In [46]: x_np = np.array([213, 167, 4, 214, 209], dtype=int); x_np
Out[46]: array([213, 167, 4, 214, 209])
In [47]: x = x_np.view(GF); x
Out[47]:
GF([ 2α^4 + α^3 + 2α^2 + 2α, 2α^4 + α + 2,
α + 1, 2α^4 + α^3 + 2α^2 + 2α + 1,
2α^4 + α^3 + 2α^2 + 2], order=3^5)
# Modifying x does modify x_np!
In [48]: x[0] = 0; x_np
Out[48]: array([ 0, 167, 4, 214, 209])
In [49]: x_np = np.array([213, 167, 4, 214, 209], dtype=int); x_np
Out[49]: array([213, 167, 4, 214, 209])
In [50]: x = x_np.view(GF); x
Out[50]: GF([α^183, α^9, α^69, α^153, α^58], order=3^5)
# Modifying x does modify x_np!
In [51]: x[0] = 0; x_np
Out[51]: array([ 0, 167, 4, 214, 209])
Classmethods¶
Several classmethods are provided in FieldArray to assist with creating arrays.
Constant arrays¶
The Zeros() and Ones() classmethods provide constant arrays that are
useful for initializing empty arrays.
In [52]: GF.Zeros(4)
Out[52]: GF([0, 0, 0, 0], order=3^5)
In [53]: GF.Ones(4)
Out[53]: GF([1, 1, 1, 1], order=3^5)
In [54]: GF.Zeros(4)
Out[54]: GF([0, 0, 0, 0], order=3^5)
In [55]: GF.Ones(4)
Out[55]: GF([1, 1, 1, 1], order=3^5)
In [56]: GF.Zeros(4)
Out[56]: GF([0, 0, 0, 0], order=3^5)
In [57]: GF.Ones(4)
Out[57]: GF([1, 1, 1, 1], order=3^5)
There is no numpy.empty() equivalent.
This is because FieldArray instances must have values in \([0, p^m)\). Empty NumPy arrays have whatever values
are currently in memory, and therefore would fail those bounds checks during instantiation.
Ordered arrays¶
The Range() classmethod produces a range of elements similar to numpy.arange(). The integer start
and stop values are the integer representation of the polynomial field elements.
In [58]: GF.Range(10, 20)
Out[58]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=3^5)
In [59]: GF.Range(10, 20, 2)
Out[59]: GF([10, 12, 14, 16, 18], order=3^5)
In [60]: GF.Range(10, 20)
Out[60]:
GF([ α^2 + 1, α^2 + 2, α^2 + α, α^2 + α + 1, α^2 + α + 2,
α^2 + 2α, α^2 + 2α + 1, α^2 + 2α + 2, 2α^2, 2α^2 + 1],
order=3^5)
In [61]: GF.Range(10, 20, 2)
Out[61]:
GF([ α^2 + 1, α^2 + α, α^2 + α + 2, α^2 + 2α + 1, 2α^2],
order=3^5)
In [62]: GF.Range(10, 20)
Out[62]:
GF([ α^46, α^74, α^70, α^10, α^209, α^6, α^138, α^222, α^123, α^195],
order=3^5)
In [63]: GF.Range(10, 20, 2)
Out[63]: GF([ α^46, α^70, α^209, α^138, α^123], order=3^5)
Random arrays¶
The Random() classmethod provides a random array of the specified shape. This is convenient
for testing. The integer low and high values are the integer representation of
the polynomial field elements.
In [64]: GF.Random(4, seed=1)
Out[64]: GF([242, 216, 32, 114], order=3^5)
In [65]: GF.Random(4, low=10, high=20, seed=2)
Out[65]: GF([17, 13, 14, 18], order=3^5)
In [66]: GF.Random(4, seed=1)
Out[66]:
GF([2α^4 + 2α^3 + 2α^2 + 2α + 2, 2α^4 + 2α^3,
α^3 + α + 2, α^4 + α^3 + 2α], order=3^5)
In [67]: GF.Random(4, low=10, high=20, seed=2)
Out[67]: GF([α^2 + 2α + 2, α^2 + α + 1, α^2 + α + 2, 2α^2], order=3^5)
In [68]: GF.Random(4, seed=1)
Out[68]: GF([α^185, α^193, α^49, α^231], order=3^5)
In [69]: GF.Random(4, low=10, high=20, seed=2)
Out[69]: GF([α^222, α^10, α^209, α^123], order=3^5)
Class properties¶
Certain class properties, such as elements, units, squares,
and primitive_elements, provide an array of elements with the specified properties.
In [70]: GF = galois.GF(3**2)
In [71]: GF.elements
Out[71]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
In [72]: GF.units
Out[72]: GF([1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
In [73]: GF.squares
Out[73]: GF([0, 1, 2, 4, 8], order=3^2)
In [74]: GF.primitive_elements
Out[74]: GF([3, 5, 6, 7], order=3^2)
In [75]: GF = galois.GF(3**2, repr="poly")
In [76]: GF.elements
Out[76]:
GF([ 0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1,
2α + 2], order=3^2)
In [77]: GF.units
Out[77]:
GF([ 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2],
order=3^2)
In [78]: GF.squares
Out[78]: GF([ 0, 1, 2, α + 1, 2α + 2], order=3^2)
In [79]: GF.primitive_elements
Out[79]: GF([ α, α + 2, 2α, 2α + 1], order=3^2)
In [80]: GF = galois.GF(3**2, repr="power")
In [81]: GF.elements
Out[81]: GF([ 0, 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
In [82]: GF.units
Out[82]: GF([ 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
In [83]: GF.squares
Out[83]: GF([ 0, 1, α^4, α^2, α^6], order=3^2)
In [84]: GF.primitive_elements
Out[84]: GF([ α, α^7, α^5, α^3], order=3^2)
Data types¶
FieldArray instances support a fixed set of NumPy data types (numpy.dtype). The data type must be
able to store all the field elements (in their integer representation).
Valid data types¶
For small finite fields, like \(\mathrm{GF}(2^4)\), every NumPy integer data type is supported.
In [85]: GF = galois.GF(2**4)
In [86]: GF.dtypes
Out[86]:
[numpy.uint8,
numpy.uint16,
numpy.uint32,
numpy.int8,
numpy.int16,
numpy.int32,
numpy.int64]
For medium finite fields, like \(\mathrm{GF}(2^{10})\), some NumPy integer data types are not supported. Here,
numpy.uint8 and numpy.int8 are not supported.
In [87]: GF = galois.GF(2**10)
In [88]: GF.dtypes
Out[88]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]
For large finite fields, like \(\mathrm{GF}(2^{100})\), only the “object” data type (numpy.object_) is
supported. This uses arrays of Python objects, rather than integer data types. The Python objects used are Python integers,
which have unlimited size.
In [89]: GF = galois.GF(2**100)
In [90]: GF.dtypes
Out[90]: [numpy.object_]
Default data type¶
When arrays are created, unless otherwise specified, they use the default data type. The default data type is
the smallest unsigned data type (the first in the dtypes list).
In [91]: GF = galois.GF(2**10)
In [92]: GF.dtypes
Out[92]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]
In [93]: x = GF.Random(4); x
Out[93]: GF([834, 292, 910, 443], order=2^10)
In [94]: x.dtype
Out[94]: dtype('uint16')
In [95]: GF = galois.GF(2**100)
In [96]: GF.dtypes
Out[96]: [numpy.object_]
In [97]: x = GF.Random(4); x
Out[97]:
GF([ 543515368133214567834056815960, 195030482105090702271332325327,
1091917272543203635224635802113, 820236713335371859122465316318],
order=2^100)
In [98]: x.dtype
Out[98]: dtype('O')
Changing data types¶
The data type may be explicitly set during array creation by setting the dtype keyword argument of the FieldArray
constructor.
In [99]: GF = galois.GF(2**10)
In [100]: x = GF([273, 388, 124, 400], dtype=np.uint32); x
Out[100]: GF([273, 388, 124, 400], order=2^10)
In [101]: x.dtype
Out[101]: dtype('uint32')
Arrays may also have their data types changed using .astype(). The data type must be valid, however.
In [102]: x.dtype
Out[102]: dtype('uint32')
In [103]: x = x.astype(np.int64)
In [104]: x.dtype
Out[104]: dtype('int64')
NumPy functions¶
Most native NumPy functions work on FieldArray instances as expected. For example, reshaping a (10,)-shape array
into a (2, 5)-shape array works as desired and returns a FieldArray instance.
In [105]: GF = galois.GF(7)
In [106]: x = GF.Random(10, seed=1); x
Out[106]: GF([6, 6, 0, 3, 6, 5, 0, 3, 2, 4], order=7)
In [107]: np.reshape(x, (2, 5))
Out[107]:
GF([[6, 6, 0, 3, 6],
[5, 0, 3, 2, 4]], order=7)
However, some functions have a subok keyword argument. This indicates whether to return a numpy.ndarray subclass
from the function. Most notably, numpy.copy() defaults subok to False.
In [108]: x
Out[108]: GF([6, 6, 0, 3, 6, 5, 0, 3, 2, 4], order=7)
# Returns np.ndarray!
In [109]: np.copy(x)
Out[109]: array([6, 6, 0, 3, 6, 5, 0, 3, 2, 4], dtype=uint8)
In [110]: np.copy(x, subok=True)
Out[110]: GF([6, 6, 0, 3, 6, 5, 0, 3, 2, 4], order=7)
The numpy.ndarray.copy() method will, however, return a subclass. Be mindful of the subok keyword argument!
In [111]: x.copy()
Out[111]: GF([6, 6, 0, 3, 6, 5, 0, 3, 2, 4], order=7)