API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 12th, 2016
49
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.32 KB | None | 0 0
raw download clone embed print report
  1. --- ffield.py 2016-02-12 16:14:40.654378453 -0500
  2. +++ ffield3.py 2016-02-12 16:16:21.017352960 -0500
  3. @@ -23,10 +23,10 @@
  4.  
  5. testing_doc Describes some tests to make sure the code is working
  6. as well as some of the built in testing routines.
  7. -
  8. +
  9. """
  10.  
  11. -import string, random, os, os.path, cPickle
  12. +import string, random, os, os.path, pickle, functools
  13.  
  14.  
  15. # The following list of primitive polynomials are the Conway Polynomials
  16. @@ -81,14 +81,11 @@
  17.  
  18. for n in gPrimitivePolysCondensed.keys():
  19. gPrimitivePolys[n] = [0]*(n+1)
  20. - if (n < 16):
  21. - unity = 1
  22. - else:
  23. - unity = long(1)
  24. + unity = 1
  25. for index in gPrimitivePolysCondensed[n]:
  26. gPrimitivePolys[n][index] = unity
  27. gPrimitivePolys[n].reverse()
  28. -
  29. +
  30.  
  31. class FField:
  32. """
  33. @@ -112,15 +109,15 @@
  34. TestFullDivision
  35. TestInverse
  36.  
  37. - Most of these methods take integers or longs representing field
  38. - elements as arguments and return integers representing the desired
  39. + Most of these methods take integers representing field elements
  40. + as arguments and return integers representing the desired
  41. field elements as output. See ffield.fields_doc for an explanation
  42. of the integer representation of field elements.
  43.  
  44. Example of how to use the FField class:
  45. -
  46. +
  47. >>> import ffield
  48. ->>> F = ffield.FField(5) # create the field GF(2^5)
  49. +>>> F = ffield.FField(5) # create the field GF(2^5)
  50. >>> a = 7 # field elements are denoted as integers from 0 to 2^5-1
  51. >>> b = 15
  52. >>> F.ShowPolynomial(a) # show the polynomial representation of a
  53. @@ -142,7 +139,7 @@
  54.  
  55. See documentation on the appropriate method for further details.
  56. """
  57. -
  58. +
  59. def __init__(self,n,gen=0,useLUT=-1):
  60. """
  61. This method constructs the field GF(2^p). It takes one
  62. @@ -162,8 +159,8 @@
  63. Note that you can look at the generator for the field object
  64. F by looking at F.generator.
  65. """
  66. -
  67. - self.n = n
  68. +
  69. + self.n = n
  70. if (gen):
  71. self.generator = gen
  72. else:
  73. @@ -172,31 +169,25 @@
  74.  
  75. if (useLUT == 1 or (useLUT == -1 and self.n < 10)): # use lookup table
  76. self.unity = 1
  77. - self.Inverse = self.DoInverseForSmallField
  78. + self.Inverse = self.DoInverse
  79. self.PrepareLUT()
  80. self.Multiply = self.LUTMultiply
  81. self.Divide = self.LUTDivide
  82. - self.Inverse = lambda x: self.LUTDivide(1,x)
  83. - elif (self.n < 15):
  84. + self.Inverse = lambda x: self.LUTDivide(1,x)
  85. + else:
  86. self.unity = 1
  87. - self.Inverse = self.DoInverseForSmallField
  88. - self.Multiply = self.DoMultiply
  89. - self.Divide = self.DoDivide
  90. - else: # Need to use longs for larger fields
  91. - self.unity = long(1)
  92. - self.Inverse = self.DoInverseForBigField
  93. - self.Multiply = lambda a,b: self.DoMultiply(long(a),long(b))
  94. - self.Divide = lambda a,b: self.DoDivide(long(a),long(b))
  95. + self.Inverse = self.DoInverse
  96. + self.Multiply = lambda a,b: self.DoMultiply(a,b)
  97. + self.Divide = lambda a,b: self.DoDivide(a,b)
  98.  
  99.  
  100.  
  101. def PrepareLUT(self):
  102. fieldSize = 1 << self.n
  103. - lutName = 'ffield.lut.' + `self.n`
  104. + lutName = 'ffield.lut.' + repr(self.n)
  105. if (os.path.exists(lutName)):
  106. - fd = open(lutName,'r')
  107. - self.lut = cPickle.load(fd)
  108. - fd.close()
  109. + with open(lutName,'rb') as fd:
  110. + self.lut = pickle.load(fd)
  111. else:
  112. self.lut = LUT()
  113. self.lut.mulLUT = range(fieldSize)
  114. @@ -204,26 +195,25 @@
  115. self.lut.mulLUT[0] = [0]*fieldSize
  116. self.lut.divLUT[0] = ['NaN']*fieldSize
  117. for i in range(1,fieldSize):
  118. - self.lut.mulLUT[i] = map(lambda x: self.DoMultiply(i,x),
  119. - range(fieldSize))
  120. - self.lut.divLUT[i] = map(lambda x: self.DoDivide(i,x),
  121. - range(fieldSize))
  122. - fd = open(lutName,'w')
  123. - cPickle.dump(self.lut,fd)
  124. - fd.close()
  125. + self.lut.mulLUT[i] = list(map(lambda x: self.DoMultiply(i,x),
  126. + range(fieldSize)))
  127. + self.lut.divLUT[i] = list(map(lambda x: self.DoDivide(i,x),
  128. + range(fieldSize)))
  129. + with open(lutName,'wb') as fd:
  130. + pickle.dump(self.lut,fd)
  131. +
  132.  
  133. -
  134. def LUTMultiply(self,i,j):
  135. return self.lut.mulLUT[i][j]
  136.  
  137. def LUTDivide(self,i,j):
  138. return self.lut.divLUT[i][j]
  139. -
  140. +
  141. def Add(self,x,y):
  142. """
  143. Adds two field elements and returns the result.
  144. """
  145. -
  146. +
  147. return x ^ y
  148.  
  149. def Subtract(self,x,y):
  150. @@ -245,8 +235,8 @@
  151. m = self.MultiplyWithoutReducing(f,v)
  152. return self.FullDivision(m,self.generator,
  153. self.FindDegree(m),self.n)[1]
  154. -
  155. - def DoInverseForSmallField(self,f):
  156. +
  157. + def DoInverse(self,f):
  158. """
  159. Computes the multiplicative inverse of its argument and
  160. returns the result.
  161. @@ -254,14 +244,6 @@
  162. return self.ExtendedEuclid(1,f,self.generator,
  163. self.FindDegree(f),self.n)[1]
  164.  
  165. - def DoInverseForBigField(self,f):
  166. - """
  167. - Computes the multiplicative inverse of its argument and
  168. - returns the result.
  169. - """
  170. - return self.ExtendedEuclid(self.unity,long(f),self.generator,
  171. - self.FindDegree(long(f)),self.n)[1]
  172. -
  173. def DoDivide(self,f,v):
  174. """
  175. Divide(f,v) returns f * v^-1.
  176. @@ -291,16 +273,13 @@
  177. Multiplies two field elements and does not take the result
  178. modulo self.generator. You probably should not use this
  179. unless you know what you are doing; look at Multiply instead.
  180. -
  181. - NOTE: If you are using fields larger than GF(2^15), you should
  182. - make sure that f and v are longs not integers.
  183. """
  184. -
  185. +
  186. result = 0
  187. mask = self.unity
  188. i = 0
  189. while (i <= self.n):
  190. - if (mask & v):
  191. + if (mask & v):
  192. result = result ^ f
  193. f = f << 1
  194. mask = mask << 1
  195. @@ -329,7 +308,7 @@
  196. f and v represented as a polynomials.
  197. This method returns the field elements a and b such that
  198.  
  199. - f(x) = a(x) * v(x) + b(x).
  200. + f(x) = a(x) * v(x) + b(x).
  201.  
  202. That is, a is the divisor and b is the remainder, or in
  203. other words a is like floor(f/v) and b is like f modulo v.
  204. @@ -361,7 +340,7 @@
  205. result.append(1)
  206. else:
  207. result.append(0)
  208. -
  209. +
  210. return result
  211.  
  212. def ShowPolynomial(self,f):
  213. @@ -374,13 +353,13 @@
  214.  
  215. if (f == 0):
  216. return '0'
  217. -
  218. +
  219. for i in range(fDegree,0,-1):
  220. if ((1 << i) & f):
  221. - result = result + (' x^' + `i`)
  222. + result = result + (' x^' + repr(i))
  223. if (1 & f):
  224. - result = result + ' ' + `1`
  225. - return string.replace(string.strip(result),' ',' + ')
  226. + result = result + ' ' + repr(1)
  227. + return result.strip().replace(' ',' + ')
  228.  
  229. def GetRandomElement(self,nonZero=0,maxDegree=None):
  230. """
  231. @@ -398,14 +377,14 @@
  232. if (maxDegree < 31):
  233. return random.randint(nonZero != 0,(1<<maxDegree)-1)
  234. else:
  235. - result = 0L
  236. + result = 0
  237. for i in range(0,maxDegree):
  238. - result = result ^ (random.randint(0,1) << long(i))
  239. + result = result ^ (random.randint(0,1) << i)
  240. if (nonZero and result == 0):
  241. return self.GetRandomElement(1)
  242. else:
  243. return result
  244. -
  245. +
  246.  
  247.  
  248. def ConvertListToElement(self,l):
  249. @@ -419,9 +398,9 @@
  250. result modulo the generator to get a proper element in the
  251. field.
  252. """
  253. -
  254. +
  255. temp = map(lambda a, b: a << b, l, range(len(l)-1,-1,-1))
  256. - return reduce(lambda a, b: a | b, temp)
  257. + return functools.reduce(lambda a, b: a | b, temp)
  258.  
  259. def TestFullDivision(self):
  260. """
  261. @@ -439,9 +418,9 @@
  262. (c,d) = self.FullDivision(a,b,aDegree,bDegree)
  263. recon = self.Add(d, self.Multiply(c,b))
  264. assert (recon == a), ('TestFullDivision failed: a='
  265. - + `a` + ', b=' + `b` + ', c='
  266. - + `c` + ', d=' + `d` + ', recon=', recon)
  267. -
  268. + + repr(a) + ', b=' + repr(b) + ', c='
  269. + + repr(c) + ', d=' + repr(d) + ', recon=', recon)
  270. +
  271. def TestInverse(self):
  272. """
  273. This function tests the Inverse function by generating
  274. @@ -452,9 +431,9 @@
  275. a = self.GetRandomElement(nonZero=1)
  276. aInv = self.Inverse(a)
  277. prod = self.Multiply(a,aInv)
  278. - assert 1 == prod, ('TestInverse failed:' + 'a=' + `a` + ', aInv='
  279. - + `aInv` + ', prod=' + `prod`,
  280. - 'gen=' + `self.generator`)
  281. + assert 1 == prod, ('TestInverse failed:' + 'a=' + repr(a) + ', aInv='
  282. + + repr(aInv) + ', prod=' + repr(prod),
  283. + 'gen=' + repr(self.generator))
  284.  
  285. class LUT:
  286. """
  287. @@ -469,13 +448,13 @@
  288. +,-,*,%,//,/ operators to be the appropriate field operation.
  289. Note that before creating FElement objects you must first
  290. create an FField object. For example,
  291. -
  292. +
  293. >>> import ffield
  294. ->>> F = FField(5)
  295. ->>> e1 = FElement(F,7)
  296. +>>> F = ffield.FField(5)
  297. +>>> e1 = ffield.FElement(F,7)
  298. >>> e1
  299. x^2 + x^1 + 1
  300. ->>> e2 = FElement(F,19)
  301. +>>> e2 = ffield.FElement(F,19)
  302. >>> e2
  303. x^4 + x^1 + 1
  304. >>> e3 = e1 + e2
  305. @@ -486,9 +465,9 @@
  306. x^4 + x^3
  307. >>> e4 * e2 == (e3)
  308. 1
  309. -
  310. +
  311. """
  312. -
  313. +
  314. def __init__(self,field,e):
  315. """
  316. The constructor takes two arguments, field, and e where
  317. @@ -499,7 +478,7 @@
  318. """
  319. self.f = e
  320. self.field = field
  321. -
  322. +
  323. def __add__(self,other):
  324. assert self.field == other.field
  325. return FElement(self.field,self.field.Add(self.f,other.f))
  326. @@ -522,7 +501,7 @@
  327. self.field.FindDegree(self.f),
  328. self.field.FindDegree(o.f))[0])
  329.  
  330. - def __div__(self,other):
  331. + def __truediv__(self,other):
  332. assert self.field == other.field
  333. return FElement(self.field,self.field.Divide(self.f,other.f))
  334.  
  335. @@ -535,7 +514,7 @@
  336. def __eq__(self,other):
  337. assert self.field == other.field
  338. return self.f == other.f
  339. -
  340. +
  341. def FullTest(testsPerField=10,sizeList=None):
  342. """
  343. This function runs TestInverse and TestFullDivision for testsPerField
  344. @@ -544,7 +523,7 @@
  345. GF(2^7). If sizeList == None (which is the default), then every
  346. field is tested.
  347. """
  348. -
  349. +
  350. if (None == sizeList):
  351. sizeList = gPrimitivePolys.keys()
  352. for i in sizeList:
  353. @@ -601,7 +580,7 @@
  354. as telling us that we can replace every occurence of
  355. x^7 with x + 1. Thus f(x) becomes x * x^7 + x^3 + x which
  356. becomes x * (x + 1) + x^3 + x = x^3 + x^2 . Essentially, taking
  357. -polynomials mod x^7 by replacing all x^7 terms with x + 1 will
  358. +polynomials mod x^7 by replacing all x^7 terms with x + 1 will
  359. force down the degree of f(x) until it is below 7 (the leading power
  360. of g(x). See a book on abstract algebra for more details.
  361. """
  362. @@ -660,9 +639,8 @@
  363. GF(2^p) with p > 31 you have to write lots of ugly bit field
  364. code in most languages. Since Python has built in support for
  365. arbitrary precision integers, you can make this code work for
  366. - arbitrary field sizes provided you operate on longs instead of
  367. - ints. That is if you give as input numbers like
  368. - 0L, 1L, 1L << 55, etc., most of the code should work.
  369. + arbitrary field sizes. That is if you give as input numbers like
  370. + 0, 1, 1 << 55, etc., most of the code should work.
  371.  
  372. --------------------------------------------------------------------
  373. BASIC DESIGN
  374. @@ -672,7 +650,7 @@
  375. using integers and design the class methods to work properly on this
  376. representation. Using integers is efficient since integers are easy
  377. to store and manipulate and allows us to handle arbitrary field sizes
  378. -without changing the code if we instead switch to using longs.
  379. +without changing the code.
  380.  
  381. Specifically, an integer represents a bit string
  382.  
  383. @@ -692,7 +670,7 @@
  384. such operations to make most of the computations efficient.
  385.  
  386. """
  387. -
  388. +
  389.  
  390. license_doc = """
  391. This code was originally written by Emin Martinian (emin@allegro.mit.edu).
  392. @@ -731,7 +709,7 @@
  393. testing_doc = """
  394. The FField class has a number of built in testing functions such as
  395. TestFullDivision, TestInverse. The simplest thing to
  396. -do is to call the FullTest method.
  397. +do is to call the FullTest method.
  398.  
  399. >>> import ffield
  400. >>> ffield.FullTest(sizeList=None,testsPerField=100)
  401. @@ -760,7 +738,7 @@
  402. return doctest.testmod(ffield)
  403.  
  404. if __name__ == "__main__":
  405. - print 'Starting automated tests (this may take a while)'
  406. + print('Starting automated tests (this may take a while)')
  407. _test()
  408. - print 'Tests passed.'
  409. + print('Tests passed.')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!