GF(2) - Galois field of two elements - is used in many areas including with Checksums and Ciphers. The multiplication function involves multiplying the binary values and ignoring the remainder. They are easy to implement and fast in their operation, especially in crypto and checksum functions. It basically involves some bit shifts and an EX-OR function, which makes it fast in computing the multiplication.
Binary multiplication (modulo 2) |
Example
For example 111 x 101 gives:
111 x101 ------ 111 000 111 ----- 11011 =====
We can represent 101 as \(x^2 + 1\) and 110 as \(x^2 + x\)
Next we multiple them together to give:
\((x^2 + 1) \times (x^2 + x)\)
\((x^4 + x^3 + x^2 + x)\)
which can be represented as 11110
For example if we use the example on Page 6 [here] of 84 x 13 (and where ** represents "to the power of")
84x13 = ((2**6+ 2**4+ 2**2)x(2**3+ 2**2+ 2**0)) (mod 2) = (2**9+ 2**8+ 2**7+2**1+ 2**6+ 2**5+ 2**1 + 2**4+ 2**2) (mod 2) = (2**9+ 2**8+ 2**7+ 2**5+ 2**2) (mod 2) which is 1110100100 [Calc]
The working out in its proper form is:
84x13 = \(((2^6+ 2^4+ 2^2)\times(2^3+ 2^2+ 2^0)) (\mod 2)\)
\(= (2^9+ 2^8+ 2^6+2^7+ 2^6+ 2^4+ 2^5 + 2^4+ 2^2) (mod 2)\)
\(= (2^9+ 2^8+ 2^7+ 2^5+ 2^2) (mod 2)\)
Coding
I have used a simple bit-shift operation and X-OR to implement the method:
import struct import sys val1=1 val2=1 if (len(sys.argv)>1): val1=str(sys.argv[1]) if (len(sys.argv)>2): val2=str(sys.argv[2]) def reverse(text): lst = [] count = 1 for i in range(0,len(text)): lst.append(text[len(text)-count]) count += 1 lst = ''.join(lst) return lst 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 multiply(a,b): bit1 = int(a,2) bit2 = int(b,2) g = [] nobits = len(b) print a.rjust(len(a)+len(b)-1) str = "x"+b; print str.rjust(len(a)+len(b)-1) print "-" * (len(a)+len(b)-1) b=reverse(b) for i in range (0,nobits): if (b[i]=='0'): g.append(0) else: g.append(int((bit1<<i))) print bin(g[i])[2:].rjust(len(a)+len(b)-1) res=int(g[0]) for i in range (1,nobits): res = int(res) ^ int(g[i]) print "-" * (len(a)+len(b)-1) print bin(res)[2:].zfill(len(a)+len(b)-1) print "=" * (len(a)+len(b)-1) return res print "Binary form:\t",val1,"x",val2 print "Decimal form:\t",int(val1,2),"x",int(val2,2) print "" showpoly(val1) showpoly(val2) print "\nWorking out:\n" res=multiply(val1,val2) print "\nResult: ",res
Some background theory is here, and if you want to check, try here