3 * $Id: exp.h,v 1.1 2001/06/16 13:00:59 mdw Exp $
5 * Generalized exponentiation
7 * (c) 2001 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 2001/06/16 13:00:59 mdw
34 * New generic exponentation code. Includes sliding-window simultaneous
40 # error "Multiple inclusion of <catacomb/exp.h>"
43 #define CATACOMB_EXP_H
49 /*----- Header files ------------------------------------------------------*/
53 #include <mLib/alloc.h>
59 /*----- Data structures ---------------------------------------------------*/
61 typedef struct exp_simulscan
{
67 typedef struct exp_simul
{
73 /*----- Macros provided ---------------------------------------------------*/
75 /* --- Parameters --- */
77 #ifndef EXP_WINSZ /* Sliding window size */
78 # define EXP_WINSZ 4 /* Predefine if you need to */
81 /* --- These are determined from the window size --- */
83 #define EXP_TABSZ (1 << EXP_WINSZ)
84 #define EXP_THRESH (((MPW_BITS / EXP_WINSZ) << 2) + 1)
86 /* --- Required operations --- *
88 * The macros here are independent of the underlying group elements. You
89 * must provide the necessary group operations and other definitions. The
90 * group operation is assumed to be written multiplicatively.
92 * @EXP_TYPE@ The type of a group element, e.g., @mp *@.
94 * @EXP_COPY(d, x)@ Makes @d@ be a copy of @x@.
96 * @EXP_DROP(x)@ Discards the element @x@, reclaiming any
99 * @EXP_MUL(a, x)@ Multiplies @a@ by @x@ (writing the result
102 * @EXP_SQR(a)@ Multiplies @a@ by itself.
104 * @EXP_SETMUL(d, x, y)@ Sets @d@ to be the product of @x@ and @y@.
105 * The value @d@ has not been initialized.
107 * @EXP_SETSQR(d, x)@ Sets @d@ to be the square of @x@.
109 * Only @EXP_TYPE@, @EXP_MUL@ and @EXP_SQR@ are required for simple
110 * exponentation. Sliding window and simultaneous exponentation require all
115 # error "EXP_TYPE not defined for <catacomb/exp.h>"
118 /* --- @EXP_SIMPLE@ --- *
120 * Arguments: @a@ = the result object, initially a multiplicative identity
121 * @g@ = the object to exponentiate
122 * @x@ = the exponent, as a multiprecision integer
124 * Use: Performs a simple left-to-right exponentiation. At the end
125 * of the code, the answer is left in @a@; @g@ and @x@ are
129 #define EXP_SIMPLE(a, g, x) do { \
133 /* --- Begin scanning --- */ \
136 if (!MP_RSTEP(&sc)) \
137 goto exp_simple_exit; \
138 while (!MP_RBIT(&sc)) \
141 /* --- Do the main body of the work --- */ \
147 if (!MP_RSTEP(&sc)) \
148 goto exp_simple_done; \
153 while (sq--) EXP_SQR(a); \
156 /* --- Do a final round of squaring --- */ \
159 while (sq--) EXP_SQR(a); \
163 /* --- @EXP_WINDOW@ --- *
165 * Arguments: @a@ = the result object, initially a multiplicative identity
166 * @g@ = the object to exponentiate
167 * @x@ = the exponent, as a multiprecision integer
169 * Use: Performs a sliding-window exponentiation. At the end of the
170 * code, the answer is left in @a@; @g@ and @x@ are unchanged.
173 #define EXP_WINDOW(a, g, x) do { \
176 unsigned i, sq = 0; \
179 /* --- Get going --- */ \
182 if (!MP_RSTEP(&sc)) \
183 goto exp_window_exit; \
185 /* --- Do the precomputation --- */ \
188 v = xmalloc(EXP_TABSZ * sizeof(EXP_TYPE)); \
190 for (i = 1; i < EXP_TABSZ; i++) \
191 EXP_SETMUL(v[i], v[i - 1], g2); \
194 /* --- Skip top-end zero bits --- * \
196 * If the initial step worked, there must be a set bit somewhere, so \
197 * keep stepping until I find it. \
200 while (!MP_RBIT(&sc)) \
203 /* --- Now for the main work --- */ \
209 /* --- The next bit is set, so read a window index --- * \
211 * Reset @i@ to zero and increment @sq@. Then, until either I read \
212 * @WINSZ@ bits or I run out of bits, scan in a bit: if it's clear, \
213 * bump the @z@ counter; if it's set, push a set bit into @i@, \
214 * shift it over by @z@ bits, bump @sq@ by @z + 1@ and clear @z@. \
215 * By the end of this palaver, @i@ is an index to the precomputed \
221 while (l < EXP_WINSZ && MP_RSTEP(&sc)) { \
226 i = ((i << 1) | 1) << z; \
232 /* --- Do the squaring --- * \
234 * Remember that @sq@ carries over from the zero-skipping stuff \
238 while (sq--) EXP_SQR(a); \
240 /* --- Do the multiply --- */ \
244 /* --- Now grind along through the rest of the bits --- */ \
248 if (!MP_RSTEP(&sc)) \
249 goto exp_window_done; \
256 /* --- Do a final round of squaring --- */ \
259 while (sq--) EXP_SQR(a); \
260 for (i = 0; i < EXP_TABSZ; i++) \
266 /* --- @EXP_SIMUL@ --- *
268 * Arguments: @a@ = the result object, initially a multiplicative identity
269 * @f@ = pointer to a vector of base/exp pairs
270 * @n@ = the number of base/exp pairs
272 * Use: Performs a simultaneous sliding-window exponentiation. The
273 * @f@ table is an array of structures containing members @base@
274 * of type @EXP_TYPE@, and @exp@ of type @mp *@.
277 #define EXP_SIMUL(a, f, n) do { \
278 size_t i, j, jj, k; \
279 size_t vn = 1 << (EXP_WINSZ * n), m = (1 << n) - 1; \
280 EXP_TYPE *v = xmalloc(vn * sizeof(EXP_TYPE)); \
284 /* --- Fill in the precomputed table --- */ \
287 for (i = 0; i < n; i++) { \
288 EXP_COPY(v[j], f[n - 1 - i].base); \
293 for (; i < k; i++) { \
294 EXP_SETSQR(v[j], v[jj]); \
297 for (i = 1; i < vn; i <<= 1) { \
298 for (j = 1; j < i; j++) \
299 EXP_SETMUL(v[j + i], v[j], v[i]); \
302 /* --- Set up the bitscanners --- * \
304 * Got to use custom scanners, to keep them all in sync. \
309 e.s = xmalloc(n * sizeof(*e.s)); \
311 for (i = 0; i < n; i++) { \
312 MP_SHRINK(f[i].exp); \
313 e.s[i].len = MP_LEN(f[i].exp); \
314 e.s[i].v = f[i].exp->v; \
315 if (e.s[i].len > e.o) \
319 /* --- Skip as far as a nonzero column in the exponent matrix --- */ \
323 goto exp_simul_done; \
324 i = exp_simulnext(&e, 0); \
325 } while (!(i & m)); \
327 /* --- Now for the main work --- */ \
333 /* --- Just read a nonzero column, so read a window index --- * \
335 * Clear high bits of @i@ and increment @sq@. Then, until either I \
336 * read @WINSZ@ columns or I run out, scan in a column and append \
337 * it to @i@. If it's zero, bump the @z@ counter; if it's nonzero, \
338 * bump @sq@ by @z + 1@ and clear @z@. By the end of this palaver, \
339 * @i@ is an index to the precomputed value in @v@, followed by \
340 * @n * z@ zero bits. \
344 while (l < EXP_WINSZ && (e.o || e.b)) { \
346 i = exp_simulnext(&e, i); \
355 /* --- Do the squaring --- * \
357 * Remember that @sq@ carries over from the zero-skipping stuff \
361 while (sq--) EXP_SQR(a); \
363 /* --- Do the multiply --- */ \
368 /* --- Now grind along through the rest of the bits --- */ \
373 goto exp_simul_done; \
374 if ((i = exp_simulnext(&e, 0)) != 0) \
380 /* --- Do a final round of squaring --- */ \
383 while (sq--) EXP_SQR(a); \
384 for (i = 1; i < vn; i++) \
389 /*----- Functions provided ------------------------------------------------*/
391 /* --- @exp_simulnext@ --- *
393 * Arguments: @exp_simul *e@ = pointer to state structure
394 * @size_t x@ = a current accumulator
396 * Returns: The next column of bits.
398 * Use: Scans the next column of bits for a simultaneous
402 extern size_t exp_simulnext(exp_simul */
*e*/
, size_t /*x*/);
404 /*----- That's all, folks -------------------------------------------------*/