viff

changeset 776:577c1e069d06

Populate tables with GF256 objects.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 23 May 2008 10:10:52 +0200
parents 99c56b32fd54
children 25b3944dc403
files viff/field.py
diffstat 1 files changed, 40 insertions(+), 38 deletions(-) [+]
line diff
     1.1 --- a/viff/field.py	Fri May 23 10:03:36 2008 +0200
     1.2 +++ b/viff/field.py	Fri May 23 10:10:52 2008 +0200
     1.3 @@ -93,42 +93,6 @@
     1.4  #: Maps *(x,y)* to *xy*. See `_generate_tables`.
     1.5  _mul_table = {}
     1.6  
     1.7 -def _generate_tables():
     1.8 -    """Generate tables with logarithms, antilogarithms (exponentials)
     1.9 -    and inverses.
    1.10 -
    1.11 -    This updates the `_log_table`, `_exp_table`, and `_inv_table`
    1.12 -    fields. The generator used is ``0x03``.
    1.13 -
    1.14 -    Code adapted from http://www.samiam.org/galois.html.
    1.15 -    """
    1.16 -    a = 1
    1.17 -    for c in range(255):
    1.18 -        a &= 0xff
    1.19 -        _exp_table[c] = a
    1.20 -        d = a & 0x80
    1.21 -        a <<= 1
    1.22 -        if d == 0x80:
    1.23 -            a ^= 0x1b
    1.24 -        a ^= _exp_table[c]
    1.25 -        _log_table[_exp_table[c]] = c
    1.26 -    _exp_table[255] = _exp_table[0]
    1.27 -    _log_table[0] = 0
    1.28 -
    1.29 -    for x in range(256):
    1.30 -        for y in range(256):
    1.31 -            if x == 0 or y == 0:
    1.32 -                z = 0
    1.33 -            else:
    1.34 -                log_product = (_log_table[x] + _log_table[y]) % 255
    1.35 -                z = _exp_table[log_product]
    1.36 -            _mul_table[(x,y)] = z
    1.37 -
    1.38 -    #_inv_table[0] = 0
    1.39 -    for c in range(1, 256):
    1.40 -        _inv_table[c] = _exp_table[255 - _log_table[c]]
    1.41 -
    1.42 -_generate_tables()
    1.43  
    1.44  # The class name is slightly wrong since the class instances cannot be
    1.45  # said to be represent a field. Instead they represent instances of
    1.46 @@ -206,7 +170,7 @@
    1.47              return NotImplemented
    1.48          if isinstance(other, GF256):
    1.49              other = other.value
    1.50 -        return GF256(_mul_table[(self.value, other)])
    1.51 +        return _mul_table[(self.value, other)]
    1.52  
    1.53  
    1.54      #: Multiply this and another GF256 element (reflected argument version).
    1.55 @@ -245,7 +209,7 @@
    1.56          """
    1.57          if self.value == 0:
    1.58              raise ZeroDivisionError("Cannot invert zero")
    1.59 -        return GF256(_inv_table[self.value])
    1.60 +        return _inv_table[self.value]
    1.61  
    1.62      def __repr__(self):
    1.63          return "[%d]" % self.value
    1.64 @@ -297,6 +261,44 @@
    1.65  GF256.field = GF256
    1.66  
    1.67  
    1.68 +def _generate_tables():
    1.69 +    """Generate tables with logarithms, antilogarithms (exponentials)
    1.70 +    and inverses.
    1.71 +
    1.72 +    This updates the `_log_table`, `_exp_table`, and `_inv_table`
    1.73 +    fields. The generator used is ``0x03``.
    1.74 +
    1.75 +    Code adapted from http://www.samiam.org/galois.html.
    1.76 +    """
    1.77 +    a = 1
    1.78 +    for c in range(255):
    1.79 +        a &= 0xff
    1.80 +        _exp_table[c] = a
    1.81 +        d = a & 0x80
    1.82 +        a <<= 1
    1.83 +        if d == 0x80:
    1.84 +            a ^= 0x1b
    1.85 +        a ^= _exp_table[c]
    1.86 +        _log_table[_exp_table[c]] = c
    1.87 +    _exp_table[255] = _exp_table[0]
    1.88 +    _log_table[0] = 0
    1.89 +
    1.90 +    for x in range(256):
    1.91 +        for y in range(256):
    1.92 +            if x == 0 or y == 0:
    1.93 +                z = 0
    1.94 +            else:
    1.95 +                log_product = (_log_table[x] + _log_table[y]) % 255
    1.96 +                z = _exp_table[log_product]
    1.97 +            _mul_table[(x,y)] = GF256(z)
    1.98 +
    1.99 +    #_inv_table[0] = 0
   1.100 +    for c in range(1, 256):
   1.101 +        _inv_table[c] = GF256(_exp_table[255 - _log_table[c]])
   1.102 +
   1.103 +_generate_tables()
   1.104 +
   1.105 +
   1.106  #: Cached fields.
   1.107  #:
   1.108  #: Calls to GF with identical modulus must return the same class