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]: GF = galois.GF(3**5, display="poly")
In [4]: 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 [5]: GF = galois.GF(3**5, display="power")
In [6]: 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
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.
In [7]: a = GF(17); a
Out[7]: GF(17, order=3^5)
In [8]: a = GF("x^2 + 2x + 2"); a
Out[8]: GF(17, order=3^5)
In [9]: a.ndim
Out[9]: 0
In [10]: a = GF(17); a
Out[10]: GF(α^2 + 2α + 2, order=3^5)
In [11]: a = GF("x^2 + 2x + 2"); a
Out[11]: GF(α^2 + 2α + 2, order=3^5)
In [12]: a.ndim
Out[12]: 0
In [13]: a = GF(17); a
Out[13]: GF(α^222, order=3^5)
In [14]: a = GF("x^2 + 2x + 2"); a
Out[14]: GF(α^222, order=3^5)
In [15]: a.ndim
Out[15]: 0
Create a new array¶
Array-Like objects¶
A FieldArray can be created from various ArrayLike objects.
In [16]: GF([17, 4, 148, 205])
Out[16]: GF([ 17, 4, 148, 205], order=3^5)
In [17]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[17]:
GF([[ 17, 4],
[148, 205]], order=3^5)
In [18]: GF([17, 4, 148, 205])
Out[18]:
GF([ α^2 + 2α + 2, α + 1,
α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1], order=3^5)
In [19]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[19]:
GF([[ α^2 + 2α + 2, α + 1],
[ α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1]], order=3^5)
In [20]: GF([17, 4, 148, 205])
Out[20]: GF([α^222, α^69, α^54, α^24], order=3^5)
In [21]: GF([["x^2 + 2x + 2", 4], ["x^4 + 2x^3 + x^2 + x + 1", 205]])
Out[21]:
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 [22]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[22]: GF([17, 4], order=3^5)
In [23]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[23]: GF([α^2 + 2α + 2, α + 1], order=3^5)
In [24]: GF.Vector([[0, 0, 1, 2, 2], [0, 0, 0, 1, 1]])
Out[24]: 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 [25]: GF([17, 4]).vector()
Out[25]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
In [26]: GF([17, 4]).vector()
Out[26]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
In [27]: GF([17, 4]).vector()
Out[27]:
GF([[0, 0, 1, 2, 2],
[0, 0, 0, 1, 1]], order=3)
Primitive element powers¶
A FieldArray can also be created from the powers of a primitive element \(\alpha\).
In [28]: alpha = GF.primitive_element; alpha
Out[28]: GF(3, order=3^5)
In [29]: powers = np.array([222, 69, 54, 24]); powers
Out[29]: array([222, 69, 54, 24])
In [30]: alpha ** powers
Out[30]: GF([ 17, 4, 148, 205], order=3^5)
In [31]: alpha = GF.primitive_element; alpha
Out[31]: GF(α, order=3^5)
In [32]: powers = np.array([222, 69, 54, 24]); powers
Out[32]: array([222, 69, 54, 24])
In [33]: alpha ** powers
Out[33]:
GF([ α^2 + 2α + 2, α + 1,
α^4 + 2α^3 + α^2 + α + 1, 2α^4 + α^3 + α^2 + 2α + 1], order=3^5)
In [34]: alpha = GF.primitive_element; alpha
Out[34]: GF(α, order=3^5)
In [35]: powers = np.array([222, 69, 54, 24]); powers
Out[35]: array([222, 69, 54, 24])
In [36]: alpha ** powers
Out[36]: GF([α^222, α^69, α^54, α^24], order=3^5)
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 [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([213, 167, 4, 214, 209], 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([ 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 [42]: x[0] = 0; x_np
Out[42]: array([213, 167, 4, 214, 209])
In [43]: x_np = np.array([213, 167, 4, 214, 209]); x_np
Out[43]: array([213, 167, 4, 214, 209])
In [44]: x = GF(x_np); x
Out[44]: GF([α^183, α^9, α^69, α^153, α^58], order=3^5)
# Modifying x does not modify x_np
In [45]: x[0] = 0; x_np
Out[45]: 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 [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([213, 167, 4, 214, 209], 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([ 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 [51]: x[0] = 0; x_np
Out[51]: array([ 0, 167, 4, 214, 209])
In [52]: x_np = np.array([213, 167, 4, 214, 209], dtype=int); x_np
Out[52]: array([213, 167, 4, 214, 209])
In [53]: x = x_np.view(GF); x
Out[53]: GF([α^183, α^9, α^69, α^153, α^58], order=3^5)
# Modifying x does modify x_np!
In [54]: x[0] = 0; x_np
Out[54]: 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 [55]: GF.Zeros(4)
Out[55]: GF([0, 0, 0, 0], order=3^5)
In [56]: GF.Ones(4)
Out[56]: GF([1, 1, 1, 1], order=3^5)
In [57]: GF.Zeros(4)
Out[57]: GF([0, 0, 0, 0], order=3^5)
In [58]: GF.Ones(4)
Out[58]: GF([1, 1, 1, 1], order=3^5)
In [59]: GF.Zeros(4)
Out[59]: GF([0, 0, 0, 0], order=3^5)
In [60]: GF.Ones(4)
Out[60]: GF([1, 1, 1, 1], order=3^5)
Note
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.
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 [61]: GF.Range(10, 20)
Out[61]: GF([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], order=3^5)
In [62]: GF.Range(10, 20, 2)
Out[62]: GF([10, 12, 14, 16, 18], order=3^5)
In [63]: GF.Range(10, 20)
Out[63]:
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 [64]: GF.Range(10, 20, 2)
Out[64]:
GF([ α^2 + 1, α^2 + α, α^2 + α + 2, α^2 + 2α + 1, 2α^2],
order=3^5)
In [65]: GF.Range(10, 20)
Out[65]:
GF([ α^46, α^74, α^70, α^10, α^209, α^6, α^138, α^222, α^123, α^195],
order=3^5)
In [66]: GF.Range(10, 20, 2)
Out[66]: 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 [67]: GF.Random(4, seed=1234)
Out[67]: GF([176, 177, 172, 237], order=3^5)
In [68]: GF.Random(4, low=10, high=20, seed=5678)
Out[68]: GF([11, 18, 12, 10], order=3^5)
In [69]: GF.Random(4, seed=1234)
Out[69]:
GF([ 2α^4 + α^2 + α + 2, 2α^4 + α^2 + 2α,
2α^4 + α^2 + 1, 2α^4 + 2α^3 + 2α^2 + α], order=3^5)
In [70]: GF.Random(4, low=10, high=20, seed=5678)
Out[70]: GF([α^2 + 2, 2α^2, α^2 + α, α^2 + 1], order=3^5)
In [71]: GF.Random(4, seed=1234)
Out[71]: GF([α^114, α^78, α^206, α^96], order=3^5)
In [72]: GF.Random(4, low=10, high=20, seed=5678)
Out[72]: GF([ α^74, α^123, α^70, α^46], 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 [73]: GF = galois.GF(3**2)
In [74]: GF.elements
Out[74]: GF([0, 1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
In [75]: GF.units
Out[75]: GF([1, 2, 3, 4, 5, 6, 7, 8], order=3^2)
In [76]: GF.squares
Out[76]: GF([0, 1, 2, 4, 8], order=3^2)
In [77]: GF.primitive_elements
Out[77]: GF([3, 5, 6, 7], order=3^2)
In [78]: GF = galois.GF(3**2, display="poly")
In [79]: GF.elements
Out[79]:
GF([ 0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1,
2α + 2], order=3^2)
In [80]: GF.units
Out[80]:
GF([ 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2],
order=3^2)
In [81]: GF.squares
Out[81]: GF([ 0, 1, 2, α + 1, 2α + 2], order=3^2)
In [82]: GF.primitive_elements
Out[82]: GF([ α, α + 2, 2α, 2α + 1], order=3^2)
In [83]: GF = galois.GF(3**2, display="power")
In [84]: GF.elements
Out[84]: GF([ 0, 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
In [85]: GF.units
Out[85]: GF([ 1, α^4, α, α^2, α^7, α^5, α^3, α^6], order=3^2)
In [86]: GF.squares
Out[86]: GF([ 0, 1, α^4, α^2, α^6], order=3^2)
In [87]: GF.primitive_elements
Out[87]: 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 [88]: GF = galois.GF(2**4)
In [89]: GF.dtypes
Out[89]:
[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 [90]: GF = galois.GF(2**10)
In [91]: GF.dtypes
Out[91]: [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 [92]: GF = galois.GF(2**100)
In [93]: GF.dtypes
Out[93]: [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 [94]: GF = galois.GF(2**10)
In [95]: GF.dtypes
Out[95]: [numpy.uint16, numpy.uint32, numpy.int16, numpy.int32, numpy.int64]
In [96]: x = GF.Random(4); x
Out[96]: GF([378, 399, 20, 843], order=2^10)
In [97]: x.dtype
Out[97]: dtype('uint16')
In [98]: GF = galois.GF(2**100)
In [99]: GF.dtypes
Out[99]: [numpy.object_]
In [100]: x = GF.Random(4); x
Out[100]:
GF([ 720661091767342954917191826791, 1157370535725608015331540849700,
445269163805583541497951683365, 923226590122090314483682299018],
order=2^100)
In [101]: x.dtype
Out[101]: 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 [102]: GF = galois.GF(2**10)
In [103]: x = GF([273, 388, 124, 400], dtype=np.uint32); x
Out[103]: GF([273, 388, 124, 400], order=2^10)
In [104]: x.dtype
Out[104]: dtype('uint32')
Arrays may also have their data types changed using .astype(). The data type must be valid, however.
In [105]: x.dtype
Out[105]: dtype('uint32')
In [106]: x = x.astype(np.int64)
In [107]: x.dtype
Out[107]: dtype('int64')