/* -*-c-*-
*
- * $Id: exp.h,v 1.1.4.1 2004/03/20 00:13:31 mdw Exp $
+ * $Id$
*
* Generalized exponentiation
*
* 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
# 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 --- *
*
for (i = 1; i < vn; i++) \
EXP_DROP(v[i]); \
xfree(v); \
+ xfree(e.s); \
} while (0)
/*----- Functions provided ------------------------------------------------*/