Minor performance tweak: use Barrett reduction rather than Montgomery.

Fast secret sharing isn't done here, though: see `gfshare' instead.

diff --git a/share.c b/share.c
index f450934..d427706 100644 (file)
--- a/share.c
+++ b/share.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: share.c,v 1.1 2000/06/17 12:09:38 mdw Exp $
+ * $Id: share.c,v 1.2 2000/06/18 23:05:19 mdw Exp $
  *
  * Shamir's secret sharing
  *
@@ -30,6 +30,10 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: share.c,v $
+ * Revision 1.2  2000/06/18 23:05:19  mdw
+ * Minor performance tweak: use Barrett reduction rather than Montgomery.
+ * Fast secret sharing isn't done here, though: see `gfshare' instead.
+ *
  * Revision 1.1  2000/06/17 12:09:38  mdw
  * Shamir's secret sharing system.
  *
@@ -44,7 +48,7 @@
 #include "grand.h"
 #include "mp.h"
 #include "mpint.h"
-#include "mpmont.h"
+#include "mpbarrett.h"
 #include "mprand.h"
 #include "pgen.h"
 #include "rabin.h"
@@ -133,8 +137,9 @@ void share_mkshares(share *s, grand *r)
 {
   mp **v;
   unsigned i;
-  mp *u;
-  mpmont mm;
+  mp u;
+  mpw uw;
+  mpbarrett mb;
 
   /* --- If there's no prime, construct one --- */
 
@@ -152,26 +157,27 @@ void share_mkshares(share *s, grand *r)
 
   /* --- Construct the coefficients --- */
 
-  mpmont_create(&mm, s->p);
+  mpbarrett_create(&mb, s->p);
   v = xmalloc(s->t * sizeof(mp *));
   for (i = 0; i < s->t - 1; i++)
     v[i] = mprand_range(MP_NEW, s->p, r, 0);
-  v[s->t - 1] = mpmont_mul(&mm, MP_NEW, s->s, mm.r2);
+  v[s->t - 1] = s->s;
 
   /* --- Construct the shares --- */
 
   if (!s->v)
     s->v = xmalloc(s->n * sizeof(share_pt));
 
-  u = mp_copy(mm.r);
-  for (i = 0; i < s->n; i++) {
+  mp_build(&u, &uw, &uw + 1);
+  for (uw = 1; uw <= s->n; uw++) {
     mp *m = MP_ZERO;
     unsigned j;
 
     /* --- Evaluate the polynomial at %$x = i + 1$% --- */
 
     for (j = 0; j < s->t; j++) {
-      m = mpmont_mul(&mm, m, m, u);
+      m = mp_mul(m, m, &u);
+      m = mpbarrett_reduce(&mb, m, m);
       m = mp_add(m, m, v[j]);
       if (MP_CMP(m, >=, s->p))
        m = mp_sub(m, m, s->p);
@@ -179,22 +185,15 @@ void share_mkshares(share *s, grand *r)
 
     /* --- Reduce the final result --- */
 
-    s->v[i].x = i;
-    s->v[i].y = mpmont_reduce(&mm, m, m);
-
-    /* --- Compute the next point in Montgomery space --- */
-
-    u = mp_add(u, u, mm.r);
-    if (MP_CMP(u, >=, s->p))
-      u = mp_sub(u, u, s->p);
+    s->v[uw - 1].x = uw - 1;
+    s->v[uw - 1].y = m;
   }
-  mpmont_destroy(&mm);
+  mpbarrett_destroy(&mb);
 
   /* --- Dispose of various bits of old rubbish --- */
 
-  for (i = 0; i < s->t; i++)
+  for (i = 0; i < s->t - 1; i++)
     mp_drop(v[i]);
-  mp_drop(u);
   xfree(v);
 }
 
@@ -244,9 +243,10 @@ unsigned share_add(share *s, unsigned x, mp *y)
 mp *share_combine(share *s)
 {
   mp *a = MP_ZERO;
-  mpmont mm;
+  mpbarrett mb;
   unsigned i, j;
-  mp *ii = MP_NEW, *jj = MP_NEW;
+  mp ii, jj;
+  mpw iiw, jjw;
   mp *m = MP_NEW;
 
   /* --- Sanity checking --- */
@@ -255,43 +255,43 @@ mp *share_combine(share *s)
 
   /* --- Initialization --- */
 
-  mpmont_create(&mm, s->p);
+  mpbarrett_create(&mb, s->p);
+  mp_build(&ii, &iiw, &iiw + 1);
+  mp_build(&jj, &jjw, &jjw + 1);
 
   /* --- Grind through the shares --- */
 
   for (i = 0; i < s->t; i++) {
-    mp *c = mp_copy(mm.r);
+    mp *c = MP_ONE;
 
-    ii = mp_fromuint(ii, s->v[i].x + 1);
+    iiw = s->v[i].x + 1;
     for (j = 0; j < s->t; j++) {
       if (i == j)
        continue;
-      jj = mp_fromuint(jj, s->v[j].x + 1);
+      jjw = s->v[j].x + 1;
       if (s->v[j].x >= s->v[i].x)
-       m = mp_sub(m, jj, ii);
+       m = mp_sub(m, &jj, &ii);
       else {
-       m = mp_sub(m, ii, jj);
+       m = mp_sub(m, &ii, &jj);
        m = mp_sub(m, s->p, m);
       }
-      jj = mpmont_mul(&mm, jj, jj, mm.r2);
       mp_gcd(0, 0, &m, s->p, m);
-      m = mpmont_mul(&mm, m, m, mm.r2);
-      m = mpmont_mul(&mm, m, m, jj);
-      c = mpmont_mul(&mm, c, c, m);
+      c = mp_mul(c, c, &jj);
+      c = mpbarrett_reduce(&mb, c, c);
+      c = mp_mul(c, c, m);
+      c = mpbarrett_reduce(&mb, c, c);
     }
-    m = mpmont_mul(&mm, m, s->v[i].y, mm.r2);
-    c = mpmont_mul(&mm, c, c, m);
+    c = mp_mul(c, c, s->v[i].y);
+    c = mpbarrett_reduce(&mb, c, c);
     a = mp_add(a, a, c);
     mp_drop(c);
   }
 
-  a = mpmont_reduce(&mm, a, a);
+  a = mpbarrett_reduce(&mb, a, a);
   s->s = mp_copy(a);
-  mp_drop(ii);
-  if (jj)
-    mp_drop(jj);
-  mp_drop(m);
-  mpmont_destroy(&mm);
+  if (m)
+    mp_drop(m);
+  mpbarrett_destroy(&mb);
   return (a);
 }