GF(2) - Galois field of two elements - is used in many areas including with Checksums and Ciphers. It basically involves some bit shifts and an EX-OR function, which makes it fast in computing the multiplication.
Binary division (modulo 2) |
Example
For example 10010 รท 11 gives:
1110 ------- 11 | 10010 11 ------ 1010 11 ----- 110 11 --- 00
Coding
I have used a simple bit-shift operation and X-OR to implement the method:
import struct import sys val1='1010' val2='110' if (len(sys.argv)>1): val1=str(sys.argv[1]) if (len(sys.argv)>2): val2=str(sys.argv[2]) def showpoly(a): str1 = "" nobits = len(a) for x in range (0,nobits-2): if (a[x] == '1'): if (len(str1)==0): str1 +="x**"+str(nobits-x-1) else: str1 +="+x**"+str(nobits-x-1) if (a[nobits-2] == '1'): if (len(str1)==0): str1 +="x" else: str1 +="+x" if (a[nobits-1] == '1'): str1 +="+1" print(str1) def toList(x): l = [] for i in range (0,len(x)): l.append(int(x[i])) return (l) def toString(x): str1 ="" for i in range (0,len(x)): str1+=str(x[i]) return (str1) def divide(val1,val2): a = toList(val1) b = toList(val2) working="" res="" while len(b) <= len(a) and a: if (a[0] == 1): del a[0] for j in range(len(b)-1): a[j] ^= b[j+1] if (len(a)>0): working +=toString(a) res+= "1" else: del a[0] working +=toString(a) res+="0" print("Result is\t",res) print("Remainder is\t",toString(a)) return print("Binary form:\t",val1," divided by ",val2) print("Decimal form:\t",int(val1,2)," divided by ",int(val2,2)) print("") showpoly(val1) showpoly(val2) print("\nDivide operation:\n") divide(val1,val2)
Some background theory is here, and if you want to check, try here