I want to perform addition and multiplication in F_{2^8}
I currently have this code which seems to work for add but doesn’t work for multiply; the issue seems to be that when I modulo by 100011011 (which represents x^8 + x^4 + x^3 + x + 1), it doesn’t seem to do it. Another idea would be to use numpy.polynomial but it isn’t as intuitive.
def toBinary(self, n): return ''.join(str(1 & int(n) >> i) for i in range(8)[::-1]) def add(self, x, y): """ "10111001" + "10010100" = "00101101" """ if len(x)<8: self.add('0'+x,y) elif len(y)<8: self.add(x,'0'+y) try: a = int(x,2); b = int(y,2) z = int(x)+int(y) s = '' for i in str(z): if int(i)%2 == 0: s+='0' else: s+='1' except: return '00000000' return s def multiply(self, x, y): """ "10111001" * "10010100" = "10110010" """ if len(x)<8: self.multiply('0'+x,y) elif len(y)<8: self.multiply(x,'0'+y) result = '00000000' result = '00000000' while y!= '00000000' : print(f'x:{x},y:{y},result:{result}') if int(y[-1]) == 1 : result = self.add(result ,x) y = self.add(y, '00000001') x = self.add(self.toBinary(int(x,2)<<1),'100011011') y = self.toBinary(int(y,2)>>1) #b = self.multiply(b,inverse('00000010')) return result
Advertisement
Answer
Python example for add (same as subtract), multiply, divide, and inverse. Assumes the input parameters are 8 bit values, and there is no check for divide by 0.
def add(x, y): # add is xor return x^y def sub(x, y): # sub is xor return x^y def mpy(x, y): # mpy two 8 bit values p = 0b100011011 # mpy modulo x^8+x^4+x^3+x+1 m = 0 # m will be product for i in range(8): m = m << 1 if m & 0b100000000: m = m ^ p if y & 0b010000000: m = m ^ x y = y << 1 return m def div(x, y): # divide using inverse return mpy(x, inv(y)) # (no check for y = 0) def inv(x): # x^254 = 1/x p=mpy(x,x) # p = x^2 x=mpy(p,p) # x = x^4 p=mpy(p,x) # p = x^(2+4) x=mpy(x,x) # x = x^8 p=mpy(p,x) # p = x^(2+4+8) x=mpy(x,x) # x = x^16 p=mpy(p,x) # p = x^(2+4+8+16) x=mpy(x,x) # x = x^32 p=mpy(p,x) # p = x^(2+4+8+16+32) x=mpy(x,x) # x = x^64 p=mpy(p,x) # p = x^(2+4+8+16+32+64) x=mpy(x,x) # x = x^128 p=mpy(p,x) # p = x^(2+4+8+16+32+64+128) return p print hex(add(0b01010101, 0b10101010)) # returns 0xff print hex(mpy(0b01010101, 0b10101010)) # returns 0x59 print hex(div(0b01011001, 0b10101010)) # returns 0x55
For GF(2^n), both add and subtract are XOR. This means multiplies are carryless and divides are borrowless. The X86 has a carryless multiply for XMM registers, PCLMULQDQ. Divide by a constant can be done with carryless multiply by 2^64 / constant and using the upper 64 bits of the product. The inverse constant is generated using a loop for borrowless divide.
The reason for this is GF(2^n) elements are polynomials with 1 bit coefficients, (the coefficients are elements of GF(2)).
For GF(2^8), it would be simpler to generate exponentiate and log tables. Example C code:
#define POLY (0x11b) /* all non-zero elements are powers of 3 for POLY == 0x11b */ typedef unsigned char BYTE; /* ... */ static BYTE exp2[512]; static BYTE log2[256]; /* ... */ static void Tbli() { int i; int b; b = 0x01; /* init exp2 table */ for(i = 0; i < 512; i++){ exp2[i] = (BYTE)b; b = (b << 1) ^ b; /* powers of 3 */ if(b & 0x100) b ^= POLY; } log2[0] = 0xff; /* init log2 table */ for(i = 0; i < 255; i++) log2[exp2[i]] = (BYTE)i; } /* ... */ static BYTE GFMpy(BYTE m0, BYTE m1) /* multiply */ { if(0 == m0 || 0 == m1) return(0); return(exp2[log2[m0] + log2[m1]]); } /* ... */ static BYTE GFDiv(BYTE m0, BYTE m1) /* divide */ { if(0 == m0) return(0); return(exp2[log2[m0] + 255 - log2[m1]]); }