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 "n_poly.h"
13
14
_n_fq_poly_taylor_shift_horner_n_fq(mp_limb_t * poly,const mp_limb_t * c,slong n,const fq_nmod_ctx_t ctx)15 static void _n_fq_poly_taylor_shift_horner_n_fq(
16 mp_limb_t * poly,
17 const mp_limb_t * c,
18 slong n,
19 const fq_nmod_ctx_t ctx)
20 {
21 slong d = fq_nmod_ctx_degree(ctx);
22 slong i, j;
23 mp_limb_t * p = FLINT_ARRAY_ALLOC(d, mp_limb_t);
24
25 for (i = n - 2; i >= 0; i--)
26 {
27 for (j = i; j < n - 1; j++)
28 {
29 n_fq_mul(p, poly + d*(j + 1), c, ctx);
30 n_fq_add(poly + d*j, poly + d*j, p, ctx);
31 }
32 }
33
34 flint_free(p);
35 }
36
37
n_fq_bpoly_taylor_shift_gen1_fq_nmod(n_bpoly_t A,const n_bpoly_t B,const fq_nmod_t c_,const fq_nmod_ctx_t ctx)38 void n_fq_bpoly_taylor_shift_gen1_fq_nmod(
39 n_bpoly_t A,
40 const n_bpoly_t B,
41 const fq_nmod_t c_,
42 const fq_nmod_ctx_t ctx)
43 {
44 slong d = fq_nmod_ctx_degree(ctx);
45 slong i;
46 mp_limb_t * c = FLINT_ARRAY_ALLOC(d, mp_limb_t);
47
48 n_fq_set_fq_nmod(c, c_, ctx);
49 n_fq_bpoly_set(A, B, ctx);
50 for (i = A->length - 1; i >= 0; i--)
51 _n_fq_poly_taylor_shift_horner_n_fq(A->coeffs[i].coeffs, c, A->coeffs[i].length, ctx);
52
53 flint_free(c);
54 }
55
n_fq_bpoly_taylor_shift_gen0_fq_nmod(n_bpoly_t A,const fq_nmod_t alpha,const fq_nmod_ctx_t ctx)56 void n_fq_bpoly_taylor_shift_gen0_fq_nmod(
57 n_bpoly_t A,
58 const fq_nmod_t alpha,
59 const fq_nmod_ctx_t ctx)
60 {
61 slong d = fq_nmod_ctx_degree(ctx);
62 slong n, i, j;
63 mp_limb_t * c;
64 n_poly_t t;
65
66 if (fq_nmod_is_zero(alpha, ctx))
67 return;
68
69 c = FLINT_ARRAY_ALLOC(d, mp_limb_t);
70 n_fq_set_fq_nmod(c, alpha, ctx);
71
72 n_poly_init(t);
73 n = A->length;
74
75 for (i = n - 2; i >= 0; i--)
76 {
77 for (j = i; j < n - 1; j++)
78 {
79 n_fq_poly_scalar_mul_n_fq(t, A->coeffs + j + 1, c, ctx);
80 n_fq_poly_add(A->coeffs + j, A->coeffs + j, t, ctx);
81 }
82 }
83
84 n_poly_clear(t);
85
86 flint_free(c);
87 }
88
89
90
n_fq_bpoly_taylor_shift_gen0_n_fq(n_fq_bpoly_t A,const mp_limb_t * alpha,const fq_nmod_ctx_t ctx)91 void n_fq_bpoly_taylor_shift_gen0_n_fq(
92 n_fq_bpoly_t A,
93 const mp_limb_t * alpha,
94 const fq_nmod_ctx_t ctx)
95 {
96 slong d = fq_nmod_ctx_degree(ctx);
97 slong i, j, n = A->length;
98 mp_limb_t * tmp, * c, * alphainv;
99 TMP_INIT;
100
101 if (_n_fq_is_zero(alpha, d))
102 return;
103
104 TMP_START;
105
106 tmp = (mp_limb_t *) TMP_ALLOC(d*N_FQ_MUL_INV_ITCH*sizeof(mp_limb_t));
107 c = TMP_ALLOC(d*sizeof(mp_limb_t));
108 alphainv = TMP_ALLOC(d*sizeof(mp_limb_t));
109
110 _n_fq_one(c, d);
111 for (i = 1; i < n; i++)
112 {
113 _n_fq_mul(c, c, alpha, ctx, tmp);
114 if (!_n_fq_is_one(c, d))
115 {
116 mp_limb_t * Aic = A->coeffs[i].coeffs;
117 for (j = 0; j < A->coeffs[i].length; j++)
118 _n_fq_mul(Aic + d*j, Aic + d*j, c, ctx, tmp);
119 }
120 }
121
122 for (i = n - 2; i >= 0; i--)
123 {
124 for (j = i; j < n - 1; j++)
125 {
126 n_fq_poly_add(A->coeffs + j, A->coeffs + j, A->coeffs + j + 1, ctx);
127 }
128 }
129
130 _n_fq_inv(alphainv, alpha, ctx, tmp);
131 _n_fq_one(c, d);
132 for (i = 1; i < n; i++)
133 {
134 _n_fq_mul(c, c, alphainv, ctx, tmp);
135 if (!_n_fq_is_one(c, d))
136 {
137 mp_limb_t * Aic = A->coeffs[i].coeffs;
138 for (j = 0; j < A->coeffs[i].length; j++)
139 _n_fq_mul(Aic + d*j, Aic + d*j, c, ctx, tmp);
140 }
141 }
142
143 TMP_END;
144
145 return;
146 }
147
148