1 # a mish-mash of various GF(2^m) functions from different sources
2 # on the internet which help demonstrate arithmetic in GF(2^m)
3 # these are intended to be implemented in hardware, so the basic
4 # primitives need to be *real* basic: XOR, shift, AND, OR, etc.
6 # development discussion and links at:
7 # https://bugs.libre-soc.org/show_bug.cgi?id=782
9 from functools
import reduce
11 # https://stackoverflow.com/questions/45442396/
23 # useful constants used throughout this module
24 degree
= mask1
= mask2
= polyred
= None
28 """reconstruct the polynomial coefficients of g(x)
30 return polyred | mask1
33 # original at https://jhafranco.com/tag/binary-finite-field/
35 """Define parameters of binary finite field GF(2^m)/g(x)
36 - irPoly: coefficients of irreducible polynomial g(x)
38 # degree: extension degree of binary field
39 global degree
, mask1
, mask2
, polyred
40 degree
= gf_degree(irPoly
)
43 """Convert an integer into a polynomial"""
44 return [(sInt
>> i
) & 1
45 for i
in reversed(range(sInt
.bit_length()))]
47 mask1
= mask2
= 1 << degree
49 polyred
= reduce(lambda x
, y
: (x
<< 1) + y
, i2P(irPoly
)[1:])
52 # original at https://jhafranco.com/tag/binary-finite-field/
54 """Multiply two polynomials in GF(2^m)/g(x)"""
66 # https://github.com/jpahullo/python-multiprocessing/
69 fDegree
, vDegree
= gf_degree(f
), gf_degree(v
)
75 res ^
= (1 << (i
- vDegree
))
76 rem ^
= (v
<< (i
- vDegree
))
82 # https://en.m.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
84 """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
85 x0
, x1
, y0
, y1
= 0, 1, 1, 0
87 (q
, a
), b
= divmodGF2(b
, a
), a
88 y0
, y1
= y1
, y0 ^
multGF2(q
, y1
)
89 x0
, x1
= x1
, x0 ^
multGF2(q
, x1
)
93 # https://bugs.libre-soc.org/show_bug.cgi?id=782#c33
94 # https://ftp.libre-soc.org/ARITH18_Kobayashi.pdf
97 s
= getGF2() # get the full polynomial (including the MSB)
103 for i
in range(1, 2*degree
+1):
104 # could use count-trailing-1s here to skip ahead
105 if r
& mask1
: # test MSB of r
106 if s
& mask1
: # test MSB of s
109 s
<<= 1 # shift left 1
111 r
, s
= s
, r
# swap r,s
112 u
, v
= v
<< 1, u
# shift v and swap
115 u
>>= 1 # right shift left
118 r
<<= 1 # shift left 1
119 u
<<= 1 # shift left 1
125 if __name__
== "__main__":
127 # Define binary field GF(2^3)/x^3 + x + 1
128 setGF2(0b1011) # degree 3
130 # Evaluate the product (x^2 + x + 1)(x^2 + 1)
131 x
= multGF2(0b111, 0b101)
134 # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
136 # note that polyred has the MSB stripped!
137 setGF2(0b100011011) # degree 8
139 # Evaluate the product (x^7 + x^2)(x^7 + x + 1)
143 print("%02x * %02x = %02x" % (x
, y
, z
))
145 # divide z by y into result/remainder
146 res
, rem
= divmodGF2(z
, y
)
147 print("%02x / %02x = (%02x, %02x)" % (z
, y
, res
, rem
))
149 # reconstruct x by multiplying divided result by y and adding the remainder
151 print("%02x == %02x" % (z
, x1 ^ rem
)) # XOR is "add" in GF2
153 # demo output of xgcd
156 # for i in range(1, 256):
157 # print (i, gf_invert(i))
159 # show how inversion-and-multiply works. answer here should be "x":
160 # z = x * y, therefore z * (1/y) should equal "x"
163 print(hex(polyred
), hex(y1
), hex(x
), "==", hex(z1
))