""" Small Finite Field class (implemented with lookup tables) This can be found here: http://www.hpcf.upr.edu/~humberto/software/fields/index.html Some modifications made to document code a bit and clean up a few items. Also added a bunch of test cases and made the code a bit more modern python. Bryan Mills Copyright (C) 2003 Humberto Ortiz-Zuazaga humberto@hpcf.upr.edu W4-15 Los Hucares San Juan PR 00926-6807 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. These use bitstrings to encode fields of the form $2^k$ """ class Field: def __init__(self, bitstring): """Uses bitstring as the generating polynomial to construct a finite field bitstring - is a string that represents a the primitive polynomial used to generate the field Example: Field('1011') - creates a field of GF(7) Field('100011101') - create a field of GF(257) Field('10000100101111') - create field of GF(8192) * Note these are just some of the possible primitive polynomials for those fields. In most cases the user will actually want the minimum primitive polynomial """ self.bitstring = bitstring self.bits = len(bitstring) - 1 self.topbit = self.bits - 1 self.groupsize = (2**self.bits) - 1 self.generator = self.stringtobits(bitstring[1:]) a = 1 self.A = [0] * (self.groupsize) self.A[0] = a self.B = [0] * (self.groupsize+1) self.B[0] = 0 self.B[1] = 0 b = a for i in xrange(1,self.groupsize): b = self.shift(b) if self.isset(b,self.bits): b = self.unset(b, self.bits) b = self.plus(b, self.generator) self.A[i] = b if self.same(b,1): raise "polynomial %s not primitive terminated at a^%d"% (bitstring, i) self.B[self.A[i]] = i def stringtobits(self, str): "Read a string of '0', '1' characters, convert to a binary number, return an arbitrary precision integer with the same bit pattern" result = 0L for c in str: if c == '1': result += 1 elif c != '0': raise "Invalid bit string " + str result *= 2 return result/2 def shift(self, a): """ Bit Shift the number by 1 """ return (a << 1) def plus(self, a,b): """ Add a to b under the finite field, an XOR operation """ return (a ^ b) def same(self, a,b): """ Returns true if the two numbers are the same """ return (a == b) def isset(self, a, pos): """ Returns true if the bit in the position pos is set to 1 """ return (a & (1L << pos)) def unset(self, a, pos): """ Unset the bit in the position pos """ return (a ^ (1L << pos)) def prod(self, a, b): if a == 0 or b == 0: return 0 pwr = self.discretelog(a) + self.discretelog(b) return self.alphatothe(pwr % self.groupsize) def inv(self, a): if a == 0: return 0 if a == 1: return 1 # print a, " -- ", self.discretelog(a) pwr = self.groupsize - (self.discretelog(a)) return self.alphatothe(pwr) def bitstostring(self, a): str = "" for i in range(self.bits): if self.isset(a, self.topbit - i): str = str + "1" else: str = str + '0' return str def pretty(self, a): if a == 0: return "0" return "a^" + str(self.discretelog(a)) def elements(self): "Return all the elements of the field as a list" return [0] + self.A def multelem(self): "Return the elements of the multiplicative group as a list" return self.A def alphatothe(self, i): return self.A[i] def discretelog(self, a): try: return self.B[a] except IndexError: raise IndexError("The value %d is out of the range of this finite field %s" % (a,self.bitstring)) def pow(self, a,i): "Raise element a to the ith power" if a == 0: retval = 0 elif i == 0: retval = 1 else: p = 1 retval = a while 2*p <= i: p = 2*p retval = self.prod(retval,retval) while p < i: p = p + 1 retval = self.prod(retval,a) return retval import unittest class TestFiniteFieldFunctions(unittest.TestCase): def setUp(self): pass def testGF7(self): """ Checks all values in GF(7) = GF(2^3) """ F = Field("1011") gf7_table_mul = [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7], [0, 2, 4, 6, 3, 1, 7, 5], [0, 3, 6, 5, 7, 4, 1, 2], [0, 4, 3, 7, 6, 2, 5, 1], [0, 5, 1, 4, 2, 7, 3, 6], [0, 6, 7, 1, 5, 3, 2, 4], [0, 7, 5, 2, 1, 6, 4, 3],] gf7_table_add = [ [0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 3, 2, 5, 4, 7, 6], [2, 3, 0, 1, 6, 7, 4, 5], [3, 2, 1, 0, 7, 6, 5, 4], [4, 5, 6, 7, 0, 1, 2, 3], [5, 4, 7, 6, 1, 0, 3, 2], [6, 7, 4, 5, 2, 3, 0, 1], [7, 6, 5, 4, 3, 2, 1, 0],] row_num = 0 for row_num in range(0,7): for col_num in range(0,7): # test multiplication v = F.prod(row_num, col_num) expected = gf7_table_mul[row_num][col_num] self.assertEqual(v, expected, "%d * %d doesn't equal %d" % \ (row_num,col_num,expected)) # test addition v = F.plus(row_num, col_num) expected = gf7_table_add[row_num][col_num] self.assertEqual(v, expected, "%d * %d doesn't equal %d" % \ (row_num,col_num,expected)) col_num += 1 row_num += 1 def testSpotCheckProdGF8192(self): """ Spot checks some multiplication values in 2^13 = 8192 """ F = Field("10000000011011") expected = [( 231, 123, 3418), (4321, 4232, 7491), ( 948, 18, 7219), ( 1, 18, 18), (8190, 18, 158)] for vals in expected: v = F.prod(vals[0], vals[1]) self.assertEqual(v, vals[2], "%d * %d doesn't equal %d" % vals) if __name__ == '__main__': unittest.main() #import string # Testing, make a field #F = Field("10000100101111") # Now do something useful # evaluate this poly: # 4653 3 1908 2 3498 5101 # f(x) = a x + a x + a x + a #print "f(x) = a^4653 x^3 + a^1908 x^2 + a^3498 x + a^5101" # #def f(x): # a3 = F.alphatothe(4653) # x3 = F.pow(x,3) # a2 = F.alphatothe(1908) # x2 = F.pow(x,2) # a1 = F.alphatothe(3498) # a0 = F.alphatothe(5101) # retval = F.prod(a3,x3) # retval = F.plus(retval,F.prod(a2,x2)) # retval = F.plus(retval,F.prod(a1,x)) # retval = F.plus(retval,a0) # return retval # ## at these points ## S = {0*a, a^5101, a^6355, a^2550, a^3804} # #S = [0, F.alphatothe(5101), F.alphatothe(6355), # F.alphatothe(2550), F.alphatothe(3804)] # #print "x =", map(F.pretty,S) # #values = map(f,S) #print "f(x) =", map(F.pretty,values) # #p = 7 #F = Field("1011") #for i in range(0,p+1): # d = [] # for j in range(0,p+1): # gg = int(F.prod(i,j)) # d.append(gg) # print d # #print F.plus(4,2) #print F.prod(4,2)