Basic Usage¶
Galois field array construction¶
Construct Galois field array classes using the GF_factory()
class factory function.
In [1]: import numpy as np
In [2]: import galois
In [3]: GF31 = galois.GF_factory(31, 1);
In [4]: print(GF31)
<Galois Field: GF(31^1), prim_poly = x + 28 (59 decimal)>
In [5]: GF31.alpha
Out[5]: GF(3, order=31)
In [6]: GF31.prim_poly
Out[6]: Poly(x + 28, GF(31))
Create any Galois field array class type: GF(2^m)
, GF(p)
, or GF(p^m)
. Even arbitrarily-large fields!
# Field used in AES
In [7]: GF256 = galois.GF_factory(2, 8); print(GF256)
<Galois Field: GF(2^8), prim_poly = x^8 + x^4 + x^3 + x^2 + 1 (285 decimal)>
# Large prime field
In [8]: prime = 36893488147419103183
In [9]: galois.is_prime(prime)
Out[9]: True
In [10]: GFp = galois.GF_factory(prime, 1); print(GFp)
<Galois Field: GF(36893488147419103183^1), prim_poly = x + 36893488147419103180 (73786976294838206363 decimal)>
# Large characteristic-2 field
In [11]: GF2_100 = galois.GF_factory(2, 100); print(GF2_100)
<Galois Field: GF(2^100), prim_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 (1267650600228486663289456659305 decimal)>
Create arrays 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([ 15, 53, 224, 255, 51, 185, 248, 180, 14, 56])
# Explicit Galois field construction
In [13]: GF256(array)
Out[13]: GF([ 15, 53, 224, 255, 51, 185, 248, 180, 14, 56], order=2^8)
# Numpy view casting to a Galois field
In [14]: array.view(GF256)
Out[14]: GF([ 15, 53, 224, 255, 51, 185, 248, 180, 14, 56], order=2^8)
Or, create Galois field arrays using alternate constructors.
In [15]: x = GF256.Random(10); x
Out[15]: GF([120, 22, 231, 14, 162, 140, 61, 64, 94, 45], order=2^8)
# Construct a random array without zeros to prevent ZeroDivisonError
In [16]: y = GF256.Random(10, low=1); y
Out[16]: GF([218, 52, 4, 30, 216, 173, 216, 30, 36, 170], order=2^8)
Galois field array arithmetic¶
Galois field arrays support traditional numpy array operations.
In [17]: x + y
Out[17]: GF([162, 34, 227, 16, 122, 33, 229, 94, 122, 135], order=2^8)
In [18]: -x
Out[18]: GF([120, 22, 231, 14, 162, 140, 61, 64, 94, 45], order=2^8)
In [19]: x * y
Out[19]: GF([121, 223, 187, 180, 167, 159, 18, 211, 106, 229], order=2^8)
In [20]: x / y
Out[20]: GF([ 14, 109, 240, 197, 242, 20, 247, 55, 17, 236], order=2^8)
# Multiple addition of a Galois field array with any integer
In [21]: x * -3 # NOTE: -3 is outside the field
Out[21]: GF([120, 22, 231, 14, 162, 140, 61, 64, 94, 45], order=2^8)
# Exponentiate a Galois field array with any integer
In [22]: y ** -2 # NOTE: -2 is outside the field
Out[22]: GF([176, 119, 216, 136, 29, 64, 29, 136, 185, 81], order=2^8)
# Log base alpha (the field's primitive element)
In [23]: np.log(y)
Out[23]: array([134, 106, 2, 76, 251, 252, 251, 76, 225, 151])
Even field arithmetic on extremely large fields!
In [24]: m = GFp.Random(3)
In [25]: n = GFp.Random(3)
In [26]: m + n
Out[26]:
GF([30580551531678419669, 31143001337395583975, 27118345337033687440],
order=36893488147419103183)
In [27]: m ** 123456
Out[27]:
GF([17203063571235620334, 33586972422939703752, 7523360037566812614],
order=36893488147419103183)
In [28]: r = GF2_100.Random(3); r
Out[28]:
GF([70254931826708829276836953880, 700251669916615000889776053596,
833222667623867657743417032410], order=2^100)
# With characteristic 2, this will always be zero
In [29]: r + r
Out[29]: GF([0, 0, 0], order=2^100)
# This is equivalent
In [30]: r * 2
Out[30]: GF([0, 0, 0], order=2^100)
# But this will result in `r`
In [31]: r * 3
Out[31]:
GF([70254931826708829276836953880, 700251669916615000889776053596,
833222667623867657743417032410], order=2^100)
Galois field arrays support numpy array broadcasting.
In [32]: a = GF31.Random((2,5)); a
Out[32]:
GF([[18, 11, 17, 8, 5],
[ 4, 24, 14, 16, 8]], order=31)
In [33]: b = GF31.Random(5); b
Out[33]: GF([15, 23, 25, 20, 19], order=31)
In [34]: a + b
Out[34]:
GF([[ 2, 3, 11, 28, 24],
[19, 16, 8, 5, 27]], order=31)
Galois field arrays also support numpy ufunc methods.
# Valid ufunc methods include "reduce", "accumulate", "reduceat", "outer", "at"
In [35]: np.multiply.reduce(a, axis=0)
Out[35]: GF([10, 16, 21, 4, 9], order=31)
In [36]: np.multiply.outer(x, y)
Out[36]:
GF([[121, 149, 253, 57, 137, 15, 137, 57, 70, 122],
[199, 223, 88, 185, 235, 203, 235, 185, 162, 169],
[239, 220, 187, 213, 60, 120, 60, 213, 10, 247],
[120, 5, 56, 180, 100, 200, 100, 180, 229, 226],
[254, 185, 178, 96, 167, 83, 167, 96, 75, 26],
[196, 114, 10, 51, 193, 159, 193, 51, 90, 28],
[104, 240, 244, 140, 18, 36, 18, 140, 7, 151],
[132, 129, 29, 211, 4, 8, 4, 211, 245, 213],
[221, 227, 101, 154, 97, 194, 97, 154, 106, 69],
[ 73, 151, 180, 113, 19, 38, 19, 113, 125, 229]], order=2^8)
Display field elements as integers or polynomials.
In [37]: print(x)
GF([120, 22, 231, 14, 162, 140, 61, 64, 94, 45], order=2^8)
# Temporarily set the display mode to represent GF(p^m) field elements as polynomials over GF(p)[x].
In [38]: with GF256.display("poly"):
....: print(x)
....:
GF([x^6 + x^5 + x^4 + x^3, x^4 + x^2 + x, x^7 + x^6 + x^5 + x^2 + x + 1,
x^3 + x^2 + x, x^7 + x^5 + x, x^7 + x^3 + x^2,
x^5 + x^4 + x^3 + x^2 + 1, x^6, x^6 + x^4 + x^3 + x^2 + x,
x^5 + x^3 + x^2 + 1], order=2^8)
Galois field polynomial construction¶
Construct Galois field polynomials.
# Construct a polynomial by specifying all the coefficients in descending-degree order
In [39]: p = galois.Poly([1, 22, 0, 17, 25], field=GF31); p
Out[39]: Poly(x^4 + 22x^3 + 17x + 25, GF(31))
# Construct a polynomial by specifying only the non-zero coefficients
In [40]: q = galois.Poly.Degrees([2, 0], coeffs=[4, 14], field=GF31); q
Out[40]: Poly(4x^2 + 14, GF(31))
Galois field polynomial arithmetic¶
Galois field polynomial arithmetic is similar to numpy array operations.
In [41]: p + q
Out[41]: Poly(x^4 + 22x^3 + 4x^2 + 17x + 8, GF(31))
In [42]: p // q, p % q
Out[42]: (Poly(8x^2 + 21x + 3, GF(31)), Poly(2x + 14, GF(31)))
In [43]: p ** 2
Out[43]: Poly(x^8 + 13x^7 + 19x^6 + 3x^5 + 23x^4 + 15x^3 + 10x^2 + 13x + 5, GF(31))
Galois field polynomials can also be evaluated at constants or arrays.
In [44]: p
Out[44]: Poly(x^4 + 22x^3 + 17x + 25, GF(31))
In [45]: a
Out[45]:
GF([[18, 11, 17, 8, 5],
[ 4, 24, 14, 16, 8]], order=31)
# Evaluate a polynomial at a single value
In [46]: p(1)
Out[46]: GF(3, order=31)
# Evaluate a polynomial at an array of values
In [47]: p(a)
Out[47]:
GF([[26, 22, 0, 21, 13],
[21, 0, 2, 15, 21]], order=31)