git.distorted.org.uk Git - u/mdw/catacomb/blob - group-exp.c

   1 /* -*-c-*-
   2  *
   3  * $Id: group-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
   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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: group-exp.c,v $
  33  * Revision 1.1  2004/04/01 12:50:09  mdw
  34  * Add cyclic group abstraction, with test code.  Separate off exponentation
  35  * functions for better static linking.  Fix a buttload of bugs on the way.
  36  * Generally ensure that negative exponents do inversion correctly.  Add
  37  * table of standard prime-field subgroups.  (Binary field subgroups are
  38  * currently unimplemented but easy to add if anyone ever finds a good one.)
  39  *
  40  */
  41
  42 /*----- Header files ------------------------------------------------------*/
  43
  44 #include "group.h"
  45 #include "group-exp.h"
  46
  47 /*----- Main code ---------------------------------------------------------*/
  48
  49 /* --- @group_stdexp@ --- *
  50  *
  51  * Arguments:   @group *g@ = abstract group
  52  *              @ge *d@ = destination pointer
  53  *              @ge *x@ = base element
  54  *              @mp *n@ = exponent
  55  *
  56  * Returns:     ---
  57  *
  58  * Use:         Computes %$d = x^n$% efficiently.
  59  */
  60
  61 void group_stdexp(group *gg, ge *d, ge *x, mp *n)
  62 {
  63   ge *t = G_CREATE(gg);
  64
  65   G_COPY(gg, t, x);
  66   MP_SHRINK(n);
  67   G_COPY(gg, d, gg->i);
  68   if (n->f & MP_BURN)
  69     G_BURN(gg, t);
  70   if (MP_LEN(n) == 0)
  71     ;
  72   else {
  73     if (n->f & MP_NEG)
  74       G_INV(gg, t, t);
  75     if (MP_LEN(n) < EXP_THRESH)
  76       EXP_SIMPLE(d, t, n);
  77     else
  78       EXP_WINDOW(d, t, n);
  79   }
  80   G_DESTROY(gg, t);
  81 }
  82
  83 /* --- @group_stdmexp@ --- *
  84  *
  85  * Arguments:   @group *g@ = abstract group
  86  *              @ge *d@ = destination pointer
  87  *              @const group_expfactor *f@ = vector of factors
  88  *              @size_t n@ = number of factors
  89  *
  90  * Returns:     ---
  91  *
  92  * Use:         Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
  93  */
  94
  95 #undef EXP_WINSZ
  96 #define EXP_WINSZ 3
  97
  98 void group_stdmexp(group *gg, ge *d, const group_expfactor *f, size_t n)
  99 {
 100   group_expfactor *ff = xmalloc(n * sizeof(group_expfactor));
 101   size_t i;
 102
 103   for (i = 0; i < n; i++) {
 104     ff[i].base = G_CREATE(gg);
 105     MP_SHRINK(f[i].exp);
 106     if (f[i].exp->f & MP_NEG)
 107       G_INV(gg, ff[i].base, f[i].base);
 108     else
 109       G_COPY(gg, ff[i].base, f[i].base);
 110     if (f[i].exp->f & MP_BURN)
 111       G_BURN(gg, ff[i].base);
 112     ff[i].exp = f[i].exp;
 113   }
 114   G_COPY(gg, d, gg->i);
 115   EXP_SIMUL(d, ff, n);
 116   for (i = 0; i < n; i++)
 117     G_DESTROY(gg, ff[i].base);
 118   xfree(ff);
 119 }
 120
 121 /*----- That's all, folks -------------------------------------------------*/