chiark / gitweb /
math/mpmont.c: Factor out the computational core of the algorithm.
[catacomb] / math / group-exp.c
CommitLineData
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
47void 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
84void 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 -------------------------------------------------*/