1 /*
2 Copyright (C) 2010 Sebastian Pancratz
3 Copyright (C) 2010 William Hart
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <http://www.gnu.org/licenses/>.
11 */
12
13 #include <gmp.h>
14 #include "flint.h"
15 #include "nmod_vec.h"
16 #include "nmod_poly.h"
17
18 void
_nmod_poly_pow(mp_ptr res,mp_srcptr poly,slong len,ulong e,nmod_t mod)19 _nmod_poly_pow(mp_ptr res, mp_srcptr poly, slong len, ulong e, nmod_t mod)
20 {
21 _nmod_poly_pow_binexp(res, poly, len, e, mod);
22 }
23
24 void
nmod_poly_pow(nmod_poly_t res,const nmod_poly_t poly,ulong e)25 nmod_poly_pow(nmod_poly_t res, const nmod_poly_t poly, ulong e)
26 {
27 const slong len = poly->length;
28 slong rlen;
29
30 if ((len < 2) | (e < UWORD(3)))
31 {
32 if (len == 0)
33 {
34 if (e == 0)
35 nmod_poly_one(res);
36 else
37 nmod_poly_zero(res);
38 }
39 else if (len == 1)
40 {
41 nmod_poly_fit_length(res, 1);
42 res->coeffs[0] = n_powmod2_ui_preinv(poly->coeffs[0], e,
43 poly->mod.n, poly->mod.ninv);
44 res->length = 1;
45 _nmod_poly_normalise(res);
46 }
47 else if (e == UWORD(0))
48 {
49 nmod_poly_set_coeff_ui(res, 0, UWORD(1));
50 res->length = 1;
51 _nmod_poly_normalise(res);
52 }
53 else if (e == UWORD(1))
54 nmod_poly_set(res, poly);
55 else /* e == UWORD(2) */
56 nmod_poly_mul(res, poly, poly);
57
58 return;
59 }
60
61 rlen = (slong) e * (len - 1) + 1;
62
63 if (res != poly)
64 {
65 nmod_poly_fit_length(res, rlen);
66 _nmod_poly_pow(res->coeffs, poly->coeffs, len, e, poly->mod);
67 }
68 else
69 {
70 nmod_poly_t t;
71 nmod_poly_init2(t, poly->mod.n, rlen);
72 _nmod_poly_pow(t->coeffs, poly->coeffs, len, e, poly->mod);
73 nmod_poly_swap(res, t);
74 nmod_poly_clear(t);
75 }
76
77 res->length = rlen;
78 _nmod_poly_normalise(res);
79 }
80