Compute square roots in a prime field.

[u/mdw/catacomb] / gfshare.h

diff --git a/gfshare.h b/gfshare.h
index b0aca05..4141156 100644 (file)
--- a/gfshare.h
+++ b/gfshare.h
@@ -1,8 +1,8 @@
 /* -*-c-*-
  *
- * $Id: gfshare.h,v 1.1 2000/06/17 10:56:30 mdw Exp $
+ * $Id: gfshare.h,v 1.3 2000/06/18 23:12:15 mdw Exp $
  *
- * Secret sharing over %$\gf(2^8)$%
+ * Secret sharing over %$\gf{2^8}$%
  *
  * (c) 2000 Straylight/Edgeware
  */
@@ -30,11 +30,34 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: gfshare.h,v $
+ * Revision 1.3  2000/06/18 23:12:15  mdw
+ * Change typesetting of Galois Field names.
+ *
+ * Revision 1.2  2000/06/17 11:05:27  mdw
+ * Add a commentary on the system.
+ *
  * Revision 1.1  2000/06/17 10:56:30  mdw
  * Fast but nonstandard secret sharing system.
  *
  */
 
+/*----- Notes on the system -----------------------------------------------*
+ *
+ * This uses a variant of Shamir's secret sharing system.  Shamir's original
+ * system used polynomials modulo a large prime.  This implementation instead
+ * uses the field %$\gf{2^8}$%, represented by
+ *
+ *   %$\gf{2}[x]/(x^8 + x^4 + x^3 + x^2 + 1)$%
+ *
+ * and shares each byte of the secret independently.  It is therefore limited
+ * to 255 players, although this probably isn't a serious limitation in
+ * practice.
+ *
+ * Share creation and reconstruction is extremely efficient.  Contrast the
+ * performance of the straightforward implementation based on multiprecision
+ * arithmetic.
+ */
+
 #ifndef CATACOMB_GFSHARE_H
 #define CATACOMB_GFSHARE_H