/* -*-c-*-
*
- * $Id: exp.h,v 1.1 2001/06/16 13:00:59 mdw Exp $
+ * $Id: exp.h,v 1.3 2004/03/22 02:19:10 mdw Exp $
*
* Generalized exponentiation
*
/*----- Revision history --------------------------------------------------*
*
* $Log: exp.h,v $
+ * Revision 1.3 2004/03/22 02:19:10 mdw
+ * Rationalise the sliding-window threshold. Drop guarantee that right
+ * arguments to EC @add@ are canonical, and fix up projective implementations
+ * to cope.
+ *
+ * Revision 1.2 2004/03/21 22:52:06 mdw
+ * Merge and close elliptic curve branch.
+ *
+ * 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.
# 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 --- *
*
* @EXP_MUL(a, x)@ Multiplies @a@ by @x@ (writing the result
* back to @a@).
*
+ * @EXP_FIX(x)@ Makes @x@ be a canonical representation of
+ * its value. All multiplications have the
+ * right argument canonical.
+ *
* @EXP_SQR(a)@ Multiplies @a@ by itself.
*
* @EXP_SETMUL(d, x, y)@ Sets @d@ to be the product of @x@ and @y@.
\
/* --- Do the main body of the work --- */ \
\
+ EXP_FIX(g); \
for (;;) { \
EXP_MUL(a, g); \
sq = 0; \
\
/* --- Do the precomputation --- */ \
\
+ EXP_FIX(g); \
EXP_SETSQR(g2, g); \
+ EXP_FIX(g2); \
v = xmalloc(EXP_TABSZ * sizeof(EXP_TYPE)); \
EXP_COPY(v[0], g); \
- for (i = 1; i < EXP_TABSZ; i++) \
+ for (i = 1; i < EXP_TABSZ; i++) { \
EXP_SETMUL(v[i], v[i - 1], g2); \
+ EXP_FIX(v[i]); \
+ } \
EXP_DROP(g2); \
\
/* --- Skip top-end zero bits --- * \
j = 1; \
for (i = 0; i < n; i++) { \
EXP_COPY(v[j], f[n - 1 - i].base); \
+ EXP_FIX(v[j]); \
j <<= 1; \
} \
k = n * EXP_WINSZ; \
jj = 1; \
for (; i < k; i++) { \
EXP_SETSQR(v[j], v[jj]); \
+ EXP_FIX(v[j]); \
j <<= 1; jj <<= 1; \
} \
for (i = 1; i < vn; i <<= 1) { \
- for (j = 1; j < i; j++) \
+ for (j = 1; j < i; j++) { \
EXP_SETMUL(v[j + i], v[j], v[i]); \
+ EXP_FIX(v[j + i]); \
+ } \
} \
\
/* --- Set up the bitscanners --- * \
\
exp_simul_done: \
while (sq--) EXP_SQR(a); \
- for (i = 1; i < vn; i++) \
+ for (i = 1; i < vn; i++) \
EXP_DROP(v[i]); \
xfree(v); \
} while (0)