Package viff :: Module field
[hide private]
[frames] | no frames]

Source Code for Module viff.field

  1  # Copyright 2007, 2008 VIFF Development Team. 
  2  # 
  3  # This file is part of VIFF, the Virtual Ideal Functionality Framework. 
  4  # 
  5  # VIFF is free software: you can redistribute it and/or modify it 
  6  # under the terms of the GNU Lesser General Public License (LGPL) as 
  7  # published by the Free Software Foundation, either version 3 of the 
  8  # License, or (at your option) any later version. 
  9  # 
 10  # VIFF is distributed in the hope that it will be useful, but WITHOUT 
 11  # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 12  # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 
 13  # Public License for more details. 
 14  # 
 15  # You should have received a copy of the GNU Lesser General Public 
 16  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>. 
 17   
 18  """Modeling of Galois (finite) fields. The GF function creates classes 
 19  which implements Galois (finite) fields of prime order whereas the 
 20  :class:`GF256` class implements the the GF(2^8) field with 
 21  characteristic 2. 
 22   
 23  All fields work the same: instantiate an object from a field to get 
 24  hold of an element of that field. Elements implement the normal 
 25  arithmetic one would expect: addition, multiplication, etc. 
 26   
 27  Defining a field: 
 28   
 29  >>> Zp = GF(19) 
 30   
 31  Defining field elements: 
 32   
 33  >>> x = Zp(10) 
 34  >>> y = Zp(15) 
 35  >>> z = Zp(1) 
 36   
 37  Addition and subtraction (with modulo reduction): 
 38   
 39  >>> x + y 
 40  {6} 
 41  >>> x - y 
 42  {14} 
 43   
 44  Bitwise xor for field elements: 
 45   
 46  >>> z ^ z 
 47  {0} 
 48  >>> z ^ 0 
 49  {1} 
 50  >>> 1 ^ z 
 51  {0} 
 52   
 53  Exponentiation: 
 54   
 55  >>> x**3 
 56  {12} 
 57   
 58  Square roots can be found for elements based on GF fields with a Blum 
 59  prime modulus (see :func:`GF` for more information): 
 60   
 61  >>> x.sqrt() 
 62  {3} 
 63   
 64  Field elements from different fields cannot be mixed, you will get a 
 65  type error if you try: 
 66   
 67  >>> Zq = GF(17) 
 68  >>> z = Zq(2) 
 69  >>> x + z 
 70  Traceback (most recent call last): 
 71      ... 
 72  TypeError: unsupported operand type(s) for +: 'GFElement' and 'GFElement' 
 73   
 74  The reason for the slightly confusing error message is that ``x`` and 
 75  ``z`` are instances of two *different* classes called ``GFElement``. 
 76  """ 
 77   
 78  __docformat__ = "restructuredtext" 
 79   
 80   
 81  from gmpy import mpz 
 82  from math import log, ceil 
 83   
 84   
85 -class FieldElement(object):
86 """Common base class for elements.""" 87
88 - def __int__(self):
89 """Extract integer value from the field element. 90 91 >>> int(GF256(10)) 92 10 93 """ 94 return self.value
95 96 __long__ = __int__ 97
98 - def split(self):
99 """Splits self into bit array LSB first. 100 101 >>> Zp = GF(29) 102 >>> Zp(3).split() 103 [{1}, {1}, {0}, {0}, {0}] 104 >>> Zp(28).split() 105 [{0}, {0}, {1}, {1}, {1}] 106 >>> GF256(8).split() 107 [[0], [0], [0], [1], [0], [0], [0], [0]] 108 """ 109 length = int(ceil(log(self.modulus,2))) 110 result = [0] * length 111 temp = self.value 112 for i in range(length): 113 result[i] = self.field(temp % 2) 114 temp = temp // 2 115 return result
116 117 #: Inversion table. 118 #: 119 #: Maps a value *x* to *x^-1*. See `_generate_tables`. 120 _inv_table = {} 121 122 #: Multiplication table. 123 #: 124 #: Maps *(x,y)* to *xy*. See `_generate_tables`. 125 _mul_table = {} 126 127 128 # The class name is slightly wrong since the class instances cannot be 129 # said to be represent a field. Instead they represent instances of 130 # GF256 elements. But the shorter name is better, though, in the 131 # common case where one talks about the class as a field.
132 -class GF256(FieldElement):
133 """Models an element of the GF(2^8) field.""" 134 135 modulus = 256 #: GF(2^8) modulus, always 256. 136
137 - def __init__(self, value):
138 """Initialize new element. 139 140 The value given is modulo reduced so the following holds: 141 142 >>> GF256(1) == GF256(257) 143 True 144 """ 145 self.value = value % self.modulus
146
147 - def __add__(self, other):
148 """Add this and another GF256 element. 149 150 >>> GF256(0x01) + GF256(0x01) 151 [0] 152 >>> GF256(0x01) + GF256(0x02) 153 [3] 154 155 Adding integers works too, the other operand is coerced into a 156 GF256 element automatically: 157 158 >>> GF256(0x01) + 1 159 [0] 160 """ 161 if not isinstance(other, (GF256, int, long)): 162 # This occurs with code like 'a + b' where b is a Share. 163 # In that case we must return NotImplemented to signal 164 # that b.__radd__(a) should be run instead. The Share will 165 # then schedule things correctly. 166 return NotImplemented 167 if isinstance(other, GF256): 168 other = other.value 169 return GF256(self.value ^ other)
170
171 - def __radd__(self, other):
172 """Add this and another number (reflected argument version). 173 174 other is not Share, otherwise Share.__add__() would have been 175 called, and other is not a GF256, otherwise GF256.__add__() 176 would have been called.""" 177 return GF256(self.value ^ other)
178 179 #: Subtract this and another GF256 element. 180 #: 181 #: Addition is its own inverse in GF(2^8) and so this is the same 182 #: as `__add__`. 183 __sub__ = __add__ 184 #: Subtract this and another GF256 element (reflected argument version). 185 __rsub__ = __radd__ 186 187 #: Exclusive-or. 188 #: 189 #: This is just addition for GF256 elements. 190 __xor__ = __add__ 191 192 #: Exclusive-or (reflected argument version). 193 __rxor__ = __radd__ 194
195 - def __mul__(self, other):
196 """Multiply this and another GF256. 197 198 >>> GF256(0) * GF256(47) 199 [0] 200 >>> GF256(2) * GF256(3) 201 [6] 202 >>> GF256(16) * GF256(32) 203 [54] 204 """ 205 if not isinstance(other, (GF256, int, long)): 206 return NotImplemented 207 if isinstance(other, GF256): 208 other = other.value 209 return _mul_table[(self.value, other)]
210 211
212 - def __rmul__(self, other):
213 """Multiply this and another number (reflected argument 214 version). 215 216 other is not Share, otherwise Share.__mul__() would have been 217 called, and other is not a GF256, otherwise GF256.__mul__() 218 would have been called.""" 219 return _mul_table[(self.value, other)]
220
221 - def __pow__(self, exponent):
222 """Exponentiation.""" 223 result = GF256(1) 224 for _ in range(exponent): 225 result *= self 226 return result
227
228 - def __div__(self, other):
229 """Division.""" 230 return self * ~other
231 232 __truediv__ = __div__ 233 __floordiv__ = __div__ 234
235 - def __rdiv__(self, other):
236 """Division (reflected argument version).""" 237 return GF256(other) / self
238 239 __rtruediv__ = __rdiv__ 240 __rfloordiv__ = __rdiv__ 241
242 - def __neg__(self):
243 """Negation.""" 244 return self
245
246 - def __invert__(self):
247 """Invertion. 248 249 Raises :exc:`ZeroDivisionError` if trying to inverse the zero 250 element. 251 """ 252 if self.value == 0: 253 raise ZeroDivisionError("Cannot invert zero") 254 return _inv_table[self.value]
255
256 - def __repr__(self):
257 return "[%d]" % self.value
258 #return "GF256(%d)" % self.value 259
260 - def __str__(self):
261 return "[%d]" % self.value
262
263 - def __eq__(self, other):
264 """Equality testing. 265 266 Testing for equality with integers works as expected: 267 268 >>> GF256(10) == 10 269 True 270 """ 271 if isinstance(other, GF256): 272 other = other.value 273 return self.value == other
274
275 - def __ne__(self, other):
276 """Inequality testing.""" 277 if isinstance(other, GF256): 278 other = other.value 279 return self.value != other
280
281 - def __hash__(self):
282 """Hash value.""" 283 return hash((self.field, self.value))
284
285 - def __nonzero__(self):
286 """Truth value testing. 287 288 Returns False if this element is zero, True otherwise. This 289 allows GF256 elements to be used directly in Boolean formula: 290 291 >>> bool(GF256(0)) 292 False 293 >>> bool(GF256(1)) 294 True 295 >>> x = GF256(1) 296 >>> not x 297 False 298 """ 299 return self.value != 0
300 301 # We provide the class here to make the construction of new elements 302 # easy in a polymorphic context. 303 GF256.field = GF256 304 305
306 -def _generate_tables():
307 """Generate multiplication and inversion tables. 308 309 This updates the `_mul_table` and `_inv_table`. The generator used 310 is ``0x03``. 311 312 Code adapted from http://www.samiam.org/galois.html. 313 """ 314 log_table = {} 315 exp_table = {} 316 a = 1 317 for c in range(255): 318 a &= 0xff 319 exp_table[c] = a 320 d = a & 0x80 321 a <<= 1 322 if d == 0x80: 323 a ^= 0x1b 324 a ^= exp_table[c] 325 log_table[exp_table[c]] = c 326 exp_table[255] = exp_table[0] 327 328 for x in range(256): 329 for y in range(256): 330 if x == 0 or y == 0: 331 z = 0 332 else: 333 log_product = (log_table[x] + log_table[y]) % 255 334 z = exp_table[log_product] 335 _mul_table[(x,y)] = GF256(z) 336 337 for c in range(1, 256): 338 _inv_table[c] = GF256(exp_table[255 - log_table[c]])
339 340 _generate_tables() 341 342 343 #: Cached fields. 344 #: 345 #: Calls to GF with identical modulus must return the same class 346 #: (field), so we cache them here. The cache is seeded with the 347 #: GF256 class which is always defined. 348 _field_cache = {256: GF256} 349 350
351 -def GF(modulus):
352 """Generate a Galois (finite) field with the given modulus. 353 354 The modulus must be a prime: 355 356 >>> Z23 = GF(23) # works 357 >>> Z10 = GF(10) # not a prime 358 Traceback (most recent call last): 359 ... 360 ValueError: 10 is not a prime 361 362 A modulus of 256 is special since it returns the GF(2^8) field 363 even though 256 is no prime: 364 365 >>> GF256 = GF(256) 366 >>> print GF256(1) 367 [1] 368 369 Please note, that if you wish to calculate square roots, the 370 modulus must be a Blum prime (congruent to 3 mod 4): 371 372 >>> Z17 = GF(17) # 17 % 4 == 1, so 17 is no Blum prime 373 >>> x = Z17(10) 374 >>> x.sqrt() 375 Traceback (most recent call last): 376 ... 377 AssertionError: Cannot compute square root of {10} with modulus 17 378 """ 379 if modulus in _field_cache: 380 return _field_cache[modulus] 381 382 if not mpz(modulus).is_prime(): 383 raise ValueError("%d is not a prime" % modulus) 384 385 # Define a new class representing the field. This class will be 386 # returned at the end of the function. 387 class GFElement(FieldElement): 388 389 def __init__(self, value): 390 self.value = value % self.modulus
391 392 def __add__(self, other): 393 """Addition.""" 394 if not isinstance(other, (GFElement, int, long)): 395 return NotImplemented 396 try: 397 # We can do a quick test using 'is' here since 398 # there will only be one class representing this 399 # field. 400 assert self.field is other.field, "Fields must be identical" 401 return GFElement(self.value + other.value) 402 except AttributeError: 403 return GFElement(self.value + other) 404 405 __radd__ = __add__ 406 407 def __sub__(self, other): 408 """Subtraction.""" 409 if not isinstance(other, (GFElement, int, long)): 410 return NotImplemented 411 try: 412 assert self.field is other.field, "Fields must be identical" 413 return GFElement(self.value - other.value) 414 except AttributeError: 415 return GFElement(self.value - other) 416 417 def __rsub__(self, other): 418 """Subtraction (reflected argument version).""" 419 return GFElement(other - self.value) 420 421 def __xor__(self, other): 422 """Xor for bitvalues.""" 423 if not isinstance(other, (GFElement, int, long)): 424 return NotImplemented 425 try: 426 assert self.field is other.field, "Fields must be identical" 427 return GFElement(self.value ^ other.value) 428 except AttributeError: 429 return GFElement(self.value ^ other) 430 431 def __rxor__(self, other): 432 """Xor for bitvalues (reflected argument version).""" 433 return GFElement(other ^ self.value) 434 435 def __mul__(self, other): 436 """Multiplication.""" 437 if not isinstance(other, (GFElement, int, long)): 438 return NotImplemented 439 try: 440 assert self.field is other.field, "Fields must be identical" 441 return GFElement(self.value * other.value) 442 except AttributeError: 443 return GFElement(self.value * other) 444 445 __rmul__ = __mul__ 446 447 def __pow__(self, exponent): 448 """Exponentiation.""" 449 return GFElement(pow(self.value, exponent, self.modulus)) 450 451 def __neg__(self): 452 """Negation.""" 453 return GFElement(-self.value) 454 455 def __invert__(self): 456 """Inversion. 457 458 Note that zero cannot be inverted, trying to do so 459 will raise a ZeroDivisionError. 460 """ 461 if self.value == 0: 462 raise ZeroDivisionError("Cannot invert zero") 463 464 def extended_gcd(a, b): 465 """The extended Euclidean algorithm.""" 466 x = 0 467 lastx = 1 468 y = 1 469 lasty = 0 470 while b != 0: 471 quotient = a // b 472 a, b = b, a % b 473 x, lastx = lastx - quotient*x, x 474 y, lasty = lasty - quotient*y, y 475 return (lastx, lasty, a) 476 477 inverse = extended_gcd(self.value, self.modulus)[0] 478 return GFElement(inverse) 479 480 def __div__(self, other): 481 """Division.""" 482 try: 483 assert self.field is other.field, "Fields must be identical" 484 return self * ~other 485 except AttributeError: 486 return self * ~GFElement(other) 487 488 __truediv__ = __div__ 489 __floordiv__ = __div__ 490 491 def __rdiv__(self, other): 492 """Division (reflected argument version).""" 493 return GFElement(other) / self 494 495 __rtruediv__ = __rdiv__ 496 __rfloordiv__ = __rdiv__ 497 498 def sqrt(self): 499 """Square root. 500 501 No attempt is made the to return the positive square root. 502 503 Computing square roots is only possible when the modulus 504 is a Blum prime (congruent to 3 mod 4). 505 """ 506 assert self.modulus % 4 == 3, "Cannot compute square " \ 507 "root of %s with modulus %s" % (self, self.modulus) 508 509 # Because we assert that the modulus is a Blum prime 510 # (congruent to 3 mod 4), there will be no reminder in the 511 # division below. 512 root = pow(self.value, (self.modulus+1)//4, self.modulus) 513 return GFElement(root) 514 515 def bit(self, index): 516 """Extract a bit (index is counted from zero).""" 517 return (self.value >> index) & 1 518 519 def signed(self): 520 """Return a signed integer representation of the value. 521 522 If x > floor(p/2) then subtract p to obtain negative integer. 523 """ 524 if self.value > ((self.modulus-1)/2): 525 return self.value - self.modulus 526 else: 527 return self.value 528 529 def unsigned(self): 530 """Return a unsigned representation of the value""" 531 return self.value 532 533 def __repr__(self): 534 return "{%d}" % self.value 535 #return "GFElement(%d)" % self.value 536 537 def __str__(self): 538 """Informal string representation. 539 540 This is simply the value enclosed in curly braces. 541 """ 542 return "{%d}" % self.unsigned() 543 544 def __eq__(self, other): 545 """Equality test.""" 546 try: 547 assert self.field is other.field, "Fields must be identical" 548 return self.value == other.value 549 except AttributeError: 550 return self.value == other 551 552 def __ne__(self, other): 553 """Inequality test.""" 554 try: 555 assert self.field is other.field, "Fields must be identical" 556 return self.value != other.value 557 except AttributeError: 558 return self.value != other 559 560 def __cmp__(self, other): 561 """Comparison.""" 562 try: 563 assert self.field is other.field, "Fields must be identical" 564 return cmp(self.value, other.value) 565 except AttributeError: 566 return cmp(self.value, other) 567 568 def __hash__(self): 569 """Hash value.""" 570 return hash((self.field, self.value)) 571 572 def __nonzero__(self): 573 """Truth value testing. 574 575 Returns False if this element is zero, True otherwise. 576 This allows GF elements to be used directly in Boolean 577 formula: 578 579 >>> bool(GF256(0)) 580 False 581 >>> bool(GF256(1)) 582 True 583 >>> x = GF256(1) 584 >>> not x 585 False 586 """ 587 return self.value != 0 588 589 GFElement.modulus = modulus 590 GFElement.field = GFElement 591 592 _field_cache[modulus] = GFElement 593 return GFElement 594
595 -def FakeGF(modulus):
596 """Construct a fake field. 597 598 These fields should only be used in benchmarking. They work like 599 any other field except that all computations will give ``-1`` as 600 the result: 601 602 >>> F = FakeGF(1031) 603 >>> a = F(123) 604 >>> b = F(234) 605 >>> a + b 606 {{1030}} 607 >>> a * b 608 {{1030}} 609 >>> a.sqrt() 610 {{1030}} 611 >>> a.bit(100) 612 1 613 """ 614 615 # Return value of all operations on FakeFieldElements. We choose 616 # this value to maximize the communication complexity. 617 return_value = modulus - 1 618 619 class FakeFieldElement(FieldElement): 620 """Fake field which does no computations.""" 621 622 def __init__(self, value): 623 """Create a fake field element. 624 625 The element will store *value* in order to take up a realistic 626 amount of RAM, but any further computation will yield the 627 value ``-1``. 628 """ 629 self.value = value
630 631 # Binary operations. 632 __add__ = __radd__ = __sub__ = __rsub__ \ 633 = __mul__ = __rmul__ = __div__ = __rdiv__ \ 634 = __truediv__ = __rtruediv__ = __floordiv__ = __rfloordiv__ \ 635 = __pow__ = __neg__ \ 636 = lambda self, other: FakeFieldElement(return_value) 637 638 # Unary operations. 639 __invert__ = sqrt = lambda self: FakeFieldElement(return_value) 640 641 # Bit extraction. We pretend that the number is *very* big. 642 bit = lambda self, index: 1 643 644 # Fake field elements are printed with double curly brackets. 645 __repr__ = __str__ = lambda self: "{{%d}}" % self.value 646 647 FakeFieldElement.field = FakeFieldElement 648 FakeFieldElement.modulus = modulus 649 return FakeFieldElement 650 651 if __name__ == "__main__": 652 import doctest #pragma NO COVER 653 doctest.testmod() #pragma NO COVER 654