chiark - git - mdw - catacomb/blob - math/group-exp.c

   1 /* -*-c-*-
   2  *
   3  * Exponentiation for abstract groups
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "group.h"
  31 #include "group-exp.h"
  32
  33 /*----- Main code ---------------------------------------------------------*/
  34
  35 /* --- @group_stdexp@ --- *
  36  *
  37  * Arguments:   @group *g@ = abstract group
  38  *              @ge *d@ = destination pointer
  39  *              @ge *x@ = base element
  40  *              @mp *n@ = exponent
  41  *
  42  * Returns:     ---
  43  *
  44  * Use:         Computes %$d = x^n$% efficiently.
  45  */
  46
  47 void group_stdexp(group *gg, ge *d, ge *x, mp *n)
  48 {
  49   ge *t = G_CREATE(gg);
  50
  51   G_COPY(gg, t, x);
  52   MP_SHRINK(n);
  53   G_COPY(gg, d, gg->i);
  54   if (n->f & MP_BURN)
  55     G_BURN(gg, t);
  56   if (MP_ZEROP(n))
  57     ;
  58   else {
  59     if (MP_NEGP(n))
  60       G_INV(gg, t, t);
  61     if (MP_LEN(n) < EXP_THRESH)
  62       EXP_SIMPLE(d, t, n);
  63     else
  64       EXP_WINDOW(d, t, n);
  65   }
  66   G_DESTROY(gg, t);
  67 }
  68
  69 /* --- @group_stdmexp@ --- *
  70  *
  71  * Arguments:   @group *g@ = abstract group
  72  *              @ge *d@ = destination pointer
  73  *              @const group_expfactor *f@ = vector of factors
  74  *              @size_t n@ = number of factors
  75  *
  76  * Returns:     ---
  77  *
  78  * Use:         Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
  79  */
  80
  81 #undef EXP_WINSZ
  82 #define EXP_WINSZ 3
  83
  84 void group_stdmexp(group *gg, ge *d, const group_expfactor *f, size_t n)
  85 {
  86   group_expfactor *ff = xmalloc(n * sizeof(group_expfactor));
  87   size_t i;
  88
  89   for (i = 0; i < n; i++) {
  90     ff[i].base = G_CREATE(gg);
  91     MP_SHRINK(f[i].exp);
  92     if (MP_NEGP(f[i].exp))
  93       G_INV(gg, ff[i].base, f[i].base);
  94     else
  95       G_COPY(gg, ff[i].base, f[i].base);
  96     if (f[i].exp->f & MP_BURN)
  97       G_BURN(gg, ff[i].base);
  98     ff[i].exp = f[i].exp;
  99   }
 100   G_COPY(gg, d, gg->i);
 101   EXP_SIMUL(d, ff, n);
 102   for (i = 0; i < n; i++)
 103     G_DESTROY(gg, ff[i].base);
 104   xfree(ff);
 105 }
 106
 107 /*----- That's all, folks -------------------------------------------------*/