Major and incompatible overhaul of key_data representation. Fix leaks.

[u/mdw/catacomb] / exp.h

diff --git a/exp.h b/exp.h
index fc9e3a9..e729e8c 100644 (file)
--- a/exp.h
+++ b/exp.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: exp.h,v 1.1.4.1 2004/03/20 00:13:31 mdw Exp $
+ * $Id$
  *
  * Generalized exponentiation
  *
@@ -27,18 +27,6 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: exp.h,v $
- * Revision 1.1.4.1  2004/03/20 00:13:31  mdw
- * Projective coordinates for prime curves
- *
- * Revision 1.1  2001/06/16 13:00:59  mdw
- * New generic exponentation code.  Includes sliding-window simultaneous
- * exponentiation.
- *
- */
-
 #ifdef CATACOMB_EXP_H
 #  error "Multiple inclusion of <catacomb/exp.h>"
 #endif
@@ -81,10 +69,19 @@ typedef struct exp_simul {
 #  define EXP_WINSZ 4                  /* Predefine if you need to */
 #endif
 
-/* --- These are determined from the window size --- */
+/* --- These are determined from the window size --- *
+ *
+ * Given a %$k$%-bit exponent, I expect to do %$k/2$% multiplies if I use the
+ * simple way.  If I use an n-bit sliding window, then I do %$2^n$%
+ * multiplies up front, but I only do %$(2^n - 1)/2^n k/n$% multiplies for
+ * the exponentiation.  This is a win when
+ *
+ *   %$k \ge \frac{n 2^{n+1}}{n - 2}$%
+ */
 
 #define EXP_TABSZ (1 << EXP_WINSZ)
-#define EXP_THRESH (((MPW_BITS / EXP_WINSZ) << 2) + 1)
+#define EXP_THRESH                                                     \
+    ((EXP_WINSZ * (2 << EXP_WINSZ))/((EXP_WINSZ - 2) * MPW_BITS))
 
 /* --- Required operations --- *
  *
@@ -400,6 +397,7 @@ exp_simul_done:                                                             \
   for (i = 1; i < vn; i++)                                             \
     EXP_DROP(v[i]);                                                    \
   xfree(v);                                                            \
+  xfree(e.s);                                                          \
 } while (0)
 
 /*----- Functions provided ------------------------------------------------*/