1 /*
2 Copyright (C) 2020 Daniel Schultz
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 <https://www.gnu.org/licenses/>.
10 */
11
12 #include "fmpz_mod_poly.h"
13
14
_fmpz_mod_poly_powmod_linear_fmpz_preinv(fmpz * res,const fmpz_t a,const fmpz_t e,const fmpz * f,slong lenf,const fmpz * finv,slong lenfinv,const fmpz_mod_ctx_t ctx)15 static void _fmpz_mod_poly_powmod_linear_fmpz_preinv(
16 fmpz * res,
17 const fmpz_t a,
18 const fmpz_t e,
19 const fmpz * f, slong lenf,
20 const fmpz* finv, slong lenfinv,
21 const fmpz_mod_ctx_t ctx)
22 {
23 fmpz * T, * Q;
24 slong lenT = 2 * lenf - 3;
25 slong lenQ = lenT - lenf + 1;
26 slong i, j;
27 fmpz_t t, lcinv;
28
29 FLINT_ASSERT(lenf > 1);
30 FLINT_ASSERT(!fmpz_is_zero(e));
31
32 fmpz_init(t);
33
34 if (lenf <= 2)
35 {
36 fmpz_mod_mul(t, f + 0, finv + 0, ctx);
37 fmpz_mod_sub(t, a, t, ctx);
38 fmpz_mod_pow_fmpz(res + 0, t, e, ctx);
39 fmpz_clear(t);
40 return;
41 }
42
43 fmpz_init(lcinv);
44 T = _fmpz_vec_init(lenT + lenQ);
45 Q = T + lenT;
46
47 _fmpz_vec_zero(res, lenf - 1);
48 fmpz_set(res + 0, a);
49 fmpz_one(res + 1);
50
51 for (i = fmpz_sizeinbase(e, 2) - 2; i >= 0; i--)
52 {
53 _fmpz_mod_poly_sqr(T, res, lenf - 1, fmpz_mod_ctx_modulus(ctx));
54 _fmpz_mod_poly_divrem_newton_n_preinv(Q, res, T, 2 * lenf - 3, f, lenf,
55 finv, lenfinv, fmpz_mod_ctx_modulus(ctx));
56 if (fmpz_tstbit(e, i))
57 {
58 j = lenf - 1;
59 fmpz_mod_mul(lcinv, finv + 0, res + j - 1, ctx);
60 fmpz_mod_neg(lcinv, lcinv, ctx);
61 for (j--; j > 0; j--)
62 {
63 fmpz_mul(t, a, res + j);
64 fmpz_addmul(t, lcinv, f + j);
65 fmpz_add(t, t, res + j - 1);
66 fmpz_mod(res + j, t, fmpz_mod_ctx_modulus(ctx));
67 }
68 fmpz_mul(t, a, res + j);
69 fmpz_addmul(t, lcinv, f + j);
70 fmpz_mod(res + j, t, fmpz_mod_ctx_modulus(ctx));
71 }
72 }
73
74 fmpz_clear(lcinv);
75 fmpz_clear(t);
76 _fmpz_vec_clear(T, lenT + lenQ);
77 }
78
79
80 /* res = (x+a)^e mod f */
fmpz_mod_poly_powmod_linear_fmpz_preinv(fmpz_mod_poly_t res,const fmpz_t a,const fmpz_t e,const fmpz_mod_poly_t f,const fmpz_mod_poly_t finv,const fmpz_mod_ctx_t ctx)81 void fmpz_mod_poly_powmod_linear_fmpz_preinv(
82 fmpz_mod_poly_t res,
83 const fmpz_t a,
84 const fmpz_t e,
85 const fmpz_mod_poly_t f,
86 const fmpz_mod_poly_t finv,
87 const fmpz_mod_ctx_t ctx)
88 {
89 slong lenf = f->length;
90 slong trunc = lenf - 1;
91 int sgn = fmpz_sgn(e);
92 fmpz_mod_poly_t tmp;
93
94 if (lenf < 2)
95 {
96 fmpz_mod_poly_zero(res, ctx);
97 return;
98 }
99
100 if (sgn < 0)
101 {
102 flint_throw(FLINT_ERROR, "fmpz_mod_poly_powmod_linear_fmpz_preinv: "
103 "negative exp not implemented");
104 }
105
106 if (sgn == 0)
107 {
108 fmpz_mod_poly_one(res, ctx);
109 return;
110 }
111
112 if (res == f || res == finv)
113 {
114 fmpz_mod_poly_init2(tmp, trunc, ctx);
115 _fmpz_mod_poly_powmod_linear_fmpz_preinv(tmp->coeffs, a, e,
116 f->coeffs, lenf, finv->coeffs, finv->length, ctx);
117 fmpz_mod_poly_swap(res, tmp, ctx);
118 fmpz_mod_poly_clear(tmp, ctx);
119 }
120 else
121 {
122 fmpz_mod_poly_fit_length(res, trunc, ctx);
123 _fmpz_mod_poly_powmod_linear_fmpz_preinv(res->coeffs, a, e,
124 f->coeffs, lenf, finv->coeffs, finv->length, ctx);
125 }
126
127 _fmpz_mod_poly_set_length(res, trunc);
128 _fmpz_mod_poly_normalise(res);
129 }
130
131