viff

changeset 781:70b74e887726

Merged.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 23 May 2008 10:43:38 +0200
parents 26371fc11801 13b7521daf43
children 4b4667df6f77
files
diffstat 4 files changed, 49 insertions(+), 45 deletions(-) [+]
line diff
     1.1 --- a/apps/gc-test.py	Fri May 23 10:41:15 2008 +0200
     1.2 +++ b/apps/gc-test.py	Fri May 23 10:43:38 2008 +0200
     1.3 @@ -24,9 +24,7 @@
     1.4  # same speed as they are allocated.
     1.5  
     1.6  import sys
     1.7 -import gc
     1.8  from time import time
     1.9 -from pprint import pprint
    1.10  
    1.11  from twisted.internet import reactor
    1.12  
     2.1 --- a/doc/prss.txt	Fri May 23 10:41:15 2008 +0200
     2.2 +++ b/doc/prss.txt	Fri May 23 10:43:38 2008 +0200
     2.3 @@ -9,4 +9,10 @@
     2.4  
     2.5     .. autofunction:: prss
     2.6  
     2.7 +   .. autofunction:: prss_lsb
     2.8 +
     2.9 +   .. autofunction:: random_replicated_sharing
    2.10 +
    2.11 +   .. autofunction:: convert_replicated_shamir
    2.12 +
    2.13     .. autofunction:: generate_subsets
     3.1 --- a/viff/field.py	Fri May 23 10:41:15 2008 +0200
     3.2 +++ b/viff/field.py	Fri May 23 10:43:38 2008 +0200
     3.3 @@ -75,47 +75,16 @@
     3.4      """Common base class for elements."""
     3.5  
     3.6  
     3.7 -#: Logarithm table.
     3.8 -#:
     3.9 -#: Maps a value *x* to *log3(x)*. See `_generate_tables`.
    3.10 -_log_table = {}
    3.11 -#: Exponentiation table.
    3.12 -#:
    3.13 -#: Maps a value *y* to *3^y*. See `_generate_tables`.
    3.14 -_exp_table = {}
    3.15  #: Inversion table.
    3.16  #:
    3.17  #: Maps a value *x* to *x^-1*. See `_generate_tables`.
    3.18  _inv_table = {}
    3.19  
    3.20 +#: Multiplication table.
    3.21 +#:
    3.22 +#: Maps *(x,y)* to *xy*. See `_generate_tables`.
    3.23 +_mul_table = {}
    3.24  
    3.25 -def _generate_tables():
    3.26 -    """Generate tables with logarithms, antilogarithms (exponentials)
    3.27 -    and inverses.
    3.28 -
    3.29 -    This updates the `_log_table`, `_exp_table`, and `_inv_table`
    3.30 -    fields. The generator used is ``0x03``.
    3.31 -
    3.32 -    Code adapted from http://www.samiam.org/galois.html.
    3.33 -    """
    3.34 -    a = 1
    3.35 -    for c in range(255):
    3.36 -        a &= 0xff
    3.37 -        _exp_table[c] = a
    3.38 -        d = a & 0x80
    3.39 -        a <<= 1
    3.40 -        if d == 0x80:
    3.41 -            a ^= 0x1b
    3.42 -        a ^= _exp_table[c]
    3.43 -        _log_table[_exp_table[c]] = c
    3.44 -    _exp_table[255] = _exp_table[0]
    3.45 -    _log_table[0] = 0
    3.46 -
    3.47 -    #_inv_table[0] = 0
    3.48 -    for c in range(1, 256):
    3.49 -        _inv_table[c] = _exp_table[255 - _log_table[c]]
    3.50 -
    3.51 -_generate_tables()
    3.52  
    3.53  # The class name is slightly wrong since the class instances cannot be
    3.54  # said to be represent a field. Instead they represent instances of
    3.55 @@ -193,11 +162,7 @@
    3.56              return NotImplemented
    3.57          if isinstance(other, GF256):
    3.58              other = other.value
    3.59 -        if self.value == 0 or other == 0:
    3.60 -            return GF256(0)
    3.61 -        else:
    3.62 -            log_product = (_log_table[self.value] + _log_table[other]) % 255
    3.63 -            return GF256(_exp_table[log_product])
    3.64 +        return _mul_table[(self.value, other)]
    3.65  
    3.66  
    3.67      #: Multiply this and another GF256 element (reflected argument version).
    3.68 @@ -236,7 +201,7 @@
    3.69          """
    3.70          if self.value == 0:
    3.71              raise ZeroDivisionError("Cannot invert zero")
    3.72 -        return GF256(_inv_table[self.value])
    3.73 +        return _inv_table[self.value]
    3.74  
    3.75      def __repr__(self):
    3.76          return "[%d]" % self.value
    3.77 @@ -288,6 +253,43 @@
    3.78  GF256.field = GF256
    3.79  
    3.80  
    3.81 +def _generate_tables():
    3.82 +    """Generate multiplication and inversion tables.
    3.83 +
    3.84 +    This updates the `_mul_table` and `_inv_table`. The generator used
    3.85 +    is ``0x03``.
    3.86 +
    3.87 +    Code adapted from http://www.samiam.org/galois.html.
    3.88 +    """
    3.89 +    log_table = {}
    3.90 +    exp_table = {}
    3.91 +    a = 1
    3.92 +    for c in range(255):
    3.93 +        a &= 0xff
    3.94 +        exp_table[c] = a
    3.95 +        d = a & 0x80
    3.96 +        a <<= 1
    3.97 +        if d == 0x80:
    3.98 +            a ^= 0x1b
    3.99 +        a ^= exp_table[c]
   3.100 +        log_table[exp_table[c]] = c
   3.101 +    exp_table[255] = exp_table[0]
   3.102 +
   3.103 +    for x in range(256):
   3.104 +        for y in range(256):
   3.105 +            if x == 0 or y == 0:
   3.106 +                z = 0
   3.107 +            else:
   3.108 +                log_product = (log_table[x] + log_table[y]) % 255
   3.109 +                z = exp_table[log_product]
   3.110 +            _mul_table[(x,y)] = GF256(z)
   3.111 +
   3.112 +    for c in range(1, 256):
   3.113 +        _inv_table[c] = GF256(exp_table[255 - log_table[c]])
   3.114 +
   3.115 +_generate_tables()
   3.116 +
   3.117 +
   3.118  #: Cached fields.
   3.119  #:
   3.120  #: Calls to GF with identical modulus must return the same class
     4.1 --- a/viff/test/test_memory.py	Fri May 23 10:41:15 2008 +0200
     4.2 +++ b/viff/test/test_memory.py	Fri May 23 10:43:38 2008 +0200
     4.3 @@ -15,8 +15,6 @@
     4.4  # You should have received a copy of the GNU Lesser General Public
     4.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     4.6  
     4.7 -from viff.field import GF256
     4.8 -from viff.runtime import Share
     4.9  from viff.test.util import RuntimeTestCase, protocol
    4.10  
    4.11  class MemoryTest(RuntimeTestCase):