1 /*
2 Copyright (C) 2013 Mike Hansen
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #ifdef T
13
14 #include "templates.h"
15
16 #include <stdlib.h>
17 #include <gmp.h>
18 #include "flint.h"
19 void
_TEMPLATE(T,poly_powmod_fmpz_binexp)20 _TEMPLATE(T, poly_powmod_fmpz_binexp) (
21 TEMPLATE(T, struct) * res,
22 const TEMPLATE(T, struct) * poly,
23 const fmpz_t e,
24 const TEMPLATE(T, struct) * f, slong lenf,
25 const TEMPLATE(T, ctx_t) ctx)
26 {
27 TEMPLATE(T, struct) * T, *Q;
28 TEMPLATE(T, t) invf;
29 slong lenT, lenQ;
30 slong i;
31
32 if (lenf == 2)
33 {
34 TEMPLATE(T, pow) (res, poly, e, ctx);
35 return;
36 }
37
38 lenT = 2 * lenf - 3;
39 lenQ = lenT - lenf + 1;
40
41 T = _TEMPLATE(T, vec_init) (lenT + lenQ, ctx);
42 Q = T + lenT;
43
44 TEMPLATE(T, init) (invf, ctx);
45 TEMPLATE(T, inv) (invf, f + lenf - 1, ctx);
46
47 _TEMPLATE(T, vec_set) (res, poly, lenf - 1, ctx);
48
49 for (i = fmpz_sizeinbase(e, 2) - 2; i >= 0; i--)
50 {
51 _TEMPLATE(T, poly_sqr) (T, res, lenf - 1, ctx);
52 _TEMPLATE(T, poly_divrem) (Q, res, T, 2 * lenf - 3, f, lenf, invf,
53 ctx);
54
55 if (fmpz_tstbit(e, i))
56 {
57 _TEMPLATE(T, poly_mul) (T, res, lenf - 1, poly, lenf - 1, ctx);
58 _TEMPLATE(T, poly_divrem) (Q, res, T, 2 * lenf - 3, f, lenf, invf,
59 ctx);
60 }
61 }
62
63 TEMPLATE(T, clear) (invf, ctx);
64 _TEMPLATE(T, vec_clear) (T, lenT + lenQ, ctx);
65 }
66
67
68 void
TEMPLATE(T,poly_powmod_fmpz_binexp)69 TEMPLATE(T, poly_powmod_fmpz_binexp) (TEMPLATE(T, poly_t) res,
70 const TEMPLATE(T, poly_t) poly,
71 const fmpz_t e,
72 const TEMPLATE(T, poly_t) f,
73 const TEMPLATE(T, ctx_t) ctx)
74 {
75 TEMPLATE(T, struct) * q;
76 slong len = poly->length;
77 slong lenf = f->length;
78 slong trunc = lenf - 1;
79 int qcopy = 0;
80
81 if (lenf == 0)
82 {
83 TEMPLATE_PRINTF
84 ("Exception: %s_poly_powmod_fmpz_binexp: divide by zero\n", T);
85 flint_abort();
86 }
87
88 if (fmpz_sgn(e) < 0)
89 {
90 TEMPLATE_PRINTF
91 ("Exception: %s_poly_powmod_fmpz_binexp: negative exp not implemented\n",
92 T);
93 flint_abort();
94 }
95
96 if (len >= lenf)
97 {
98 TEMPLATE(T, poly_t) t, r;
99 TEMPLATE(T, poly_init) (t, ctx);
100 TEMPLATE(T, poly_init) (r, ctx);
101 TEMPLATE(T, poly_divrem) (t, r, poly, f, ctx);
102 TEMPLATE(T, poly_powmod_fmpz_binexp) (res, r, e, f, ctx);
103 TEMPLATE(T, poly_clear) (t, ctx);
104 TEMPLATE(T, poly_clear) (r, ctx);
105 return;
106 }
107
108 if (fmpz_abs_fits_ui(e))
109 {
110 ulong exp = fmpz_get_ui(e);
111
112 if (exp <= 2)
113 {
114 if (exp == UWORD(0))
115 {
116 TEMPLATE(T, poly_fit_length) (res, 1, ctx);
117 TEMPLATE(T, one) (res->coeffs, ctx);
118 _TEMPLATE(T, poly_set_length) (res, 1, ctx);
119 }
120 else if (exp == UWORD(1))
121 {
122 TEMPLATE(T, poly_set) (res, poly, ctx);
123 }
124 else
125 TEMPLATE(T, poly_mulmod) (res, poly, poly, f, ctx);
126 return;
127 }
128 }
129
130 if (lenf == 1 || len == 0)
131 {
132 TEMPLATE(T, poly_zero) (res, ctx);
133 return;
134 }
135
136 if (poly->length < trunc)
137 {
138 q = _TEMPLATE(T, vec_init) (trunc, ctx);
139 _TEMPLATE(T, vec_set) (q, poly->coeffs, len, ctx);
140 _TEMPLATE(T, vec_zero) (q + len, trunc - len, ctx);
141 qcopy = 1;
142 }
143 else
144 {
145 q = poly->coeffs;
146 }
147
148 if ((res == poly && !qcopy) || (res == f))
149 {
150 TEMPLATE(T, poly_t) t;
151 TEMPLATE(T, poly_init2) (t, 2 * lenf - 3, ctx);
152 _TEMPLATE(T, poly_powmod_fmpz_binexp) (t->coeffs, q, e, f->coeffs,
153 lenf, ctx);
154 TEMPLATE(T, poly_swap) (res, t, ctx);
155 TEMPLATE(T, poly_clear) (t, ctx);
156 }
157 else
158 {
159 TEMPLATE(T, poly_fit_length) (res, 2 * lenf - 3, ctx);
160 _TEMPLATE(T, poly_powmod_fmpz_binexp) (res->coeffs, q, e, f->coeffs,
161 lenf, ctx);
162 }
163
164 if (qcopy)
165 _TEMPLATE(T, vec_clear) (q, trunc, ctx);
166
167 _TEMPLATE(T, poly_set_length) (res, trunc, ctx);
168 _TEMPLATE(T, poly_normalise) (res, ctx);
169 }
170
171
172 #endif
173