+++ /dev/null
-/* -*-c-*-
- *
- * $Id$
- *
- * Generalized exponentiation
- *
- * (c) 2001 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * Catacomb is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * Catacomb is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with Catacomb; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-#ifdef CATACOMB_EXP_H
-# error "Multiple inclusion of <catacomb/exp.h>"
-#endif
-
-#define CATACOMB_EXP_H
-
-#ifdef __cplusplus
- extern "C" {
-#endif
-
-/*----- Header files ------------------------------------------------------*/
-
-#include <stddef.h>
-
-#include <mLib/alloc.h>
-
-#ifndef CATACOMB_MP_H
-# include "mp.h"
-#endif
-
-/*----- Data structures ---------------------------------------------------*/
-
-typedef struct exp_simulscan {
- mpw w;
- size_t len;
- const mpw *v;
-} exp_simulscan;
-
-typedef struct exp_simul {
- unsigned b;
- size_t o, n;
- exp_simulscan *s;
-} exp_simul;
-
-/*----- Macros provided ---------------------------------------------------*/
-
-/* --- Parameters --- */
-
-#ifndef EXP_WINSZ /* Sliding window size */
-# define EXP_WINSZ 4 /* Predefine if you need to */
-#endif
-
-/* --- 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 \
- ((EXP_WINSZ * (2 << EXP_WINSZ))/((EXP_WINSZ - 2) * MPW_BITS))
-
-/* --- Required operations --- *
- *
- * The macros here are independent of the underlying group elements. You
- * must provide the necessary group operations and other definitions. The
- * group operation is assumed to be written multiplicatively.
- *
- * @EXP_TYPE@ The type of a group element, e.g., @mp *@.
- *
- * @EXP_COPY(d, x)@ Makes @d@ be a copy of @x@.
- *
- * @EXP_DROP(x)@ Discards the element @x@, reclaiming any
- * memory it used.
- *
- * @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@.
- * The value @d@ has not been initialized.
- *
- * @EXP_SETSQR(d, x)@ Sets @d@ to be the square of @x@.
- *
- * Only @EXP_TYPE@, @EXP_MUL@ and @EXP_SQR@ are required for simple
- * exponentation. Sliding window and simultaneous exponentation require all
- * of the operations.
- */
-
-#ifndef EXP_TYPE
-# error "EXP_TYPE not defined for <catacomb/exp.h>"
-#endif
-
-/* --- @EXP_SIMPLE@ --- *
- *
- * Arguments: @a@ = the result object, initially a multiplicative identity
- * @g@ = the object to exponentiate
- * @x@ = the exponent, as a multiprecision integer
- *
- * Use: Performs a simple left-to-right exponentiation. At the end
- * of the code, the answer is left in @a@; @g@ and @x@ are
- * unchanged.
- */
-
-#define EXP_SIMPLE(a, g, x) do { \
- mpscan sc; \
- unsigned sq = 0; \
- \
- /* --- Begin scanning --- */ \
- \
- mp_rscan(&sc, x); \
- if (!MP_RSTEP(&sc)) \
- goto exp_simple_exit; \
- while (!MP_RBIT(&sc)) \
- MP_RSTEP(&sc); \
- \
- /* --- Do the main body of the work --- */ \
- \
- EXP_FIX(g); \
- for (;;) { \
- EXP_MUL(a, g); \
- sq = 0; \
- for (;;) { \
- if (!MP_RSTEP(&sc)) \
- goto exp_simple_done; \
- sq++; \
- if (MP_RBIT(&sc)) \
- break; \
- } \
- while (sq--) EXP_SQR(a); \
- } \
- \
- /* --- Do a final round of squaring --- */ \
- \
-exp_simple_done: \
- while (sq--) EXP_SQR(a); \
-exp_simple_exit:; \
-} while (0)
-
-/* --- @EXP_WINDOW@ --- *
- *
- * Arguments: @a@ = the result object, initially a multiplicative identity
- * @g@ = the object to exponentiate
- * @x@ = the exponent, as a multiprecision integer
- *
- * Use: Performs a sliding-window exponentiation. At the end of the
- * code, the answer is left in @a@; @g@ and @x@ are unchanged.
- */
-
-#define EXP_WINDOW(a, g, x) do { \
- EXP_TYPE *v; \
- EXP_TYPE g2; \
- unsigned i, sq = 0; \
- mpscan sc; \
- \
- /* --- Get going --- */ \
- \
- mp_rscan(&sc, x); \
- if (!MP_RSTEP(&sc)) \
- goto exp_window_exit; \
- \
- /* --- 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++) { \
- EXP_SETMUL(v[i], v[i - 1], g2); \
- EXP_FIX(v[i]); \
- } \
- EXP_DROP(g2); \
- \
- /* --- Skip top-end zero bits --- * \
- * \
- * If the initial step worked, there must be a set bit somewhere, so \
- * keep stepping until I find it. \
- */ \
- \
- while (!MP_RBIT(&sc)) \
- MP_RSTEP(&sc); \
- \
- /* --- Now for the main work --- */ \
- \
- for (;;) { \
- unsigned l = 1; \
- unsigned z = 0; \
- \
- /* --- The next bit is set, so read a window index --- * \
- * \
- * Reset @i@ to zero and increment @sq@. Then, until either I read \
- * @WINSZ@ bits or I run out of bits, scan in a bit: if it's clear, \
- * bump the @z@ counter; if it's set, push a set bit into @i@, \
- * shift it over by @z@ bits, bump @sq@ by @z + 1@ and clear @z@. \
- * By the end of this palaver, @i@ is an index to the precomputed \
- * value in @v@. \
- */ \
- \
- i = 0; \
- sq++; \
- while (l < EXP_WINSZ && MP_RSTEP(&sc)) { \
- l++; \
- if (!MP_RBIT(&sc)) \
- z++; \
- else { \
- i = ((i << 1) | 1) << z; \
- sq += z + 1; \
- z = 0; \
- } \
- } \
- \
- /* --- Do the squaring --- * \
- * \
- * Remember that @sq@ carries over from the zero-skipping stuff \
- * below. \
- */ \
- \
- while (sq--) EXP_SQR(a); \
- \
- /* --- Do the multiply --- */ \
- \
- EXP_MUL(a, v[i]); \
- \
- /* --- Now grind along through the rest of the bits --- */ \
- \
- sq = z; \
- for (;;) { \
- if (!MP_RSTEP(&sc)) \
- goto exp_window_done; \
- if (MP_RBIT(&sc)) \
- break; \
- sq++; \
- } \
- } \
- \
- /* --- Do a final round of squaring --- */ \
- \
-exp_window_done: \
- while (sq--) EXP_SQR(a); \
- for (i = 0; i < EXP_TABSZ; i++) \
- EXP_DROP(v[i]); \
- xfree(v); \
-exp_window_exit:; \
-} while (0)
-
-/* --- @EXP_SIMUL@ --- *
- *
- * Arguments: @a@ = the result object, initially a multiplicative identity
- * @f@ = pointer to a vector of base/exp pairs
- * @n@ = the number of base/exp pairs
- *
- * Use: Performs a simultaneous sliding-window exponentiation. The
- * @f@ table is an array of structures containing members @base@
- * of type @EXP_TYPE@, and @exp@ of type @mp *@.
- */
-
-#define EXP_SIMUL(a, f, n) do { \
- size_t i, j, jj, k; \
- size_t vn = 1 << (EXP_WINSZ * n), m = (1 << n) - 1; \
- EXP_TYPE *v = xmalloc(vn * sizeof(EXP_TYPE)); \
- exp_simul e; \
- unsigned sq = 0; \
- \
- /* --- Fill in the precomputed table --- */ \
- \
- 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++) { \
- EXP_SETMUL(v[j + i], v[j], v[i]); \
- EXP_FIX(v[j + i]); \
- } \
- } \
- \
- /* --- Set up the bitscanners --- * \
- * \
- * Got to use custom scanners, to keep them all in sync. \
- */ \
- \
- e.n = n; \
- e.b = 0; \
- e.s = xmalloc(n * sizeof(*e.s)); \
- e.o = 0; \
- for (i = 0; i < n; i++) { \
- MP_SHRINK(f[i].exp); \
- e.s[i].len = MP_LEN(f[i].exp); \
- e.s[i].v = f[i].exp->v; \
- if (e.s[i].len > e.o) \
- e.o = e.s[i].len; \
- } \
- \
- /* --- Skip as far as a nonzero column in the exponent matrix --- */ \
- \
- do { \
- if (!e.o && !e.b) \
- goto exp_simul_done; \
- i = exp_simulnext(&e, 0); \
- } while (!(i & m)); \
- \
- /* --- Now for the main work --- */ \
- \
- for (;;) { \
- unsigned l = 1; \
- unsigned z = 0; \
- \
- /* --- Just read a nonzero column, so read a window index --- * \
- * \
- * Clear high bits of @i@ and increment @sq@. Then, until either I \
- * read @WINSZ@ columns or I run out, scan in a column and append \
- * it to @i@. If it's zero, bump the @z@ counter; if it's nonzero, \
- * bump @sq@ by @z + 1@ and clear @z@. By the end of this palaver, \
- * @i@ is an index to the precomputed value in @v@, followed by \
- * @n * z@ zero bits. \
- */ \
- \
- sq++; \
- while (l < EXP_WINSZ && (e.o || e.b)) { \
- l++; \
- i = exp_simulnext(&e, i); \
- if (!(i & m)) \
- z++; \
- else { \
- sq += z + 1; \
- z = 0; \
- } \
- } \
- \
- /* --- Do the squaring --- * \
- * \
- * Remember that @sq@ carries over from the zero-skipping stuff \
- * below. \
- */ \
- \
- while (sq--) EXP_SQR(a); \
- \
- /* --- Do the multiply --- */ \
- \
- i >>= (z * n); \
- EXP_MUL(a, v[i]); \
- \
- /* --- Now grind along through the rest of the bits --- */ \
- \
- sq = z; \
- for (;;) { \
- if (!e.o && !e.b) \
- goto exp_simul_done; \
- if ((i = exp_simulnext(&e, 0)) != 0) \
- break; \
- sq++; \
- } \
- } \
- \
- /* --- Do a final round of squaring --- */ \
- \
-exp_simul_done: \
- while (sq--) EXP_SQR(a); \
- for (i = 1; i < vn; i++) \
- EXP_DROP(v[i]); \
- xfree(v); \
- xfree(e.s); \
-} while (0)
-
-/*----- Functions provided ------------------------------------------------*/
-
-/* --- @exp_simulnext@ --- *
- *
- * Arguments: @exp_simul *e@ = pointer to state structure
- * @size_t x@ = a current accumulator
- *
- * Returns: The next column of bits.
- *
- * Use: Scans the next column of bits for a simultaneous
- * exponentiation.
- */
-
-extern size_t exp_simulnext(exp_simul */*e*/, size_t /*x*/);
-
-/*----- That's all, folks -------------------------------------------------*/
-
-#ifdef __cplusplus
- }
-#endif
~mdw / catacomb / blobdiff