1 /*
2 Copyright (C) 2019 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 "fq_nmod_mpoly.h"
13
14
15 /*
16 interp_reduce: map from Fp[x] to Fp[x]/poly(x)
17 interp_lift: map from Fp[x]/poly(x) to Fp[x]
18 interp_crt: update element of Fp[x] with a new image in Fp[x]/poly(x)
19 interp_mcrt: same as interp_mcrt, but monomial match, thus easier
20
21 ..._sm: poly(x) is x - alpha
22 ..._lg: poly(x) is modulus of finite field
23 */
24
_n_poly_mul_n_fq(n_poly_t a,const n_poly_t b,const mp_limb_t * c,const fq_nmod_ctx_t ctx)25 static void _n_poly_mul_n_fq(
26 n_poly_t a,
27 const n_poly_t b,
28 const mp_limb_t * c,
29 const fq_nmod_ctx_t ctx)
30 {
31 slong d = fq_nmod_ctx_degree(ctx);
32 n_poly_t C;
33 C->coeffs = (mp_limb_t *) c;
34 C->length = d;
35 C->alloc = d;
36 _n_poly_normalise(C);
37 n_poly_mod_mul(a, b, C, ctx->mod);
38 }
39
40 /****************** bivar - image in F_q *************************************/
41
42 /*
43 E = A mod alpha(v)
44 A is in Fp[X][][v]
45 E is in (Fp/alpha(v))[X]
46 */
47
nmod_mpolyn_interp_reduce_lg_poly(fq_nmod_poly_t E,const fq_nmod_ctx_t fqctx,const nmod_mpolyn_t A,const nmod_mpoly_ctx_t ctx)48 void nmod_mpolyn_interp_reduce_lg_poly(
49 fq_nmod_poly_t E,
50 const fq_nmod_ctx_t fqctx,
51 const nmod_mpolyn_t A,
52 const nmod_mpoly_ctx_t ctx)
53 {
54 fq_nmod_t v;
55 slong Ai, Alen, k;
56 n_poly_struct * Acoeff;
57 ulong * Aexp;
58 slong N, off, shift;
59
60 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
61 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
62
63 fq_nmod_init(v, fqctx);
64
65 Acoeff = A->coeffs;
66 Aexp = A->exps;
67 Alen = A->length;
68
69 fq_nmod_poly_zero(E, fqctx);
70 for (Ai = 0; Ai < Alen; Ai++)
71 {
72 k = (Aexp + N*Ai)[off] >> shift;
73 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(v), Acoeff + Ai,
74 evil_const_cast_nmod_poly_to_n_poly(fqctx->modulus), ctx->mod);
75 fq_nmod_poly_set_coeff(E, k, v, fqctx);
76 }
77
78 fq_nmod_clear(v, fqctx);
79 }
80
81
82 /*
83 Convert B to A using the lowest degree representative
84 A is in Fp [X][][v]
85 B is in (Fp/alpha(v))[X]
86 */
87
nmod_mpolyn_interp_lift_lg_poly(slong * lastdeg_,nmod_mpolyn_t A,const nmod_mpoly_ctx_t ctx,const fq_nmod_poly_t B,const fq_nmod_ctx_t fqctx)88 void nmod_mpolyn_interp_lift_lg_poly(
89 slong * lastdeg_,
90 nmod_mpolyn_t A,
91 const nmod_mpoly_ctx_t ctx,
92 const fq_nmod_poly_t B,
93 const fq_nmod_ctx_t fqctx)
94 {
95 slong Bexp;
96 slong Blen = fq_nmod_poly_length(B, fqctx);
97 fq_nmod_struct * Bcoeff = B->coeffs;
98 n_poly_struct * Acoeff;
99 ulong * Aexp;
100 slong Ai;
101 slong lastdeg = -WORD(1);
102 slong N, off, shift;
103
104 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
105 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
106
107 nmod_mpolyn_fit_length(A, Blen, ctx);
108 Acoeff = A->coeffs;
109 Aexp = A->exps;
110
111 Ai = 0;
112 for (Bexp = Blen - 1; Bexp >= 0; Bexp--)
113 {
114 if (!fq_nmod_is_zero(Bcoeff + Bexp, fqctx))
115 {
116 FLINT_ASSERT(Ai < A->alloc);
117 n_poly_set_nmod_poly(Acoeff + Ai, Bcoeff + Bexp);
118 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(Acoeff + Ai));
119 mpoly_monomial_zero(Aexp + N*Ai, N);
120 (Aexp + N*Ai)[off] = Bexp << shift;
121 Ai++;
122 }
123 }
124 A->length = Ai;
125
126 *lastdeg_ = lastdeg;
127 }
128
129
130 /*
131 F = F + modulus*((A - F(alpha))/(modulus(alpha)))
132 no assumptions about matching monomials
133 F is in Fp[X][v]
134 A is in (Fp/alpha(v))[X] alpha(v) is fqctx->modulus(v)
135 */
136
nmod_mpolyn_interp_crt_lg_poly(slong * lastdeg_,nmod_mpolyn_t F,nmod_mpolyn_t T,n_poly_t modulus,const nmod_mpoly_ctx_t ctx,fq_nmod_poly_t A,const fq_nmod_ctx_t fqctx)137 int nmod_mpolyn_interp_crt_lg_poly(
138 slong * lastdeg_,
139 nmod_mpolyn_t F,
140 nmod_mpolyn_t T,
141 n_poly_t modulus,
142 const nmod_mpoly_ctx_t ctx,
143 fq_nmod_poly_t A,
144 const fq_nmod_ctx_t fqctx)
145 {
146 int changed = 0;
147 slong lastdeg = -WORD(1);
148 fq_nmod_t u, v;
149 n_poly_t w;
150 slong Fi, Ti, Aexp;
151 fq_nmod_struct * Acoeff = A->coeffs;
152 slong Flen = F->length;
153 n_poly_struct * Fcoeffs = F->coeffs;
154 ulong * Fexps = F->exps;
155 n_poly_struct * Tcoeffs;
156 ulong * Texps;
157 fq_nmod_t inv_m_eval;
158 slong N, off, shift;
159
160 FLINT_ASSERT(T->bits == F->bits);
161
162 N = mpoly_words_per_exp_sp(F->bits, ctx->minfo);
163 mpoly_gen_offset_shift_sp(&off, &shift, 0, F->bits, ctx->minfo);
164
165 fq_nmod_init(inv_m_eval, fqctx);
166 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(inv_m_eval), modulus,
167 evil_const_cast_nmod_poly_to_n_poly(fqctx->modulus), ctx->mod);
168 fq_nmod_inv(inv_m_eval, inv_m_eval, fqctx);
169
170 Fi = 0;
171
172 fq_nmod_init(u, fqctx);
173 fq_nmod_init(v, fqctx);
174 n_poly_init(w);
175
176 Aexp = fq_nmod_poly_degree(A, fqctx);
177
178 nmod_mpolyn_fit_length(T, Flen + Aexp + 1, ctx);
179 Tcoeffs = T->coeffs;
180 Texps = T->exps;
181 Ti = 0;
182
183 while (Fi < Flen || Aexp >= 0)
184 {
185 FLINT_ASSERT(Ti < T->alloc);
186
187 if (Fi < Flen)
188 {
189 FLINT_ASSERT(!n_poly_is_zero(Fcoeffs + Fi));
190 FLINT_ASSERT(n_poly_degree(Fcoeffs + Fi) < n_poly_degree(modulus));
191 }
192
193 if (Aexp >= 0)
194 {
195 FLINT_ASSERT(!fq_nmod_is_zero(Acoeff + Aexp, fqctx));
196 }
197
198 mpoly_monomial_zero(Texps + N*Ti, N);
199
200 if (Fi < Flen && Aexp >= 0 && ((Fexps + N*Fi)[off]>>shift) == Aexp)
201 {
202 /* F term ok, A term ok */
203 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(u), Fcoeffs + Fi,
204 evil_const_cast_nmod_poly_to_n_poly(fqctx->modulus), ctx->mod);
205 fq_nmod_sub(v, Acoeff + Aexp, u, fqctx);
206 if (!fq_nmod_is_zero(v, fqctx))
207 {
208 changed = 1;
209 fq_nmod_mul(u, v, inv_m_eval, fqctx);
210 n_poly_mod_mul(w, modulus, evil_cast_nmod_poly_to_n_poly(u), ctx->mod);
211 n_poly_mod_add(Tcoeffs + Ti, Fcoeffs + Fi, w, ctx->mod);
212 }
213 else
214 {
215 n_poly_set(Tcoeffs + Ti, Fcoeffs + Fi);
216 }
217
218 (Texps + N*Ti)[off] = (Fexps + N*Fi)[off];
219 Fi++;
220 do {
221 Aexp--;
222 } while (Aexp >= 0 && fq_nmod_is_zero(Acoeff + Aexp, fqctx));
223 }
224 else if (Fi < Flen && (Aexp < 0 || ((Fexps + N*Fi)[off]>>shift) > Aexp))
225 {
226 /* F term ok, A term missing */
227 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(v), Fcoeffs + Fi,
228 evil_const_cast_nmod_poly_to_n_poly(fqctx->modulus), ctx->mod);
229 if (!fq_nmod_is_zero(v, fqctx))
230 {
231 changed = 1;
232 fq_nmod_mul(u, v, inv_m_eval, fqctx);
233 n_poly_mod_mul(w, evil_const_cast_nmod_poly_to_n_poly(u), modulus, ctx->mod);
234 n_poly_mod_sub(Tcoeffs + Ti, Fcoeffs + Fi, w, ctx->mod);
235 }
236 else
237 {
238 n_poly_set(Tcoeffs + Ti, Fcoeffs + Fi);
239 }
240
241 (Texps + N*Ti)[off] = (Fexps + N*Fi)[off];
242 Fi++;
243 }
244 else if (Aexp >= 0 && (Fi >= Flen || ((Fexps + N*Fi)[off]>>shift) < Aexp))
245 {
246 /* F term missing, A term ok */
247 changed = 1;
248 fq_nmod_mul(u, Acoeff + Aexp, inv_m_eval, fqctx);
249 n_poly_mod_mul(Tcoeffs + Ti, modulus,
250 evil_const_cast_nmod_poly_to_n_poly(u), ctx->mod);
251 (Texps + N*Ti)[off] = Aexp << shift;
252 do {
253 Aexp--;
254 } while (Aexp >= 0 && fq_nmod_is_zero(Acoeff + Aexp, fqctx));
255 }
256 else
257 {
258 FLINT_ASSERT(0);
259 }
260
261 FLINT_ASSERT(!n_poly_is_zero(Tcoeffs + Ti));
262 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(Tcoeffs + Ti));
263 Ti++;
264 }
265 T->length = Ti;
266
267 if (changed)
268 {
269 nmod_mpolyn_swap(T, F);
270 }
271
272 fq_nmod_clear(u, fqctx);
273 fq_nmod_clear(v, fqctx);
274 n_poly_clear(w);
275
276 fq_nmod_clear(inv_m_eval, fqctx);
277
278 *lastdeg_ = lastdeg;
279 return changed;
280 }
281
nmod_mpolyn_interp_lift_lg_bpoly(slong * lastdeg_,nmod_mpolyn_t F,const nmod_mpoly_ctx_t smctx,n_fq_bpoly_t A,const fq_nmod_mpoly_ctx_t lgctx)282 void nmod_mpolyn_interp_lift_lg_bpoly(
283 slong * lastdeg_,
284 nmod_mpolyn_t F,
285 const nmod_mpoly_ctx_t smctx,
286 n_fq_bpoly_t A,
287 const fq_nmod_mpoly_ctx_t lgctx)
288 {
289 slong lgd = fq_nmod_ctx_degree(lgctx->fqctx);
290 slong N = mpoly_words_per_exp_sp(F->bits, smctx->minfo);
291 slong i, j, Fi;
292 slong lastdeg = -WORD(1);
293 slong off0, shift0, off1, shift1;
294
295 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, smctx->minfo);
296 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, smctx->minfo);
297
298 Fi = 0;
299 for (i = A->length - 1; i >= 0; i--)
300 {
301 n_fq_poly_struct * Ai = A->coeffs + i;
302 for (j = Ai->length - 1; j >= 0; j--)
303 {
304 if (_n_fq_is_zero(Ai->coeffs + lgd*j, lgd))
305 continue;
306
307 nmod_mpolyn_fit_length(F, Fi + 1, smctx);
308 mpoly_monomial_zero(F->exps + N*Fi, N);
309 (F->exps + N*Fi)[off0] += (i << shift0);
310 (F->exps + N*Fi)[off1] += (j << shift1);
311 n_fq_get_n_poly(F->coeffs + Fi, Ai->coeffs + lgd*j, lgctx->fqctx);
312 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(F->coeffs + Fi));
313
314 Fi++;
315 }
316 }
317
318 F->length = Fi;
319
320 *lastdeg_ = lastdeg;
321 }
322
nmod_mpolyn_interp_crt_lg_bpoly(slong * lastdeg,nmod_mpolyn_t F,nmod_mpolyn_t T,n_fq_poly_t modulus,const nmod_mpoly_ctx_t smctx,n_fq_bpoly_t A,const fq_nmod_mpoly_ctx_t lgctx)323 int nmod_mpolyn_interp_crt_lg_bpoly(
324 slong * lastdeg,
325 nmod_mpolyn_t F,
326 nmod_mpolyn_t T,
327 n_fq_poly_t modulus,
328 const nmod_mpoly_ctx_t smctx,
329 n_fq_bpoly_t A,
330 const fq_nmod_mpoly_ctx_t lgctx)
331 {
332 slong lgd = fq_nmod_ctx_degree(lgctx->fqctx);
333 int changed = 0;
334 slong N = mpoly_words_per_exp(T->bits, smctx->minfo);
335 slong off0, shift0, off1, shift1;
336 n_fq_poly_struct * Acoeffs = A->coeffs;
337 slong Fi, Ti, Ai, ai;
338 slong Flen = F->length;
339 ulong * Fexps = F->exps;
340 n_poly_struct * Fcoeffs = F->coeffs;
341 ulong * Texps = T->exps;
342 n_poly_struct * Tcoeffs = T->coeffs;
343 mp_limb_t * u = FLINT_ARRAY_ALLOC(3*lgd, mp_limb_t);
344 mp_limb_t * v = u + lgd;
345 mp_limb_t * inv_m_eval = v + lgd;
346 ulong Fexpi, mask;
347
348 mask = (-UWORD(1)) >> (FLINT_BITS - F->bits);
349 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, smctx->minfo);
350 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, smctx->minfo);
351
352 _n_fq_set_n_poly(u, modulus->coeffs, modulus->length, lgctx->fqctx);
353
354 n_fq_inv(inv_m_eval, u, lgctx->fqctx);
355
356 FLINT_ASSERT(nmod_mpolyn_is_canonical(F, smctx));
357 FLINT_ASSERT(n_fq_bpoly_is_canonical(A, lgctx->fqctx));
358
359 FLINT_ASSERT(T->bits == F->bits);
360
361 *lastdeg = -1;
362
363 Ti = Fi = 0;
364 Ai = A->length - 1;
365 ai = (Ai < 0) ? 0 : n_fq_poly_degree(Acoeffs + Ai);
366
367 while (Fi < Flen || Ai >= 0)
368 {
369 if (Ti >= T->alloc)
370 {
371 slong extra = FLINT_MAX(Flen - Fi, Ai);
372 nmod_mpolyn_fit_length(T, Ti + extra + 1, smctx);
373 Tcoeffs = T->coeffs;
374 Texps = T->exps;
375 }
376
377 if (Fi < Flen)
378 {
379 Fexpi = pack_exp2(((Fexps + N*Fi)[off0]>>shift0)&mask,
380 ((Fexps + N*Fi)[off1]>>shift1)&mask);
381 }
382 else
383 {
384 Fexpi = 0;
385 }
386
387 if (Fi < Flen && Ai >= 0 && Fexpi == pack_exp2(Ai, ai))
388 {
389 /* F term ok, A term ok */
390 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
391
392 _n_fq_set_n_poly(u, Fcoeffs[Fi].coeffs, Fcoeffs[Fi].length, lgctx->fqctx);
393 n_fq_sub(v, Acoeffs[Ai].coeffs + lgd*ai, u, lgctx->fqctx);
394 if (!_n_fq_is_zero(v, lgd))
395 {
396 changed = 1;
397 n_fq_mul(u, v, inv_m_eval, lgctx->fqctx);
398 _n_poly_mul_n_fq(Tcoeffs + Ti, modulus, u, lgctx->fqctx);
399 n_poly_mod_add(Tcoeffs + Ti, Tcoeffs + Ti, Fcoeffs + Fi, smctx->mod);
400 }
401 else
402 {
403 n_poly_set(Tcoeffs + Ti, Fcoeffs + Fi);
404 }
405
406 Fi++;
407 do {
408 ai--;
409 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + lgd*ai, lgd));
410 if (ai < 0)
411 {
412 do {
413 Ai--;
414 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
415 if (Ai >= 0)
416 ai = n_fq_poly_degree(Acoeffs + Ai);
417 }
418 }
419 else if (Fi < Flen && (Ai < 0 || Fexpi > pack_exp2(Ai, ai)))
420 {
421 /* F term ok, Aterm missing */
422 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
423
424 _n_fq_set_n_poly(v, Fcoeffs[Fi].coeffs, Fcoeffs[Fi].length, lgctx->fqctx);
425 if (!_n_fq_is_zero(v, lgd))
426 {
427 changed = 1;
428 n_fq_mul(u, v, inv_m_eval, lgctx->fqctx);
429 _n_poly_mul_n_fq(Tcoeffs + Ti, modulus, u, lgctx->fqctx);
430 n_poly_mod_sub(Tcoeffs + Ti, Fcoeffs + Fi, Tcoeffs + Ti, smctx->mod);
431 }
432 else
433 {
434 n_poly_set(Tcoeffs + Ti, Fcoeffs + Fi);
435 }
436
437 Fi++;
438 }
439 else
440 {
441 FLINT_ASSERT(Ai >= 0 && (Fi >= Flen || Fexpi < pack_exp2(Ai, ai)));
442
443 /* F term missing, A term ok */
444 mpoly_monomial_zero(Texps + N*Ti, N);
445 (Texps + N*Ti)[off0] += (Ai << shift0);
446 (Texps + N*Ti)[off1] += (ai << shift1);
447
448 changed = 1;
449 n_fq_mul(u, Acoeffs[Ai].coeffs + lgd*ai, inv_m_eval, lgctx->fqctx);
450 _n_poly_mul_n_fq(Tcoeffs + Ti, modulus, u, lgctx->fqctx);
451
452 do {
453 ai--;
454 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + lgd*ai, lgd));
455 if (ai < 0)
456 {
457 do {
458 Ai--;
459 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
460 if (Ai >= 0)
461 ai = n_fq_poly_degree(Acoeffs + Ai);
462 }
463 }
464
465 FLINT_ASSERT(!n_poly_is_zero(Tcoeffs + Ti));
466 *lastdeg = FLINT_MAX(*lastdeg, n_poly_degree(Tcoeffs + Ti));
467 Ti++;
468 }
469
470 T->length = Ti;
471
472 if (changed)
473 nmod_mpolyn_swap(T, F);
474
475 FLINT_ASSERT(nmod_mpolyn_is_canonical(F, smctx));
476
477 flint_free(u);
478
479 return changed;
480 }
481
482
483
484 /*********************** multivar - image in F_q *****************************/
485
486 /*
487 E = A mod alpha(x_var)
488 A is in Fp[x_0, ..., x_(var-2), x_(var-1)][x_var]
489 E is in (Fp/alpha(x_var))[x_0, ..., x_(var-2)][x_(var-1)]
490 alpha is ectx->modulus
491 */
492
nmod_mpolyn_interp_reduce_lg_mpolyn(fq_nmod_mpolyn_t E,fq_nmod_mpoly_ctx_t ectx,nmod_mpolyn_t A,slong var,const nmod_mpoly_ctx_t ctx)493 void nmod_mpolyn_interp_reduce_lg_mpolyn(
494 fq_nmod_mpolyn_t E,
495 fq_nmod_mpoly_ctx_t ectx,
496 nmod_mpolyn_t A,
497 slong var,
498 const nmod_mpoly_ctx_t ctx)
499 {
500 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
501 slong offset, shift, k;
502 ulong mask;
503 fq_nmod_t v;
504 n_poly_struct * Acoeff = A->coeffs;
505 ulong * Aexp = A->exps;
506 slong Alen = A->length;
507 slong Ai;
508 n_poly_struct * Ecoeff;
509 ulong * Eexp;
510 slong Ei;
511
512 fq_nmod_init(v, ectx->fqctx);
513
514 FLINT_ASSERT(var > 0);
515 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
516 mask = (-UWORD(1)) >> (FLINT_BITS - A->bits);
517
518 Ecoeff = E->coeffs;
519 Eexp = E->exps;
520 Ei = 0;
521 for (Ai = 0; Ai < Alen; Ai++)
522 {
523 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(v), Acoeff + Ai,
524 evil_const_cast_nmod_poly_to_n_poly(ectx->fqctx->modulus), ctx->mod);
525 k = ((Aexp + N*Ai)[offset] >> shift) & mask;
526 if (fq_nmod_is_zero(v, ectx->fqctx))
527 {
528 continue;
529 }
530
531 if (Ei > 0 && mpoly_monomial_equal_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)))
532 {
533 /* append to previous */
534 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei - 1, k, v, ectx->fqctx);
535 }
536 else
537 {
538 FLINT_ASSERT(Ei == 0 || mpoly_monomial_gt_nomask_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)));
539
540 /* create new */
541 if (Ei >= E->alloc)
542 {
543 fq_nmod_mpolyn_fit_length(E, Ei + 1, ectx);
544 Ecoeff = E->coeffs;
545 Eexp = E->exps;
546 }
547 mpoly_monomial_set_extra(Eexp + N*Ei, Aexp + N*Ai, N, offset, -(k << shift));
548 n_poly_zero(Ecoeff + Ei);
549 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei, k, v, ectx->fqctx);
550 Ei++;
551 }
552 }
553 E->length = Ei;
554
555 fq_nmod_clear(v, ectx->fqctx);
556 }
557
558
559 /*
560 A = B using lowest degree representative
561 A is in Fp [x_0, ..., x_(var-1), x_(var-1)][x_var]
562 B is in (Fp[x_var]/alpha(x_var))[x_0, ..., x_(var-2)][x_(var-1)]
563 */
nmod_mpolyn_interp_lift_lg_mpolyn(slong * lastdeg_,nmod_mpolyn_t A,slong var,const nmod_mpoly_ctx_t ctx,fq_nmod_mpolyn_t B,const fq_nmod_mpoly_ctx_t ectx)564 void nmod_mpolyn_interp_lift_lg_mpolyn(
565 slong * lastdeg_,
566 nmod_mpolyn_t A,
567 slong var,
568 const nmod_mpoly_ctx_t ctx,
569 fq_nmod_mpolyn_t B,
570 const fq_nmod_mpoly_ctx_t ectx)
571 {
572 slong d = fq_nmod_ctx_degree(ectx->fqctx);
573 slong N = mpoly_words_per_exp_sp(B->bits, ctx->minfo);
574 slong offset, shift;
575 slong vi;
576 n_fq_poly_struct * Bcoeff = B->coeffs;
577 ulong * Bexp = B->exps;
578 slong Blen = B->length;
579 slong Bi;
580 n_poly_struct * Acoeff;
581 ulong * Aexp;
582 slong Ai;
583 slong lastdeg = -WORD(1);
584
585 FLINT_ASSERT(A->bits == B->bits);
586
587 nmod_mpolyn_fit_length(A, Blen, ctx);
588 Acoeff = A->coeffs;
589 Aexp = A->exps;
590
591 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
592
593 Ai = 0;
594 for (Bi = 0; Bi < Blen; Bi++)
595 {
596 if (Ai + (Bcoeff + Bi)->length >= A->alloc)
597 {
598 nmod_mpolyn_fit_length(A, Ai + (Bcoeff + Bi)->length, ctx);
599 Acoeff = A->coeffs;
600 Aexp = A->exps;
601 }
602 for (vi = (Bcoeff + Bi)->length - 1; vi >= 0; vi--)
603 {
604 if (!_n_fq_is_zero((Bcoeff + Bi)->coeffs + d*vi, d))
605 {
606 mpoly_monomial_set_extra(Aexp + N*Ai, Bexp + N*Bi, N, offset, vi << shift);
607 n_fq_get_n_poly(Acoeff + Ai, (Bcoeff + Bi)->coeffs + d*vi, ectx->fqctx);
608 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(Acoeff + Ai));
609 Ai++;
610 }
611 }
612 }
613 A->length = Ai;
614
615 *lastdeg_ = lastdeg;
616 }
617
618
nmod_mpolyn_interp_crt_lg_mpolyn(slong * lastdeg_,nmod_mpolyn_t F,nmod_mpolyn_t T,n_poly_t modulus,slong var,const nmod_mpoly_ctx_t ctx,fq_nmod_mpolyn_t A,const fq_nmod_mpoly_ctx_t ectx)619 int nmod_mpolyn_interp_crt_lg_mpolyn(
620 slong * lastdeg_,
621 nmod_mpolyn_t F,
622 nmod_mpolyn_t T,
623 n_poly_t modulus,
624 slong var,
625 const nmod_mpoly_ctx_t ctx,
626 fq_nmod_mpolyn_t A,
627 const fq_nmod_mpoly_ctx_t ectx)
628 {
629 slong d = fq_nmod_ctx_degree(ectx->fqctx);
630 int changed = 0;
631 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
632 slong offset, shift;
633 slong lastdeg = -WORD(1);
634 slong vi;
635 fq_nmod_t u, v;
636 n_poly_t w;
637 n_poly_struct * Tcoeff;
638 ulong * Texp;
639 slong Ti;
640 n_fq_poly_struct * Acoeff = A->coeffs;
641 slong Alen = A->length;
642 ulong * Aexp = A->exps;
643 slong Ai;
644 n_poly_struct * Fcoeff = F->coeffs;
645 slong Flen = F->length;
646 ulong * Fexp = F->exps;
647 slong Fi;
648 fq_nmod_t inv_m_eval;
649 fq_nmod_t at;
650
651 fq_nmod_init(inv_m_eval, ectx->fqctx);
652 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(inv_m_eval), modulus,
653 evil_const_cast_nmod_poly_to_n_poly(ectx->fqctx->modulus), ctx->mod);
654 fq_nmod_inv(inv_m_eval, inv_m_eval, ectx->fqctx);
655
656 fq_nmod_init(at, ectx->fqctx);
657 fq_nmod_init(u, ectx->fqctx);
658 fq_nmod_init(v, ectx->fqctx);
659 n_poly_init(w);
660
661 FLINT_ASSERT(var > 0);
662 FLINT_ASSERT(T->bits == A->bits);
663 FLINT_ASSERT(F->bits == A->bits);
664
665 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
666
667 Flen = F->length;
668
669 nmod_mpolyn_fit_length(T, FLINT_MAX(Flen, Alen), ctx);
670 Tcoeff = T->coeffs;
671 Texp = T->exps;
672 Ti = 0;
673
674 Fi = Ai = vi = 0;
675 if (Ai < Alen)
676 {
677 vi = n_poly_degree(A->coeffs + Ai);
678 }
679 while (Fi < Flen || Ai < Alen)
680 {
681 if (Ti >= T->alloc)
682 {
683 nmod_mpolyn_fit_length(T, Ti + FLINT_MAX(Flen - Fi, Alen - Ai), ctx);
684 Tcoeff = T->coeffs;
685 Texp = T->exps;
686 }
687
688 if (Fi < Flen && Ai < Alen && mpoly_monomial_equal_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift))
689 {
690 /* F term ok, A term ok */
691 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(u), Fcoeff + Fi,
692 evil_const_cast_nmod_poly_to_n_poly(ectx->fqctx->modulus), ctx->mod);
693 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + d*vi, ectx->fqctx);
694 fq_nmod_sub(v, at, u, ectx->fqctx);
695 if (!fq_nmod_is_zero(v, ectx->fqctx))
696 {
697 changed = 1;
698 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
699 n_poly_mod_mul(w, modulus,
700 evil_const_cast_nmod_poly_to_n_poly(u), ctx->mod);
701 n_poly_mod_add(Tcoeff + Ti, Fcoeff + Fi, w, ctx->mod);
702 }
703 else
704 {
705 n_poly_set(Tcoeff + Ti, Fcoeff + Fi);
706 }
707 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
708
709 Fi++;
710 do {
711 vi--;
712 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + d*vi, d));
713 if (vi < 0)
714 {
715 Ai++;
716 if (Ai < Alen)
717 {
718 vi = n_poly_degree(A->coeffs + Ai);
719 }
720 }
721 }
722 else if (Fi < Flen && (Ai >= Alen || mpoly_monomial_gt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)))
723 {
724 /* F term ok, A term missing */
725 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(v), Fcoeff + Fi,
726 evil_const_cast_nmod_poly_to_n_poly(ectx->fqctx->modulus), ctx->mod);
727 if (!fq_nmod_is_zero(v, ectx->fqctx))
728 {
729 changed = 1;
730 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
731 n_poly_mod_mul(w, evil_const_cast_nmod_poly_to_n_poly(u),
732 modulus, ctx->mod);
733 n_poly_mod_sub(Tcoeff + Ti, Fcoeff + Fi, w, ctx->mod);
734 }
735 else
736 {
737 n_poly_set(Tcoeff + Ti, Fcoeff + Fi);
738 }
739 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
740
741 Fi++;
742 }
743 else
744 {
745 FLINT_ASSERT(Ai < Alen && (Fi >= Flen || mpoly_monomial_lt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)));
746
747 /* F term missing, A term ok */
748 changed = 1;
749 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + d*vi, ectx->fqctx);
750 fq_nmod_mul(u, at, inv_m_eval, ectx->fqctx);
751 n_poly_mod_mul(Tcoeff + Ti, evil_const_cast_nmod_poly_to_n_poly(u),
752 modulus, ctx->mod);
753 mpoly_monomial_set_extra(Texp + N*Ti, Aexp + N*Ai, N, offset, vi << shift);
754
755 do {
756 vi--;
757 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + d*vi, d));
758 if (vi < 0)
759 {
760 Ai++;
761 if (Ai < Alen)
762 {
763 vi = n_poly_degree(A->coeffs + Ai);
764 }
765 }
766 }
767
768 FLINT_ASSERT(!n_poly_is_zero(Tcoeff + Ti));
769 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(Tcoeff + Ti));
770 Ti++;
771 }
772 T->length = Ti;
773
774 if (changed)
775 {
776 nmod_mpolyn_swap(T, F);
777 }
778
779 fq_nmod_clear(inv_m_eval, ectx->fqctx);
780 fq_nmod_clear(u, ectx->fqctx);
781 fq_nmod_clear(v, ectx->fqctx);
782 fq_nmod_clear(at, ectx->fqctx);
783 n_poly_clear(w);
784
785 FLINT_ASSERT(nmod_mpolyn_is_canonical(F, ctx));
786
787 *lastdeg_ = lastdeg;
788
789 return changed;
790 }
791
792
793 /******************** multivar - image in Fq *********************************/
794
795 /*
796 A = B mod alpha(x_var)
797 B is in Fp [x_0, ..., x_(var-2), x_(var-1)][x_var]
798 A is in (Fp/alpha(x_var))[x_0, ..., x_(var-2), x_(var-1)]
799 alpha is ectx->modulus
800 */
nmod_mpolyn_interp_reduce_lg_mpoly(fq_nmod_mpoly_t A,nmod_mpolyn_t B,const fq_nmod_mpoly_ctx_t ffctx,const nmod_mpoly_ctx_t ctx)801 void nmod_mpolyn_interp_reduce_lg_mpoly(
802 fq_nmod_mpoly_t A,
803 nmod_mpolyn_t B,
804 const fq_nmod_mpoly_ctx_t ffctx,
805 const nmod_mpoly_ctx_t ctx)
806 {
807 slong d = fq_nmod_ctx_degree(ffctx->fqctx);
808 slong N = N = mpoly_words_per_exp(B->bits, ctx->minfo);
809 slong i, Alen;
810
811 FLINT_ASSERT(A->bits == B->bits);
812 FLINT_ASSERT(B->bits <= FLINT_BITS);
813 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
814 FLINT_ASSERT(ffctx->minfo->ord == ORD_LEX);
815 FLINT_ASSERT(ffctx->minfo->nvars == ctx->minfo->nvars);
816
817 Alen = 0;
818 fq_nmod_mpoly_fit_length(A, B->length, ffctx);
819 for (i = 0; i < B->length; i++)
820 {
821 mpoly_monomial_set(A->exps + N*Alen, B->exps + N*i, N);
822
823 if (B->coeffs[i].length > d)
824 {
825 _nmod_poly_rem(A->coeffs + d*Alen, B->coeffs[i].coeffs,
826 B->coeffs[i].length, ffctx->fqctx->modulus->coeffs, d + 1,
827 fq_nmod_ctx_mod(ffctx->fqctx));
828 }
829 else
830 {
831 _n_fq_set_n_poly(A->coeffs + d*Alen, B->coeffs[i].coeffs,
832 B->coeffs[i].length, ffctx->fqctx);
833 }
834
835 Alen += !_n_fq_is_zero(A->coeffs + d*Alen, d);
836 }
837 A->length = Alen;
838 }
839
840 /*
841 A = B mod alpha(x_var)
842 B is in Fp [X][x_0, ..., x_(var-2), x_(var-1)][x_var]
843 A is in (Fp/alpha(x_var))[X][x_0, ..., x_(var-2), x_(var-1)]
844 alpha is ectx->modulus
845 */
nmod_mpolyun_interp_reduce_lg_mpolyu(fq_nmod_mpolyu_t A,nmod_mpolyun_t B,const fq_nmod_mpoly_ctx_t ffctx,const nmod_mpoly_ctx_t ctx)846 void nmod_mpolyun_interp_reduce_lg_mpolyu(
847 fq_nmod_mpolyu_t A,
848 nmod_mpolyun_t B,
849 const fq_nmod_mpoly_ctx_t ffctx,
850 const nmod_mpoly_ctx_t ctx)
851 {
852 slong i, k, Blen;
853 fq_nmod_mpoly_struct * Acoeff;
854 nmod_mpolyn_struct * Bcoeff;
855 ulong * Aexp, * Bexp;
856
857 Blen = B->length;
858 fq_nmod_mpolyu_fit_length(A, Blen, ffctx);
859 Acoeff = A->coeffs;
860 Bcoeff = B->coeffs;
861 Aexp = A->exps;
862 Bexp = B->exps;
863
864 k = 0;
865 for (i = 0; i < Blen; i++)
866 {
867 nmod_mpolyn_interp_reduce_lg_mpoly(Acoeff + k, Bcoeff + i, ffctx, ctx);
868 Aexp[k] = Bexp[i];
869 k += !fq_nmod_mpoly_is_zero(Acoeff + k, ffctx);
870 }
871 A->length = k;
872 }
873
874
875 /*
876 A = Ap using lowest degree
877 A is in Fp [x_0, ..., x_(var-2), x_(var-1)][x_var]
878 Ap is in (Fp/alpha(x_var))[x_0, ..., x_(var-2), x_(var-1)]
879 alpha is ectx->modulus
880 */
nmod_mpolyn_interp_lift_lg_mpoly(nmod_mpolyn_t A,const nmod_mpoly_ctx_t ctx,fq_nmod_mpoly_t Ap,const fq_nmod_mpoly_ctx_t ctxp)881 void nmod_mpolyn_interp_lift_lg_mpoly(
882 nmod_mpolyn_t A,
883 const nmod_mpoly_ctx_t ctx,
884 fq_nmod_mpoly_t Ap,
885 const fq_nmod_mpoly_ctx_t ctxp)
886 {
887 slong d = fq_nmod_ctx_degree(ctxp->fqctx);
888 slong i, N;
889
890 FLINT_ASSERT(Ap->bits == A->bits);
891 nmod_mpolyn_fit_length(A, Ap->length, ctx);
892 N = mpoly_words_per_exp(A->bits, ctx->minfo);
893 for (i = 0; i < Ap->length; i++)
894 {
895 mpoly_monomial_set(A->exps + N*i, Ap->exps + N*i, N);
896 n_fq_get_n_poly(A->coeffs + i, Ap->coeffs + d*i, ctxp->fqctx);
897 }
898 A->length = Ap->length;
899 }
900
901 /*
902 A = Ap using lowest degree
903 A is in Fp [X][x_0, ..., x_(var-2), x_(var-1)][x_var]
904 Ap is in (Fp/alpha(x_var))[X][x_0, ..., x_(var-2), x_(var-1)]
905 alpha is ectx->modulus
906 */
nmod_mpolyun_interp_lift_lg_mpolyu(nmod_mpolyun_t A,const nmod_mpoly_ctx_t ctx,fq_nmod_mpolyu_t Ap,const fq_nmod_mpoly_ctx_t ctxp)907 void nmod_mpolyun_interp_lift_lg_mpolyu(
908 nmod_mpolyun_t A,
909 const nmod_mpoly_ctx_t ctx,
910 fq_nmod_mpolyu_t Ap,
911 const fq_nmod_mpoly_ctx_t ctxp)
912 {
913 slong i;
914
915 FLINT_ASSERT(Ap->bits == A->bits);
916 nmod_mpolyun_fit_length(A, Ap->length, ctx);
917 for (i = 0; i < Ap->length; i++)
918 {
919 A->exps[i] = Ap->exps[i];
920 nmod_mpolyn_interp_lift_lg_mpoly(A->coeffs + i, ctx, Ap->coeffs + i, ctxp);
921 }
922 A->length = Ap->length;
923 }
924
925 /*
926 F = F + modulus*((A - F(alpha))/(modulus(alpha)))
927 no assumptions about matching monomials
928 */
nmod_mpolyn_interp_crt_lg_mpoly(slong * lastdeg,nmod_mpolyn_t F,nmod_mpolyn_t T,n_poly_t m,const nmod_mpoly_ctx_t ctx,fq_nmod_mpoly_t A,fq_nmod_t inv_m_eval,const fq_nmod_mpoly_ctx_t ffctx)929 static int nmod_mpolyn_interp_crt_lg_mpoly(
930 slong * lastdeg,
931 nmod_mpolyn_t F,
932 nmod_mpolyn_t T,
933 n_poly_t m,
934 const nmod_mpoly_ctx_t ctx,
935 fq_nmod_mpoly_t A,
936 fq_nmod_t inv_m_eval,
937 const fq_nmod_mpoly_ctx_t ffctx)
938 {
939 slong d = fq_nmod_ctx_degree(ffctx->fqctx);
940 int changed = 0;
941 slong i, j, k;
942 slong N;
943 fq_nmod_t u, v;
944 n_poly_t w;
945 flint_bitcnt_t bits = A->bits;
946 slong Flen = F->length, Alen = A->length;
947 ulong * Fexp = F->exps, * Aexp = A->exps;
948 ulong * Texp;
949 mp_limb_t * Acoeff = A->coeffs;
950 n_poly_struct * Fcoeff = F->coeffs;
951 n_poly_struct * Tcoeff;
952 fq_nmod_t at;
953
954 FLINT_ASSERT(F->bits == bits);
955 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
956
957 fq_nmod_init(u, ffctx->fqctx);
958 fq_nmod_init(v, ffctx->fqctx);
959 n_poly_init(w);
960 fq_nmod_init(at, ffctx->fqctx);
961
962 nmod_mpolyn_fit_length(T, Flen + Alen, ctx);
963 Texp = T->exps;
964 Tcoeff = T->coeffs;
965
966 N = mpoly_words_per_exp(bits, ctx->minfo);
967
968 i = j = k = 0;
969 while (i < Flen || j < Alen)
970 {
971 if (i < Flen && (j >= Alen
972 || mpoly_monomial_gt_nomask(Fexp + N*i, Aexp + N*j, N)))
973 {
974 FLINT_ASSERT(!n_poly_is_zero(Fcoeff + i));
975 FLINT_ASSERT(n_poly_degree(Fcoeff + i) < n_poly_degree(m));
976
977 /* F term ok, A term missing */
978 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(v), Fcoeff + i,
979 evil_const_cast_nmod_poly_to_n_poly(ffctx->fqctx->modulus), ctx->mod);
980 if (!fq_nmod_is_zero(v, ffctx->fqctx))
981 {
982 changed = 1;
983 fq_nmod_mul(u, v, inv_m_eval, ffctx->fqctx);
984 n_poly_mod_mul(w, evil_const_cast_nmod_poly_to_n_poly(u),
985 m, ctx->mod);
986 n_poly_mod_sub(Tcoeff + k, Fcoeff + i, w, ctx->mod);
987 } else {
988 n_poly_set(Tcoeff + k, Fcoeff + i);
989 }
990 FLINT_ASSERT(!n_poly_is_zero(Tcoeff + k));
991 *lastdeg = FLINT_MAX(*lastdeg, n_poly_degree(Tcoeff + k));
992
993 mpoly_monomial_set(Texp + N*k, Fexp + N*i, N);
994 k++;
995 i++;
996 }
997 else if (j < Alen && (i >= Flen
998 || mpoly_monomial_lt_nomask(Fexp + N*i, Aexp + N*j, N)))
999 {
1000 /* F term missing, A term ok */
1001 if (!_n_fq_is_zero(Acoeff + d*j, d))
1002 {
1003 changed = 1;
1004 n_fq_get_fq_nmod(at, Acoeff + d*j, ffctx->fqctx);
1005 fq_nmod_mul(u, at, inv_m_eval, ffctx->fqctx);
1006 n_poly_mod_mul(Tcoeff + k, m,
1007 evil_const_cast_nmod_poly_to_n_poly(u), ctx->mod);
1008 *lastdeg = FLINT_MAX(*lastdeg, n_poly_degree(Tcoeff + k));
1009 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
1010 k++;
1011 }
1012 j++;
1013 }
1014 else if (i < Flen && j < Alen
1015 && mpoly_monomial_equal(Fexp + N*i, Aexp + N*j, N))
1016 {
1017 FLINT_ASSERT(!n_poly_is_zero(Fcoeff + i));
1018 FLINT_ASSERT(n_poly_degree(Fcoeff + i) < n_poly_degree(m));
1019
1020 /* F term ok, A term ok */
1021 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(u), Fcoeff + i,
1022 evil_const_cast_nmod_poly_to_n_poly(ffctx->fqctx->modulus), ctx->mod);
1023 n_fq_get_fq_nmod(at, Acoeff + d*j, ffctx->fqctx);
1024 fq_nmod_sub(v, at, u, ffctx->fqctx);
1025 if (!fq_nmod_is_zero(v, ffctx->fqctx))
1026 {
1027 changed = 1;
1028 fq_nmod_mul(u, v, inv_m_eval, ffctx->fqctx);
1029 n_poly_mod_mul(w, m, evil_const_cast_nmod_poly_to_n_poly(u), ctx->mod);
1030 n_poly_mod_add(Tcoeff + k, Fcoeff + i, w, ctx->mod);
1031 } else {
1032 n_poly_set(Tcoeff + k, Fcoeff + i);
1033 }
1034 FLINT_ASSERT(!n_poly_is_zero(Tcoeff + k));
1035 *lastdeg = FLINT_MAX(*lastdeg, n_poly_degree(Tcoeff + k));
1036 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
1037 k++;
1038 i++;
1039 j++;
1040 }
1041 else
1042 {
1043 FLINT_ASSERT(0);
1044 }
1045 }
1046
1047 nmod_mpolyn_set_length(T, k, ctx);
1048
1049 if (changed)
1050 {
1051 nmod_mpolyn_swap(T, F);
1052 }
1053
1054 fq_nmod_clear(u, ffctx->fqctx);
1055 fq_nmod_clear(v, ffctx->fqctx);
1056 n_poly_clear(w);
1057 fq_nmod_clear(at, ffctx->fqctx);
1058
1059 return changed;
1060 }
1061
1062 /*
1063 F = F + modulus*((A - F(alpha))/(modulus(alpha)))
1064 no assumptions about matching monomials
1065 */
nmod_mpolyun_interp_crt_lg_mpolyu(slong * lastdeg,nmod_mpolyun_t F,nmod_mpolyun_t T,n_poly_t m,const nmod_mpoly_ctx_t ctx,fq_nmod_mpolyu_t A,const fq_nmod_mpoly_ctx_t ffctx)1066 int nmod_mpolyun_interp_crt_lg_mpolyu(
1067 slong * lastdeg,
1068 nmod_mpolyun_t F,
1069 nmod_mpolyun_t T,
1070 n_poly_t m,
1071 const nmod_mpoly_ctx_t ctx,
1072 fq_nmod_mpolyu_t A,
1073 const fq_nmod_mpoly_ctx_t ffctx)
1074 {
1075 int changed = 0;
1076 slong i, j, k;
1077 ulong * Texp;
1078 ulong * Fexp;
1079 ulong * Aexp;
1080 slong Flen;
1081 slong Alen;
1082 nmod_mpolyn_t S;
1083 nmod_mpolyn_struct * Tcoeff;
1084 nmod_mpolyn_struct * Fcoeff;
1085 fq_nmod_mpoly_struct * Acoeff;
1086 fq_nmod_mpoly_t zero;
1087 fq_nmod_t inv_m_eval;
1088
1089 *lastdeg = -WORD(1);
1090
1091 FLINT_ASSERT(F->bits == T->bits);
1092 FLINT_ASSERT(T->bits == A->bits);
1093
1094 nmod_mpolyn_init(S, F->bits, ctx);
1095
1096 Flen = F->length;
1097 Alen = A->length;
1098 nmod_mpolyun_fit_length(T, Flen + Alen, ctx);
1099
1100 Tcoeff = T->coeffs;
1101 Fcoeff = F->coeffs;
1102 Acoeff = A->coeffs;
1103 Texp = T->exps;
1104 Fexp = F->exps;
1105 Aexp = A->exps;
1106
1107 fq_nmod_mpoly_init(zero, ffctx);
1108 fq_nmod_mpoly_fit_length_reset_bits(zero, 0, A->bits, ffctx);
1109
1110 fq_nmod_init(inv_m_eval, ffctx->fqctx);
1111 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(inv_m_eval), m,
1112 evil_const_cast_nmod_poly_to_n_poly(ffctx->fqctx->modulus), ctx->mod);
1113 fq_nmod_inv(inv_m_eval, inv_m_eval, ffctx->fqctx);
1114
1115 i = j = k = 0;
1116 while (i < Flen || j < Alen)
1117 {
1118 if (i < Flen && (j >= Alen || Fexp[i] > Aexp[j]))
1119 {
1120 /* F term ok, A term missing */
1121 nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
1122 changed |= nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
1123 S, m, ctx, zero, inv_m_eval, ffctx);
1124 Texp[k] = Fexp[i];
1125 k++;
1126 i++;
1127 }
1128 else if (j < Alen && (i >= Flen || Aexp[j] > Fexp[i]))
1129 {
1130 /* F term missing, A term ok */
1131 nmod_mpolyn_zero(Tcoeff + k, ctx);
1132 changed |= nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
1133 S, m, ctx, Acoeff + j, inv_m_eval, ffctx);
1134 Texp[k] = Aexp[j];
1135 k++;
1136 j++;
1137 }
1138 else if (i < Flen && j < Alen && (Fexp[i] == Aexp[j]))
1139 {
1140 /* F term ok, A term ok */
1141 nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
1142 changed |= nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
1143 S, m, ctx, Acoeff + j, inv_m_eval, ffctx);
1144 Texp[k] = Aexp[j];
1145 FLINT_ASSERT(!nmod_mpolyn_is_zero(Tcoeff + k, ctx));
1146 k++;
1147 i++;
1148 j++;
1149 }
1150 else
1151 {
1152 FLINT_ASSERT(0);
1153 }
1154 }
1155 T->length = k;
1156
1157 if (changed)
1158 {
1159 nmod_mpolyun_swap(T, F);
1160 }
1161
1162 fq_nmod_clear(inv_m_eval, ffctx->fqctx);
1163
1164 nmod_mpolyn_clear(S, ctx);
1165 fq_nmod_mpoly_clear(zero, ffctx);
1166 return changed;
1167 }
1168
nmod_mpolyn_interp_mcrt_lg_mpoly(slong * lastdeg_,nmod_mpolyn_t H,const nmod_mpoly_ctx_t smctx,const n_poly_t m,const mp_limb_t * inv_m_eval,fq_nmod_mpoly_t A,const fq_nmod_mpoly_ctx_t lgctx)1169 int nmod_mpolyn_interp_mcrt_lg_mpoly(
1170 slong * lastdeg_,
1171 nmod_mpolyn_t H,
1172 const nmod_mpoly_ctx_t smctx,
1173 const n_poly_t m,
1174 const mp_limb_t * inv_m_eval,
1175 fq_nmod_mpoly_t A,
1176 const fq_nmod_mpoly_ctx_t lgctx)
1177 {
1178 slong lastdeg = *lastdeg_;
1179 slong i, lgd = fq_nmod_ctx_degree(lgctx->fqctx);
1180 #if FLINT_WANT_ASSERT
1181 slong N = mpoly_words_per_exp(A->bits, smctx->minfo);
1182 #endif
1183 int changed = 0;
1184 mp_limb_t * u = FLINT_ARRAY_ALLOC(lgd, mp_limb_t);
1185 n_poly_t w;
1186
1187 n_poly_init(w);
1188
1189 FLINT_ASSERT(H->length == A->length);
1190 FLINT_ASSERT(H->bits == A->bits);
1191
1192 for (i = 0; i < A->length; i++)
1193 {
1194 FLINT_ASSERT(mpoly_monomial_equal(H->exps + N*i, A->exps + N*i, N));
1195 _n_fq_set_n_poly(u, H->coeffs[i].coeffs, H->coeffs[i].length, lgctx->fqctx);
1196 n_fq_sub(u, A->coeffs + lgd*i, u, lgctx->fqctx);
1197 if (!_n_fq_is_zero(u, lgd))
1198 {
1199 changed = 1;
1200 n_fq_mul(u, u, inv_m_eval, lgctx->fqctx);
1201 _n_poly_mul_n_fq(w, m, u, lgctx->fqctx);
1202 n_poly_mod_add(H->coeffs + i, H->coeffs + i, w, smctx->mod);
1203 }
1204
1205 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(H->coeffs + i));
1206
1207 FLINT_ASSERT(n_poly_degree(H->coeffs + i) < n_poly_degree(m) +
1208 nmod_poly_degree(lgctx->fqctx->modulus));
1209 }
1210
1211 *lastdeg_ = lastdeg;
1212
1213 flint_free(u);
1214 n_poly_clear(w);
1215
1216 return changed;
1217 }
1218
1219
1220
1221 /*
1222 Update H so that it does not change mod m, and is now A mod p
1223 It is asserted that the monomials in H and A match
1224 */
nmod_mpolyn_CRT_fq_nmod_mpoly(slong * lastdeg,nmod_mpolyn_t H,const nmod_mpoly_ctx_t ctx,n_poly_t m,fq_nmod_t inv_m_eval,fq_nmod_mpoly_t A,const fq_nmod_mpoly_ctx_t ctxp)1225 int nmod_mpolyn_CRT_fq_nmod_mpoly(
1226 slong * lastdeg,
1227 nmod_mpolyn_t H,
1228 const nmod_mpoly_ctx_t ctx,
1229 n_poly_t m,
1230 fq_nmod_t inv_m_eval,
1231 fq_nmod_mpoly_t A,
1232 const fq_nmod_mpoly_ctx_t ctxp)
1233 {
1234 slong d = fq_nmod_ctx_degree(ctxp->fqctx);
1235 slong i;
1236 #if FLINT_WANT_ASSERT
1237 slong N;
1238 #endif
1239 int changed = 0;
1240 fq_nmod_t u, v, at;
1241 n_poly_t w;
1242
1243 fq_nmod_init(u, ctxp->fqctx);
1244 fq_nmod_init(v, ctxp->fqctx);
1245 fq_nmod_init(at, ctxp->fqctx);
1246 n_poly_init(w);
1247
1248 FLINT_ASSERT(H->length == A->length);
1249 FLINT_ASSERT(H->bits == A->bits);
1250 #if FLINT_WANT_ASSERT
1251 N = mpoly_words_per_exp(A->bits, ctx->minfo);
1252 #endif
1253 for (i = 0; i < A->length; i++)
1254 {
1255 FLINT_ASSERT(mpoly_monomial_equal(H->exps + N*i, A->exps + N*i, N));
1256 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(u), H->coeffs + i,
1257 evil_const_cast_nmod_poly_to_n_poly(ctxp->fqctx->modulus), ctx->mod);
1258 n_fq_get_fq_nmod(at, A->coeffs + d*i, ctxp->fqctx);
1259 fq_nmod_sub(v, at, u, ctxp->fqctx);
1260 if (!fq_nmod_is_zero(v, ctxp->fqctx))
1261 {
1262 changed = 1;
1263 fq_nmod_mul(u, v, inv_m_eval, ctxp->fqctx);
1264 n_poly_mod_mul(w, evil_const_cast_nmod_poly_to_n_poly(u), m, ctx->mod);
1265 n_poly_mod_add(H->coeffs + i, H->coeffs + i, w, ctx->mod);
1266 }
1267
1268 *lastdeg = FLINT_MAX(*lastdeg, n_poly_degree(H->coeffs + i));
1269
1270 FLINT_ASSERT(n_poly_degree(H->coeffs + i) < n_poly_degree(m) +
1271 nmod_poly_degree(ctxp->fqctx->modulus));
1272 }
1273
1274 fq_nmod_clear(u, ctxp->fqctx);
1275 fq_nmod_clear(v, ctxp->fqctx);
1276 fq_nmod_clear(at, ctxp->fqctx);
1277 n_poly_clear(w);
1278
1279 return changed;
1280 }
1281
nmod_mpolyun_interp_mcrt_lg_mpolyu(slong * lastdeg,nmod_mpolyun_t H,const nmod_mpoly_ctx_t ctx,n_poly_t m,fq_nmod_mpolyu_t A,const fq_nmod_mpoly_ctx_t ctxp)1282 int nmod_mpolyun_interp_mcrt_lg_mpolyu(
1283 slong * lastdeg,
1284 nmod_mpolyun_t H,
1285 const nmod_mpoly_ctx_t ctx,
1286 n_poly_t m,
1287 fq_nmod_mpolyu_t A,
1288 const fq_nmod_mpoly_ctx_t ctxp)
1289 {
1290 slong i;
1291 int changed = 0;
1292 fq_nmod_t inv_m_eval;
1293
1294 *lastdeg = -WORD(1);
1295
1296 fq_nmod_init(inv_m_eval, ctxp->fqctx);
1297 n_poly_mod_rem(evil_cast_nmod_poly_to_n_poly(inv_m_eval), m,
1298 evil_const_cast_nmod_poly_to_n_poly(ctxp->fqctx->modulus), ctx->mod);
1299 fq_nmod_inv(inv_m_eval, inv_m_eval, ctxp->fqctx);
1300
1301 FLINT_ASSERT(H->bits == A->bits);
1302 FLINT_ASSERT(H->length == A->length);
1303 for (i = 0; i < A->length; i++)
1304 {
1305 FLINT_ASSERT(H->exps[i] == A->exps[i]);
1306 changed |= nmod_mpolyn_CRT_fq_nmod_mpoly(lastdeg, H->coeffs + i, ctx, m,
1307 inv_m_eval, A->coeffs + i, ctxp);
1308 }
1309 H->length = A->length;
1310 fq_nmod_clear(inv_m_eval, ctxp->fqctx);
1311 return changed;
1312 }
1313
1314 /*****************************************************************************/
1315
1316 /*
1317 E = A(v = alpha)
1318 A is in Fq[X][v]
1319 E is in Fq[X]
1320 */
1321
fq_nmod_mpolyn_interp_reduce_sm_poly(fq_nmod_poly_t E,const fq_nmod_mpolyn_t A,const fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)1322 void fq_nmod_mpolyn_interp_reduce_sm_poly(
1323 fq_nmod_poly_t E,
1324 const fq_nmod_mpolyn_t A,
1325 const fq_nmod_t alpha,
1326 const fq_nmod_mpoly_ctx_t ctx)
1327 {
1328 fq_nmod_t v;
1329 slong Ai, Alen, k;
1330 n_poly_struct * Acoeff;
1331 ulong * Aexp;
1332 slong N, off, shift;
1333
1334 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
1335 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
1336
1337 fq_nmod_init(v, ctx->fqctx);
1338
1339 Acoeff = A->coeffs;
1340 Aexp = A->exps;
1341 Alen = A->length;
1342 Ai = 0;
1343 fq_nmod_poly_zero(E, ctx->fqctx);
1344 for (Ai = 0; Ai < Alen; Ai++)
1345 {
1346 n_fq_poly_evaluate_fq_nmod(v, Acoeff + Ai, alpha, ctx->fqctx);
1347 k = (Aexp + N*Ai)[off] >> shift;
1348 fq_nmod_poly_set_coeff(E, k, v, ctx->fqctx);
1349 }
1350
1351 fq_nmod_clear(v, ctx->fqctx);
1352 }
1353
1354 /*
1355 A = B
1356 A is in Fq[X][v] (no v appears)
1357 B is in Fq[X]
1358 */
1359
fq_nmod_mpolyn_interp_lift_sm_poly(fq_nmod_mpolyn_t A,const fq_nmod_poly_t B,const fq_nmod_mpoly_ctx_t ctx)1360 void fq_nmod_mpolyn_interp_lift_sm_poly(
1361 fq_nmod_mpolyn_t A,
1362 const fq_nmod_poly_t B,
1363 const fq_nmod_mpoly_ctx_t ctx)
1364 {
1365 slong Bi;
1366 slong Blen = fq_nmod_poly_length(B, ctx->fqctx);
1367 fq_nmod_struct * Bcoeff = B->coeffs;
1368 n_poly_struct * Acoeff;
1369 ulong * Aexp;
1370 slong Ai;
1371 slong N, off, shift;
1372
1373 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
1374 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
1375
1376 fq_nmod_mpolyn_fit_length(A, Blen, ctx);
1377 Acoeff = A->coeffs;
1378 Aexp = A->exps;
1379
1380 Ai = 0;
1381 for (Bi = Blen - 1; Bi >= 0; Bi--)
1382 {
1383 if (!fq_nmod_is_zero(Bcoeff + Bi, ctx->fqctx))
1384 {
1385 FLINT_ASSERT(Ai < A->alloc);
1386
1387 n_fq_poly_set_fq_nmod(Acoeff + Ai, Bcoeff + Bi, ctx->fqctx);
1388 mpoly_monomial_zero(Aexp + N*Ai, N);
1389 (Aexp + N*Ai)[off] = Bi << shift;
1390 Ai++;
1391 }
1392 }
1393 A->length = Ai;
1394 }
1395
1396 /*
1397 F = F + modulus*(A - F(v = alpha))
1398 no assumptions about matching monomials
1399 F is in Fq[X][v]
1400 A is in Fq[X]
1401 it is expected that modulus(alpha) == 1
1402 */
1403
fq_nmod_mpolyn_interp_crt_sm_poly(slong * lastdeg_,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,const fq_nmod_poly_t A,const fq_nmod_poly_t modulus,const fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)1404 int fq_nmod_mpolyn_interp_crt_sm_poly(
1405 slong * lastdeg_,
1406 fq_nmod_mpolyn_t F,
1407 fq_nmod_mpolyn_t T,
1408 const fq_nmod_poly_t A,
1409 const fq_nmod_poly_t modulus,
1410 const fq_nmod_t alpha,
1411 const fq_nmod_mpoly_ctx_t ctx)
1412 {
1413 int changed = 0;
1414 slong lastdeg = -WORD(1);
1415 fq_nmod_t u, v;
1416 slong Fi, Ti, Ai;
1417 fq_nmod_struct * Acoeff = A->coeffs;
1418 slong Flen = F->length;
1419 n_poly_struct * Fcoeffs = F->coeffs;
1420 ulong * Fexps = F->exps;
1421 n_poly_struct * Tcoeffs;
1422 ulong * Texps;
1423 fq_nmod_poly_t tp;
1424 slong N, off, shift;
1425 n_poly_t tpt;
1426
1427 N = mpoly_words_per_exp_sp(F->bits, ctx->minfo);
1428 mpoly_gen_offset_shift_sp(&off, &shift, 0, F->bits, ctx->minfo);
1429
1430 Fi = 0;
1431 Ai = fq_nmod_poly_degree(A, ctx->fqctx);
1432
1433 fq_nmod_init(u, ctx->fqctx);
1434 fq_nmod_init(v, ctx->fqctx);
1435 fq_nmod_poly_init(tp, ctx->fqctx);
1436 n_poly_init(tpt);
1437
1438 fq_nmod_mpolyn_fit_length(T, Flen + Ai + 1, ctx);
1439 Tcoeffs = T->coeffs;
1440 Texps = T->exps;
1441 Ti = 0;
1442
1443 while (Fi < Flen || Ai >= 0)
1444 {
1445 FLINT_ASSERT(Ti < T->alloc);
1446
1447 if (Fi < Flen)
1448 {
1449 FLINT_ASSERT(!n_poly_is_zero(Fcoeffs + Fi));
1450 FLINT_ASSERT(n_poly_degree(Fcoeffs + Fi) < fq_nmod_poly_degree(modulus, ctx->fqctx));
1451 }
1452
1453 if (Ai >= 0)
1454 {
1455 FLINT_ASSERT(!fq_nmod_is_zero(Acoeff + Ai, ctx->fqctx));
1456 }
1457
1458 mpoly_monomial_zero(Texps + N*Ti, N);
1459
1460 if (Fi < Flen && Ai >= 0 && ((Fexps + N*Fi)[off]>>shift) == Ai)
1461 {
1462 /* F term ok, A term ok */
1463 n_fq_poly_evaluate_fq_nmod(u, Fcoeffs + Fi, alpha, ctx->fqctx);
1464 fq_nmod_sub(v, Acoeff + Ai, u, ctx->fqctx);
1465 if (!fq_nmod_is_zero(v, ctx->fqctx))
1466 {
1467 changed = 1;
1468 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
1469 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
1470 n_fq_poly_add(Tcoeffs + Ti, Fcoeffs + Fi, tpt, ctx->fqctx);
1471 }
1472 else
1473 {
1474 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, ctx->fqctx);
1475 }
1476
1477 (Texps + N*Ti)[off] = Ai << shift;
1478 Fi++;
1479 do {
1480 Ai--;
1481 } while (Ai >= 0 && fq_nmod_is_zero(Acoeff + Ai, ctx->fqctx));
1482 }
1483 else if (Fi < Flen && (Ai < 0 || ((Fexps + N*Fi)[off]>>shift) > Ai))
1484 {
1485 /* F term ok, A term missing */
1486 n_fq_poly_evaluate_fq_nmod(v, Fcoeffs + Fi, alpha, ctx->fqctx);
1487 if (!fq_nmod_is_zero(v, ctx->fqctx))
1488 {
1489 changed = 1;
1490 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
1491 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
1492 n_fq_poly_sub(Tcoeffs + Ti, Fcoeffs + Fi, tpt, ctx->fqctx);
1493 }
1494 else
1495 {
1496 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, ctx->fqctx);
1497 }
1498
1499 (Texps + N*Ti)[off] = (Fexps + N*Fi)[off];
1500 Fi++;
1501 }
1502 else if (Ai >= 0 && (Fi >= Flen || ((Fexps + N*Fi)[off]>>shift) < Ai))
1503 {
1504 /* F term missing, A term ok */
1505 changed = 1;
1506 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, Acoeff + Ai, ctx->fqctx);
1507 n_fq_poly_set_fq_nmod_poly(Tcoeffs + Ti, tp, ctx->fqctx);
1508
1509 (Texps + N*Ti)[off] = Ai << shift;
1510 do {
1511 Ai--;
1512 } while (Ai >= 0 && fq_nmod_is_zero(Acoeff + Ai, ctx->fqctx));
1513 }
1514 else
1515 {
1516 FLINT_ASSERT(0);
1517 }
1518
1519 FLINT_ASSERT(!n_poly_is_zero(Tcoeffs + Ti));
1520 lastdeg = FLINT_MAX(lastdeg, n_poly_degree(Tcoeffs + Ti));
1521
1522 Ti++;
1523 }
1524 T->length = Ti;
1525
1526 fq_nmod_clear(u, ctx->fqctx);
1527 fq_nmod_clear(v, ctx->fqctx);
1528 fq_nmod_poly_clear(tp, ctx->fqctx);
1529 n_poly_clear(tpt);
1530
1531 if (changed)
1532 {
1533 fq_nmod_mpolyn_swap(T, F);
1534 }
1535
1536 *lastdeg_ = lastdeg;
1537 return changed;
1538 }
1539
1540
fq_nmod_mpolyn_interp_lift_sm_bpoly(fq_nmod_mpolyn_t F,n_fq_bpoly_t A,const fq_nmod_mpoly_ctx_t ctx)1541 void fq_nmod_mpolyn_interp_lift_sm_bpoly(
1542 fq_nmod_mpolyn_t F,
1543 n_fq_bpoly_t A,
1544 const fq_nmod_mpoly_ctx_t ctx)
1545 {
1546 slong d = fq_nmod_ctx_degree(ctx->fqctx);
1547 slong N = mpoly_words_per_exp_sp(F->bits, ctx->minfo);
1548 slong i, j, Fi;
1549 slong off0, shift0, off1, shift1;
1550
1551 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, ctx->minfo);
1552 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, ctx->minfo);
1553
1554 Fi = 0;
1555 for (i = A->length - 1; i >= 0; i--)
1556 {
1557 n_fq_poly_struct * Ai = A->coeffs + i;
1558 for (j = Ai->length - 1; j >= 0; j--)
1559 {
1560 if (_n_fq_is_zero(Ai->coeffs + d*j, d))
1561 continue;
1562
1563 fq_nmod_mpolyn_fit_length(F, Fi + 1, ctx);
1564 mpoly_monomial_zero(F->exps + N*Fi, N);
1565 (F->exps + N*Fi)[off0] += (i << shift0);
1566 (F->exps + N*Fi)[off1] += (j << shift1);
1567 n_fq_poly_set_n_fq(F->coeffs + Fi, Ai->coeffs + d*j, ctx->fqctx);
1568 Fi++;
1569 }
1570 }
1571
1572 F->length = Fi;
1573 }
1574
1575
fq_nmod_mpolyn_interp_crt_sm_bpoly(slong * lastdeg,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,const n_fq_bpoly_t A,const n_fq_poly_t modulus,n_fq_poly_t alphapow,const fq_nmod_mpoly_ctx_t ctx)1576 int fq_nmod_mpolyn_interp_crt_sm_bpoly(
1577 slong * lastdeg,
1578 fq_nmod_mpolyn_t F,
1579 fq_nmod_mpolyn_t T,
1580 const n_fq_bpoly_t A,
1581 const n_fq_poly_t modulus,
1582 n_fq_poly_t alphapow,
1583 const fq_nmod_mpoly_ctx_t ctx)
1584 {
1585 int changed = 0;
1586 slong d = fq_nmod_ctx_degree(ctx->fqctx);
1587 slong N = mpoly_words_per_exp(F->bits, ctx->minfo);
1588 slong off0, shift0, off1, shift1;
1589 n_poly_struct * Acoeffs = A->coeffs;
1590 slong Fi, Ti, Ai, ai;
1591 slong Flen = F->length;
1592 ulong * Fexps = F->exps;
1593 n_fq_poly_struct * Fcoeffs = F->coeffs;
1594 ulong * Texps = T->exps;
1595 n_fq_poly_struct * Tcoeffs = T->coeffs;
1596 mp_limb_t * v = FLINT_ARRAY_ALLOC(d, mp_limb_t);
1597 ulong Fexpi, mask;
1598
1599 FLINT_ASSERT(fq_nmod_mpolyn_is_canonical(F, ctx));
1600 FLINT_ASSERT(n_fq_bpoly_is_canonical(A, ctx->fqctx));
1601
1602 mask = (-UWORD(1)) >> (FLINT_BITS - F->bits);
1603 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, ctx->minfo);
1604 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, ctx->minfo);
1605
1606 FLINT_ASSERT(T->bits == F->bits);
1607
1608 *lastdeg = -1;
1609
1610 Ti = Fi = 0;
1611 Ai = A->length - 1;
1612 ai = (Ai < 0) ? 0 : n_poly_degree(Acoeffs + Ai);
1613
1614 while (Fi < Flen || Ai >= 0)
1615 {
1616 if (Ti >= T->alloc)
1617 {
1618 slong extra = FLINT_MAX(Flen - Fi, Ai);
1619 fq_nmod_mpolyn_fit_length(T, Ti + extra + 1, ctx);
1620 Tcoeffs = T->coeffs;
1621 Texps = T->exps;
1622 }
1623
1624 if (Fi < Flen)
1625 Fexpi = pack_exp2(((Fexps + N*Fi)[off0]>>shift0)&mask,
1626 ((Fexps + N*Fi)[off1]>>shift1)&mask);
1627 else
1628 Fexpi = 0;
1629
1630 if (Fi < Flen && Ai >= 0 && Fexpi == pack_exp2(Ai, ai))
1631 {
1632 /* F term ok, A term ok */
1633 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
1634
1635 n_fq_poly_eval_pow(v, Fcoeffs + Fi, alphapow, ctx->fqctx);
1636 n_fq_sub(v, Acoeffs[Ai].coeffs + d*ai, v, ctx->fqctx);
1637 if (!_n_fq_is_zero(v, d))
1638 {
1639 changed = 1;
1640 n_fq_poly_scalar_addmul_n_fq(Tcoeffs + Ti,
1641 Fcoeffs + Fi, modulus, v, ctx->fqctx);
1642 }
1643 else
1644 {
1645 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, ctx->fqctx);
1646 }
1647
1648 Fi++;
1649 do {
1650 ai--;
1651 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + d*ai, d));
1652 if (ai < 0)
1653 {
1654 do {
1655 Ai--;
1656 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
1657 if (Ai >= 0)
1658 ai = n_fq_poly_degree(Acoeffs + Ai);
1659 }
1660 }
1661 else if (Ai >= 0 && (Fi >= Flen || Fexpi < pack_exp2(Ai, ai)))
1662 {
1663 /* F term missing, A term ok */
1664
1665 mpoly_monomial_zero(Texps + N*Ti, N);
1666 (Texps + N*Ti)[off0] += (Ai << shift0);
1667 (Texps + N*Ti)[off1] += (ai << shift1);
1668
1669 changed = 1;
1670 n_fq_poly_scalar_mul_n_fq(Tcoeffs + Ti, modulus,
1671 Acoeffs[Ai].coeffs + d*ai, ctx->fqctx);
1672
1673 do {
1674 ai--;
1675 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + d*ai, d));
1676 if (ai < 0)
1677 {
1678 do {
1679 Ai--;
1680 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
1681 if (Ai >= 0)
1682 ai = n_fq_poly_degree(Acoeffs + Ai);
1683 }
1684 }
1685 else
1686 {
1687 FLINT_ASSERT(Fi < Flen && (Ai < 0 || Fexpi > pack_exp2(Ai, ai)));
1688 /* F term ok, Aterm missing */
1689 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
1690
1691 n_fq_poly_eval_pow(v, Fcoeffs + Fi, alphapow, ctx->fqctx);
1692 if (!_n_fq_is_zero(v, d))
1693 {
1694 changed = 1;
1695 _n_fq_neg(v, v, d, ctx->fqctx->mod);
1696 n_fq_poly_scalar_addmul_n_fq(Tcoeffs + Ti,
1697 Fcoeffs + Fi, modulus, v, ctx->fqctx);
1698 }
1699 else
1700 {
1701 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, ctx->fqctx);
1702 }
1703
1704 Fi++;
1705 }
1706
1707 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeffs + Ti));
1708 *lastdeg = FLINT_MAX(*lastdeg, n_fq_poly_degree(Tcoeffs + Ti));
1709 Ti++;
1710 }
1711
1712 T->length = Ti;
1713
1714 if (changed)
1715 fq_nmod_mpolyn_swap(T, F);
1716
1717 flint_free(v);
1718
1719 return changed;
1720 }
1721
1722
1723 /****************************************************************************/
1724
1725 /*
1726 E = A(x_var = alpha)
1727 A is in Fq[x_0, ..., x_(var-2), x_(var-1)][x_var]
1728 E is in Fq[x_0, ..., x_(var-2)][x_(var-1)]
1729 */
fq_nmod_mpolyn_interp_reduce_sm_mpolyn(fq_nmod_mpolyn_t E,fq_nmod_mpolyn_t A,slong var,fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)1730 void fq_nmod_mpolyn_interp_reduce_sm_mpolyn(
1731 fq_nmod_mpolyn_t E,
1732 fq_nmod_mpolyn_t A,
1733 slong var,
1734 fq_nmod_t alpha,
1735 const fq_nmod_mpoly_ctx_t ctx)
1736 {
1737 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
1738 slong offset, shift, k;
1739 ulong mask;
1740 fq_nmod_t v;
1741 n_poly_struct * Acoeff = A->coeffs;
1742 ulong * Aexp = A->exps;
1743 slong Alen = A->length;
1744 slong Ai;
1745 n_poly_struct * Ecoeff;
1746 ulong * Eexp;
1747 slong Ei;
1748
1749 fq_nmod_init(v, ctx->fqctx);
1750
1751 FLINT_ASSERT(var > 0);
1752 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
1753 mask = (-UWORD(1)) >> (FLINT_BITS - A->bits);
1754
1755 Ecoeff = E->coeffs;
1756 Eexp = E->exps;
1757 Ei = 0;
1758 for (Ai = 0; Ai < Alen; Ai++)
1759 {
1760 n_fq_poly_evaluate_fq_nmod(v, Acoeff + Ai, alpha, ctx->fqctx);
1761 k = ((Aexp + N*Ai)[offset] >> shift) & mask;
1762 if (fq_nmod_is_zero(v, ctx->fqctx))
1763 {
1764 continue;
1765 }
1766
1767 if (Ei > 0 && mpoly_monomial_equal_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)))
1768 {
1769 /* append to previous */
1770 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei - 1, k, v, ctx->fqctx);
1771 }
1772 else
1773 {
1774 FLINT_ASSERT(Ei == 0 || mpoly_monomial_gt_nomask_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)));
1775
1776 /* create new */
1777 if (Ei >= E->alloc)
1778 {
1779 fq_nmod_mpolyn_fit_length(E, Ei + 1, ctx);
1780 Ecoeff = E->coeffs;
1781 Eexp = E->exps;
1782 }
1783 mpoly_monomial_set_extra(Eexp + N*Ei, Aexp + N*Ai, N, offset, -(k << shift));
1784 n_poly_zero(Ecoeff + Ei);
1785 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei, k, v, ctx->fqctx);
1786 Ei++;
1787 }
1788 }
1789 E->length = Ei;
1790
1791 fq_nmod_clear(v, ctx->fqctx);
1792 }
1793
1794
1795 /*
1796 A = B
1797 A is in Fq[x_0, ..., x_(var-1), x_(var-1)][x_var]
1798 B is in Fq[x_0, ..., x_(var-2)][x_(var-1)]
1799 */
fq_nmod_mpolyn_interp_lift_sm_mpolyn(fq_nmod_mpolyn_t A,fq_nmod_mpolyn_t B,slong var,const fq_nmod_mpoly_ctx_t ctx)1800 void fq_nmod_mpolyn_interp_lift_sm_mpolyn(
1801 fq_nmod_mpolyn_t A,
1802 fq_nmod_mpolyn_t B,
1803 slong var,
1804 const fq_nmod_mpoly_ctx_t ctx)
1805 {
1806 slong d = fq_nmod_ctx_degree(ctx->fqctx);
1807 slong N = mpoly_words_per_exp_sp(B->bits, ctx->minfo);
1808 slong offset, shift;
1809 slong vi;
1810
1811 n_fq_poly_struct * Bcoeff = B->coeffs;
1812 ulong * Bexp = B->exps;
1813 slong Blen = B->length;
1814 slong Bi;
1815
1816 n_fq_poly_struct * Acoeff;
1817 ulong * Aexp;
1818 slong Ai;
1819
1820 fq_nmod_mpolyn_fit_length(A, Blen, ctx);
1821 Acoeff = A->coeffs;
1822 Aexp = A->exps;
1823
1824 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
1825
1826 Ai = 0;
1827 for (Bi = 0; Bi < Blen; Bi++)
1828 {
1829 if (Ai + (Bcoeff + Bi)->length >= A->alloc)
1830 {
1831 fq_nmod_mpolyn_fit_length(A, Ai + (Bcoeff + Bi)->length, ctx);
1832 Acoeff = A->coeffs;
1833 Aexp = A->exps;
1834 }
1835 for (vi = (Bcoeff + Bi)->length - 1; vi >= 0; vi--)
1836 {
1837 if (!_n_fq_is_zero(Bcoeff[Bi].coeffs + d*vi, d))
1838 {
1839 mpoly_monomial_set_extra(Aexp + N*Ai, Bexp + N*Bi, N, offset, vi << shift);
1840 n_fq_poly_zero(Acoeff + Ai);
1841 n_fq_poly_set_coeff_n_fq(Acoeff + Ai, 0, Bcoeff[Bi].coeffs + d*vi, ctx->fqctx);
1842 Ai++;
1843 }
1844 }
1845 }
1846 A->length = Ai;
1847 }
1848
1849
1850 /* F = F + modulus*(A - F(alpha)) with matching monomials */
fq_nmod_mpolyn_interp_mcrt_sm_mpoly(slong * lastdeg_,fq_nmod_mpolyn_t F,fq_nmod_mpoly_t A,const n_fq_poly_t modulus,n_fq_poly_t alphapow,const fq_nmod_mpoly_ctx_t ctx)1851 int fq_nmod_mpolyn_interp_mcrt_sm_mpoly(
1852 slong * lastdeg_,
1853 fq_nmod_mpolyn_t F,
1854 fq_nmod_mpoly_t A, /* could have zero coeffs */
1855 const n_fq_poly_t modulus,
1856 n_fq_poly_t alphapow,
1857 const fq_nmod_mpoly_ctx_t ctx)
1858 {
1859 slong d = fq_nmod_ctx_degree(ctx->fqctx);
1860 #if FLINT_WANT_ASSERT
1861 slong N = mpoly_words_per_exp(A->bits, ctx->minfo);
1862 #endif
1863 slong lastdeg = *lastdeg_;
1864 int changed = 0;
1865 mp_limb_t * v = FLINT_ARRAY_ALLOC(d, mp_limb_t);
1866 slong i, Alen = A->length;
1867 mp_limb_t * Acoeffs = A->coeffs;
1868 n_fq_poly_struct * Fcoeffs = F->coeffs;
1869
1870 FLINT_ASSERT(F->bits == A->bits);
1871 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
1872
1873 FLINT_ASSERT(F->length == Alen);
1874 for (i = 0; i < Alen; i++)
1875 {
1876 FLINT_ASSERT(mpoly_monomial_equal(F->exps + N*i, A->exps + N*i, N));
1877 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeffs + i));
1878 FLINT_ASSERT(n_fq_poly_degree(Fcoeffs + i) < n_fq_poly_degree(modulus));
1879
1880 n_fq_poly_eval_pow(v, Fcoeffs + i, alphapow, ctx->fqctx);
1881 n_fq_sub(v, Acoeffs + d*i, v, ctx->fqctx);
1882 if (!_n_fq_is_zero(v, d))
1883 {
1884 changed = 1;
1885 n_fq_poly_scalar_addmul_n_fq(Fcoeffs + i, Fcoeffs + i,
1886 modulus, v, ctx->fqctx);
1887 }
1888
1889 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeffs + i));
1890 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Fcoeffs + i));
1891 }
1892
1893 flint_free(v);
1894
1895 *lastdeg_ = lastdeg;
1896 return changed;
1897 }
1898
1899
1900 /*
1901 T = F + modulus*(A - F(x_var = alpha))
1902 no assumptions about matching monomials
1903 F is in Fq[x_0, ..., x_(var-1), x_(var-1)][x_var]
1904 A is in Fq[x_0, ..., x_(var-2)][x_(var-1)]
1905 in order to fxn correctly, modulus(alpha) should be 1
1906 */
fq_nmod_mpolyn_interp_crt_sm_mpolyn(slong * lastdeg_,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,fq_nmod_mpolyn_t A,slong var,fq_nmod_poly_t modulus,const fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)1907 int fq_nmod_mpolyn_interp_crt_sm_mpolyn(
1908 slong * lastdeg_,
1909 fq_nmod_mpolyn_t F,
1910 fq_nmod_mpolyn_t T,
1911 fq_nmod_mpolyn_t A,
1912 slong var,
1913 fq_nmod_poly_t modulus,
1914 const fq_nmod_t alpha,
1915 const fq_nmod_mpoly_ctx_t ctx)
1916 {
1917 slong d = fq_nmod_ctx_degree(ctx->fqctx);
1918 int changed = 0;
1919 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
1920 slong lastdeg = -WORD(1);
1921 slong offset, shift;
1922 slong vi;
1923 fq_nmod_t v, at;
1924 fq_nmod_poly_t tp;
1925 n_fq_poly_t tpt;
1926
1927 n_fq_poly_struct * Tcoeff;
1928 ulong * Texp;
1929 slong Ti;
1930
1931 n_fq_poly_struct * Acoeff = A->coeffs;
1932 slong Alen = A->length;
1933 ulong * Aexp = A->exps;
1934 slong Ai;
1935
1936 n_fq_poly_struct * Fcoeff = F->coeffs;
1937 slong Flen = F->length;
1938 ulong * Fexp = F->exps;
1939 slong Fi;
1940
1941 fq_nmod_poly_init(tp, ctx->fqctx);
1942 fq_nmod_init(v, ctx->fqctx);
1943 fq_nmod_init(at, ctx->fqctx);
1944 n_fq_poly_init(tpt);
1945
1946 FLINT_ASSERT(var > 0);
1947 FLINT_ASSERT(T->bits == A->bits);
1948 FLINT_ASSERT(F->bits == A->bits);
1949
1950 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
1951
1952 Flen = F->length;
1953
1954 fq_nmod_mpolyn_fit_length(T, FLINT_MAX(Flen, Alen), ctx);
1955 Tcoeff = T->coeffs;
1956 Texp = T->exps;
1957 Ti = 0;
1958
1959 Fi = Ai = vi = 0;
1960 if (Ai < Alen)
1961 {
1962 vi = n_fq_poly_degree(A->coeffs + Ai);
1963 }
1964 while (Fi < Flen || Ai < Alen)
1965 {
1966 if (Ti >= T->alloc)
1967 {
1968 fq_nmod_mpolyn_fit_length(T, Ti + FLINT_MAX(Flen - Fi, Alen - Ai), ctx);
1969 Tcoeff = T->coeffs;
1970 Texp = T->exps;
1971 }
1972
1973 if (Ai < Alen)
1974 {
1975 FLINT_ASSERT(!_n_fq_is_zero(Acoeff[Ai].coeffs + d*vi, d));
1976 }
1977
1978 if (Fi < Flen && Ai < Alen && mpoly_monomial_equal_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift))
1979 {
1980 /* F term ok, A term ok */
1981 n_fq_poly_evaluate_fq_nmod(v, Fcoeff + Fi, alpha, ctx->fqctx);
1982 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + d*vi, ctx->fqctx);
1983 fq_nmod_sub(v, at, v, ctx->fqctx);
1984 if (!fq_nmod_is_zero(v, ctx->fqctx))
1985 {
1986 changed = 1;
1987 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
1988 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
1989 n_fq_poly_add(Tcoeff + Ti, Fcoeff + Fi, tpt, ctx->fqctx);
1990 }
1991 else
1992 {
1993 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
1994 }
1995 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
1996
1997 Fi++;
1998 do {
1999 vi--;
2000 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + d*vi, d));
2001 if (vi < 0)
2002 {
2003 Ai++;
2004 if (Ai < Alen)
2005 {
2006 vi = n_fq_poly_degree(A->coeffs + Ai);
2007 }
2008 }
2009 }
2010 else if (Fi < Flen && (Ai >= Alen || mpoly_monomial_gt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)))
2011 {
2012 /* F term ok, A term missing */
2013 n_fq_poly_evaluate_fq_nmod(v, Fcoeff + Fi, alpha, ctx->fqctx);
2014 if (!fq_nmod_is_zero(v, ctx->fqctx))
2015 {
2016 changed = 1;
2017 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
2018 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
2019 n_fq_poly_sub(Tcoeff + Ti, Fcoeff + Fi, tpt, ctx->fqctx);
2020 }
2021 else
2022 {
2023 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
2024 }
2025 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
2026
2027 Fi++;
2028 }
2029 else
2030 {
2031 FLINT_ASSERT(Ai < Alen && (Fi >= Flen || mpoly_monomial_lt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)));
2032
2033 /* F term missing, A term ok */
2034 changed = 1;
2035 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + d*vi, ctx->fqctx);
2036 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, at, ctx->fqctx);
2037 n_fq_poly_set_fq_nmod_poly(Tcoeff + Ti, tp, ctx->fqctx);
2038 mpoly_monomial_set_extra(Texp + N*Ti, Aexp + N*Ai, N, offset, vi << shift);
2039
2040 do {
2041 vi--;
2042 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + d*vi, d));
2043 if (vi < 0)
2044 {
2045 Ai++;
2046 if (Ai < Alen)
2047 {
2048 vi = n_fq_poly_degree(A->coeffs + Ai);
2049 }
2050 }
2051 }
2052
2053 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + Ti));
2054 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Tcoeff + Ti));
2055 Ti++;
2056 }
2057 T->length = Ti;
2058
2059 if (changed)
2060 {
2061 fq_nmod_mpolyn_swap(T, F);
2062 }
2063
2064 fq_nmod_poly_clear(tp, ctx->fqctx);
2065 fq_nmod_clear(v, ctx->fqctx);
2066 fq_nmod_clear(at, ctx->fqctx);
2067 n_fq_poly_clear(tpt);
2068
2069 FLINT_ASSERT(fq_nmod_mpolyn_is_canonical(F, ctx));
2070
2071 *lastdeg_ = lastdeg;
2072 return changed;
2073 }
2074
2075 /*****************************************************************************/
2076
2077 /*
2078 A is in Fq [X][v]
2079 E is in (Fq[v]/alpha(v))[X]
2080 */
fq_nmod_mpolyn_interp_reduce_lg_poly(fq_nmod_poly_t E,const fq_nmod_mpoly_ctx_t ectx,fq_nmod_mpolyn_t A,const fq_nmod_mpoly_ctx_t ctx,const bad_fq_nmod_embed_t emb)2081 void fq_nmod_mpolyn_interp_reduce_lg_poly(
2082 fq_nmod_poly_t E,
2083 const fq_nmod_mpoly_ctx_t ectx,
2084 fq_nmod_mpolyn_t A,
2085 const fq_nmod_mpoly_ctx_t ctx,
2086 const bad_fq_nmod_embed_t emb)
2087 {
2088 fq_nmod_t v;
2089 slong Ai, Alen, k;
2090 n_fq_poly_struct * Acoeff;
2091 ulong * Aexp;
2092 slong N, off, shift;
2093
2094 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
2095 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
2096
2097 fq_nmod_init(v, ectx->fqctx);
2098
2099 Acoeff = A->coeffs;
2100 Aexp = A->exps;
2101 Alen = A->length;
2102
2103 fq_nmod_poly_zero(E, ectx->fqctx);
2104 for (Ai = 0; Ai < Alen; Ai++)
2105 {
2106 k = (Aexp + N*Ai)[off] >> shift;
2107 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(v, Acoeff + Ai, emb);
2108 fq_nmod_poly_set_coeff(E, k, v, ectx->fqctx);
2109 }
2110
2111 fq_nmod_clear(v, ectx->fqctx);
2112 }
2113
2114
2115 /*
2116 A = B
2117 A is in Fq [X][][v]
2118 B is in (Fq[v]/alpha(v))[X]
2119 */
fq_nmod_mpolyn_interp_lift_lg_poly(slong * lastdeg_,fq_nmod_mpolyn_t A,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_poly_t B,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)2120 void fq_nmod_mpolyn_interp_lift_lg_poly(
2121 slong * lastdeg_,
2122 fq_nmod_mpolyn_t A,
2123 const fq_nmod_mpoly_ctx_t ctx,
2124 fq_nmod_poly_t B,
2125 const fq_nmod_mpoly_ctx_t ectx,
2126 const bad_fq_nmod_embed_t emb)
2127 {
2128 slong Bexp;
2129 slong Blen = fq_nmod_poly_length(B, ectx->fqctx);
2130 fq_nmod_struct * Bcoeff = B->coeffs;
2131 n_fq_poly_struct * Acoeff;
2132 ulong * Aexp;
2133 slong Ai;
2134 slong lastdeg = -WORD(1);
2135 slong N, off, shift;
2136
2137 N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
2138 mpoly_gen_offset_shift_sp(&off, &shift, 0, A->bits, ctx->minfo);
2139
2140 fq_nmod_mpolyn_fit_length(A, Blen, ctx);
2141 Acoeff = A->coeffs;
2142 Aexp = A->exps;
2143
2144 Ai = 0;
2145 for (Bexp = Blen - 1; Bexp >= 0; Bexp--)
2146 {
2147 if (!fq_nmod_is_zero(Bcoeff + Bexp, ectx->fqctx))
2148 {
2149 FLINT_ASSERT(Ai < A->alloc);
2150 bad_fq_nmod_embed_fq_nmod_lg_to_n_fq_sm(Acoeff + Ai, Bcoeff + Bexp, emb);
2151 FLINT_ASSERT(!n_fq_poly_is_zero(Acoeff + Ai));
2152 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Acoeff + Ai));
2153 mpoly_monomial_zero(Aexp + N*Ai, N);
2154 (Aexp + N*Ai)[off] = Bexp << shift;
2155 Ai++;
2156 }
2157 }
2158 A->length = Ai;
2159
2160 *lastdeg_ = lastdeg;
2161 }
2162
2163
2164 /*
2165 F = F + modulus*((A - F(alpha))/(modulus(alpha)))
2166 F is in Fq [X][][v]
2167 A is in (Fq[v]/alpha(v))[X]
2168 alpha(v) is ectx->fqctx->modulus(v)
2169 */
fq_nmod_mpolyn_interp_crt_lg_poly(slong * lastdeg_,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,fq_nmod_poly_t modulus,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_poly_t A,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)2170 int fq_nmod_mpolyn_interp_crt_lg_poly(
2171 slong * lastdeg_,
2172 fq_nmod_mpolyn_t F,
2173 fq_nmod_mpolyn_t T,
2174 fq_nmod_poly_t modulus,
2175 const fq_nmod_mpoly_ctx_t ctx,
2176 fq_nmod_poly_t A,
2177 const fq_nmod_mpoly_ctx_t ectx,
2178 const bad_fq_nmod_embed_t emb)
2179 {
2180 int changed = 0;
2181 slong lastdeg = -WORD(1);
2182 fq_nmod_t u, v;
2183 fq_nmod_poly_t u_sm, w;
2184 n_fq_poly_t wt;
2185 slong Fi, Ti, Aexp;
2186 fq_nmod_struct * Acoeff = A->coeffs;
2187 slong Flen = F->length;
2188 n_fq_poly_struct * Fcoeff = F->coeffs;
2189 ulong * Fexp = F->exps;
2190 n_fq_poly_struct * Tcoeff;
2191 ulong * Texp;
2192 fq_nmod_poly_t tp;
2193 fq_nmod_t inv_m_eval;
2194 slong N, off, shift;
2195
2196 FLINT_ASSERT(T->bits == F->bits);
2197
2198 N = mpoly_words_per_exp_sp(F->bits, ctx->minfo);
2199 mpoly_gen_offset_shift_sp(&off, &shift, 0, F->bits, ctx->minfo);
2200
2201 fq_nmod_init(inv_m_eval, ectx->fqctx);
2202 bad_fq_nmod_embed_sm_to_lg(inv_m_eval, modulus, emb);
2203 fq_nmod_inv(inv_m_eval, inv_m_eval, ectx->fqctx);
2204
2205 fq_nmod_init(u, ectx->fqctx);
2206 fq_nmod_init(v, ectx->fqctx);
2207 fq_nmod_poly_init(u_sm, ctx->fqctx);
2208 fq_nmod_poly_init(w, ctx->fqctx);
2209 n_fq_poly_init(wt);
2210
2211 Fi = 0;
2212
2213 Aexp = fq_nmod_poly_degree(A, ectx->fqctx);
2214
2215 fq_nmod_poly_init(tp, ctx->fqctx);
2216
2217 fq_nmod_mpolyn_fit_length(T, Flen + Aexp + 1, ctx);
2218 Tcoeff = T->coeffs;
2219 Texp = T->exps;
2220 Ti = 0;
2221
2222 while (Fi < Flen || Aexp >= 0)
2223 {
2224 FLINT_ASSERT(Ti < T->alloc);
2225
2226 if (Fi < Flen)
2227 {
2228 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeff + Fi));
2229 FLINT_ASSERT(n_fq_poly_degree(Fcoeff + Fi) < fq_nmod_poly_degree(modulus, ctx->fqctx));
2230 }
2231
2232 if (Aexp >= 0)
2233 {
2234 FLINT_ASSERT(!fq_nmod_is_zero(Acoeff + Aexp, ectx->fqctx));
2235 }
2236
2237 mpoly_monomial_zero(Texp + N*Ti, N);
2238
2239 if (Fi < Flen && Aexp >= 0 && ((Fexp + N*Fi)[off]>>shift) == Aexp)
2240 {
2241 /* F term ok, A term ok */
2242 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(u, Fcoeff + Fi, emb);
2243 fq_nmod_sub(v, Acoeff + Aexp, u, ectx->fqctx);
2244 if (!fq_nmod_is_zero(v, ectx->fqctx))
2245 {
2246 changed = 1;
2247 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
2248 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2249 fq_nmod_poly_mul(w, modulus, u_sm, ctx->fqctx);
2250 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
2251 n_fq_poly_add(Tcoeff + Ti, Fcoeff + Fi, wt, ctx->fqctx);
2252 }
2253 else
2254 {
2255 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
2256 }
2257
2258 (Texp + N*Ti)[off] = (Fexp + N*Fi)[off];
2259 Fi++;
2260 do {
2261 Aexp--;
2262 } while (Aexp >= 0 && fq_nmod_is_zero(Acoeff + Aexp, ectx->fqctx));
2263 }
2264 else if (Fi < Flen && (Aexp < 0 || ((Fexp + N*Fi)[off]>>shift) > Aexp))
2265 {
2266 /* F term ok, A term missing */
2267 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(v, Fcoeff + Fi, emb);
2268 if (!fq_nmod_is_zero(v, ectx->fqctx))
2269 {
2270 changed = 1;
2271 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
2272 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2273 fq_nmod_poly_mul(w, u_sm, modulus, ctx->fqctx);
2274 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
2275 n_fq_poly_add(Tcoeff + Ti, Fcoeff + Fi, wt, ctx->fqctx);
2276 }
2277 else
2278 {
2279 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
2280 }
2281
2282 (Texp + N*Ti)[off] = (Fexp + N*Fi)[off];
2283 Fi++;
2284 }
2285 else if (Aexp >= 0 && (Fi >= Flen || ((Fexp + N*Fi)[off]>>shift) < Aexp))
2286 {
2287 /* F term missing, A term ok */
2288 changed = 1;
2289 fq_nmod_mul(u, Acoeff + Aexp, inv_m_eval, ectx->fqctx);
2290 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2291 fq_nmod_poly_mul(w, modulus, u_sm, ctx->fqctx);
2292 n_fq_poly_set_fq_nmod_poly(Tcoeff + Ti, w, ctx->fqctx);
2293
2294 (Texp + N*Ti)[off] = Aexp << shift;
2295 do {
2296 Aexp--;
2297 } while (Aexp >= 0 && fq_nmod_is_zero(Acoeff + Aexp, ectx->fqctx));
2298 }
2299 else
2300 {
2301 FLINT_ASSERT(0);
2302 }
2303
2304 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + Ti));
2305 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Tcoeff + Ti));
2306 Ti++;
2307 }
2308 T->length = Ti;
2309
2310 if (changed)
2311 {
2312 fq_nmod_mpolyn_swap(T, F);
2313 }
2314
2315 fq_nmod_clear(u, ectx->fqctx);
2316 fq_nmod_clear(v, ectx->fqctx);
2317 fq_nmod_poly_clear(u_sm, ctx->fqctx);
2318 fq_nmod_poly_clear(w, ctx->fqctx);
2319 n_fq_poly_clear(wt);
2320
2321 fq_nmod_clear(inv_m_eval, ectx->fqctx);
2322
2323 *lastdeg_ = lastdeg;
2324 return changed;
2325 }
2326
2327
fq_nmod_mpolyn_interp_lift_lg_bpoly(slong * lastdeg_,fq_nmod_mpolyn_t F,const fq_nmod_mpoly_ctx_t smctx,n_fq_bpoly_t A,const fq_nmod_mpoly_ctx_t lgctx,const bad_fq_nmod_embed_t emb)2328 void fq_nmod_mpolyn_interp_lift_lg_bpoly(
2329 slong * lastdeg_,
2330 fq_nmod_mpolyn_t F,
2331 const fq_nmod_mpoly_ctx_t smctx,
2332 n_fq_bpoly_t A,
2333 const fq_nmod_mpoly_ctx_t lgctx,
2334 const bad_fq_nmod_embed_t emb)
2335 {
2336 slong lgd = fq_nmod_ctx_degree(lgctx->fqctx);
2337 slong N = mpoly_words_per_exp_sp(F->bits, smctx->minfo);
2338 slong i, j, Fi;
2339 slong lastdeg = -WORD(1);
2340 slong off0, shift0, off1, shift1;
2341
2342 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, smctx->minfo);
2343 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, smctx->minfo);
2344
2345 Fi = 0;
2346 for (i = A->length - 1; i >= 0; i--)
2347 {
2348 n_fq_poly_struct * Ai = A->coeffs + i;
2349 for (j = Ai->length - 1; j >= 0; j--)
2350 {
2351 if (_n_fq_is_zero(Ai->coeffs + lgd*j, lgd))
2352 continue;
2353
2354 fq_nmod_mpolyn_fit_length(F, Fi + 1, smctx);
2355 mpoly_monomial_zero(F->exps + N*Fi, N);
2356 (F->exps + N*Fi)[off0] += (i << shift0);
2357 (F->exps + N*Fi)[off1] += (j << shift1);
2358 bad_n_fq_embed_lg_to_sm(F->coeffs + Fi, Ai->coeffs + lgd*j, emb);
2359 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(F->coeffs + Fi));
2360
2361 Fi++;
2362 }
2363 }
2364
2365 F->length = Fi;
2366
2367 *lastdeg_ = lastdeg;
2368 }
2369
fq_nmod_mpolyn_interp_crt_lg_bpoly(slong * lastdeg,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,n_fq_poly_t modulus,const fq_nmod_mpoly_ctx_t smctx,n_fq_bpoly_t A,const fq_nmod_mpoly_ctx_t lgctx,const bad_fq_nmod_embed_t emb)2370 int fq_nmod_mpolyn_interp_crt_lg_bpoly(
2371 slong * lastdeg,
2372 fq_nmod_mpolyn_t F,
2373 fq_nmod_mpolyn_t T,
2374 n_fq_poly_t modulus,
2375 const fq_nmod_mpoly_ctx_t smctx,
2376 n_fq_bpoly_t A,
2377 const fq_nmod_mpoly_ctx_t lgctx,
2378 const bad_fq_nmod_embed_t emb)
2379 {
2380 slong lgd = fq_nmod_ctx_degree(lgctx->fqctx);
2381 int changed = 0;
2382 slong N = mpoly_words_per_exp(T->bits, smctx->minfo);
2383 slong off0, shift0, off1, shift1;
2384 n_fq_poly_struct * Acoeffs = A->coeffs;
2385 slong Fi, Ti, Ai, ai;
2386 slong Flen = F->length;
2387 ulong * Fexps = F->exps;
2388 n_fq_poly_struct * Fcoeffs = F->coeffs;
2389 ulong * Texps = T->exps;
2390 n_fq_poly_struct * Tcoeffs = T->coeffs;
2391 mp_limb_t * u = FLINT_ARRAY_ALLOC(3*lgd, mp_limb_t);
2392 mp_limb_t * v = u + lgd;
2393 mp_limb_t * inv_m_eval = v + lgd;
2394 n_fq_poly_t u_sm;
2395 ulong Fexpi, mask;
2396
2397 mask = (-UWORD(1)) >> (FLINT_BITS - F->bits);
2398 mpoly_gen_offset_shift_sp(&off0, &shift0, 0, F->bits, smctx->minfo);
2399 mpoly_gen_offset_shift_sp(&off1, &shift1, 1, F->bits, smctx->minfo);
2400
2401 n_fq_poly_init(u_sm);
2402
2403 bad_n_fq_embed_sm_to_lg(u, modulus, emb);
2404 n_fq_inv(inv_m_eval, u, lgctx->fqctx);
2405
2406 FLINT_ASSERT(fq_nmod_mpolyn_is_canonical(F, smctx));
2407 FLINT_ASSERT(n_fq_bpoly_is_canonical(A, lgctx->fqctx));
2408
2409 FLINT_ASSERT(T->bits == F->bits);
2410
2411 *lastdeg = -1;
2412
2413 Ti = Fi = 0;
2414 Ai = A->length - 1;
2415 ai = (Ai < 0) ? 0 : n_fq_poly_degree(Acoeffs + Ai);
2416
2417 while (Fi < Flen || Ai >= 0)
2418 {
2419 if (Ti >= T->alloc)
2420 {
2421 slong extra = FLINT_MAX(Flen - Fi, Ai);
2422 fq_nmod_mpolyn_fit_length(T, Ti + extra + 1, smctx);
2423 Tcoeffs = T->coeffs;
2424 Texps = T->exps;
2425 }
2426
2427 if (Fi < Flen)
2428 {
2429 Fexpi = pack_exp2(((Fexps + N*Fi)[off0]>>shift0)&mask,
2430 ((Fexps + N*Fi)[off1]>>shift1)&mask);
2431 }
2432 else
2433 {
2434 Fexpi = 0;
2435 }
2436
2437 if (Fi < Flen && Ai >= 0 && Fexpi == pack_exp2(Ai, ai))
2438 {
2439 /* F term ok, A term ok */
2440 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
2441
2442 bad_n_fq_embed_sm_to_lg(u, Fcoeffs + Fi, emb);
2443 n_fq_sub(v, Acoeffs[Ai].coeffs + lgd*ai, u, lgctx->fqctx);
2444 if (!_n_fq_is_zero(v, lgd))
2445 {
2446 changed = 1;
2447 n_fq_mul(u, v, inv_m_eval, lgctx->fqctx);
2448 bad_n_fq_embed_lg_to_sm(u_sm, u, emb);
2449 n_fq_poly_mul(Tcoeffs + Ti, modulus, u_sm, smctx->fqctx);
2450 n_fq_poly_add(Tcoeffs + Ti, Tcoeffs + Ti, Fcoeffs + Fi, smctx->fqctx);
2451 }
2452 else
2453 {
2454 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, smctx->fqctx);
2455 }
2456
2457 Fi++;
2458 do {
2459 ai--;
2460 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + lgd*ai, lgd));
2461 if (ai < 0)
2462 {
2463 do {
2464 Ai--;
2465 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
2466 if (Ai >= 0)
2467 ai = n_fq_poly_degree(Acoeffs + Ai);
2468 }
2469 }
2470 else if (Fi < Flen && (Ai < 0 || Fexpi > pack_exp2(Ai, ai)))
2471 {
2472 /* F term ok, Aterm missing */
2473 mpoly_monomial_set(Texps + N*Ti, Fexps + N*Fi, N);
2474
2475 bad_n_fq_embed_sm_to_lg(v, Fcoeffs + Fi, emb);
2476 if (!_n_fq_is_zero(v, lgd))
2477 {
2478 changed = 1;
2479 n_fq_mul(u, v, inv_m_eval, lgctx->fqctx);
2480 bad_n_fq_embed_lg_to_sm(u_sm, u, emb);
2481 n_fq_poly_mul(Tcoeffs + Ti, modulus, u_sm, smctx->fqctx);
2482 n_fq_poly_sub(Tcoeffs + Ti, Fcoeffs + Fi, Tcoeffs + Ti, smctx->fqctx);
2483 }
2484 else
2485 {
2486 n_fq_poly_set(Tcoeffs + Ti, Fcoeffs + Fi, smctx->fqctx);
2487 }
2488
2489 Fi++;
2490 }
2491 else
2492 {
2493 FLINT_ASSERT(Ai >= 0 && (Fi >= Flen || Fexpi < pack_exp2(Ai, ai)));
2494
2495 /* F term missing, A term ok */
2496 mpoly_monomial_zero(Texps + N*Ti, N);
2497 (Texps + N*Ti)[off0] += (Ai << shift0);
2498 (Texps + N*Ti)[off1] += (ai << shift1);
2499
2500 changed = 1;
2501 n_fq_mul(u, Acoeffs[Ai].coeffs + lgd*ai, inv_m_eval, lgctx->fqctx);
2502 bad_n_fq_embed_lg_to_sm(u_sm, u, emb);
2503 n_fq_poly_mul(Tcoeffs + Ti, modulus, u_sm, smctx->fqctx);
2504
2505 do {
2506 ai--;
2507 } while (ai >= 0 && _n_fq_is_zero(Acoeffs[Ai].coeffs + lgd*ai, lgd));
2508 if (ai < 0)
2509 {
2510 do {
2511 Ai--;
2512 } while (Ai >= 0 && Acoeffs[Ai].length == 0);
2513 if (Ai >= 0)
2514 ai = n_fq_poly_degree(Acoeffs + Ai);
2515 }
2516 }
2517
2518 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeffs + Ti));
2519 *lastdeg = FLINT_MAX(*lastdeg, n_fq_poly_degree(Tcoeffs + Ti));
2520 Ti++;
2521 }
2522
2523 T->length = Ti;
2524
2525 if (changed)
2526 fq_nmod_mpolyn_swap(T, F);
2527
2528 FLINT_ASSERT(fq_nmod_mpolyn_is_canonical(F, smctx));
2529
2530 n_fq_poly_clear(u_sm);
2531 flint_free(u);
2532
2533 return changed;
2534 }
2535
2536 /*****************************************************************************/
2537
2538 /*
2539 A is in Fq [x_0,...,x_(var-2), x_(var-1)][x_var]
2540 E is in (Fq[x_var]/alpha(x_var))[x_0,...,x_(var-2)][x_(var-1)]
2541 */
2542
fq_nmod_mpolyn_interp_reduce_lg_mpolyn(fq_nmod_mpolyn_t E,const fq_nmod_mpoly_ctx_t ectx,fq_nmod_mpolyn_t A,slong var,const fq_nmod_mpoly_ctx_t ctx,const bad_fq_nmod_embed_t emb)2543 void fq_nmod_mpolyn_interp_reduce_lg_mpolyn(
2544 fq_nmod_mpolyn_t E,
2545 const fq_nmod_mpoly_ctx_t ectx,
2546 fq_nmod_mpolyn_t A,
2547 slong var,
2548 const fq_nmod_mpoly_ctx_t ctx,
2549 const bad_fq_nmod_embed_t emb)
2550 {
2551 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
2552 slong offset, shift, k;
2553 ulong mask;
2554 fq_nmod_t v;
2555 n_fq_poly_struct * Acoeff = A->coeffs;
2556 ulong * Aexp = A->exps;
2557 slong Alen = A->length;
2558 slong Ai;
2559 n_fq_poly_struct * Ecoeff;
2560 ulong * Eexp;
2561 slong Ei;
2562
2563 fq_nmod_init(v, ectx->fqctx);
2564
2565 FLINT_ASSERT(var > 0);
2566 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
2567 mask = (-UWORD(1)) >> (FLINT_BITS - A->bits);
2568
2569 Ecoeff = E->coeffs;
2570 Eexp = E->exps;
2571 Ei = 0;
2572 for (Ai = 0; Ai < Alen; Ai++)
2573 {
2574 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(v, Acoeff + Ai, emb);
2575 k = ((Aexp + N*Ai)[offset] >> shift) & mask;
2576 if (fq_nmod_is_zero(v, ectx->fqctx))
2577 {
2578 continue;
2579 }
2580
2581 if (Ei > 0 && mpoly_monomial_equal_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)))
2582 {
2583 /* append to previous */
2584 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei - 1, k, v, ectx->fqctx);
2585 }
2586 else
2587 {
2588 FLINT_ASSERT(Ei == 0 || mpoly_monomial_gt_nomask_extra(Eexp + N*(Ei - 1), Aexp + N*Ai, N, offset, -(k << shift)));
2589
2590 /* create new */
2591 if (Ei >= E->alloc)
2592 {
2593 fq_nmod_mpolyn_fit_length(E, Ei + 1, ectx);
2594 Ecoeff = E->coeffs;
2595 Eexp = E->exps;
2596 }
2597 mpoly_monomial_set_extra(Eexp + N*Ei, Aexp + N*Ai, N, offset, -(k << shift));
2598 n_fq_poly_zero(Ecoeff + Ei);
2599 n_fq_poly_set_coeff_fq_nmod(Ecoeff + Ei, k, v, ectx->fqctx);
2600 Ei++;
2601 }
2602 }
2603 E->length = Ei;
2604
2605 fq_nmod_clear(v, ectx->fqctx);
2606 }
2607
2608
2609 /*
2610 A = B using lowest degree representative
2611 A is in Fq [x_0,...,x_(var-2), x_(var-1)][x_var]
2612 B is in (Fq[x_var]/alpha(x_var))[x_0,...,x_(var-2)][x_(var-1)]
2613 alpha is emb->h
2614 */
fq_nmod_mpolyn_interp_lift_lg_mpolyn(slong * lastdeg_,fq_nmod_mpolyn_t A,slong var,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpolyn_t B,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)2615 void fq_nmod_mpolyn_interp_lift_lg_mpolyn(
2616 slong * lastdeg_,
2617 fq_nmod_mpolyn_t A,
2618 slong var,
2619 const fq_nmod_mpoly_ctx_t ctx,
2620 fq_nmod_mpolyn_t B,
2621 const fq_nmod_mpoly_ctx_t ectx,
2622 const bad_fq_nmod_embed_t emb)
2623 {
2624 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
2625 slong N = mpoly_words_per_exp_sp(B->bits, ctx->minfo);
2626 slong offset, shift;
2627 slong vi;
2628 n_fq_poly_struct * Bcoeff = B->coeffs;
2629 ulong * Bexp = B->exps;
2630 slong Blen = B->length;
2631 slong Bi;
2632 n_fq_poly_struct * Acoeff;
2633 ulong * Aexp;
2634 slong Ai;
2635 slong lastdeg = -WORD(1);
2636
2637 FLINT_ASSERT(A->bits == B->bits);
2638
2639 fq_nmod_mpolyn_fit_length(A, Blen, ctx);
2640 Acoeff = A->coeffs;
2641 Aexp = A->exps;
2642
2643 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
2644
2645 Ai = 0;
2646 for (Bi = 0; Bi < Blen; Bi++)
2647 {
2648 if (Ai + Bcoeff[Bi].length >= A->alloc)
2649 {
2650 fq_nmod_mpolyn_fit_length(A, Ai + Bcoeff[Bi].length, ctx);
2651 Acoeff = A->coeffs;
2652 Aexp = A->exps;
2653 }
2654 for (vi = Bcoeff[Bi].length - 1; vi >= 0; vi--)
2655 {
2656 if (_n_fq_is_zero(Bcoeff[Bi].coeffs + lgd*vi, lgd))
2657 continue;
2658
2659 mpoly_monomial_set_extra(Aexp + N*Ai, Bexp + N*Bi, N, offset, vi << shift);
2660 bad_n_fq_embed_lg_to_sm(Acoeff + Ai, Bcoeff[Bi].coeffs + lgd*vi, emb);
2661 FLINT_ASSERT(!n_fq_poly_is_zero(Acoeff + Ai));
2662 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Acoeff + Ai));
2663 Ai++;
2664 }
2665 }
2666 A->length = Ai;
2667
2668 *lastdeg_ = lastdeg;
2669 }
2670
2671
2672 /*
2673 F = F + modulus*((A - F(alpha))/modulus(alpha))
2674 F is in Fq [x_0,...,x_(var-2), x_(var-1)][x_var]
2675 A is in (Fq[x_var]/alpha(x_var))[x_0,...,x_(var-2)][x_(var-1)]
2676 */
fq_nmod_mpolyn_interp_crt_lg_mpolyn(slong * lastdeg_,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,fq_nmod_poly_t modulus,slong var,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpolyn_t A,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)2677 int fq_nmod_mpolyn_interp_crt_lg_mpolyn(
2678 slong * lastdeg_,
2679 fq_nmod_mpolyn_t F,
2680 fq_nmod_mpolyn_t T,
2681 fq_nmod_poly_t modulus,
2682 slong var,
2683 const fq_nmod_mpoly_ctx_t ctx,
2684 fq_nmod_mpolyn_t A,
2685 const fq_nmod_mpoly_ctx_t ectx,
2686 const bad_fq_nmod_embed_t emb)
2687 {
2688 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
2689 int changed = 0;
2690 slong N = mpoly_words_per_exp_sp(A->bits, ctx->minfo);
2691 slong offset, shift;
2692 slong lastdeg = -WORD(1);
2693 slong vi;
2694 fq_nmod_t u, v;
2695 fq_nmod_poly_t u_sm, w;
2696 fq_nmod_t inv_m_eval;
2697 fq_nmod_t at;
2698 n_fq_poly_t wt;
2699
2700 n_fq_poly_struct * Tcoeff;
2701 ulong * Texp;
2702 slong Ti;
2703
2704 n_fq_poly_struct * Acoeff = A->coeffs;
2705 slong Alen = A->length;
2706 ulong * Aexp = A->exps;
2707 slong Ai;
2708
2709 n_fq_poly_struct * Fcoeff = F->coeffs;
2710 slong Flen = F->length;
2711 ulong * Fexp = F->exps;
2712 slong Fi;
2713
2714 fq_nmod_init(inv_m_eval, ectx->fqctx);
2715 bad_fq_nmod_embed_sm_to_lg(inv_m_eval, modulus, emb);
2716 fq_nmod_inv(inv_m_eval, inv_m_eval, ectx->fqctx);
2717
2718 fq_nmod_init(u, ectx->fqctx);
2719 fq_nmod_init(v, ectx->fqctx);
2720 fq_nmod_poly_init(u_sm, ctx->fqctx);
2721 fq_nmod_poly_init(w, ctx->fqctx);
2722 fq_nmod_init(at, ectx->fqctx);
2723 n_fq_poly_init(wt);
2724
2725 FLINT_ASSERT(var > 0);
2726 FLINT_ASSERT(T->bits == A->bits);
2727 FLINT_ASSERT(F->bits == A->bits);
2728
2729 mpoly_gen_offset_shift_sp(&offset, &shift, var - 1, A->bits, ctx->minfo);
2730
2731 Flen = F->length;
2732
2733 fq_nmod_mpolyn_fit_length(T, FLINT_MAX(Flen, Alen), ctx);
2734 Tcoeff = T->coeffs;
2735 Texp = T->exps;
2736 Ti = 0;
2737
2738 Fi = Ai = vi = 0;
2739 if (Ai < Alen)
2740 {
2741 vi = n_fq_poly_degree(A->coeffs + Ai);
2742 }
2743 while (Fi < Flen || Ai < Alen)
2744 {
2745 if (Ti >= T->alloc)
2746 {
2747 fq_nmod_mpolyn_fit_length(T, Ti + FLINT_MAX(Flen - Fi, Alen - Ai), ctx);
2748 Tcoeff = T->coeffs;
2749 Texp = T->exps;
2750 }
2751
2752 if (Fi < Flen && Ai < Alen && mpoly_monomial_equal_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift))
2753 {
2754 /* F term ok, A term ok */
2755 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(u, Fcoeff + Fi, emb);
2756 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + lgd*vi, ectx->fqctx);
2757 fq_nmod_sub(v, at, u, ectx->fqctx);
2758 if (!fq_nmod_is_zero(v, ectx->fqctx))
2759 {
2760 changed = 1;
2761 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
2762 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2763 fq_nmod_poly_mul(w, modulus, u_sm, ctx->fqctx);
2764 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
2765 n_fq_poly_add(Tcoeff + Ti, Fcoeff + Fi, wt, ctx->fqctx);
2766 }
2767 else
2768 {
2769 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
2770 }
2771 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
2772
2773 Fi++;
2774 do {
2775 vi--;
2776 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + lgd*vi, lgd));
2777 if (vi < 0)
2778 {
2779 Ai++;
2780 if (Ai < Alen)
2781 {
2782 vi = n_fq_poly_degree(A->coeffs + Ai);
2783 }
2784 }
2785 }
2786 else if (Fi < Flen && (Ai >= Alen || mpoly_monomial_gt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)))
2787 {
2788 /* F term ok, A term missing */
2789 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(v, Fcoeff + Fi, emb);
2790 if (!fq_nmod_is_zero(v, ectx->fqctx))
2791 {
2792 changed = 1;
2793 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
2794 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2795 fq_nmod_poly_mul(w, u_sm, modulus, ctx->fqctx);
2796 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
2797 n_fq_poly_sub(Tcoeff + Ti, Fcoeff + Fi, wt, ctx->fqctx);
2798 }
2799 else
2800 {
2801 n_fq_poly_set(Tcoeff + Ti, Fcoeff + Fi, ctx->fqctx);
2802 }
2803 mpoly_monomial_set(Texp + N*Ti, Fexp + N*Fi, N);
2804
2805 Fi++;
2806 }
2807 else
2808 {
2809 FLINT_ASSERT(Ai < Alen && (Fi >= Flen || mpoly_monomial_lt_nomask_extra(Fexp + N*Fi, Aexp + N*Ai, N, offset, vi << shift)));
2810
2811 /* F term missing, A term ok */
2812 changed = 1;
2813 n_fq_get_fq_nmod(at, Acoeff[Ai].coeffs + lgd*vi, ectx->fqctx);
2814 fq_nmod_mul(u, at, inv_m_eval, ectx->fqctx);
2815 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
2816 fq_nmod_poly_mul(w, modulus, u_sm, ctx->fqctx);
2817 n_fq_poly_set_fq_nmod_poly(Tcoeff + Ti, w, ctx->fqctx);
2818 mpoly_monomial_set_extra(Texp + N*Ti, Aexp + N*Ai, N, offset, vi << shift);
2819
2820 do {
2821 vi--;
2822 } while (vi >= 0 && _n_fq_is_zero(Acoeff[Ai].coeffs + lgd*vi, lgd));
2823 if (vi < 0)
2824 {
2825 Ai++;
2826 if (Ai < Alen)
2827 {
2828 vi = n_fq_poly_degree(A->coeffs + Ai);
2829 }
2830 }
2831 }
2832
2833 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + Ti));
2834 lastdeg = FLINT_MAX(lastdeg, n_fq_poly_degree(Tcoeff + Ti));
2835 Ti++;
2836 }
2837 T->length = Ti;
2838
2839 if (changed)
2840 {
2841 fq_nmod_mpolyn_swap(T, F);
2842 }
2843
2844 fq_nmod_clear(inv_m_eval, ectx->fqctx);
2845 fq_nmod_clear(u, ectx->fqctx);
2846 fq_nmod_clear(v, ectx->fqctx);
2847 fq_nmod_poly_clear(u_sm, ctx->fqctx);
2848 fq_nmod_poly_clear(w, ctx->fqctx);
2849 fq_nmod_clear(at, ectx->fqctx);
2850 n_fq_poly_clear(wt);
2851
2852 FLINT_ASSERT(fq_nmod_mpolyn_is_canonical(F, ctx));
2853
2854 *lastdeg_ = lastdeg;
2855 return changed;
2856 }
2857
2858
2859
2860 /*****************************************************************************/
2861
2862 /* evaluate A at lastvar = alpha */
fq_nmod_mpolyn_interp_reduce_sm_mpoly(fq_nmod_mpoly_t B,fq_nmod_mpolyn_t A,fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)2863 void fq_nmod_mpolyn_interp_reduce_sm_mpoly(
2864 fq_nmod_mpoly_t B,
2865 fq_nmod_mpolyn_t A,
2866 fq_nmod_t alpha,
2867 const fq_nmod_mpoly_ctx_t ctx)
2868 {
2869 slong d = fq_nmod_ctx_degree(ctx->fqctx);
2870 slong i, k, N;
2871 fq_nmod_t bt;
2872 FLINT_ASSERT(B->bits == A->bits);
2873
2874 fq_nmod_init(bt, ctx->fqctx);
2875
2876 fq_nmod_mpoly_fit_length(B, A->length, ctx);
2877 N = mpoly_words_per_exp(A->bits, ctx->minfo);
2878 k = 0;
2879 for (i = 0; i < A->length; i++)
2880 {
2881 mpoly_monomial_set(B->exps + N*k, A->exps + N*i, N);
2882 n_fq_poly_evaluate_fq_nmod(bt, A->coeffs + i, alpha, ctx->fqctx);
2883 n_fq_set_fq_nmod(B->coeffs + d*k, bt, ctx->fqctx);
2884 k += !_n_fq_is_zero(B->coeffs + d*k, d);
2885 }
2886 B->length = k;
2887
2888 fq_nmod_clear(bt, ctx->fqctx);
2889 }
2890
fq_nmod_mpolyun_interp_reduce_sm_mpolyu(fq_nmod_mpolyu_t B,fq_nmod_mpolyun_t A,fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)2891 void fq_nmod_mpolyun_interp_reduce_sm_mpolyu(
2892 fq_nmod_mpolyu_t B,
2893 fq_nmod_mpolyun_t A,
2894 fq_nmod_t alpha,
2895 const fq_nmod_mpoly_ctx_t ctx)
2896 {
2897 slong i, k;
2898
2899 FLINT_ASSERT(B->bits == A->bits);
2900
2901 fq_nmod_mpolyu_fit_length(B, A->length, ctx);
2902 k = 0;
2903 for (i = 0; i < A->length; i++)
2904 {
2905 B->exps[k] = A->exps[i];
2906 fq_nmod_mpolyn_interp_reduce_sm_mpoly(B->coeffs + k, A->coeffs + i, alpha, ctx);
2907 k += !fq_nmod_mpoly_is_zero(B->coeffs + k, ctx);
2908 }
2909 B->length = k;
2910 }
2911
2912
fq_nmod_mpolyn_interp_lift_sm_mpoly(fq_nmod_mpolyn_t A,const fq_nmod_mpoly_t B,const fq_nmod_mpoly_ctx_t ctx)2913 void fq_nmod_mpolyn_interp_lift_sm_mpoly(
2914 fq_nmod_mpolyn_t A,
2915 const fq_nmod_mpoly_t B,
2916 const fq_nmod_mpoly_ctx_t ctx)
2917 {
2918 slong d = fq_nmod_ctx_degree(ctx->fqctx);
2919 slong i;
2920 slong N;
2921 n_fq_poly_struct * Acoeff;
2922 mp_limb_t * Bcoeff;
2923 ulong * Aexp, * Bexp;
2924 slong Blen;
2925
2926 fq_nmod_mpolyn_fit_bits(A, B->bits, ctx);
2927 A->bits = B->bits;
2928
2929 Blen = B->length;
2930 fq_nmod_mpolyn_fit_length(A, Blen, ctx);
2931 Acoeff = A->coeffs;
2932 Bcoeff = B->coeffs;
2933 Aexp = A->exps;
2934 Bexp = B->exps;
2935
2936 N = mpoly_words_per_exp(B->bits, ctx->minfo);
2937
2938 for (i = 0; i < Blen; i++)
2939 {
2940 n_fq_poly_set_n_fq(Acoeff + i, Bcoeff + d*i, ctx->fqctx);
2941 mpoly_monomial_set(Aexp + N*i, Bexp + N*i, N);
2942 }
2943 A->length = Blen;
2944 }
2945
fq_nmod_mpolyun_interp_lift_sm_mpolyu(fq_nmod_mpolyun_t A,const fq_nmod_mpolyu_t B,const fq_nmod_mpoly_ctx_t ctx)2946 void fq_nmod_mpolyun_interp_lift_sm_mpolyu(
2947 fq_nmod_mpolyun_t A,
2948 const fq_nmod_mpolyu_t B,
2949 const fq_nmod_mpoly_ctx_t ctx)
2950 {
2951 slong i;
2952
2953 FLINT_ASSERT(A->bits == B->bits);
2954 fq_nmod_mpolyun_fit_length(A, B->length, ctx);
2955 for (i = 0; i < B->length; i++)
2956 {
2957 A->exps[i] = B->exps[i];
2958 fq_nmod_mpolyn_interp_lift_sm_mpoly(A->coeffs + i, B->coeffs + i, ctx);
2959 FLINT_ASSERT((A->coeffs + i)->bits == B->bits);
2960 }
2961 A->length = B->length;
2962 }
2963
2964
2965 /*
2966 F = F + modulus*(A - F(alpha))
2967 */
fq_nmod_mpolyn_interp_crt_sm_mpoly(slong * lastdeg,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,fq_nmod_mpoly_t A,fq_nmod_poly_t modulus,fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)2968 int fq_nmod_mpolyn_interp_crt_sm_mpoly(
2969 slong * lastdeg,
2970 fq_nmod_mpolyn_t F,
2971 fq_nmod_mpolyn_t T,
2972 fq_nmod_mpoly_t A,
2973 fq_nmod_poly_t modulus,
2974 fq_nmod_t alpha,
2975 const fq_nmod_mpoly_ctx_t ctx)
2976 {
2977 slong d = fq_nmod_ctx_degree(ctx->fqctx);
2978 flint_bitcnt_t bits = A->bits;
2979 slong N = mpoly_words_per_exp(bits, ctx->minfo);
2980 int changed = 0;
2981 slong i, j, k;
2982 fq_nmod_t v;
2983 slong Flen = F->length, Alen = A->length;
2984 ulong * Fexp = F->exps, * Aexp = A->exps;
2985 ulong * Texp;
2986 mp_limb_t * Acoeff = A->coeffs;
2987 n_fq_poly_struct * Fcoeff = F->coeffs;
2988 n_fq_poly_struct * Tcoeff;
2989 fq_nmod_poly_t tp;
2990 n_fq_poly_t tpt;
2991 fq_nmod_t at;
2992
2993 FLINT_ASSERT(F->bits == bits);
2994 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
2995
2996 fq_nmod_init(v, ctx->fqctx);
2997 fq_nmod_poly_init(tp, ctx->fqctx);
2998 n_fq_poly_init(tpt);
2999 fq_nmod_init(at, ctx->fqctx);
3000
3001 fq_nmod_mpolyn_fit_length(T, Flen + Alen, ctx);
3002 Texp = T->exps;
3003 Tcoeff = T->coeffs;
3004
3005
3006 i = j = k = 0;
3007 while (i < Flen || j < Alen)
3008 {
3009 if (i < Flen && (j >= Alen
3010 || mpoly_monomial_gt_nomask(Fexp + N*i, Aexp + N*j, N)))
3011 {
3012 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeff + i));
3013 FLINT_ASSERT(n_fq_poly_degree(Fcoeff + i) < fq_nmod_poly_degree(modulus, ctx->fqctx));
3014
3015 /* F term ok, A term missing */
3016 n_fq_poly_evaluate_fq_nmod(v, Fcoeff + i, alpha, ctx->fqctx);
3017 if (!fq_nmod_is_zero(v, ctx->fqctx))
3018 {
3019 changed = 1;
3020 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
3021 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
3022 n_fq_poly_sub(Tcoeff + k, Fcoeff + i, tpt, ctx->fqctx);
3023 }
3024 else
3025 {
3026 n_fq_poly_set(Tcoeff + k, Fcoeff + i, ctx->fqctx);
3027 }
3028
3029 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3030 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3031
3032 mpoly_monomial_set(Texp + N*k, Fexp + N*i, N);
3033 k++;
3034 i++;
3035 }
3036 else if (j < Alen && (i >= Flen
3037 || mpoly_monomial_lt_nomask(Fexp + N*i, Aexp + N*j, N)))
3038 {
3039 /* F term missing, A term ok */
3040 if (!_n_fq_is_zero(Acoeff + d*j, d))
3041 {
3042 changed = 1;
3043 n_fq_get_fq_nmod(at, Acoeff + d*j, ctx->fqctx);
3044 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, at, ctx->fqctx);
3045 n_fq_poly_set_fq_nmod_poly(Tcoeff + k, tp, ctx->fqctx);
3046
3047 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3048 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3049 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
3050 k++;
3051 }
3052 j++;
3053 }
3054 else if (i < Flen && j < Alen
3055 && mpoly_monomial_equal(Fexp + N*i, Aexp + N*j, N))
3056 {
3057 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeff + i));
3058 FLINT_ASSERT(n_fq_poly_degree(Fcoeff + i) < fq_nmod_poly_degree(modulus, ctx->fqctx));
3059
3060 /* F term ok, A term ok */
3061 n_fq_poly_evaluate_fq_nmod(v, Fcoeff + i, alpha, ctx->fqctx);
3062 n_fq_get_fq_nmod(at, Acoeff + d*j, ctx->fqctx);
3063 fq_nmod_sub(v, at, v, ctx->fqctx);
3064 if (!fq_nmod_is_zero(v, ctx->fqctx))
3065 {
3066 changed = 1;
3067 fq_nmod_poly_scalar_mul_fq_nmod(tp, modulus, v, ctx->fqctx);
3068 n_fq_poly_set_fq_nmod_poly(tpt, tp, ctx->fqctx);
3069 n_fq_poly_add(Tcoeff + k, Fcoeff + i, tpt, ctx->fqctx);
3070 }
3071 else
3072 {
3073 n_fq_poly_set(Tcoeff + k, Fcoeff + i, ctx->fqctx);
3074 }
3075
3076 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3077 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3078
3079 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
3080 k++;
3081 i++;
3082 j++;
3083 }
3084 else
3085 {
3086 FLINT_ASSERT(0);
3087 }
3088 }
3089 T->length = k;
3090
3091 if (changed)
3092 {
3093 fq_nmod_mpolyn_swap(T, F);
3094 }
3095
3096 fq_nmod_poly_clear(tp, ctx->fqctx);
3097 fq_nmod_clear(v, ctx->fqctx);
3098 n_fq_poly_clear(tpt);
3099 fq_nmod_clear(at, ctx->fqctx);
3100
3101 return changed;
3102 }
3103
3104
fq_nmod_mpolyun_interp_crt_sm_mpolyu(slong * lastdeg,fq_nmod_mpolyun_t F,fq_nmod_mpolyun_t T,fq_nmod_mpolyu_t A,fq_nmod_poly_t modulus,fq_nmod_t alpha,const fq_nmod_mpoly_ctx_t ctx)3105 int fq_nmod_mpolyun_interp_crt_sm_mpolyu(
3106 slong * lastdeg,
3107 fq_nmod_mpolyun_t F,
3108 fq_nmod_mpolyun_t T,
3109 fq_nmod_mpolyu_t A,
3110 fq_nmod_poly_t modulus,
3111 fq_nmod_t alpha,
3112 const fq_nmod_mpoly_ctx_t ctx)
3113 {
3114 int changed = 0;
3115 slong i, j, k;
3116 ulong * Texp;
3117 ulong * Fexp;
3118 ulong * Aexp;
3119 slong Flen;
3120 slong Alen;
3121 fq_nmod_mpolyn_t S;
3122 fq_nmod_mpolyn_struct * Tcoeff;
3123 fq_nmod_mpolyn_struct * Fcoeff;
3124 fq_nmod_mpoly_struct * Acoeff;
3125 fq_nmod_mpoly_t zero;
3126
3127 lastdeg[0] = -WORD(1);
3128
3129 FLINT_ASSERT(F->bits == T->bits);
3130 FLINT_ASSERT(T->bits == A->bits);
3131
3132 fq_nmod_mpolyn_init(S, F->bits, ctx);
3133
3134 Flen = F->length;
3135 Alen = A->length;
3136 fq_nmod_mpolyun_fit_length(T, Flen + Alen, ctx);
3137
3138 Tcoeff = T->coeffs;
3139 Fcoeff = F->coeffs;
3140 Acoeff = A->coeffs;
3141 Texp = T->exps;
3142 Fexp = F->exps;
3143 Aexp = A->exps;
3144
3145 fq_nmod_mpoly_init(zero, ctx);
3146 fq_nmod_mpoly_fit_length_reset_bits(zero, 0, A->bits, ctx);
3147
3148 i = j = k = 0;
3149 while (i < Flen || j < Alen)
3150 {
3151 if (i < Flen && (j >= Alen || Fexp[i] > Aexp[j]))
3152 {
3153 /* F term ok, A term missing */
3154 fq_nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
3155 changed |= fq_nmod_mpolyn_interp_crt_sm_mpoly(lastdeg, Tcoeff + k, S, zero, modulus, alpha, ctx);
3156 Texp[k] = Fexp[i];
3157 k++;
3158 i++;
3159 }
3160 else if (j < Alen && (i >= Flen || Aexp[j] > Fexp[i]))
3161 {
3162 /* F term missing, A term ok */
3163 fq_nmod_mpolyn_zero(Tcoeff + k, ctx);
3164 changed |= fq_nmod_mpolyn_interp_crt_sm_mpoly(lastdeg, Tcoeff + k, S, Acoeff + j, modulus, alpha, ctx);
3165 Texp[k] = Aexp[j];
3166 k++;
3167 j++;
3168 }
3169 else if (i < Flen && j < Alen && (Fexp[i] == Aexp[j]))
3170 {
3171 /* F term ok, A term ok */
3172 fq_nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
3173 changed |= fq_nmod_mpolyn_interp_crt_sm_mpoly(lastdeg, Tcoeff + k, S, Acoeff + j, modulus, alpha, ctx);
3174 Texp[k] = Aexp[j];
3175 FLINT_ASSERT(!fq_nmod_mpolyn_is_zero(Tcoeff + k, ctx));
3176 k++;
3177 i++;
3178 j++;
3179 } else
3180 {
3181 FLINT_ASSERT(0);
3182 }
3183 }
3184 T->length = k;
3185
3186 if (changed)
3187 {
3188 fq_nmod_mpolyun_swap(T, F);
3189 }
3190
3191 fq_nmod_mpolyn_clear(S, ctx);
3192 fq_nmod_mpoly_clear(zero, ctx);
3193 return changed;
3194 }
3195
3196
3197 /*****************************************************************************/
3198
3199 /* reduce B via the map F_q[x] -> F_q^n */
fq_nmod_mpolyn_interp_reduce_lg_mpoly(fq_nmod_mpoly_t A,fq_nmod_mpolyn_t B,const fq_nmod_mpoly_ctx_t ectx,const fq_nmod_mpoly_ctx_t ctx,const bad_fq_nmod_embed_t emb)3200 void fq_nmod_mpolyn_interp_reduce_lg_mpoly(
3201 fq_nmod_mpoly_t A,
3202 fq_nmod_mpolyn_t B,
3203 const fq_nmod_mpoly_ctx_t ectx,
3204 const fq_nmod_mpoly_ctx_t ctx,
3205 const bad_fq_nmod_embed_t emb)
3206 {
3207 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
3208 slong N = mpoly_words_per_exp_sp(B->bits, ctx->minfo);
3209 slong i, k;
3210
3211 FLINT_ASSERT(A->bits == B->bits);
3212 FLINT_ASSERT(B->bits <= FLINT_BITS);
3213 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
3214 FLINT_ASSERT(ectx->minfo->ord == ORD_LEX);
3215 FLINT_ASSERT(ectx->minfo->nvars == ctx->minfo->nvars);
3216
3217 k = 0;
3218 for (i = 0; i < B->length; i++)
3219 {
3220 fq_nmod_mpoly_fit_length(A, k + 1, ectx);
3221 mpoly_monomial_set(A->exps + N*k, B->exps + N*i, N);
3222 bad_n_fq_embed_sm_to_lg(A->coeffs + lgd*k, B->coeffs + i, emb);
3223 k += !_n_fq_is_zero(A->coeffs + lgd*k, lgd);
3224 }
3225
3226 _fq_nmod_mpoly_set_length(A, k, ectx);
3227 }
3228
3229 /* reduce B via the map from F_q[x] -> F_q^n */
fq_nmod_mpolyun_interp_reduce_lg_mpolyu(fq_nmod_mpolyu_t A,fq_nmod_mpolyun_t B,const fq_nmod_mpoly_ctx_t ectx,const fq_nmod_mpoly_ctx_t ctx,const bad_fq_nmod_embed_t emb)3230 void fq_nmod_mpolyun_interp_reduce_lg_mpolyu(
3231 fq_nmod_mpolyu_t A,
3232 fq_nmod_mpolyun_t B,
3233 const fq_nmod_mpoly_ctx_t ectx,
3234 const fq_nmod_mpoly_ctx_t ctx,
3235 const bad_fq_nmod_embed_t emb)
3236 {
3237 slong i, k, Blen;
3238 fq_nmod_mpoly_struct * Acoeff;
3239 fq_nmod_mpolyn_struct * Bcoeff;
3240 ulong * Aexp, * Bexp;
3241
3242 Blen = B->length;
3243 fq_nmod_mpolyu_fit_length(A, Blen, ectx);
3244 Acoeff = A->coeffs;
3245 Bcoeff = B->coeffs;
3246 Aexp = A->exps;
3247 Bexp = B->exps;
3248
3249 k = 0;
3250 for (i = 0; i < Blen; i++)
3251 {
3252 fq_nmod_mpolyn_interp_reduce_lg_mpoly(Acoeff + k, Bcoeff + i, ectx, ctx, emb);
3253 Aexp[k] = Bexp[i];
3254 k += !fq_nmod_mpoly_is_zero(Acoeff + k, ectx);
3255 }
3256 A->length = k;
3257 }
3258
3259 /* Convert B to A using the map F_q^n -> F_q[x] */
fq_nmod_mpolyn_interp_lift_lg_mpoly(fq_nmod_mpolyn_t A,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpoly_t B,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)3260 void fq_nmod_mpolyn_interp_lift_lg_mpoly(
3261 fq_nmod_mpolyn_t A,
3262 const fq_nmod_mpoly_ctx_t ctx,
3263 fq_nmod_mpoly_t B,
3264 const fq_nmod_mpoly_ctx_t ectx,
3265 const bad_fq_nmod_embed_t emb)
3266 {
3267 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
3268 slong N = mpoly_words_per_exp(A->bits, ctx->minfo);
3269 slong i;
3270
3271 FLINT_ASSERT(B->bits == A->bits);
3272
3273 fq_nmod_mpolyn_fit_length(A, B->length, ctx);
3274 for (i = 0; i < B->length; i++)
3275 {
3276 mpoly_monomial_set(A->exps + N*i, B->exps + N*i, N);
3277 bad_n_fq_embed_lg_to_sm(A->coeffs + i, B->coeffs + lgd*i, emb);
3278 FLINT_ASSERT(!n_fq_poly_is_zero(A->coeffs + i));
3279 }
3280 A->length = B->length;
3281 }
3282
fq_nmod_mpolyun_interp_lift_lg_mpolyu(fq_nmod_mpolyun_t A,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpolyu_t B,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)3283 void fq_nmod_mpolyun_interp_lift_lg_mpolyu(
3284 fq_nmod_mpolyun_t A,
3285 const fq_nmod_mpoly_ctx_t ctx,
3286 fq_nmod_mpolyu_t B,
3287 const fq_nmod_mpoly_ctx_t ectx,
3288 const bad_fq_nmod_embed_t emb)
3289 {
3290 slong i;
3291
3292 FLINT_ASSERT(B->bits == A->bits);
3293 fq_nmod_mpolyun_fit_length(A, B->length, ctx);
3294 for (i = 0; i < B->length; i++)
3295 {
3296 A->exps[i] = B->exps[i];
3297 fq_nmod_mpolyn_interp_lift_lg_mpoly(A->coeffs + i, ctx, B->coeffs + i, ectx, emb);
3298 FLINT_ASSERT(!fq_nmod_mpolyn_is_zero(A->coeffs + i, ctx));
3299 }
3300 A->length = B->length;
3301 }
3302
3303
3304 /*
3305 update F so that it doesn't change mod m and is A mod emb->h
3306
3307 F = F + m*((A - F(alpha))/(m(alpha)))
3308
3309 no assumptions about matching monomials
3310 */
fq_nmod_mpolyn_interp_crt_lg_mpoly(slong * lastdeg,fq_nmod_mpolyn_t F,fq_nmod_mpolyn_t T,fq_nmod_poly_t m,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpoly_t A,fq_nmod_t inv_m_eval,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)3311 int fq_nmod_mpolyn_interp_crt_lg_mpoly(
3312 slong * lastdeg,
3313 fq_nmod_mpolyn_t F,
3314 fq_nmod_mpolyn_t T,
3315 fq_nmod_poly_t m,
3316 const fq_nmod_mpoly_ctx_t ctx,
3317 fq_nmod_mpoly_t A,
3318 fq_nmod_t inv_m_eval,
3319 const fq_nmod_mpoly_ctx_t ectx,
3320 const bad_fq_nmod_embed_t emb)
3321 {
3322 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
3323 int changed = 0;
3324 slong i, j, k;
3325 slong N;
3326 fq_nmod_t u, v;
3327 fq_nmod_poly_t u_sm, w;
3328 flint_bitcnt_t bits = A->bits;
3329 slong Flen = F->length, Alen = A->length;
3330 ulong * Fexp = F->exps, * Aexp = A->exps;
3331 ulong * Texp;
3332 mp_limb_t * Acoeff = A->coeffs;
3333 n_fq_poly_struct * Fcoeff = F->coeffs;
3334 n_fq_poly_struct * Tcoeff;
3335 fq_nmod_t at;
3336 n_fq_poly_t wt;
3337
3338 FLINT_ASSERT(bits <= FLINT_BITS);
3339 FLINT_ASSERT(F->bits == bits);
3340 FLINT_ASSERT(ctx->minfo->ord == ORD_LEX);
3341
3342 fq_nmod_init(u, ectx->fqctx);
3343 fq_nmod_init(v, ectx->fqctx);
3344 fq_nmod_poly_init(u_sm, ctx->fqctx);
3345 fq_nmod_poly_init(w, ctx->fqctx);
3346 n_fq_poly_init(wt);
3347 fq_nmod_init(at, ectx->fqctx);
3348
3349 fq_nmod_mpolyn_fit_length(T, Flen + Alen, ctx);
3350 Texp = T->exps;
3351 Tcoeff = T->coeffs;
3352
3353 N = mpoly_words_per_exp(bits, ctx->minfo);
3354
3355 i = j = k = 0;
3356 while (i < Flen || j < Alen)
3357 {
3358 if (i < Flen && (j >= Alen
3359 || mpoly_monomial_gt_nomask(Fexp + N*i, Aexp + N*j, N)))
3360 {
3361 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeff + i));
3362 FLINT_ASSERT(n_fq_poly_degree(Fcoeff + i) < fq_nmod_poly_degree(m, ctx->fqctx));
3363
3364 /* F term ok, A term missing */
3365 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(v, Fcoeff + i, emb);
3366 if (!fq_nmod_is_zero(v, ectx->fqctx))
3367 {
3368 changed = 1;
3369 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
3370 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
3371 fq_nmod_poly_mul(w, u_sm, m, ctx->fqctx);
3372 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
3373 n_fq_poly_sub(Tcoeff + k, Fcoeff + i, wt, ctx->fqctx);
3374 }
3375 else
3376 {
3377 n_fq_poly_set(Tcoeff + k, Fcoeff + i, ctx->fqctx);
3378 }
3379
3380 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3381 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3382
3383 mpoly_monomial_set(Texp + N*k, Fexp + N*i, N);
3384 k++;
3385 i++;
3386 }
3387 else if (j < Alen && (i >= Flen
3388 || mpoly_monomial_lt_nomask(Fexp + N*i, Aexp + N*j, N)))
3389 {
3390 /* F term missing, A term ok */
3391 if (!_n_fq_is_zero(Acoeff + lgd*j, lgd))
3392 {
3393 changed = 1;
3394 n_fq_get_fq_nmod(at, Acoeff + lgd*j, ectx->fqctx);
3395 fq_nmod_mul(u, at, inv_m_eval, ectx->fqctx);
3396 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
3397 fq_nmod_poly_mul(w, m, u_sm, ctx->fqctx);
3398 n_fq_poly_set_fq_nmod_poly(Tcoeff + k, w, ctx->fqctx);
3399
3400 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3401 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3402 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
3403 k++;
3404 }
3405 j++;
3406 }
3407 else if (i < Flen && j < Alen
3408 && mpoly_monomial_equal(Fexp + N*i, Aexp + N*j, N))
3409 {
3410 FLINT_ASSERT(!n_fq_poly_is_zero(Fcoeff + i));
3411 FLINT_ASSERT(n_fq_poly_degree(Fcoeff + i) < fq_nmod_poly_degree(m, ctx->fqctx));
3412
3413 /* F term ok, A term ok */
3414 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(u, Fcoeff + i, emb);
3415 n_fq_get_fq_nmod(at, Acoeff + lgd*j, ectx->fqctx);
3416 fq_nmod_sub(v, at, u, ectx->fqctx);
3417 if (!fq_nmod_is_zero(v, ectx->fqctx))
3418 {
3419 changed = 1;
3420 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
3421 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
3422 fq_nmod_poly_mul(w, m, u_sm, ctx->fqctx);
3423 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
3424 n_fq_poly_add(Tcoeff + k, Fcoeff + i, wt, ctx->fqctx);
3425 }
3426 else
3427 {
3428 n_fq_poly_set(Tcoeff + k, Fcoeff + i, ctx->fqctx);
3429 }
3430
3431 FLINT_ASSERT(!n_fq_poly_is_zero(Tcoeff + k));
3432 lastdeg[0] = FLINT_MAX(lastdeg[0], n_fq_poly_degree(Tcoeff + k));
3433 mpoly_monomial_set(Texp + N*k, Aexp + N*j, N);
3434 k++;
3435 i++;
3436 j++;
3437 }
3438 else
3439 {
3440 FLINT_ASSERT(0);
3441 }
3442 }
3443
3444 T->length = k;
3445
3446 if (changed)
3447 {
3448 fq_nmod_mpolyn_swap(T, F);
3449 }
3450
3451 fq_nmod_clear(u, ectx->fqctx);
3452 fq_nmod_clear(v, ectx->fqctx);
3453 fq_nmod_poly_clear(u_sm, ctx->fqctx);
3454 fq_nmod_poly_clear(w, ctx->fqctx);
3455 n_fq_poly_clear(wt);
3456 fq_nmod_clear(at, ectx->fqctx);
3457
3458 return changed;
3459 }
3460
3461
fq_nmod_mpolyun_interp_crt_lg_mpolyu(slong * lastdeg,fq_nmod_mpolyun_t F,fq_nmod_mpolyun_t T,fq_nmod_poly_t m,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_mpolyu_t A,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)3462 int fq_nmod_mpolyun_interp_crt_lg_mpolyu(
3463 slong * lastdeg,
3464 fq_nmod_mpolyun_t F,
3465 fq_nmod_mpolyun_t T,
3466 fq_nmod_poly_t m,
3467 const fq_nmod_mpoly_ctx_t ctx,
3468 fq_nmod_mpolyu_t A,
3469 const fq_nmod_mpoly_ctx_t ectx,
3470 const bad_fq_nmod_embed_t emb)
3471 {
3472 int changed = 0;
3473 slong i, j, k;
3474 ulong * Texp;
3475 ulong * Fexp;
3476 ulong * Aexp;
3477 slong Flen;
3478 slong Alen;
3479 fq_nmod_mpolyn_t S;
3480 fq_nmod_mpolyn_struct * Tcoeff;
3481 fq_nmod_mpolyn_struct * Fcoeff;
3482 fq_nmod_mpoly_struct * Acoeff;
3483 fq_nmod_mpoly_t zero;
3484 fq_nmod_t inv_m_eval;
3485
3486 lastdeg[0] = -WORD(1);
3487
3488 FLINT_ASSERT(F->bits == T->bits);
3489 FLINT_ASSERT(T->bits == A->bits);
3490
3491 fq_nmod_mpolyn_init(S, F->bits, ctx);
3492
3493 Flen = F->length;
3494 Alen = A->length;
3495 fq_nmod_mpolyun_fit_length(T, Flen + Alen, ctx);
3496
3497 Tcoeff = T->coeffs;
3498 Fcoeff = F->coeffs;
3499 Acoeff = A->coeffs;
3500 Texp = T->exps;
3501 Fexp = F->exps;
3502 Aexp = A->exps;
3503
3504 fq_nmod_mpoly_init(zero, ectx);
3505 fq_nmod_mpoly_fit_length_reset_bits(zero, 0, A->bits, ectx);
3506
3507 fq_nmod_init(inv_m_eval, ectx->fqctx);
3508 bad_fq_nmod_embed_sm_to_lg(inv_m_eval, m, emb);
3509 fq_nmod_inv(inv_m_eval, inv_m_eval, ectx->fqctx);
3510
3511 i = j = k = 0;
3512 while (i < Flen || j < Alen)
3513 {
3514 if (i < Flen && (j >= Alen || Fexp[i] > Aexp[j]))
3515 {
3516 /* F term ok, A term missing */
3517 fq_nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
3518 changed |= fq_nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
3519 S, m, ctx, zero, inv_m_eval, ectx, emb);
3520 Texp[k] = Fexp[i];
3521 FLINT_ASSERT(!fq_nmod_mpolyn_is_zero(Tcoeff + k, ctx));
3522 k++;
3523 i++;
3524 }
3525 else if (j < Alen && (i >= Flen || Aexp[j] > Fexp[i]))
3526 {
3527 /* F term missing, A term ok */
3528 fq_nmod_mpolyn_zero(Tcoeff + k, ctx);
3529 changed |= fq_nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
3530 S, m, ctx, Acoeff + j, inv_m_eval, ectx, emb);
3531 Texp[k] = Aexp[j];
3532 FLINT_ASSERT(!fq_nmod_mpolyn_is_zero(Tcoeff + k, ctx));
3533 k++;
3534 j++;
3535 }
3536 else if (i < Flen && j < Alen && (Fexp[i] == Aexp[j]))
3537 {
3538 /* F term ok, A term ok */
3539 fq_nmod_mpolyn_set(Tcoeff + k, Fcoeff + i, ctx);
3540 changed |= fq_nmod_mpolyn_interp_crt_lg_mpoly(lastdeg, Tcoeff + k,
3541 S, m, ctx, Acoeff + j, inv_m_eval, ectx, emb);
3542 Texp[k] = Aexp[j];
3543 FLINT_ASSERT(!fq_nmod_mpolyn_is_zero(Tcoeff + k, ctx));
3544 k++;
3545 i++;
3546 j++;
3547 }
3548 else
3549 {
3550 FLINT_ASSERT(0);
3551 }
3552 }
3553
3554 T->length = k;
3555
3556 if (changed)
3557 {
3558 fq_nmod_mpolyun_swap(T, F);
3559 }
3560
3561 fq_nmod_clear(inv_m_eval, ectx->fqctx);
3562
3563 fq_nmod_mpolyn_clear(S, ctx);
3564 fq_nmod_mpoly_clear(zero, ectx);
3565 return changed;
3566 }
3567
3568 /*
3569 Update H so that it does not change mod m, and is now A mod p
3570 It is asserted that the monomials in H and A match
3571 */
fq_nmod_mpolyn_interp_mcrt_lg_mpoly(slong * lastdeg,fq_nmod_mpolyn_t H,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_poly_t m,fq_nmod_t inv_m_eval,fq_nmod_mpoly_t A,const fq_nmod_mpoly_ctx_t ectx,const bad_fq_nmod_embed_t emb)3572 int fq_nmod_mpolyn_interp_mcrt_lg_mpoly(
3573 slong * lastdeg,
3574 fq_nmod_mpolyn_t H,
3575 const fq_nmod_mpoly_ctx_t ctx,
3576 fq_nmod_poly_t m,
3577 fq_nmod_t inv_m_eval,
3578 fq_nmod_mpoly_t A,
3579 const fq_nmod_mpoly_ctx_t ectx,
3580 const bad_fq_nmod_embed_t emb)
3581 {
3582 slong lgd = fq_nmod_ctx_degree(ectx->fqctx);
3583 slong i;
3584 #if FLINT_WANT_ASSERT
3585 slong N = mpoly_words_per_exp(A->bits, ctx->minfo);
3586 #endif
3587 int changed = 0;
3588 fq_nmod_t u, v, at;
3589 fq_nmod_poly_t w, u_sm;
3590 n_fq_poly_t wt;
3591
3592 fq_nmod_init(u, ectx->fqctx);
3593 fq_nmod_init(v, ectx->fqctx);
3594 fq_nmod_poly_init(w, ctx->fqctx);
3595 n_fq_poly_init(wt);
3596 fq_nmod_poly_init(u_sm, ctx->fqctx);
3597 fq_nmod_init(at, ectx->fqctx);
3598
3599 FLINT_ASSERT(H->length == A->length);
3600 FLINT_ASSERT(H->bits == A->bits);
3601
3602 for (i = 0; i < A->length; i++)
3603 {
3604 FLINT_ASSERT(mpoly_monomial_equal(H->exps + N*i, A->exps + N*i, N));
3605 bad_fq_nmod_embed_n_fq_sm_to_fq_nmod_lg(u, H->coeffs + i, emb);
3606 n_fq_get_fq_nmod(at, A->coeffs + lgd*i, ectx->fqctx);
3607 fq_nmod_sub(v, at, u, ectx->fqctx);
3608 if (!fq_nmod_is_zero(v, ectx->fqctx))
3609 {
3610 changed = 1;
3611 fq_nmod_mul(u, v, inv_m_eval, ectx->fqctx);
3612 bad_fq_nmod_embed_lg_to_sm(u_sm, u, emb);
3613 fq_nmod_poly_mul(w, u_sm, m, ctx->fqctx);
3614 n_fq_poly_set_fq_nmod_poly(wt, w, ctx->fqctx);
3615 n_fq_poly_add(H->coeffs + i, H->coeffs + i, wt, ctx->fqctx);
3616 }
3617
3618 *lastdeg = FLINT_MAX(*lastdeg, n_fq_poly_degree(H->coeffs + i));
3619
3620 FLINT_ASSERT(n_fq_poly_degree(H->coeffs + i)
3621 < fq_nmod_poly_degree(m, ctx->fqctx)
3622 + fq_nmod_poly_degree(emb->h, ctx->fqctx));
3623 }
3624
3625 fq_nmod_clear(u, ectx->fqctx);
3626 fq_nmod_clear(v, ectx->fqctx);
3627 fq_nmod_poly_clear(w, ctx->fqctx);
3628 n_fq_poly_clear(wt);
3629 fq_nmod_poly_clear(u_sm, ctx->fqctx);
3630 fq_nmod_clear(at, ectx->fqctx);
3631
3632 return changed;
3633 }
3634
fq_nmod_mpolyun_interp_mcrt_lg_mpolyu(slong * lastdeg,fq_nmod_mpolyun_t H,const fq_nmod_mpoly_ctx_t ctx,fq_nmod_poly_t m,fq_nmod_mpolyu_t A,const fq_nmod_mpoly_ctx_t ectx,bad_fq_nmod_embed_t emb)3635 int fq_nmod_mpolyun_interp_mcrt_lg_mpolyu(
3636 slong * lastdeg,
3637 fq_nmod_mpolyun_t H,
3638 const fq_nmod_mpoly_ctx_t ctx,
3639 fq_nmod_poly_t m,
3640 fq_nmod_mpolyu_t A,
3641 const fq_nmod_mpoly_ctx_t ectx,
3642 bad_fq_nmod_embed_t emb)
3643 {
3644 slong i;
3645 int changed = 0;
3646 fq_nmod_t inv_m_eval;
3647
3648 *lastdeg = -WORD(1);
3649
3650 fq_nmod_init(inv_m_eval, ectx->fqctx);
3651 bad_fq_nmod_embed_sm_to_lg(inv_m_eval, m, emb);
3652 fq_nmod_inv(inv_m_eval, inv_m_eval, ectx->fqctx);
3653
3654 FLINT_ASSERT(H->bits == A->bits);
3655 FLINT_ASSERT(H->length == A->length);
3656 for (i = 0; i < A->length; i++)
3657 {
3658 FLINT_ASSERT(H->exps[i] == A->exps[i]);
3659 changed |= fq_nmod_mpolyn_interp_mcrt_lg_mpoly(lastdeg, H->coeffs + i,
3660 ctx, m, inv_m_eval, A->coeffs + i, ectx, emb);
3661 }
3662 H->length = A->length;
3663 fq_nmod_clear(inv_m_eval, ectx->fqctx);
3664 return changed;
3665 }
3666
3667
3668