Skip to content

Instantly share code, notes, and snippets.

@zrneely

zrneely/ffield_py3.patch

Created February 12, 2016 21:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zrneely/8321ebdf61c36cbab128 to your computer and use it in GitHub Desktop.
Save zrneely/8321ebdf61c36cbab128 to your computer and use it in GitHub Desktop.
Download ZIP
Patches an existing ffield.py to create a Python 3 version, ffield3.py
Raw
ffield_py3.patch
--- ffield.py 2016-02-12 16:14:40.654378453 -0500
+++ ffield3.py 2016-02-12 16:16:21.017352960 -0500
@@ -23,10 +23,10 @@
testing_doc Describes some tests to make sure the code is working
as well as some of the built in testing routines.
-
+
"""
-import string, random, os, os.path, cPickle
+import string, random, os, os.path, pickle, functools
# The following list of primitive polynomials are the Conway Polynomials
@@ -81,14 +81,11 @@
for n in gPrimitivePolysCondensed.keys():
gPrimitivePolys[n] = [0]*(n+1)
- if (n < 16):
- unity = 1
- else:
- unity = long(1)
+ unity = 1
for index in gPrimitivePolysCondensed[n]:
gPrimitivePolys[n][index] = unity
gPrimitivePolys[n].reverse()
-
+
class FField:
"""
@@ -112,15 +109,15 @@
TestFullDivision
TestInverse
- Most of these methods take integers or longs representing field
- elements as arguments and return integers representing the desired
+ Most of these methods take integers representing field elements
+ as arguments and return integers representing the desired
field elements as output. See ffield.fields_doc for an explanation
of the integer representation of field elements.
Example of how to use the FField class:
-
+
>>> import ffield
->>> F = ffield.FField(5) # create the field GF(2^5)
+>>> F = ffield.FField(5) # create the field GF(2^5)
>>> a = 7 # field elements are denoted as integers from 0 to 2^5-1
>>> b = 15
>>> F.ShowPolynomial(a) # show the polynomial representation of a
@@ -142,7 +139,7 @@
See documentation on the appropriate method for further details.
"""
-
+
def __init__(self,n,gen=0,useLUT=-1):
"""
This method constructs the field GF(2^p). It takes one
@@ -162,8 +159,8 @@
Note that you can look at the generator for the field object
F by looking at F.generator.
"""
-
- self.n = n
+
+ self.n = n
if (gen):
self.generator = gen
else:
@@ -172,31 +169,25 @@
if (useLUT == 1 or (useLUT == -1 and self.n < 10)): # use lookup table
self.unity = 1
- self.Inverse = self.DoInverseForSmallField
+ self.Inverse = self.DoInverse
self.PrepareLUT()
self.Multiply = self.LUTMultiply
self.Divide = self.LUTDivide
- self.Inverse = lambda x: self.LUTDivide(1,x)
- elif (self.n < 15):
+ self.Inverse = lambda x: self.LUTDivide(1,x)
+ else:
self.unity = 1
- self.Inverse = self.DoInverseForSmallField
- self.Multiply = self.DoMultiply
- self.Divide = self.DoDivide
- else: # Need to use longs for larger fields
- self.unity = long(1)
- self.Inverse = self.DoInverseForBigField
- self.Multiply = lambda a,b: self.DoMultiply(long(a),long(b))
- self.Divide = lambda a,b: self.DoDivide(long(a),long(b))
+ self.Inverse = self.DoInverse
+ self.Multiply = lambda a,b: self.DoMultiply(a,b)
+ self.Divide = lambda a,b: self.DoDivide(a,b)
def PrepareLUT(self):
fieldSize = 1 << self.n
- lutName = 'ffield.lut.' + `self.n`
+ lutName = 'ffield.lut.' + repr(self.n)
if (os.path.exists(lutName)):
- fd = open(lutName,'r')
- self.lut = cPickle.load(fd)
- fd.close()
+ with open(lutName,'rb') as fd:
+ self.lut = pickle.load(fd)
else:
self.lut = LUT()
self.lut.mulLUT = range(fieldSize)
@@ -204,26 +195,25 @@
self.lut.mulLUT[0] = [0]*fieldSize
self.lut.divLUT[0] = ['NaN']*fieldSize
for i in range(1,fieldSize):
- self.lut.mulLUT[i] = map(lambda x: self.DoMultiply(i,x),
- range(fieldSize))
- self.lut.divLUT[i] = map(lambda x: self.DoDivide(i,x),
- range(fieldSize))
- fd = open(lutName,'w')
- cPickle.dump(self.lut,fd)
- fd.close()
+ self.lut.mulLUT[i] = list(map(lambda x: self.DoMultiply(i,x),
+ range(fieldSize)))
+ self.lut.divLUT[i] = list(map(lambda x: self.DoDivide(i,x),
+ range(fieldSize)))
+ with open(lutName,'wb') as fd:
+ pickle.dump(self.lut,fd)
+
-
def LUTMultiply(self,i,j):
return self.lut.mulLUT[i][j]
def LUTDivide(self,i,j):
return self.lut.divLUT[i][j]
-
+
def Add(self,x,y):
"""
Adds two field elements and returns the result.
"""
-
+
return x ^ y
def Subtract(self,x,y):
@@ -245,8 +235,8 @@
m = self.MultiplyWithoutReducing(f,v)
return self.FullDivision(m,self.generator,
self.FindDegree(m),self.n)[1]
-
- def DoInverseForSmallField(self,f):
+
+ def DoInverse(self,f):
"""
Computes the multiplicative inverse of its argument and
returns the result.
@@ -254,14 +244,6 @@
return self.ExtendedEuclid(1,f,self.generator,
self.FindDegree(f),self.n)[1]
- def DoInverseForBigField(self,f):
- """
- Computes the multiplicative inverse of its argument and
- returns the result.
- """
- return self.ExtendedEuclid(self.unity,long(f),self.generator,
- self.FindDegree(long(f)),self.n)[1]
-
def DoDivide(self,f,v):
"""
Divide(f,v) returns f * v^-1.
@@ -291,16 +273,13 @@
Multiplies two field elements and does not take the result
modulo self.generator. You probably should not use this
unless you know what you are doing; look at Multiply instead.
-
- NOTE: If you are using fields larger than GF(2^15), you should
- make sure that f and v are longs not integers.
"""
-
+
result = 0
mask = self.unity
i = 0
while (i <= self.n):
- if (mask & v):
+ if (mask & v):
result = result ^ f
f = f << 1
mask = mask << 1
@@ -329,7 +308,7 @@
f and v represented as a polynomials.
This method returns the field elements a and b such that
- f(x) = a(x) * v(x) + b(x).
+ f(x) = a(x) * v(x) + b(x).
That is, a is the divisor and b is the remainder, or in
other words a is like floor(f/v) and b is like f modulo v.
@@ -361,7 +340,7 @@
result.append(1)
else:
result.append(0)
-
+
return result
def ShowPolynomial(self,f):
@@ -374,13 +353,13 @@
if (f == 0):
return '0'
-
+
for i in range(fDegree,0,-1):
if ((1 << i) & f):
- result = result + (' x^' + `i`)
+ result = result + (' x^' + repr(i))
if (1 & f):
- result = result + ' ' + `1`
- return string.replace(string.strip(result),' ',' + ')
+ result = result + ' ' + repr(1)
+ return result.strip().replace(' ',' + ')
def GetRandomElement(self,nonZero=0,maxDegree=None):
"""
@@ -398,14 +377,14 @@
if (maxDegree < 31):
return random.randint(nonZero != 0,(1<<maxDegree)-1)
else:
- result = 0L
+ result = 0
for i in range(0,maxDegree):
- result = result ^ (random.randint(0,1) << long(i))
+ result = result ^ (random.randint(0,1) << i)
if (nonZero and result == 0):
return self.GetRandomElement(1)
else:
return result
-
+
def ConvertListToElement(self,l):
@@ -419,9 +398,9 @@
result modulo the generator to get a proper element in the
field.
"""
-
+
temp = map(lambda a, b: a << b, l, range(len(l)-1,-1,-1))
- return reduce(lambda a, b: a | b, temp)
+ return functools.reduce(lambda a, b: a | b, temp)
def TestFullDivision(self):
"""
@@ -439,9 +418,9 @@
(c,d) = self.FullDivision(a,b,aDegree,bDegree)
recon = self.Add(d, self.Multiply(c,b))
assert (recon == a), ('TestFullDivision failed: a='
- + `a` + ', b=' + `b` + ', c='
- + `c` + ', d=' + `d` + ', recon=', recon)
-
+ + repr(a) + ', b=' + repr(b) + ', c='
+ + repr(c) + ', d=' + repr(d) + ', recon=', recon)
+
def TestInverse(self):
"""
This function tests the Inverse function by generating
@@ -452,9 +431,9 @@
a = self.GetRandomElement(nonZero=1)
aInv = self.Inverse(a)
prod = self.Multiply(a,aInv)
- assert 1 == prod, ('TestInverse failed:' + 'a=' + `a` + ', aInv='
- + `aInv` + ', prod=' + `prod`,
- 'gen=' + `self.generator`)
+ assert 1 == prod, ('TestInverse failed:' + 'a=' + repr(a) + ', aInv='
+ + repr(aInv) + ', prod=' + repr(prod),
+ 'gen=' + repr(self.generator))
class LUT:
"""
@@ -469,13 +448,13 @@
+,-,*,%,//,/ operators to be the appropriate field operation.
Note that before creating FElement objects you must first
create an FField object. For example,
-
+
>>> import ffield
->>> F = FField(5)
->>> e1 = FElement(F,7)
+>>> F = ffield.FField(5)
+>>> e1 = ffield.FElement(F,7)
>>> e1
x^2 + x^1 + 1
->>> e2 = FElement(F,19)
+>>> e2 = ffield.FElement(F,19)
>>> e2
x^4 + x^1 + 1
>>> e3 = e1 + e2
@@ -486,9 +465,9 @@
x^4 + x^3
>>> e4 * e2 == (e3)
1
-
+
"""
-
+
def __init__(self,field,e):
"""
The constructor takes two arguments, field, and e where
@@ -499,7 +478,7 @@
"""
self.f = e
self.field = field
-
+
def __add__(self,other):
assert self.field == other.field
return FElement(self.field,self.field.Add(self.f,other.f))
@@ -522,7 +501,7 @@
self.field.FindDegree(self.f),
self.field.FindDegree(o.f))[0])
- def __div__(self,other):
+ def __truediv__(self,other):
assert self.field == other.field
return FElement(self.field,self.field.Divide(self.f,other.f))
@@ -535,7 +514,7 @@
def __eq__(self,other):
assert self.field == other.field
return self.f == other.f
-
+
def FullTest(testsPerField=10,sizeList=None):
"""
This function runs TestInverse and TestFullDivision for testsPerField
@@ -544,7 +523,7 @@
GF(2^7). If sizeList == None (which is the default), then every
field is tested.
"""
-
+
if (None == sizeList):
sizeList = gPrimitivePolys.keys()
for i in sizeList:
@@ -601,7 +580,7 @@
as telling us that we can replace every occurence of
x^7 with x + 1. Thus f(x) becomes x * x^7 + x^3 + x which
becomes x * (x + 1) + x^3 + x = x^3 + x^2 . Essentially, taking
-polynomials mod x^7 by replacing all x^7 terms with x + 1 will
+polynomials mod x^7 by replacing all x^7 terms with x + 1 will
force down the degree of f(x) until it is below 7 (the leading power
of g(x). See a book on abstract algebra for more details.
"""
@@ -660,9 +639,8 @@
GF(2^p) with p > 31 you have to write lots of ugly bit field
code in most languages. Since Python has built in support for
arbitrary precision integers, you can make this code work for
- arbitrary field sizes provided you operate on longs instead of
- ints. That is if you give as input numbers like
- 0L, 1L, 1L << 55, etc., most of the code should work.
+ arbitrary field sizes. That is if you give as input numbers like
+ 0, 1, 1 << 55, etc., most of the code should work.
--------------------------------------------------------------------
BASIC DESIGN
@@ -672,7 +650,7 @@
using integers and design the class methods to work properly on this
representation. Using integers is efficient since integers are easy
to store and manipulate and allows us to handle arbitrary field sizes
-without changing the code if we instead switch to using longs.
+without changing the code.
Specifically, an integer represents a bit string
@@ -692,7 +670,7 @@
such operations to make most of the computations efficient.
"""
-
+
license_doc = """
This code was originally written by Emin Martinian (emin@allegro.mit.edu).
@@ -731,7 +709,7 @@
testing_doc = """
The FField class has a number of built in testing functions such as
TestFullDivision, TestInverse. The simplest thing to
-do is to call the FullTest method.
+do is to call the FullTest method.
>>> import ffield
>>> ffield.FullTest(sizeList=None,testsPerField=100)
@@ -760,7 +738,7 @@
return doctest.testmod(ffield)
if __name__ == "__main__":
- print 'Starting automated tests (this may take a while)'
+ print('Starting automated tests (this may take a while)')
_test()
- print 'Tests passed.'
+ print('Tests passed.')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment