Forget that old maths … Modulo 2 is coming to town
Forget that old maths … Modulo 2 is coming to town
There’s a new show in town and it’s part of the next generation of cybersecurity… Modulo 2 or GF(2) — Galois field of two elements. It is used in many areas including with checksums and ciphers, and now is being applied into quantum robust cryptography. The multiplication function involves multiplying the binary values and ignoring the remainder. They are easy to implement and fast in their operation, especially in cryptography and checksum functions. It basically involves some bit shifts and an EX-OR function, which makes it fast in computing the multiplication.
For example 111 x 101 gives:
111
x101
------
111
000
111
-----
11011
=====
We can represent 101 as x²+1 and 110 as x²+x. Next we multiple them together to give:
(x²+1)×(x²+x)
and which is:
(x⁴+x³+x²+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⁶+2⁴+2²)×(2³+2²+2⁰))(mod 2)
=(2⁹+2⁸+2⁶+2⁷+2⁶+2⁴+2⁵+2⁴+2²)(mod 2)
=(2⁹+2⁸+2⁷+2⁵+2²)(mod 2)
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
Try an example:
- 111 multiplied by 101 should give 11011. Calc [Check]
- 1100101 multiplied by 1101 should give 1011011001. Calc [Check]
- 1010101 multiplied by 1010 should give 1000000010. Calc [Check]
- 10101010 multiplied by 10101 should give 100010100010. Calc [Check]
- 84 multiplied by 13 should give 1110100100. Calc
And with divide, we can take an example of 10010 ÷ 11 gives:
1110
-------
11 | 10010
11
------
1010
11
-----
110
11
---
00
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 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 "\nWorking out:\n"
print "\nDivide operation:\n"
Try an example:
- 10010 divided by 11 should give 1110 rem 0 Calc [Check]
- 10011 divided by 11 should give 1110 rem 1 Calc [Check]
- 10010 divided by 111 should give 110 rem 0 Calc [Check]
- 10010 divided by 110 should give 111 rem 0 Calc [Check]
- 10010 divided by 101 should give 101 rem 11 Calc [Check]
- 10010 divided by 1010 should give 101 rem 11 Calc [Check]
Now go and do this challenge: