chiark / gitweb /
math/mpx-mul4-test.c: Set `dstr' length correctly in conversion function.
[catacomb] / 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 -------------------------------------------------*/