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, GF31)
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([212, 169, 162, 10, 197, 158, 174, 240, 91, 212])
# Explicit Galois field construction
In [13]: GF256(array)
Out[13]: GF([212, 169, 162, 10, 197, 158, 174, 240, 91, 212], order=2^8)
# Numpy view casting to a Galois field
In [14]: array.view(GF256)
Out[14]: GF([212, 169, 162, 10, 197, 158, 174, 240, 91, 212], order=2^8)
Or, create Galois field arrays using alternate constructors.
In [15]: x = GF256.Random(10); x
Out[15]: GF([194, 70, 244, 112, 127, 58, 232, 162, 40, 148], order=2^8)
# Construct a random array without zeros to prevent ZeroDivisonError
In [16]: y = GF256.Random(10, low=1); y
Out[16]: GF([206, 200, 125, 20, 50, 246, 164, 156, 179, 201], order=2^8)
Galois field array arithmetic¶
Galois field arrays support traditional numpy array operations.
In [17]: x + y
Out[17]: GF([ 12, 142, 137, 100, 77, 204, 76, 62, 155, 93], order=2^8)
In [18]: -x
Out[18]: GF([194, 70, 244, 112, 127, 58, 232, 162, 40, 148], order=2^8)
In [19]: x * y
Out[19]: GF([171, 250, 43, 142, 6, 98, 230, 250, 18, 111], order=2^8)
In [20]: x / y
Out[20]: GF([178, 104, 176, 85, 82, 163, 237, 241, 158, 38], 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([194, 70, 244, 112, 127, 58, 232, 162, 40, 148], order=2^8)
# Exponentiate a Galois field array with any integer
In [22]: y ** -2 # NOTE: -2 is outside the field
Out[22]: GF([ 39, 199, 143, 170, 236, 198, 121, 55, 252, 162], order=2^8)
# Log base alpha (the field's primitive element)
In [23]: np.log(y)
Out[23]: array([111, 196, 243, 52, 194, 173, 149, 35, 171, 23])
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([27278556452559323149, 16317386437570256584, 28553426700578708895],
order=36893488147419103183)
In [27]: m ** 123456
Out[27]:
GF([16401527513823891316, 1652264077942075408, 23610944267758244330],
order=36893488147419103183)
In [28]: r = GF2_100.Random(3); r
Out[28]:
GF([589333022200231855128153187224, 1045292767747485264682412721411,
309792230480417268354427773104], 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([589333022200231855128153187224, 1045292767747485264682412721411,
309792230480417268354427773104], order=2^100)
Galois field arrays support numpy array broadcasting.
In [32]: a = GF31.Random((2,5)); a
Out[32]:
GF([[14, 29, 5, 9, 29],
[29, 20, 0, 18, 12]], order=31)
In [33]: b = GF31.Random(5); b
Out[33]: GF([17, 2, 7, 11, 18], order=31)
In [34]: a + b
Out[34]:
GF([[ 0, 0, 12, 20, 16],
[15, 22, 7, 29, 30]], 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([ 3, 22, 0, 7, 7], order=31)
In [36]: np.multiply.outer(x, y)
Out[36]:
GF([[171, 29, 160, 147, 64, 44, 195, 68, 11, 223],
[115, 250, 37, 17, 176, 69, 141, 187, 86, 188],
[177, 179, 43, 12, 229, 82, 151, 116, 154, 71],
[105, 84, 174, 142, 21, 59, 217, 139, 199, 36],
[ 7, 24, 15, 66, 6, 32, 203, 236, 8, 103],
[ 59, 167, 173, 111, 224, 98, 183, 238, 150, 157],
[236, 166, 142, 161, 167, 149, 230, 159, 98, 78],
[190, 85, 141, 64, 82, 204, 136, 250, 51, 247],
[198, 54, 212, 26, 131, 72, 112, 254, 18, 30],
[164, 251, 6, 223, 247, 178, 220, 202, 162, 111]], order=2^8)
Display field elements as integers or polynomials.
In [37]: x
Out[37]: GF([194, 70, 244, 112, 127, 58, 232, 162, 40, 148], order=2^8)
# Set the display mode to represent GF(p^m) field elements as polynomials over GF(p)[x].
In [38]: GF256.display("poly")
In [39]: x
Out[39]:
GF([x^7 + x^6 + x, x^6 + x^2 + x, x^7 + x^6 + x^5 + x^4 + x^2,
x^6 + x^5 + x^4, x^6 + x^5 + x^4 + x^3 + x^2 + x + 1,
x^5 + x^4 + x^3 + x, x^7 + x^6 + x^5 + x^3, x^7 + x^5 + x, x^5 + x^3,
x^7 + x^4 + x^2], order=2^8)
# Reset the display settings to the default of "int"
In [40]: GF256.display()
Galois field polynomial construction¶
Construct Galois field polynomials.
# Construct a polynomial by specifying all the coefficients in descending-degree order
In [41]: p = galois.Poly([1, 22, 0, 17, 25], field=GF31); p
Out[41]: Poly(x^4 + 22x^3 + 17x + 25, GF31)
# Construct a polynomial by specifying only the non-zero coefficients
In [42]: q = galois.Poly.NonZero([4, 14], [2, 0], field=GF31); q
Out[42]: Poly(4x^2 + 14, GF31)
Galois field polynomial arithmetic¶
Galois field polynomial arithmetic is similar to numpy array operations.
In [43]: p + q
Out[43]: Poly(x^4 + 22x^3 + 4x^2 + 17x + 8, GF31)
In [44]: p // q, p % q
Out[44]: (Poly(8x^2 + 21x + 3, GF31), Poly(2x + 14, GF31))
In [45]: p ** 2
Out[45]: Poly(x^8 + 13x^7 + 19x^6 + 3x^5 + 23x^4 + 15x^3 + 10x^2 + 13x + 5, GF31)
Galois field polynomials can also be evaluated at constants or arrays.
In [46]: p
Out[46]: Poly(x^4 + 22x^3 + 17x + 25, GF31)
In [47]: a
Out[47]:
GF([[14, 29, 5, 9, 29],
[29, 20, 0, 18, 12]], order=31)
# Evaluate a polynomial at a single value
In [48]: p(1)
Out[48]: GF(3, order=31)
# Evaluate a polynomial at an array of values
In [49]: p(a)
Out[49]:
GF([[ 2, 17, 13, 23, 17],
[17, 15, 25, 26, 19]], order=31)