changeset 775:99c56b32fd54

Precompute a multiplication table for GF256.
author Martin Geisler <mg@daimi.au.dk>
date Fri, 23 May 2008 10:03:36 +0200
parents d7d3f6ddb39b
children 577c1e069d06
files viff/field.py
diffstat 1 files changed, 14 insertions(+), 5 deletions(-) [+]
line wrap: on
line diff
--- a/viff/field.py	Thu May 22 10:12:46 2008 +0200
+++ b/viff/field.py	Fri May 23 10:03:36 2008 +0200
@@ -88,6 +88,10 @@
 #: Maps a value *x* to *x^-1*. See `_generate_tables`.
 _inv_table = {}
 
+#: Multiplication table.
+#:
+#: Maps *(x,y)* to *xy*. See `_generate_tables`.
+_mul_table = {}
 
 def _generate_tables():
     """Generate tables with logarithms, antilogarithms (exponentials)
@@ -111,6 +115,15 @@
     _exp_table[255] = _exp_table[0]
     _log_table[0] = 0
 
+    for x in range(256):
+        for y in range(256):
+            if x == 0 or y == 0:
+                z = 0
+            else:
+                log_product = (_log_table[x] + _log_table[y]) % 255
+                z = _exp_table[log_product]
+            _mul_table[(x,y)] = z
+
     #_inv_table[0] = 0
     for c in range(1, 256):
         _inv_table[c] = _exp_table[255 - _log_table[c]]
@@ -193,11 +206,7 @@
             return NotImplemented
         if isinstance(other, GF256):
             other = other.value
-        if self.value == 0 or other == 0:
-            return GF256(0)
-        else:
-            log_product = (_log_table[self.value] + _log_table[other]) % 255
-            return GF256(_exp_table[log_product])
+        return GF256(_mul_table[(self.value, other)])
 
 
     #: Multiply this and another GF256 element (reflected argument version).