34e4f738 |
1 | /* -*-c-*- |
34e4f738 |
2 | * |
3 | * Exponentiation for abstract groups |
4 | * |
5 | * (c) 2004 Straylight/Edgeware |
6 | */ |
7 | |
45c0fd36 |
8 | /*----- Licensing notice --------------------------------------------------* |
34e4f738 |
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. |
45c0fd36 |
16 | * |
34e4f738 |
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. |
45c0fd36 |
21 | * |
34e4f738 |
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 | |
34e4f738 |
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); |
a69a3efd |
56 | if (MP_ZEROP(n)) |
34e4f738 |
57 | ; |
58 | else { |
a69a3efd |
59 | if (MP_NEGP(n)) |
34e4f738 |
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); |
a69a3efd |
92 | if (MP_NEGP(f[i].exp)) |
34e4f738 |
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 -------------------------------------------------*/ |