changeset 1047:30e34b801d65

Square-and-multiply exponentiation with known exponent.
author Marcel Keller <mkeller@cs.au.dk>
date Wed, 10 Dec 2008 20:22:20 +0100
parents b283e3136f61
children 73844d576756
files viff/passive.py viff/runtime.py viff/test/test_runtime.py
diffstat 3 files changed, 38 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/viff/passive.py	Wed Dec 10 12:43:05 2008 +0100
+++ b/viff/passive.py	Wed Dec 10 20:22:20 2008 +0100
@@ -179,6 +179,20 @@
         self.schedule_callback(result, share_recombine)
         return result
 
+    def pow(self, share, exponent):
+        """Exponentation of a share to an integer by square-and-multiply."""
+
+        assert isinstance(exponent, int), "Exponent must be an integer"
+        assert exponent >= 0, "Exponent must be non-negative"
+
+        if exponent == 0:
+            return 1
+        elif exponent % 2 == 0:
+            tmp = share ** (exponent / 2)
+            return tmp * tmp
+        else:
+            return share * (share ** (exponent-1))
+    
     @increment_pc
     def xor(self, share_a, share_b):
         field = getattr(share_a, "field", getattr(share_b, "field", None))
--- a/viff/runtime.py	Wed Dec 10 12:43:05 2008 +0100
+++ b/viff/runtime.py	Wed Dec 10 20:22:20 2008 +0100
@@ -102,6 +102,10 @@
         """Multiplication (reflected argument version)."""
         return self.runtime.mul(other, self)
 
+    def __pow__(self, exponent):
+        """Exponentation to open integer exponents."""
+        return self.runtime.pow(self, exponent)
+
     def __xor__(self, other):
         """Exclusive-or."""
         return self.runtime.xor(self, other)
--- a/viff/test/test_runtime.py	Wed Dec 10 12:43:05 2008 +0100
+++ b/viff/test/test_runtime.py	Wed Dec 10 20:22:20 2008 +0100
@@ -50,6 +50,26 @@
     operator = operator.mul
 
 
+class PowTest(RuntimeTestCase):
+    """Tests power to known integer"""
+
+    a = 1337
+    b = 123
+    
+    def _verify(self, runtime, result, expected):
+        self.assert_type(result, Share)
+        opened = runtime.open(result)
+        opened.addCallback(self.assertEquals, expected)
+        return opened
+
+    @protocol
+    def test_pow(self, runtime):
+        share_a = Share(runtime, self.Zp, self.Zp(self.a))
+        return self._verify(runtime,
+                            share_a ** self.b,
+                            pow(self.a, self.b, self.Zp.modulus))
+
+
 class XorTest(BinaryOperatorTestCase, RuntimeTestCase):
     a = 0
     b = 1