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

   1 /* -*-c-*-
   2  *
   3  * $Id$
   4  *
   5  * Exponentiation for abstract groups
   6  *
   7  * (c) 2004 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  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.
  18  *
  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.
  23  *
  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,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "group.h"
  33 #include "group-exp.h"
  34
  35 /*----- Main code ---------------------------------------------------------*/
  36
  37 /* --- @group_stdexp@ --- *
  38  *
  39  * Arguments:   @group *g@ = abstract group
  40  *              @ge *d@ = destination pointer
  41  *              @ge *x@ = base element
  42  *              @mp *n@ = exponent
  43  *
  44  * Returns:     ---
  45  *
  46  * Use:         Computes %$d = x^n$% efficiently.
  47  */
  48
  49 void group_stdexp(group *gg, ge *d, ge *x, mp *n)
  50 {
  51   ge *t = G_CREATE(gg);
  52
  53   G_COPY(gg, t, x);
  54   MP_SHRINK(n);
  55   G_COPY(gg, d, gg->i);
  56   if (n->f & MP_BURN)
  57     G_BURN(gg, t);
  58   if (MP_ZEROP(n))
  59     ;
  60   else {
  61     if (MP_NEGP(n))
  62       G_INV(gg, t, t);
  63     if (MP_LEN(n) < EXP_THRESH)
  64       EXP_SIMPLE(d, t, n);
  65     else
  66       EXP_WINDOW(d, t, n);
  67   }
  68   G_DESTROY(gg, t);
  69 }
  70
  71 /* --- @group_stdmexp@ --- *
  72  *
  73  * Arguments:   @group *g@ = abstract group
  74  *              @ge *d@ = destination pointer
  75  *              @const group_expfactor *f@ = vector of factors
  76  *              @size_t n@ = number of factors
  77  *
  78  * Returns:     ---
  79  *
  80  * Use:         Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
  81  */
  82
  83 #undef EXP_WINSZ
  84 #define EXP_WINSZ 3
  85
  86 void group_stdmexp(group *gg, ge *d, const group_expfactor *f, size_t n)
  87 {
  88   group_expfactor *ff = xmalloc(n * sizeof(group_expfactor));
  89   size_t i;
  90
  91   for (i = 0; i < n; i++) {
  92     ff[i].base = G_CREATE(gg);
  93     MP_SHRINK(f[i].exp);
  94     if (MP_NEGP(f[i].exp))
  95       G_INV(gg, ff[i].base, f[i].base);
  96     else
  97       G_COPY(gg, ff[i].base, f[i].base);
  98     if (f[i].exp->f & MP_BURN)
  99       G_BURN(gg, ff[i].base);
 100     ff[i].exp = f[i].exp;
 101   }
 102   G_COPY(gg, d, gg->i);
 103   EXP_SIMUL(d, ff, n);
 104   for (i = 0; i < n; i++)
 105     G_DESTROY(gg, ff[i].base);
 106   xfree(ff);
 107 }
 108
 109 /*----- That's all, folks -------------------------------------------------*/