Basic Usage¶
The main idea of the galois
package can be summarized as follows. The user creates a “Galois field array class” using GF = galois.GF(p**m)
.
A Galois field array class GF
is a subclass of numpy.ndarray
and its constructor x = GF(array_like)
mimics
the call signature of numpy.array()
. A Galois field array x
is operated on like any other numpy array, but all
arithmetic is performed in \(\mathrm{GF}(p^m)\) not \(\mathbb{Z}\) or \(\mathbb{R}\).
Internally, the Galois field arithmetic is implemented by replacing numpy ufuncs. The new ufuncs are written in python and then just-in-time compiled with numba. The ufuncs can be configured to use either lookup tables (for speed) or explicit calculation (for memory savings). Numba also provides the ability to “target” the JIT-compiled ufuncs for CPUs or GPUs.
In addition to normal array arithmetic, galois
also supports linear algebra (with numpy.linalg
functions) and polynomials over Galois fields
(with the galois.Poly
class).
Class construction¶
Galois field array classes are created using the galois.GF()
class factory function.
In [1]: import numpy as np
In [2]: import galois
In [3]: GF256 = galois.GF(2**8)
In [4]: print(GF256)
<class 'numpy.ndarray over GF(2^8)'>
These classes are subclasses of galois.GFArray
(which itself subclasses numpy.ndarray
) and have galois.GFMeta
as their metaclass.
In [5]: issubclass(GF256, np.ndarray)
Out[5]: True
In [6]: issubclass(GF256, galois.GFArray)
Out[6]: True
In [7]: issubclass(type(GF256), galois.GFMeta)
Out[7]: True
A Galois field array class contains attributes relating to its Galois field and methods to modify how the field
is calculated or displayed. See the attributes and methods in galois.GFMeta
.
# Summarizes some properties of the Galois field
In [8]: print(GF256.properties)
GF(2^8):
structure: Finite Field
characteristic: 2
degree: 8
order: 256
irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
is_primitive_poly: True
primitive_element: GF(2, order=2^8)
# Access each attribute individually
In [9]: GF256.irreducible_poly
Out[9]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
The galois
package even supports arbitrarily-large fields! This is accomplished by using numpy arrays
with dtype=object
and pure-python ufuncs. This comes at a performance penalty compared to smaller fields
which use numpy integer dtypes (e.g., numpy.uint32
) and have compiled ufuncs.
In [10]: GF = galois.GF(36893488147419103183); print(GF.properties)
GF(36893488147419103183):
structure: Finite Field
characteristic: 36893488147419103183
degree: 1
order: 36893488147419103183
irreducible_poly: Poly(x + 36893488147419103180, GF(36893488147419103183))
is_primitive_poly: True
primitive_element: GF(3, order=36893488147419103183)
In [11]: GF = galois.GF(2**100); print(GF.properties)
GF(2^100):
structure: Finite Field
characteristic: 2
degree: 100
order: 1267650600228229401496703205376
irreducible_poly: Poly(x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1, GF(2))
is_primitive_poly: True
primitive_element: GF(2, order=2^100)
Array creation¶
Galois field arrays can be created from existing numpy arrays.
# Represents an existing numpy array
In [12]: array = np.random.randint(0, GF256.order, 10, dtype=int); array
Out[12]: array([195, 188, 120, 144, 182, 218, 236, 238, 71, 249])
# Explicit Galois field array creation (a copy is performed)
In [13]: GF256(array)
Out[13]: GF([195, 188, 120, 144, 182, 218, 236, 238, 71, 249], order=2^8)
# Or view an existing numpy array as a Galois field array (no copy is performed)
In [14]: array.view(GF256)
Out[14]: GF([195, 188, 120, 144, 182, 218, 236, 238, 71, 249], order=2^8)
Or they can be created from “array-like” objects. These include strings representing a Galois field element as a polynomial over its prime subfield.
# Arrays can be specified as iterables of iterables
In [15]: GF256([[217, 130, 42], [74, 208, 113]])
Out[15]:
GF([[217, 130, 42],
[ 74, 208, 113]], order=2^8)
# You can mix-and-match polynomial strings and integers
In [16]: GF256(["x^6 + 1", 2, "1", "x^5 + x^4 + x"])
Out[16]: GF([65, 2, 1, 50], order=2^8)
# Single field elements are 0-dimensional arrays
In [17]: GF256("x^6 + x^4 + 1")
Out[17]: GF(81, order=2^8)
Galois field arrays also have constructor class methods for convenience. They include:
galois.GFArray.Zeros()
,galois.GFArray.Ones()
,galois.GFArray.Identity()
,galois.GFArray.Range()
,galois.GFArray.Random()
,galois.GFArray.Elements()
Galois field elements can either be displayed using their integer representation, polynomial representation, or
power representation. Calling galois.GFMeta.display()
will change the element representation. If called as a context
manager, the display mode will only be temporarily changed.
In [18]: x = GF256(["y**6 + 1", 0, 2, "1", "y**5 + y**4 + y"]); x
Out[18]: GF([65, 0, 2, 1, 50], order=2^8)
# Set the display mode to represent GF(2^8) field elements as polynomials over GF(2) with degree less than 8
In [19]: GF256.display("poly");
In [20]: x
Out[20]: GF([α^6 + 1, 0, α, 1, α^5 + α^4 + α], order=2^8)
# Temporarily set the display mode to represent GF(2^8) field elements as powers of the primitive element
In [21]: with GF256.display("power"):
....: print(x)
....:
GF([α^191, -∞, α, 1, α^194], order=2^8)
# Resets the display mode to the integer representation
In [22]: GF256.display();
Field arithmetic¶
Galois field arrays are treated like any other numpy array. Array arithmetic is performed using python operators or numpy functions.
In the list below, GF
is a Galois field array class created by GF = galois.GF(p**m)
, x
and y
are GF
arrays, and z
is an
integer numpy.ndarray
. All arithmetic operations follow normal numpy broadcasting rules.
Addition:
x + y == np.add(x, y)
Subtraction:
x - y == np.subtract(x, y)
Multiplication:
x * y == np.multiply(x, y)
Division:
x / y == x // y == np.divide(x, y)
Scalar multiplication:
x * z == np.multiply(x, z)
, e.g.x * 3 == x + x + x
Additive inverse:
-x == np.negative(x)
Multiplicative inverse:
GF(1) / x == np.reciprocal(x)
Exponentiation:
x ** z == np.power(x, z)
, e.g.x ** 3 == x * x * x
Logarithm:
np.log(x)
, e.g.GF.primitive_element ** np.log(x) == x
COMING SOON: Logarithm base
b
:GF.log(x, b)
, whereb
is any field elementMatrix multiplication:
A @ B == np.matmul(A, B)
In [23]: x = GF256.Random((2,5)); x
Out[23]:
GF([[168, 237, 60, 238, 17],
[150, 34, 92, 227, 90]], order=2^8)
In [24]: y = GF256.Random(5); y
Out[24]: GF([185, 101, 62, 248, 70], order=2^8)
# y is broadcast over the last dimension of x
In [25]: x + y
Out[25]:
GF([[ 17, 136, 2, 22, 87],
[ 47, 71, 98, 27, 28]], order=2^8)
Linear algebra¶
The galois
package intercepts relevant calls to numpy’s linear algebra functions and performs the specified
operation in \(\mathrm{GF}(p^m)\) not in \(\mathbb{R}\). Some of these functions include:
np.trace()
np.dot()
,np.inner()
,np.outer()
np.linalg.matrix_rank()
,np.linalg.matrix_power()
np.linalg.det()
,np.linalg.inv()
,np.linalg.solve()
In [26]: A = GF256.Random((3,3)); A
Out[26]:
GF([[ 39, 216, 230],
[ 7, 112, 163],
[212, 114, 15]], order=2^8)
In [27]: b = GF256.Random(3); b
Out[27]: GF([154, 189, 42], order=2^8)
In [28]: x = np.linalg.solve(A, b); x
Out[28]: GF([169, 199, 231], order=2^8)
In [29]: np.array_equal(A @ x, b)
Out[29]: True
Galois field arrays also contain matrix decomposition routines not included in numpy. These include:
Numpy ufunc methods¶
Galois field arrays support numpy ufunc methods. This allows the user to apply a ufunc in a unique way across the target
array. The ufunc method signature is <ufunc>.<method>(*args, **kwargs)
. All arithmetic ufuncs are supported. Below
is a list of their ufunc methods.
<method>
:reduce
,accumulate
,reduceat
,outer
,at
In [30]: X = GF256.Random((2,5)); X
Out[30]:
GF([[205, 46, 246, 48, 238],
[ 2, 184, 15, 133, 201]], order=2^8)
In [31]: np.multiply.reduce(X, axis=0)
Out[31]: GF([135, 128, 27, 213, 194], order=2^8)
In [32]: x = GF256.Random(5); x
Out[32]: GF([200, 200, 64, 241, 235], order=2^8)
In [33]: y = GF256.Random(5); y
Out[33]: GF([ 97, 155, 187, 41, 29], order=2^8)
In [34]: np.multiply.outer(x, y)
Out[34]:
GF([[128, 183, 143, 254, 221],
[128, 183, 143, 254, 221],
[101, 9, 225, 146, 19],
[ 44, 79, 4, 97, 98],
[159, 141, 161, 204, 125]], order=2^8)
Numpy functions¶
Many other relevant numpy functions are supported on Galois field arrays. These include:
np.copy()
,np.concatenate()
,np.insert()
,np.reshape()
Polynomial construction¶
The galois
package supports polynomials over Galois fields with the galois.Poly
class. galois.Poly
does not subclass numpy.ndarray
but instead contains a galois.GFArray
of coefficients as an attribute
(implements the “has-a”, not “is-a”, architecture).
Polynomials can be created by specifying the polynomial coefficients as either a galois.GFArray
or an “array-like”
object with the field
keyword argument.
In [35]: p = galois.Poly([172, 22, 0, 0, 225], field=GF256); p
Out[35]: Poly(172x^4 + 22x^3 + 225, GF(2^8))
In [36]: coeffs = GF256([33, 17, 0, 225]); coeffs
Out[36]: GF([ 33, 17, 0, 225], order=2^8)
In [37]: p = galois.Poly(coeffs, order="asc"); p
Out[37]: Poly(225x^3 + 17x + 33, GF(2^8))
Polynomials over Galois fields can also display the field elements as polynomials over their prime subfields. This can be quite confusing to read, so be warned!
In [38]: print(p)
Poly(225x^3 + 17x + 33, GF(2^8))
In [39]: with GF256.display("poly"):
....: print(p)
....:
Poly((α^7 + α^6 + α^5 + 1)x^3 + (α^4 + 1)x + (α^5 + 1), GF(2^8))
Polynomials can also be created using a number of constructor class methods. They include:
galois.Poly.Zero()
,galois.Poly.One()
,galois.Poly.Identity()
,galois.Poly.Random()
,galois.Poly.Integer()
,galois.Poly.Degrees()
,galois.Poly.Roots()
# Construct a polynomial by specifying its roots
In [40]: q = galois.Poly.Roots([155, 37], field=GF256); q
Out[40]: Poly(x^2 + 190x + 71, GF(2^8))
In [41]: q.roots()
Out[41]: GF([ 37, 155], order=2^8)
Polynomial arithmetic¶
Polynomial arithmetic is performed using python operators.
In [42]: p
Out[42]: Poly(225x^3 + 17x + 33, GF(2^8))
In [43]: q
Out[43]: Poly(x^2 + 190x + 71, GF(2^8))
In [44]: p + q
Out[44]: Poly(225x^3 + x^2 + 175x + 102, GF(2^8))
In [45]: divmod(p, q)
Out[45]: (Poly(225x + 57, GF(2^8)), Poly(56x + 104, GF(2^8)))
In [46]: p ** 2
Out[46]: Poly(171x^6 + 28x^2 + 117, GF(2^8))
Polynomials over Galois fields can be evaluated at scalars or arrays of field elements.
In [47]: p = galois.Poly.Degrees([4, 3, 0], [172, 22, 225], field=GF256); p
Out[47]: Poly(172x^4 + 22x^3 + 225, GF(2^8))
# Evaluate the polynomial at a single value
In [48]: p(1)
Out[48]: GF(91, order=2^8)
In [49]: x = GF256.Random((2,5)); x
Out[49]:
GF([[136, 243, 33, 53, 69],
[242, 35, 253, 161, 226]], order=2^8)
# Evaluate the polynomial at an array of values
In [50]: p(x)
Out[50]:
GF([[153, 175, 53, 181, 20],
[234, 64, 147, 140, 45]], order=2^8)
Polynomials can also be evaluated in superfields. For example, evaluating a Galois field’s irreducible polynomial at one of its elements.
# Notice the irreducible polynomial is over GF(2), not GF(2^8)
In [51]: p = GF256.irreducible_poly; p
Out[51]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
In [52]: GF256.is_primitive_poly
Out[52]: True
# Notice the primitive element is in GF(2^8)
In [53]: alpha = GF256.primitive_element; alpha
Out[53]: GF(2, order=2^8)
# Since p(x) is a primitive polynomial, alpha is one of its roots
In [54]: p(alpha, field=GF256)
Out[54]: GF(0, order=2^8)