Array Arithmetic¶
After creating a FieldArray subclass and one or two arrays, nearly any arithmetic operation can be
performed using normal NumPy ufuncs or Python operators.
In the sections below, the finite field \(\mathrm{GF}(3^5)\) and arrays \(x\) and \(y\) are used.
In [1]: GF = galois.GF(3**5)
In [2]: x = GF([184, 25, 157, 31]); x
Out[2]: GF([184, 25, 157, 31], order=3^5)
In [3]: y = GF([179, 9, 139, 27]); y
Out[3]: GF([179, 9, 139, 27], order=3^5)
Standard arithmetic¶
NumPy ufuncs are universal functions that operate on scalars. Unary ufuncs operate on a single scalar and binary ufuncs operate on two scalars. NumPy extends the scalar operation of ufuncs to operate on arrays in various ways. This extensibility enables NumPy broadcasting.
Expand any section for more details.
Addition: x + y == np.add(x, y)
In [4]: x
Out[4]: GF([184, 25, 157, 31], order=3^5)
In [5]: y
Out[5]: GF([179, 9, 139, 27], order=3^5)
In [6]: x + y
Out[6]: GF([ 81, 7, 215, 58], order=3^5)
In [7]: np.add(x, y)
Out[7]: GF([ 81, 7, 215, 58], order=3^5)
In [8]: x
Out[8]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [9]: y
Out[9]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [10]: x + y
Out[10]:
GF([ α^4, 2α + 1,
2α^4 + α^3 + 2α^2 + 2α + 2, 2α^3 + α + 1], order=3^5)
In [11]: np.add(x, y)
Out[11]:
GF([ α^4, 2α + 1,
2α^4 + α^3 + 2α^2 + 2α + 2, 2α^3 + α + 1], order=3^5)
In [12]: x
Out[12]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [13]: y
Out[13]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [14]: x + y
Out[14]: GF([ α^4, α^126, α^175, α^28], order=3^5)
In [15]: np.add(x, y)
Out[15]: GF([ α^4, α^126, α^175, α^28], order=3^5)
Additive inverse: -x == np.negative(x)
In [16]: x
Out[16]: GF([184, 25, 157, 31], order=3^5)
In [17]: -x
Out[17]: GF([ 98, 14, 206, 62], order=3^5)
In [18]: np.negative(x)
Out[18]: GF([ 98, 14, 206, 62], order=3^5)
In [19]: x
Out[19]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [20]: -x
Out[20]:
GF([ α^4 + α^2 + 2α + 2, α^2 + α + 2,
2α^4 + α^3 + α^2 + 2α + 2, 2α^3 + 2α + 2], order=3^5)
In [21]: np.negative(x)
Out[21]:
GF([ α^4 + α^2 + 2α + 2, α^2 + α + 2,
2α^4 + α^3 + α^2 + 2α + 2, 2α^3 + 2α + 2], order=3^5)
In [22]: x
Out[22]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [23]: -x
Out[23]: GF([ α^35, α^209, α^55, α^93], order=3^5)
In [24]: np.negative(x)
Out[24]: GF([ α^35, α^209, α^55, α^93], order=3^5)
Any array added to its additive inverse results in zero.
In [25]: x
Out[25]: GF([184, 25, 157, 31], order=3^5)
In [26]: x + np.negative(x)
Out[26]: GF([0, 0, 0, 0], order=3^5)
In [27]: x
Out[27]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [28]: x + np.negative(x)
Out[28]: GF([0, 0, 0, 0], order=3^5)
In [29]: x
Out[29]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [30]: x + np.negative(x)
Out[30]: GF([0, 0, 0, 0], order=3^5)
Subtraction: x - y == np.subtract(x, y)
In [31]: x
Out[31]: GF([184, 25, 157, 31], order=3^5)
In [32]: y
Out[32]: GF([179, 9, 139, 27], order=3^5)
In [33]: x - y
Out[33]: GF([17, 16, 18, 4], order=3^5)
In [34]: np.subtract(x, y)
Out[34]: GF([17, 16, 18, 4], order=3^5)
In [35]: x
Out[35]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [36]: y
Out[36]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [37]: x - y
Out[37]: GF([α^2 + 2α + 2, α^2 + 2α + 1, 2α^2, α + 1], order=3^5)
In [38]: np.subtract(x, y)
Out[38]: GF([α^2 + 2α + 2, α^2 + 2α + 1, 2α^2, α + 1], order=3^5)
In [39]: x
Out[39]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [40]: y
Out[40]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [41]: x - y
Out[41]: GF([α^222, α^138, α^123, α^69], order=3^5)
In [42]: np.subtract(x, y)
Out[42]: GF([α^222, α^138, α^123, α^69], order=3^5)
Multiplication: x * y == np.multiply(x, y)
In [43]: x
Out[43]: GF([184, 25, 157, 31], order=3^5)
In [44]: y
Out[44]: GF([179, 9, 139, 27], order=3^5)
In [45]: x * y
Out[45]: GF([ 41, 225, 106, 123], order=3^5)
In [46]: np.multiply(x, y)
Out[46]: GF([ 41, 225, 106, 123], order=3^5)
In [47]: x
Out[47]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [48]: y
Out[48]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [49]: x * y
Out[49]:
GF([ α^3 + α^2 + α + 2, 2α^4 + 2α^3 + α^2, α^4 + 2α^2 + 2α + 1,
α^4 + α^3 + α^2 + 2α], order=3^5)
In [50]: np.multiply(x, y)
Out[50]:
GF([ α^3 + α^2 + α + 2, 2α^4 + 2α^3 + α^2, α^4 + 2α^2 + 2α + 1,
α^4 + α^3 + α^2 + 2α], order=3^5)
In [51]: x
Out[51]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [52]: y
Out[52]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [53]: x * y
Out[53]: GF([α^216, α^90, α^235, α^217], order=3^5)
In [54]: np.multiply(x, y)
Out[54]: GF([α^216, α^90, α^235, α^217], order=3^5)
Scalar multiplication: x * 4 == np.multiply(x, 4)
Scalar multiplication is essentially repeated addition. It is the “multiplication” of finite field elements and integers. The integer value indicates how many additions of the field element to sum.
In [55]: x
Out[55]: GF([184, 25, 157, 31], order=3^5)
In [56]: x * 4
Out[56]: GF([184, 25, 157, 31], order=3^5)
In [57]: np.multiply(x, 4)
Out[57]: GF([184, 25, 157, 31], order=3^5)
In [58]: x + x + x + x
Out[58]: GF([184, 25, 157, 31], order=3^5)
In [59]: x
Out[59]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [60]: x * 4
Out[60]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [61]: np.multiply(x, 4)
Out[61]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [62]: x + x + x + x
Out[62]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [63]: x
Out[63]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [64]: x * 4
Out[64]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [65]: np.multiply(x, 4)
Out[65]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [66]: x + x + x + x
Out[66]: GF([α^156, α^88, α^176, α^214], order=3^5)
In finite fields \(\mathrm{GF}(p^m)\), the characteristic \(p\) is the smallest value when multiplied by any non-zero field element that results in 0.
In [67]: p = GF.characteristic; p
Out[67]: 3
In [68]: x * p
Out[68]: GF([0, 0, 0, 0], order=3^5)
In [69]: p = GF.characteristic; p
Out[69]: 3
In [70]: x * p
Out[70]: GF([0, 0, 0, 0], order=3^5)
In [71]: p = GF.characteristic; p
Out[71]: 3
In [72]: x * p
Out[72]: GF([0, 0, 0, 0], order=3^5)
Multiplicative inverse: y ** -1 == np.reciprocal(y)
In [73]: y
Out[73]: GF([179, 9, 139, 27], order=3^5)
In [74]: y ** -1
Out[74]: GF([ 71, 217, 213, 235], order=3^5)
In [75]: GF(1) / y
Out[75]: GF([ 71, 217, 213, 235], order=3^5)
In [76]: np.reciprocal(y)
Out[76]: GF([ 71, 217, 213, 235], order=3^5)
In [77]: y
Out[77]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [78]: y ** -1
Out[78]:
GF([ 2α^3 + α^2 + 2α + 2, 2α^4 + 2α^3 + 1,
2α^4 + α^3 + 2α^2 + 2α, 2α^4 + 2α^3 + 2α^2 + 1], order=3^5)
In [79]: GF(1) / y
Out[79]:
GF([ 2α^3 + α^2 + 2α + 2, 2α^4 + 2α^3 + 1,
2α^4 + α^3 + 2α^2 + 2α, 2α^4 + 2α^3 + 2α^2 + 1], order=3^5)
In [80]: np.reciprocal(y)
Out[80]:
GF([ 2α^3 + α^2 + 2α + 2, 2α^4 + 2α^3 + 1,
2α^4 + α^3 + 2α^2 + 2α, 2α^4 + 2α^3 + 2α^2 + 1], order=3^5)
In [81]: y
Out[81]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [82]: y ** -1
Out[82]: GF([α^182, α^240, α^183, α^239], order=3^5)
In [83]: GF(1) / y
Out[83]: GF([α^182, α^240, α^183, α^239], order=3^5)
In [84]: np.reciprocal(y)
Out[84]: GF([α^182, α^240, α^183, α^239], order=3^5)
Any array multiplied by its multiplicative inverse results in one.
In [85]: y * np.reciprocal(y)
Out[85]: GF([1, 1, 1, 1], order=3^5)
In [86]: y * np.reciprocal(y)
Out[86]: GF([1, 1, 1, 1], order=3^5)
In [87]: y * np.reciprocal(y)
Out[87]: GF([1, 1, 1, 1], order=3^5)
Division: x / y == x // y == np.divide(x, y)
In [88]: x
Out[88]: GF([184, 25, 157, 31], order=3^5)
In [89]: y
Out[89]: GF([179, 9, 139, 27], order=3^5)
In [90]: x / y
Out[90]: GF([237, 56, 122, 126], order=3^5)
In [91]: x // y
Out[91]: GF([237, 56, 122, 126], order=3^5)
In [92]: np.divide(x, y)
Out[92]: GF([237, 56, 122, 126], order=3^5)
In [93]: x
Out[93]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [94]: y
Out[94]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [95]: x / y
Out[95]:
GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5)
In [96]: x // y
Out[96]:
GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5)
In [97]: np.divide(x, y)
Out[97]:
GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5)
In [98]: x
Out[98]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [99]: y
Out[99]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [100]: x / y
Out[100]: GF([ α^96, α^86, α^117, α^211], order=3^5)
In [101]: x // y
Out[101]: GF([ α^96, α^86, α^117, α^211], order=3^5)
In [102]: np.divide(x, y)
Out[102]: GF([ α^96, α^86, α^117, α^211], order=3^5)
Remainder: x % y == np.remainder(x, y)
In [103]: x
Out[103]: GF([184, 25, 157, 31], order=3^5)
In [104]: y
Out[104]: GF([179, 9, 139, 27], order=3^5)
In [105]: x % y
Out[105]: GF([0, 0, 0, 0], order=3^5)
In [106]: np.remainder(x, y)
Out[106]: GF([0, 0, 0, 0], order=3^5)
In [107]: x
Out[107]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [108]: y
Out[108]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [109]: x % y
Out[109]: GF([0, 0, 0, 0], order=3^5)
In [110]: np.remainder(x, y)
Out[110]: GF([0, 0, 0, 0], order=3^5)
In [111]: x
Out[111]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [112]: y
Out[112]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [113]: x % y
Out[113]: GF([0, 0, 0, 0], order=3^5)
In [114]: np.remainder(x, y)
Out[114]: GF([0, 0, 0, 0], order=3^5)
Divmod: divmod(x, y) == np.divmod(x, y)
In [115]: x
Out[115]: GF([184, 25, 157, 31], order=3^5)
In [116]: y
Out[116]: GF([179, 9, 139, 27], order=3^5)
In [117]: x // y, x % y
Out[117]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [118]: divmod(x, y)
Out[118]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [119]: np.divmod(x, y)
Out[119]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [120]: x
Out[120]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [121]: y
Out[121]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [122]: x // y, x % y
Out[122]:
(GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5),
GF([0, 0, 0, 0], order=3^5))
In [123]: divmod(x, y)
Out[123]:
(GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5),
GF([0, 0, 0, 0], order=3^5))
In [124]: np.divmod(x, y)
Out[124]:
(GF([ 2α^4 + 2α^3 + 2α^2 + α, 2α^3 + 2,
α^4 + α^3 + α^2 + α + 2, α^4 + α^3 + 2α^2], order=3^5),
GF([0, 0, 0, 0], order=3^5))
In [125]: x
Out[125]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [126]: y
Out[126]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [127]: x // y, x % y
Out[127]: (GF([ α^96, α^86, α^117, α^211], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [128]: divmod(x, y)
Out[128]: (GF([ α^96, α^86, α^117, α^211], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [129]: np.divmod(x, y)
Out[129]: (GF([ α^96, α^86, α^117, α^211], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [130]: q, r = divmod(x, y)
In [131]: q*y + r == x
Out[131]: array([ True, True, True, True])
In [132]: q, r = divmod(x, y)
In [133]: q*y + r == x
Out[133]: array([ True, True, True, True])
In [134]: q, r = divmod(x, y)
In [135]: q*y + r == x
Out[135]: array([ True, True, True, True])
Exponentiation: x ** 3 == np.power(x, 3)
In [136]: x
Out[136]: GF([184, 25, 157, 31], order=3^5)
In [137]: x ** 3
Out[137]: GF([175, 76, 218, 192], order=3^5)
In [138]: np.power(x, 3)
Out[138]: GF([175, 76, 218, 192], order=3^5)
In [139]: x * x * x
Out[139]: GF([175, 76, 218, 192], order=3^5)
In [140]: x
Out[140]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [141]: x ** 3
Out[141]:
GF([ 2α^4 + α^2 + α + 1, 2α^3 + 2α^2 + α + 1, 2α^4 + 2α^3 + 2,
2α^4 + α^3 + α], order=3^5)
In [142]: np.power(x, 3)
Out[142]:
GF([ 2α^4 + α^2 + α + 1, 2α^3 + 2α^2 + α + 1, 2α^4 + 2α^3 + 2,
2α^4 + α^3 + α], order=3^5)
In [143]: x * x * x
Out[143]:
GF([ 2α^4 + α^2 + α + 1, 2α^3 + 2α^2 + α + 1, 2α^4 + 2α^3 + 2,
2α^4 + α^3 + α], order=3^5)
In [144]: x
Out[144]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [145]: x ** 3
Out[145]: GF([α^226, α^22, α^44, α^158], order=3^5)
In [146]: np.power(x, 3)
Out[146]: GF([α^226, α^22, α^44, α^158], order=3^5)
In [147]: x * x * x
Out[147]: GF([α^226, α^22, α^44, α^158], order=3^5)
Square root: np.sqrt(x)
In [148]: x
Out[148]: GF([184, 25, 157, 31], order=3^5)
In [149]: x.is_square()
Out[149]: array([ True, True, True, True])
In [150]: z = np.sqrt(x); z
Out[150]: GF([102, 109, 14, 111], order=3^5)
In [151]: z ** 2 == x
Out[151]: array([ True, True, True, True])
In [152]: x
Out[152]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [153]: x.is_square()
Out[153]: array([ True, True, True, True])
In [154]: z = np.sqrt(x); z
Out[154]:
GF([α^4 + 2α^2 + α, α^4 + α^3 + 1, α^2 + α + 2, α^4 + α^3 + α],
order=3^5)
In [155]: z ** 2 == x
Out[155]: array([ True, True, True, True])
In [156]: x
Out[156]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [157]: x.is_square()
Out[157]: array([ True, True, True, True])
In [158]: z = np.sqrt(x); z
Out[158]: GF([α^199, α^165, α^209, α^228], order=3^5)
In [159]: z ** 2 == x
Out[159]: array([ True, True, True, True])
See also is_square(), squares(), and non_squares().
Logarithm: np.log(x) or x.log()
Compute the logarithm base \(\alpha\), the primitive element of the field.
In [160]: y
Out[160]: GF([179, 9, 139, 27], order=3^5)
In [161]: z = np.log(y); z
Out[161]: array([60, 2, 59, 3])
In [162]: alpha = GF.primitive_element; alpha
Out[162]: GF(3, order=3^5)
In [163]: alpha ** z == y
Out[163]: array([ True, True, True, True])
In [164]: y
Out[164]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [165]: z = np.log(y); z
Out[165]: array([60, 2, 59, 3])
In [166]: alpha = GF.primitive_element; alpha
Out[166]: GF(α, order=3^5)
In [167]: alpha ** z == y
Out[167]: array([ True, True, True, True])
In [168]: y
Out[168]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [169]: z = np.log(y); z
Out[169]: array([60, 2, 59, 3])
In [170]: alpha = GF.primitive_element; alpha
Out[170]: GF(α, order=3^5)
In [171]: alpha ** z == y
Out[171]: array([ True, True, True, True])
Compute the logarithm base \(\beta\), a different primitive element of the field. See FieldArray.log() for more
details.
In [172]: y
Out[172]: GF([179, 9, 139, 27], order=3^5)
In [173]: beta = GF.primitive_elements[-1]; beta
Out[173]: GF(242, order=3^5)
In [174]: z = y.log(beta); z
Out[174]: array([190, 208, 207, 191])
In [175]: beta ** z == y
Out[175]: array([ True, True, True, True])
In [176]: y
Out[176]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [177]: beta = GF.primitive_elements[-1]; beta
Out[177]: GF(2α^4 + 2α^3 + 2α^2 + 2α + 2, order=3^5)
In [178]: z = y.log(beta); z
Out[178]: array([190, 208, 207, 191])
In [179]: beta ** z == y
Out[179]: array([ True, True, True, True])
In [180]: y
Out[180]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [181]: beta = GF.primitive_elements[-1]; beta
Out[181]: GF(α^185, order=3^5)
In [182]: z = y.log(beta); z
Out[182]: array([190, 208, 207, 191])
In [183]: beta ** z == y
Out[183]: array([ True, True, True, True])
Ufunc methods¶
FieldArray instances support NumPy ufunc methods. Ufunc methods allow
a user to apply a NumPy ufunc in a unique way across the target array. All arithmetic ufuncs are supported.
Expand any section for more details.
reduce()
The reduce methods reduce the input array’s dimension by one, applying the ufunc across one axis.
In [184]: x
Out[184]: GF([184, 25, 157, 31], order=3^5)
In [185]: np.add.reduce(x)
Out[185]: GF(7, order=3^5)
In [186]: x[0] + x[1] + x[2] + x[3]
Out[186]: GF(7, order=3^5)
In [187]: x
Out[187]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [188]: np.add.reduce(x)
Out[188]: GF(2α + 1, order=3^5)
In [189]: x[0] + x[1] + x[2] + x[3]
Out[189]: GF(2α + 1, order=3^5)
In [190]: x
Out[190]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [191]: np.add.reduce(x)
Out[191]: GF(α^126, order=3^5)
In [192]: x[0] + x[1] + x[2] + x[3]
Out[192]: GF(α^126, order=3^5)
In [193]: np.multiply.reduce(x)
Out[193]: GF(105, order=3^5)
In [194]: x[0] * x[1] * x[2] * x[3]
Out[194]: GF(105, order=3^5)
In [195]: np.multiply.reduce(x)
Out[195]: GF(α^4 + 2α^2 + 2α, order=3^5)
In [196]: x[0] * x[1] * x[2] * x[3]
Out[196]: GF(α^4 + 2α^2 + 2α, order=3^5)
In [197]: np.multiply.reduce(x)
Out[197]: GF(α^150, order=3^5)
In [198]: x[0] * x[1] * x[2] * x[3]
Out[198]: GF(α^150, order=3^5)
accumulate()
The accumulate methods accumulate the result of the ufunc across a specified axis.
In [199]: x
Out[199]: GF([184, 25, 157, 31], order=3^5)
In [200]: np.add.accumulate(x)
Out[200]: GF([184, 173, 57, 7], order=3^5)
In [201]: GF([x[0], x[0] + x[1], x[0] + x[1] + x[2], x[0] + x[1] + x[2] + x[3]])
Out[201]: GF([184, 173, 57, 7], order=3^5)
In [202]: x
Out[202]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [203]: np.add.accumulate(x)
Out[203]:
GF([2α^4 + 2α^2 + α + 1, 2α^4 + α^2 + 2, 2α^3 + α,
2α + 1], order=3^5)
In [204]: GF([x[0], x[0] + x[1], x[0] + x[1] + x[2], x[0] + x[1] + x[2] + x[3]])
Out[204]:
GF([2α^4 + 2α^2 + α + 1, 2α^4 + α^2 + 2, 2α^3 + α,
2α + 1], order=3^5)
In [205]: x
Out[205]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [206]: np.add.accumulate(x)
Out[206]: GF([α^156, α^213, α^196, α^126], order=3^5)
In [207]: GF([x[0], x[0] + x[1], x[0] + x[1] + x[2], x[0] + x[1] + x[2] + x[3]])
Out[207]: GF([α^156, α^213, α^196, α^126], order=3^5)
In [208]: np.multiply.accumulate(x)
Out[208]: GF([184, 9, 211, 105], order=3^5)
In [209]: GF([x[0], x[0] * x[1], x[0] * x[1] * x[2], x[0] * x[1] * x[2] * x[3]])
Out[209]: GF([184, 9, 211, 105], order=3^5)
In [210]: np.multiply.accumulate(x)
Out[210]:
GF([ 2α^4 + 2α^2 + α + 1, α^2,
2α^4 + α^3 + 2α^2 + α + 1, α^4 + 2α^2 + 2α], order=3^5)
In [211]: GF([x[0], x[0] * x[1], x[0] * x[1] * x[2], x[0] * x[1] * x[2] * x[3]])
Out[211]:
GF([ 2α^4 + 2α^2 + α + 1, α^2,
2α^4 + α^3 + 2α^2 + α + 1, α^4 + 2α^2 + 2α], order=3^5)
In [212]: np.multiply.accumulate(x)
Out[212]: GF([α^156, α^2, α^178, α^150], order=3^5)
In [213]: GF([x[0], x[0] * x[1], x[0] * x[1] * x[2], x[0] * x[1] * x[2] * x[3]])
Out[213]: GF([α^156, α^2, α^178, α^150], order=3^5)
reduceat()
The reduceat methods reduces the input array’s dimension by one, applying the ufunc across one axis
in-between certain indices.
In [214]: x
Out[214]: GF([184, 25, 157, 31], order=3^5)
In [215]: np.add.reduceat(x, [0, 3])
Out[215]: GF([57, 31], order=3^5)
In [216]: GF([x[0] + x[1] + x[2], x[3]])
Out[216]: GF([57, 31], order=3^5)
In [217]: x
Out[217]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [218]: np.add.reduceat(x, [0, 3])
Out[218]: GF([ 2α^3 + α, α^3 + α + 1], order=3^5)
In [219]: GF([x[0] + x[1] + x[2], x[3]])
Out[219]: GF([ 2α^3 + α, α^3 + α + 1], order=3^5)
In [220]: x
Out[220]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [221]: np.add.reduceat(x, [0, 3])
Out[221]: GF([α^196, α^214], order=3^5)
In [222]: GF([x[0] + x[1] + x[2], x[3]])
Out[222]: GF([α^196, α^214], order=3^5)
In [223]: np.multiply.reduceat(x, [0, 3])
Out[223]: GF([211, 31], order=3^5)
In [224]: GF([x[0] * x[1] * x[2], x[3]])
Out[224]: GF([211, 31], order=3^5)
In [225]: np.multiply.reduceat(x, [0, 3])
Out[225]: GF([2α^4 + α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [226]: GF([x[0] * x[1] * x[2], x[3]])
Out[226]: GF([2α^4 + α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [227]: np.multiply.reduceat(x, [0, 3])
Out[227]: GF([α^178, α^214], order=3^5)
In [228]: GF([x[0] * x[1] * x[2], x[3]])
Out[228]: GF([α^178, α^214], order=3^5)
outer()
The outer methods applies the ufunc to each pair of inputs.
In [229]: x
Out[229]: GF([184, 25, 157, 31], order=3^5)
In [230]: y
Out[230]: GF([179, 9, 139, 27], order=3^5)
In [231]: np.add.outer(x, y)
Out[231]:
GF([[ 81, 166, 80, 211],
[165, 7, 155, 52],
[ 54, 139, 215, 103],
[198, 40, 89, 58]], order=3^5)
In [232]: x
Out[232]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [233]: y
Out[233]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [234]: np.add.outer(x, y)
Out[234]:
GF([[ α^4, 2α^4 + α + 1,
2α^3 + 2α^2 + 2α + 2, 2α^4 + α^3 + 2α^2 + α + 1],
[ 2α^4 + α, 2α + 1,
α^4 + 2α^3 + 2α^2 + 2, α^3 + 2α^2 + 2α + 1],
[ 2α^3, α^4 + 2α^3 + α + 1,
2α^4 + α^3 + 2α^2 + 2α + 2, α^4 + 2α^2 + α + 1],
[ 2α^4 + α^3 + α^2, α^3 + α^2 + α + 1,
α^4 + 2α + 2, 2α^3 + α + 1]], order=3^5)
In [235]: x
Out[235]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [236]: y
Out[236]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [237]: np.add.outer(x, y)
Out[237]:
GF([[ α^4, α^45, α^236, α^178],
[α^137, α^126, α^43, α^79],
[α^124, α^59, α^175, α^181],
[α^103, α^115, α^166, α^28]], order=3^5)
In [238]: np.multiply.outer(x, y)
Out[238]:
GF([[ 41, 192, 93, 97],
[ 91, 225, 193, 196],
[ 80, 211, 106, 145],
[149, 41, 129, 123]], order=3^5)
In [239]: np.multiply.outer(x, y)
Out[239]:
GF([[ α^3 + α^2 + α + 2, 2α^4 + α^3 + α,
α^4 + α^2 + α, α^4 + α^2 + 2α + 1],
[ α^4 + α^2 + 1, 2α^4 + 2α^3 + α^2,
2α^4 + α^3 + α + 1, 2α^4 + α^3 + 2α + 1],
[ 2α^3 + 2α^2 + 2α + 2, 2α^4 + α^3 + 2α^2 + α + 1,
α^4 + 2α^2 + 2α + 1, α^4 + 2α^3 + α^2 + 1],
[ α^4 + 2α^3 + α^2 + α + 2, α^3 + α^2 + α + 2,
α^4 + α^3 + 2α^2 + α, α^4 + α^3 + α^2 + 2α]], order=3^5)
In [240]: np.multiply.outer(x, y)
Out[240]:
GF([[α^216, α^158, α^215, α^159],
[α^148, α^90, α^147, α^91],
[α^236, α^178, α^235, α^179],
[ α^32, α^216, α^31, α^217]], order=3^5)
at()
The at methods performs the ufunc in-place at the specified indices.
In [241]: x
Out[241]: GF([184, 25, 157, 31], order=3^5)
In [242]: z = x.copy()
# Negate indices 0 and 1 in-place
In [243]: np.negative.at(x, [0, 1]); x
Out[243]: GF([ 98, 14, 157, 31], order=3^5)
In [244]: z[0:1] *= -1; z
Out[244]: GF([ 98, 25, 157, 31], order=3^5)
In [245]: x
Out[245]:
GF([ α^4 + α^2 + 2α + 2, α^2 + α + 2,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [246]: z = x.copy()
# Negate indices 0 and 1 in-place
In [247]: np.negative.at(x, [0, 1]); x
Out[247]:
GF([ 2α^4 + 2α^2 + α + 1, 2α^2 + 2α + 1,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [248]: z[0:1] *= -1; z
Out[248]:
GF([ 2α^4 + 2α^2 + α + 1, α^2 + α + 2,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [249]: x
Out[249]: GF([α^156, α^88, α^176, α^214], order=3^5)
In [250]: z = x.copy()
# Negate indices 0 and 1 in-place
In [251]: np.negative.at(x, [0, 1]); x
Out[251]: GF([ α^35, α^209, α^176, α^214], order=3^5)
In [252]: z[0:1] *= -1; z
Out[252]: GF([ α^35, α^88, α^176, α^214], order=3^5)
Advanced arithmetic¶
Convolution: np.convolve(x, y)
In [253]: x
Out[253]: GF([ 98, 14, 157, 31], order=3^5)
In [254]: y
Out[254]: GF([179, 9, 139, 27], order=3^5)
In [255]: np.convolve(x, y)
Out[255]: GF([ 79, 80, 5, 79, 167, 166, 123], order=3^5)
In [256]: x
Out[256]:
GF([ α^4 + α^2 + 2α + 2, α^2 + α + 2,
α^4 + 2α^3 + 2α^2 + α + 1, α^3 + α + 1], order=3^5)
In [257]: y
Out[257]:
GF([2α^4 + α^2 + 2α + 2, α^2, α^4 + 2α^3 + α + 1,
α^3], order=3^5)
In [258]: np.convolve(x, y)
Out[258]:
GF([2α^3 + 2α^2 + 2α + 1, 2α^3 + 2α^2 + 2α + 2, α + 2,
2α^3 + 2α^2 + 2α + 1, 2α^4 + α + 2, 2α^4 + α + 1,
α^4 + α^3 + α^2 + 2α], order=3^5)
In [259]: x
Out[259]: GF([ α^35, α^209, α^176, α^214], order=3^5)
In [260]: y
Out[260]: GF([α^60, α^2, α^59, α^3], order=3^5)
In [261]: np.convolve(x, y)
Out[261]: GF([ α^95, α^236, α^5, α^95, α^9, α^45, α^217], order=3^5)
FFT: np.fft.fft(x)
The Discrete Fourier Transform (DFT) of size \(n\) over the finite field \(\mathrm{GF}(p^m)\) exists when there exists a primitive \(n\)-th root of unity. This occurs when \(n\ |\ p^m - 1\).
In [262]: GF = galois.GF(7**5)
In [263]: n = 6
# n divides p^m - 1
In [264]: (GF.order - 1) % n
Out[264]: 0
In [265]: x = GF.Random(n, seed=1); x
Out[265]: GF([ 7952, 12470, 8601, 11055, 12691, 9895], order=7^5)
In [266]: X = np.fft.fft(x); X
Out[266]: GF([ 9387, 10789, 14695, 13079, 14025, 5694], order=7^5)
In [267]: np.fft.ifft(X)
Out[267]: GF([ 7952, 12470, 8601, 11055, 12691, 9895], order=7^5)
In [268]: GF = galois.GF(7**5, display="poly")
In [269]: n = 6
# n divides p^m - 1
In [270]: (GF.order - 1) % n
Out[270]: 0
In [271]: x = GF.Random(n, seed=1); x
Out[271]:
GF([ 3α^4 + 2α^3 + α^2 + 2α, 5α^4 + α^3 + 2α^2 + 3α + 3,
3α^4 + 4α^3 + 3α + 5, 4α^4 + 4α^3 + α^2 + 4α + 2,
5α^4 + 2α^3, 4α^4 + 5α^2 + 6α + 4], order=7^5)
In [272]: X = np.fft.fft(x); X
Out[272]:
GF([ 3α^4 + 6α^3 + 2α^2 + 4α, 4α^4 + 3α^3 + 3α^2 + α + 2,
6α^4 + 5α^2 + 6α + 2, 5α^4 + 3α^3 + 6α + 3,
5α^4 + 5α^3 + 6α^2 + α + 4, 2α^4 + 2α^3 + 4α^2 + α + 3], order=7^5)
In [273]: np.fft.ifft(X)
Out[273]:
GF([ 3α^4 + 2α^3 + α^2 + 2α, 5α^4 + α^3 + 2α^2 + 3α + 3,
3α^4 + 4α^3 + 3α + 5, 4α^4 + 4α^3 + α^2 + 4α + 2,
5α^4 + 2α^3, 4α^4 + 5α^2 + 6α + 4], order=7^5)
In [274]: GF = galois.GF(7**5, display="power")
In [275]: n = 6
# n divides p^m - 1
In [276]: (GF.order - 1) % n
Out[276]: 0
In [277]: x = GF.Random(n, seed=1); x
Out[277]: GF([α^11363, α^2127, α^15189, α^5863, α^1240, α^255], order=7^5)
In [278]: X = np.fft.fft(x); X
Out[278]: GF([ α^7664, α^14905, α^15266, α^13358, α^9822, α^16312], order=7^5)
In [279]: np.fft.ifft(X)
Out[279]: GF([α^11363, α^2127, α^15189, α^5863, α^1240, α^255], order=7^5)
See also ntt() and primitive_root_of_unity.
Inverse FFT: np.fft.ifft(X)
The inverse Discrete Fourier Transform (DFT) of size \(n\) over the finite field \(\mathrm{GF}(p^m)\) exists when there exists a primitive \(n\)-th root of unity. This occurs when \(n\ |\ p^m - 1\).
In [280]: GF = galois.GF(7**5)
In [281]: n = 6
# n divides p^m - 1
In [282]: (GF.order - 1) % n
Out[282]: 0
In [283]: x = GF.Random(n, seed=1); x
Out[283]: GF([ 7952, 12470, 8601, 11055, 12691, 9895], order=7^5)
In [284]: X = np.fft.fft(x); X
Out[284]: GF([ 9387, 10789, 14695, 13079, 14025, 5694], order=7^5)
In [285]: np.fft.ifft(X)
Out[285]: GF([ 7952, 12470, 8601, 11055, 12691, 9895], order=7^5)
In [286]: GF = galois.GF(7**5, display="poly")
In [287]: n = 6
# n divides p^m - 1
In [288]: (GF.order - 1) % n
Out[288]: 0
In [289]: x = GF.Random(n, seed=1); x
Out[289]:
GF([ 3α^4 + 2α^3 + α^2 + 2α, 5α^4 + α^3 + 2α^2 + 3α + 3,
3α^4 + 4α^3 + 3α + 5, 4α^4 + 4α^3 + α^2 + 4α + 2,
5α^4 + 2α^3, 4α^4 + 5α^2 + 6α + 4], order=7^5)
In [290]: X = np.fft.fft(x); X
Out[290]:
GF([ 3α^4 + 6α^3 + 2α^2 + 4α, 4α^4 + 3α^3 + 3α^2 + α + 2,
6α^4 + 5α^2 + 6α + 2, 5α^4 + 3α^3 + 6α + 3,
5α^4 + 5α^3 + 6α^2 + α + 4, 2α^4 + 2α^3 + 4α^2 + α + 3], order=7^5)
In [291]: np.fft.ifft(X)
Out[291]:
GF([ 3α^4 + 2α^3 + α^2 + 2α, 5α^4 + α^3 + 2α^2 + 3α + 3,
3α^4 + 4α^3 + 3α + 5, 4α^4 + 4α^3 + α^2 + 4α + 2,
5α^4 + 2α^3, 4α^4 + 5α^2 + 6α + 4], order=7^5)
In [292]: GF = galois.GF(7**5, display="power")
In [293]: n = 6
# n divides p^m - 1
In [294]: (GF.order - 1) % n
Out[294]: 0
In [295]: x = GF.Random(n, seed=1); x
Out[295]: GF([α^11363, α^2127, α^15189, α^5863, α^1240, α^255], order=7^5)
In [296]: X = np.fft.fft(x); X
Out[296]: GF([ α^7664, α^14905, α^15266, α^13358, α^9822, α^16312], order=7^5)
In [297]: np.fft.ifft(X)
Out[297]: GF([α^11363, α^2127, α^15189, α^5863, α^1240, α^255], order=7^5)
See also ntt() and primitive_root_of_unity.
Linear algebra¶
Linear algebra on FieldArray arrays/matrices is supported through both native NumPy linear algebra functions
in numpy.linalg and additional linear algebra routines not included in NumPy.
Expand any section for more details.
Dot product: np.dot(a, b)
In [298]: GF = galois.GF(31)
In [299]: a = GF([29, 0, 2, 21]); a
Out[299]: GF([29, 0, 2, 21], order=31)
In [300]: b = GF([23, 5, 15, 12]); b
Out[300]: GF([23, 5, 15, 12], order=31)
In [301]: np.dot(a, b)
Out[301]: GF(19, order=31)
Vector dot product: np.vdot(a, b)
In [302]: GF = galois.GF(31)
In [303]: a = GF([29, 0, 2, 21]); a
Out[303]: GF([29, 0, 2, 21], order=31)
In [304]: b = GF([23, 5, 15, 12]); b
Out[304]: GF([23, 5, 15, 12], order=31)
In [305]: np.vdot(a, b)
Out[305]: GF(19, order=31)
Inner product: np.inner(a, b)
In [306]: GF = galois.GF(31)
In [307]: a = GF([29, 0, 2, 21]); a
Out[307]: GF([29, 0, 2, 21], order=31)
In [308]: b = GF([23, 5, 15, 12]); b
Out[308]: GF([23, 5, 15, 12], order=31)
In [309]: np.inner(a, b)
Out[309]: GF(19, order=31)
Outer product: np.outer(a, b)
In [310]: GF = galois.GF(31)
In [311]: a = GF([29, 0, 2, 21]); a
Out[311]: GF([29, 0, 2, 21], order=31)
In [312]: b = GF([23, 5, 15, 12]); b
Out[312]: GF([23, 5, 15, 12], order=31)
In [313]: np.outer(a, b)
Out[313]:
GF([[16, 21, 1, 7],
[ 0, 0, 0, 0],
[15, 10, 30, 24],
[18, 12, 5, 4]], order=31)
Matrix multiplication: A @ B == np.matmul(A, B)
In [314]: GF = galois.GF(31)
In [315]: A = GF([[17, 25, 18, 8], [7, 9, 21, 15], [6, 16, 6, 30]]); A
Out[315]:
GF([[17, 25, 18, 8],
[ 7, 9, 21, 15],
[ 6, 16, 6, 30]], order=31)
In [316]: B = GF([[8, 18], [22, 0], [7, 8], [20, 24]]); B
Out[316]:
GF([[ 8, 18],
[22, 0],
[ 7, 8],
[20, 24]], order=31)
In [317]: A @ B
Out[317]:
GF([[11, 22],
[19, 3],
[19, 8]], order=31)
In [318]: np.matmul(A, B)
Out[318]:
GF([[11, 22],
[19, 3],
[19, 8]], order=31)
Matrix exponentiation: np.linalg.matrix_power(A, 3)
In [319]: GF = galois.GF(31)
In [320]: A = GF([[14, 1, 5], [3, 23, 6], [24, 27, 4]]); A
Out[320]:
GF([[14, 1, 5],
[ 3, 23, 6],
[24, 27, 4]], order=31)
In [321]: np.linalg.matrix_power(A, 3)
Out[321]:
GF([[ 1, 16, 4],
[11, 9, 9],
[ 8, 24, 29]], order=31)
In [322]: A @ A @ A
Out[322]:
GF([[ 1, 16, 4],
[11, 9, 9],
[ 8, 24, 29]], order=31)
Matrix determinant: np.linalg.det(A)
In [323]: GF = galois.GF(31)
In [324]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[324]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [325]: np.linalg.det(A)
Out[325]: GF(0, order=31)
Matrix rank: np.linalg.matrix_rank(A)
In [326]: GF = galois.GF(31)
In [327]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[327]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [328]: np.linalg.matrix_rank(A)
Out[328]: 3
In [329]: A.row_reduce()
Out[329]:
GF([[ 1, 0, 0, 11],
[ 0, 1, 0, 25],
[ 0, 0, 1, 11],
[ 0, 0, 0, 0]], order=31)
Matrix trace: np.trace(A)
In [330]: GF = galois.GF(31)
In [331]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[331]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [332]: np.trace(A)
Out[332]: GF(0, order=31)
In [333]: A[0,0] + A[1,1] + A[2,2] + A[3,3]
Out[333]: GF(0, order=31)
Solve a system of equations: np.linalg.solve(A, b)
In [334]: GF = galois.GF(31)
In [335]: A = GF([[14, 21, 14, 28], [24, 22, 23, 23], [16, 30, 26, 18], [4, 23, 18, 3]]); A
Out[335]:
GF([[14, 21, 14, 28],
[24, 22, 23, 23],
[16, 30, 26, 18],
[ 4, 23, 18, 3]], order=31)
In [336]: b = GF([15, 11, 6, 29]); b
Out[336]: GF([15, 11, 6, 29], order=31)
In [337]: x = np.linalg.solve(A, b)
In [338]: np.array_equal(A @ x, b)
Out[338]: True
Matrix inverse: np.linalg.inv(A)
In [339]: GF = galois.GF(31)
In [340]: A = GF([[14, 21, 14, 28], [24, 22, 23, 23], [16, 30, 26, 18], [4, 23, 18, 3]]); A
Out[340]:
GF([[14, 21, 14, 28],
[24, 22, 23, 23],
[16, 30, 26, 18],
[ 4, 23, 18, 3]], order=31)
In [341]: A_inv = np.linalg.inv(A); A_inv
Out[341]:
GF([[27, 17, 9, 8],
[20, 21, 12, 4],
[30, 10, 23, 22],
[13, 25, 6, 13]], order=31)
In [342]: A @ A_inv
Out[342]:
GF([[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1]], order=31)
Additional linear algebra¶
Below are additional linear algebra routines provided for FieldArray arrays/matrices that are
not included in NumPy.
Row space: A.row_space()
In [343]: GF = galois.GF(31)
In [344]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[344]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [345]: A.row_space()
Out[345]:
GF([[ 1, 0, 0, 11],
[ 0, 1, 0, 25],
[ 0, 0, 1, 11]], order=31)
See row_space() for more details.
Column space: A.column_space()
In [346]: GF = galois.GF(31)
In [347]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[347]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [348]: A.column_space()
Out[348]:
GF([[ 1, 0, 0, 0],
[ 0, 1, 0, 11],
[ 0, 0, 1, 5]], order=31)
See column_space() for more details.
Left null space: A.left_null_space()
In [349]: GF = galois.GF(31)
In [350]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[350]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [351]: A.left_null_space()
Out[351]: GF([[ 0, 1, 23, 14]], order=31)
See left_null_space() for more details.
Null space: A.null_space()
In [352]: GF = galois.GF(31)
In [353]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[353]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [354]: A.null_space()
Out[354]: GF([[ 1, 22, 1, 14]], order=31)
See null_space() for more details.
Gaussian elimination: A.row_reduce()
In [355]: GF = galois.GF(31)
In [356]: A = GF([[23, 11, 3, 3], [13, 6, 16, 4], [12, 10, 5, 3], [17, 23, 15, 28]]); A
Out[356]:
GF([[23, 11, 3, 3],
[13, 6, 16, 4],
[12, 10, 5, 3],
[17, 23, 15, 28]], order=31)
In [357]: A.row_reduce()
Out[357]:
GF([[ 1, 0, 0, 11],
[ 0, 1, 0, 25],
[ 0, 0, 1, 11],
[ 0, 0, 0, 0]], order=31)
See row_reduce() for more details.
LU decomposition: A.lu_decompose()
In [358]: GF = galois.GF(31)
In [359]: A = GF([[4, 1, 24], [7, 6, 1], [11, 20, 2]]); A
Out[359]:
GF([[ 4, 1, 24],
[ 7, 6, 1],
[11, 20, 2]], order=31)
In [360]: L, U = A.lu_decompose()
In [361]: L
Out[361]:
GF([[ 1, 0, 0],
[25, 1, 0],
[26, 15, 1]], order=31)
In [362]: U
Out[362]:
GF([[ 4, 1, 24],
[ 0, 12, 21],
[ 0, 0, 24]], order=31)
In [363]: np.array_equal(L @ U, A)
Out[363]: True
See lu_decompose() for more details.
PLU decomposition: A.plu_decompose()
In [364]: GF = galois.GF(31)
In [365]: A = GF([[15, 4, 11], [7, 6, 1], [11, 20, 2]]); A
Out[365]:
GF([[15, 4, 11],
[ 7, 6, 1],
[11, 20, 2]], order=31)
In [366]: P, L, U = A.plu_decompose()
In [367]: P
Out[367]:
GF([[1, 0, 0],
[0, 0, 1],
[0, 1, 0]], order=31)
In [368]: L
Out[368]:
GF([[ 1, 0, 0],
[ 9, 1, 0],
[17, 0, 1]], order=31)
In [369]: U
Out[369]:
GF([[15, 4, 11],
[ 0, 15, 27],
[ 0, 0, 0]], order=31)
In [370]: np.array_equal(P @ L @ U, A)
Out[370]: True
See plu_decompose() for more details.
Last update:
Nov 04, 2022