1 /*
2 Copyright (C) 2020 Daniel Schultz
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <https://www.gnu.org/licenses/>.
10 */
11
12 #ifndef N_POLY_H
13 #define N_POLY_H
14
15 #ifdef N_POLY_INLINES_C
16 #define N_POLY_INLINE FLINT_DLL
17 #else
18 #define N_POLY_INLINE static __inline__
19 #endif
20
21 #undef ulong
22 #define ulong ulongxx /* interferes with system includes */
23 #include <stdio.h>
24 #undef ulong
25 #include <gmp.h>
26 #define ulong mp_limb_t
27
28 #include "nmod_poly.h"
29 #include "fq_nmod_poly.h"
30
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34
35 /* arrays of ulong */
36 typedef struct
37 {
38 mp_limb_t * coeffs;
39 slong alloc;
40 slong length;
41 } n_poly_struct;
42
43 typedef n_poly_struct n_poly_t[1];
44
45 typedef n_poly_struct n_fq_poly_struct;
46
47 typedef n_poly_t n_fq_poly_t;
48
49 /* arrays of arrays of ulong */
50 typedef struct
51 {
52 n_poly_struct * coeffs;
53 slong alloc;
54 slong length;
55 } n_bpoly_struct;
56
57 typedef n_bpoly_struct n_bpoly_t[1];
58
59 typedef n_bpoly_struct n_fq_bpoly_struct;
60
61 typedef n_bpoly_t n_fq_bpoly_t;
62
63 /* arrays of arrays of arrays of ulong */
64 typedef struct
65 {
66 n_bpoly_struct * coeffs;
67 slong alloc;
68 slong length;
69 } n_tpoly_struct;
70
71 typedef n_tpoly_struct n_tpoly_t[1];
72
73 typedef n_tpoly_struct n_fq_tpoly_struct;
74
75 typedef n_tpoly_t n_fq_tpoly_t;
76
77 /* sparse arrays of ulong */
78 typedef struct
79 {
80 ulong * exps;
81 mp_limb_t * coeffs;
82 slong length;
83 slong alloc;
84 } n_polyu_struct;
85
86 typedef n_polyu_struct n_polyu_t[1];
87
88 typedef n_polyu_struct n_fq_polyu_struct;
89
90 typedef n_polyu_t n_fq_polyu_t;
91
92 /*
93 sparse arrays of arrays of ulong
94 n_polyu1n => one exponent is in the exps[i]
95 n_polyu2n => two exponents are packed into the exps[i]
96 ...
97 */
98 typedef struct
99 {
100 n_poly_struct * coeffs;
101 ulong * exps;
102 slong length;
103 slong alloc;
104 } n_polyun_struct;
105
106 typedef n_polyun_struct n_polyun_t[1];
107
108 typedef n_polyun_struct n_fq_polyun_struct;
109
110 typedef n_polyun_t n_fq_polyun_t;
111
112 /* n_poly stack */
113 typedef struct
114 {
115 n_poly_struct ** array;
116 slong alloc;
117 slong top;
118 } n_poly_stack_struct;
119
120 typedef n_poly_stack_struct n_poly_stack_t[1];
121
122 /* n_bpoly stack */
123 typedef struct
124 {
125 n_bpoly_struct ** array;
126 slong alloc;
127 slong top;
128 } n_bpoly_stack_struct;
129
130 typedef n_bpoly_stack_struct n_bpoly_stack_t[1];
131
132 typedef struct {
133 n_poly_stack_t poly_stack;
134 n_bpoly_stack_t bpoly_stack;
135 } n_poly_bpoly_stack_struct;
136
137 typedef n_poly_bpoly_stack_struct n_poly_bpoly_stack_t[1];
138
139 /* n_polyun stack */
140 typedef struct
141 {
142 n_polyun_struct ** array;
143 slong alloc;
144 slong top;
145 } n_polyun_stack_struct;
146
147 typedef n_polyun_stack_struct n_polyun_stack_t[1];
148
149 typedef struct {
150 n_poly_stack_t poly_stack;
151 n_polyun_stack_t polyun_stack;
152 } n_poly_polyun_stack_struct;
153
154 typedef n_poly_polyun_stack_struct n_poly_polyun_stack_t[1];
155
156
157 /*****************************************************************************/
158
159 N_POLY_INLINE
n_poly_init(n_poly_t A)160 void n_poly_init(n_poly_t A)
161 {
162 A->length = 0;
163 A->alloc = 0;
164 A->coeffs = NULL;
165 }
166
167 N_POLY_INLINE
n_poly_init2(n_poly_t A,slong alloc)168 void n_poly_init2(n_poly_t A, slong alloc)
169 {
170 A->length = 0;
171 A->alloc = alloc;
172 A->coeffs = NULL;
173 if (alloc > 0)
174 A->coeffs = (mp_limb_t *) flint_malloc(alloc*sizeof(mp_limb_t));
175 }
176
177 N_POLY_INLINE
n_poly_clear(n_poly_t A)178 void n_poly_clear(n_poly_t A)
179 {
180 FLINT_ASSERT(A->alloc != 0 || A->coeffs == NULL);
181 if (A->alloc > 0)
182 flint_free(A->coeffs);
183 }
184
185 FLINT_DLL int n_poly_is_canonical(const n_poly_t A);
186
187 FLINT_DLL void n_poly_realloc(n_poly_t A, slong len);
188
189 FLINT_DLL void n_poly_print_pretty(const n_poly_t A, const char * x);
190
191 N_POLY_INLINE
n_poly_fit_length(n_poly_t A,slong len)192 void n_poly_fit_length(n_poly_t A, slong len)
193 {
194 if (len > A->alloc)
195 n_poly_realloc(A, len);
196 }
197
198
199 N_POLY_INLINE
nmod_poly_mock(nmod_poly_t a,const n_poly_t b,nmod_t mod)200 void nmod_poly_mock(nmod_poly_t a, const n_poly_t b, nmod_t mod)
201 {
202 a->coeffs = b->coeffs;
203 a->length = b->length;
204 a->alloc = b->alloc;
205 a->mod = mod;
206 }
207
208 N_POLY_INLINE
n_poly_mock(n_poly_t a,const nmod_poly_t b)209 void n_poly_mock(n_poly_t a, const nmod_poly_t b)
210 {
211 a->coeffs = b->coeffs;
212 a->length = b->length;
213 a->alloc = b->alloc;
214 }
215
216
217 N_POLY_INLINE
n_poly_set(n_poly_t A,const n_poly_t B)218 void n_poly_set(n_poly_t A, const n_poly_t B)
219 {
220 n_poly_fit_length(A, B->length);
221 flint_mpn_copyi(A->coeffs, B->coeffs, B->length);
222 A->length = B->length;
223 }
224
225
226 N_POLY_INLINE
n_poly_swap(n_poly_t A,n_poly_t B)227 void n_poly_swap(n_poly_t A, n_poly_t B)
228 {
229 n_poly_struct t = *B;
230 *B = *A;
231 *A = t;
232 }
233
234 N_POLY_INLINE
_n_poly_normalise(n_poly_t A)235 void _n_poly_normalise(n_poly_t A)
236 {
237 while (A->length > 0 && A->coeffs[A->length - 1] == 0)
238 A->length--;
239 }
240
241 N_POLY_INLINE
n_poly_degree(const n_poly_t A)242 slong n_poly_degree(const n_poly_t A)
243 {
244 FLINT_ASSERT(A->length >= 0);
245 return A->length - 1;
246 }
247
248 N_POLY_INLINE
n_poly_is_one(const n_poly_t A)249 int n_poly_is_one(const n_poly_t A)
250 {
251 return A->length == 1 && A->coeffs[0] == 1;
252 }
253
254 N_POLY_INLINE
n_poly_lead(const n_poly_t A)255 mp_limb_t n_poly_lead(const n_poly_t A)
256 {
257 FLINT_ASSERT(A->length > 0);
258 return A->coeffs[A->length - 1];
259 }
260
261 N_POLY_INLINE
n_poly_one(n_poly_t A)262 void n_poly_one(n_poly_t A)
263 {
264 n_poly_fit_length(A, 1);
265 A->length = 1;
266 A->coeffs[0] = 1;
267 }
268
269 N_POLY_INLINE
n_poly_set_ui(n_poly_t A,mp_limb_t c)270 void n_poly_set_ui(n_poly_t A, mp_limb_t c)
271 {
272 n_poly_fit_length(A, 1);
273 A->coeffs[0] = c;
274 A->length = (c != 0);
275 }
276
277 N_POLY_INLINE
n_poly_is_zero(const n_poly_t poly)278 int n_poly_is_zero(const n_poly_t poly)
279 {
280 return poly->length == 0;
281 }
282
283 N_POLY_INLINE
n_poly_zero(n_poly_t res)284 void n_poly_zero(n_poly_t res)
285 {
286 res->length = 0;
287 }
288
289 N_POLY_INLINE
n_poly_equal(const n_poly_t a,const n_poly_t b)290 int n_poly_equal(const n_poly_t a, const n_poly_t b)
291 {
292 if (a->length != b->length)
293 return 0;
294
295 if (a != b)
296 {
297 if (!_nmod_vec_equal(a->coeffs, b->coeffs, a->length))
298 return 0;
299 }
300
301 return 1;
302 }
303
304 /*****************************************************************************/
305
306 FLINT_DLL int n_poly_mod_is_canonical(const n_poly_t A, nmod_t mod);
307
308 N_POLY_INLINE
n_poly_mod_make_monic(n_poly_t A,const n_poly_t B,nmod_t mod)309 void n_poly_mod_make_monic(n_poly_t A, const n_poly_t B, nmod_t mod)
310 {
311 FLINT_ASSERT(B->length > 0);
312 n_poly_fit_length(A, B->length);
313 A->length = B->length;
314 _nmod_poly_make_monic(A->coeffs, B->coeffs, B->length, mod);
315 }
316
317 N_POLY_INLINE
n_poly_mod_taylor_shift(n_poly_t g,mp_limb_t c,nmod_t mod)318 void n_poly_mod_taylor_shift(n_poly_t g, mp_limb_t c, nmod_t mod)
319 {
320 _nmod_poly_taylor_shift(g->coeffs, c, g->length, mod);
321 }
322
323 N_POLY_INLINE
n_poly_get_coeff(const n_poly_t poly,slong j)324 ulong n_poly_get_coeff(const n_poly_t poly, slong j)
325 {
326 return (j >= poly->length) ? 0 : poly->coeffs[j];
327 }
328
329 N_POLY_INLINE
n_poly_set_coeff_nonzero(n_poly_t A,slong j,ulong c)330 void n_poly_set_coeff_nonzero(n_poly_t A, slong j, ulong c)
331 {
332 FLINT_ASSERT(c != 0);
333 if (j >= A->length)
334 {
335 n_poly_fit_length(A, j + 1);
336 flint_mpn_zero(A->coeffs + A->length, j - A->length);
337 A->length = j + 1;
338 }
339 A->coeffs[j] = c;
340 }
341
342 FLINT_DLL void n_poly_set_coeff(n_poly_t A, slong e, ulong c);
343
344 FLINT_DLL void n_poly_mod_set_coeff_ui(n_poly_t A, slong j, ulong c, nmod_t mod);
345
346 N_POLY_INLINE
n_poly_set_nmod_poly(n_poly_t a,const nmod_poly_t b)347 void n_poly_set_nmod_poly(n_poly_t a, const nmod_poly_t b)
348 {
349 n_poly_fit_length(a, b->length);
350 flint_mpn_copyi(a->coeffs, b->coeffs, b->length);
351 a->length = b->length;
352 }
353
354 N_POLY_INLINE
nmod_poly_set_n_poly(nmod_poly_t a,const n_poly_t b)355 void nmod_poly_set_n_poly(nmod_poly_t a, const n_poly_t b)
356 {
357 nmod_poly_fit_length(a, b->length);
358 flint_mpn_copyi(a->coeffs, b->coeffs, b->length);
359 a->length = b->length;
360 }
361
362 N_POLY_INLINE
n_poly_shift_left(n_poly_t A,const n_poly_t B,slong k)363 void n_poly_shift_left(n_poly_t A, const n_poly_t B, slong k)
364 {
365 n_poly_fit_length(A, B->length + k);
366 _nmod_poly_shift_left(A->coeffs, B->coeffs, B->length, k);
367 A->length = B->length + k;
368 }
369
370 N_POLY_INLINE
n_poly_shift_right(n_poly_t res,const n_poly_t poly,slong k)371 void n_poly_shift_right(n_poly_t res, const n_poly_t poly, slong k)
372 {
373 if (k >= poly->length)
374 {
375 res->length = 0;
376 }
377 else
378 {
379 const slong len = poly->length - k;
380 n_poly_fit_length(res, len);
381 _nmod_poly_shift_right(res->coeffs, poly->coeffs, len, k);
382 res->length = len;
383 }
384 }
385
386 N_POLY_INLINE
n_poly_truncate(n_poly_t poly,slong len)387 void n_poly_truncate(n_poly_t poly, slong len)
388 {
389 if (poly->length > len)
390 {
391 poly->length = len;
392 _n_poly_normalise(poly);
393 }
394 }
395
396 N_POLY_INLINE
_n_poly_mod_scalar_mul_nmod(n_poly_t A,const n_poly_t B,mp_limb_t c,nmod_t mod)397 void _n_poly_mod_scalar_mul_nmod(n_poly_t A, const n_poly_t B, mp_limb_t c,
398 nmod_t mod)
399 {
400 FLINT_ASSERT(B->length <= B->alloc);
401 n_poly_fit_length(A, B->length);
402 _nmod_vec_scalar_mul_nmod(A->coeffs, B->coeffs, B->length, c, mod);
403 A->length = B->length;
404 }
405
406 N_POLY_INLINE
_n_poly_mod_scalar_mul_nmod_inplace(n_poly_t A,mp_limb_t c,nmod_t mod)407 void _n_poly_mod_scalar_mul_nmod_inplace(n_poly_t A, mp_limb_t c, nmod_t mod)
408 {
409 _nmod_vec_scalar_mul_nmod(A->coeffs, A->coeffs, A->length, c, mod);
410 }
411
412 FLINT_DLL void n_poly_mod_scalar_mul_ui(n_poly_t A, const n_poly_t B,
413 mp_limb_t c, nmod_t ctx);
414
415 FLINT_DLL mp_limb_t n_poly_mod_eval_step2(n_poly_t Acur, const n_poly_t Ainc,
416 nmod_t mod);
417
418 N_POLY_INLINE
n_poly_mod_evaluate_nmod(const n_poly_t A,mp_limb_t c,nmod_t mod)419 mp_limb_t n_poly_mod_evaluate_nmod(const n_poly_t A, mp_limb_t c, nmod_t mod)
420 {
421 return _nmod_poly_evaluate_nmod(A->coeffs, A->length, c, mod);
422 }
423
424 N_POLY_INLINE
n_poly_mod_neg(n_poly_t A,const n_poly_t B,nmod_t mod)425 void n_poly_mod_neg(n_poly_t A, const n_poly_t B, nmod_t mod)
426 {
427 n_poly_fit_length(A, B->length);
428 _nmod_vec_neg(A->coeffs, B->coeffs, B->length, mod);
429 A->length = B->length;
430 }
431
432 N_POLY_INLINE
n_poly_mod_add(n_poly_t A,const n_poly_t B,const n_poly_t C,nmod_t mod)433 void n_poly_mod_add(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t mod)
434 {
435 slong Alen = FLINT_MAX(B->length, C->length);
436 n_poly_fit_length(A, Alen);
437 _nmod_poly_add(A->coeffs, B->coeffs, B->length, C->coeffs, C->length, mod);
438 A->length = Alen;
439 _n_poly_normalise(A);
440 }
441
442 FLINT_DLL void n_poly_mod_add_ui(n_poly_t res, const n_poly_t poly, ulong c, nmod_t ctx);
443
444
445 N_POLY_INLINE
n_poly_mod_sub(n_poly_t A,const n_poly_t B,const n_poly_t C,nmod_t mod)446 void n_poly_mod_sub(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t mod)
447 {
448 slong Alen = FLINT_MAX(B->length, C->length);
449 n_poly_fit_length(A, Alen);
450 _nmod_poly_sub(A->coeffs, B->coeffs, B->length, C->coeffs, C->length, mod);
451 A->length = Alen;
452 _n_poly_normalise(A);
453 }
454
455 N_POLY_INLINE
n_poly_mod_product_roots_nmod_vec(n_poly_t A,mp_srcptr r,slong n,nmod_t mod)456 void n_poly_mod_product_roots_nmod_vec(n_poly_t A, mp_srcptr r, slong n, nmod_t mod)
457 {
458 n_poly_fit_length(A, n + 1);
459 A->length = n + 1;
460 _nmod_poly_product_roots_nmod_vec(A->coeffs, r, n, mod);
461 }
462
463 FLINT_DLL void n_poly_mod_shift_left_scalar_addmul(n_poly_t A, slong k,
464 mp_limb_t c, nmod_t mod);
465
466 FLINT_DLL void n_poly_mod_addmul_linear(n_poly_t A, const n_poly_t B,
467 const n_poly_t C, mp_limb_t d1, mp_limb_t d0, nmod_t mod);
468
469 FLINT_DLL void n_poly_mod_scalar_addmul_nmod(n_poly_t A, const n_poly_t B,
470 const n_poly_t C, mp_limb_t d0, nmod_t ctx);
471
472 FLINT_DLL mp_limb_t _n_poly_eval_pow(n_poly_t P, n_poly_t alphapow, int nlimbs,
473 nmod_t ctx);
474
475 FLINT_DLL mp_limb_t n_poly_mod_eval_pow(n_poly_t P, n_poly_t alphapow,
476 nmod_t ctx);
477
478 FLINT_DLL void n_poly_mod_eval2_pow(mp_limb_t * vp, mp_limb_t * vm,
479 const n_poly_t P, n_poly_t alphapow, nmod_t ctx);
480
481 FLINT_DLL mp_limb_t n_poly_mod_div_root(n_poly_t Q,
482 const n_poly_t A, mp_limb_t c, nmod_t ctx);
483
484 N_POLY_INLINE
_n_poly_mod_mul(n_poly_t A,const n_poly_t B,const n_poly_t C,nmod_t ctx)485 void _n_poly_mod_mul(n_poly_t A, const n_poly_t B, const n_poly_t C, nmod_t ctx)
486 {
487 slong Blen = B->length;
488 slong Clen = C->length;
489 slong Alen = Blen + Clen - 1;
490
491 FLINT_ASSERT(A != B);
492 FLINT_ASSERT(A != C);
493
494 if (Clen < 1 || Blen < 1)
495 {
496 A->length = 0;
497 return;
498 }
499
500 n_poly_fit_length(A, Alen);
501 A->length = Alen;
502
503 if (Blen >= Clen)
504 _nmod_poly_mul(A->coeffs, B->coeffs, Blen, C->coeffs, Clen, ctx);
505 else
506 _nmod_poly_mul(A->coeffs, C->coeffs, Clen, B->coeffs, Blen, ctx);
507 }
508
509 N_POLY_INLINE
_n_poly_mod_div(n_poly_t Q,const n_poly_t A,const n_poly_t B,nmod_t mod)510 void _n_poly_mod_div(n_poly_t Q, const n_poly_t A, const n_poly_t B, nmod_t mod)
511 {
512 const slong lenA = A->length, lenB = B->length;
513 FLINT_ASSERT(lenB > 0);
514 FLINT_ASSERT(Q != A && Q != B);
515 if (lenA < lenB)
516 {
517 n_poly_zero(Q);
518 return;
519 }
520 n_poly_fit_length(Q, lenA - lenB + 1);
521 _nmod_poly_div(Q->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
522 Q->length = lenA - lenB + 1;
523 }
524
525 N_POLY_INLINE
_n_poly_mod_rem(n_poly_t R,const n_poly_t A,const n_poly_t B,nmod_t mod)526 void _n_poly_mod_rem(n_poly_t R, const n_poly_t A, const n_poly_t B, nmod_t mod)
527 {
528 const slong lenA = A->length, lenB = B->length;
529 FLINT_ASSERT(R != A && R != B);
530 FLINT_ASSERT(lenB > 0);
531 if (lenA < lenB)
532 {
533 n_poly_set(R, A);
534 return;
535 }
536 n_poly_fit_length(R, lenB - 1);
537 _nmod_poly_rem(R->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
538 R->length = lenB - 1;
539 _n_poly_normalise(R);
540 }
541
542 N_POLY_INLINE
_n_poly_mod_divrem(n_poly_t Q,n_poly_t R,const n_poly_t A,const n_poly_t B,nmod_t mod)543 void _n_poly_mod_divrem(n_poly_t Q, n_poly_t R, const n_poly_t A,
544 const n_poly_t B, nmod_t mod)
545 {
546 const slong lenA = A->length, lenB = B->length;
547
548 FLINT_ASSERT(lenB > 0);
549 FLINT_ASSERT(Q != A && Q != B);
550 FLINT_ASSERT(R != A && R != B);
551
552 if (lenA < lenB)
553 {
554 n_poly_set(R, A);
555 n_poly_zero(Q);
556 return;
557 }
558
559 n_poly_fit_length(Q, lenA - lenB + 1);
560 n_poly_fit_length(R, lenB - 1);
561 _nmod_poly_divrem(Q->coeffs, R->coeffs, A->coeffs, lenA, B->coeffs, lenB, mod);
562 Q->length = lenA - lenB + 1;
563 R->length = lenB - 1;
564 _n_poly_normalise(R);
565 }
566
567 FLINT_DLL ulong n_poly_mod_remove(n_poly_t f, const n_poly_t p, nmod_t ctx);
568
569 FLINT_DLL void n_poly_mod_pow(n_poly_t res, const n_poly_t poly, ulong e,
570 nmod_t ctx);
571
572 FLINT_DLL void n_poly_mod_mul(n_poly_t A, const n_poly_t B, const n_poly_t C,
573 nmod_t mod);
574
575 FLINT_DLL void n_poly_mod_mullow(n_poly_t A, const n_poly_t B,
576 const n_poly_t C, slong n, nmod_t mod);
577
578 FLINT_DLL void n_poly_mod_div(n_poly_t Q, const n_poly_t A, const n_poly_t B,
579 nmod_t mod);
580
581 FLINT_DLL void n_poly_mod_rem(n_poly_t R, const n_poly_t A, const n_poly_t B,
582 nmod_t mod);
583
584 FLINT_DLL void n_poly_mod_divrem(n_poly_t Q, n_poly_t R, const n_poly_t A,
585 const n_poly_t B, nmod_t mod);
586
587 FLINT_DLL void n_poly_mod_mulmod(n_poly_t res, const n_poly_t poly1,
588 const n_poly_t poly2, const n_poly_t f, nmod_t mod);
589
590 FLINT_DLL int n_poly_mod_invmod(n_poly_t A, const n_poly_t B, const n_poly_t P,
591 nmod_t mod);
592
593 FLINT_DLL void n_poly_mod_gcd(n_poly_t G, const n_poly_t A, const n_poly_t B,
594 nmod_t mod);
595
596 FLINT_DLL void n_poly_mod_xgcd(n_poly_t G, n_poly_t S, n_poly_t T,
597 const n_poly_t A, const n_poly_t B, nmod_t mod);
598
599 FLINT_DLL void n_poly_mod_inv_series(n_poly_t Qinv, const n_poly_t Q, slong n,
600 nmod_t mod);
601
602 FLINT_DLL void n_poly_mod_div_series(n_poly_t Q, const n_poly_t A,
603 const n_poly_t B, slong order, nmod_t ctx);
604
605 FLINT_DLL void n_poly_reverse(n_poly_t output, const n_poly_t input, slong m);
606
607 FLINT_DLL void n_poly_mod_mulmod_preinv(n_poly_t A, const n_poly_t B,
608 const n_poly_t C, const n_poly_t M, const n_poly_t Minv, nmod_t ctx);
609
610 /*****************************************************************************/
611
612 N_POLY_INLINE
fq_nmod_ctx_mod(const fq_nmod_ctx_t ctx)613 nmod_t fq_nmod_ctx_mod(const fq_nmod_ctx_t ctx)
614 {
615 return ctx->modulus->mod;
616 }
617
618 N_POLY_INLINE
_n_fq_is_zero(const mp_limb_t * a,slong d)619 int _n_fq_is_zero(const mp_limb_t * a, slong d)
620 {
621 do {
622 if (a[--d] != 0)
623 return 0;
624 } while (d > 0);
625 return 1;
626 }
627
628 N_POLY_INLINE
_n_fq_zero(mp_limb_t * a,slong d)629 void _n_fq_zero(mp_limb_t * a, slong d)
630 {
631 slong i;
632 for (i = 0; i < d; i++)
633 a[i] = 0;
634 }
635
636 N_POLY_INLINE
_n_fq_is_one(const mp_limb_t * a,slong d)637 int _n_fq_is_one(const mp_limb_t * a, slong d)
638 {
639 slong i;
640 if (a[0] != 1)
641 return 0;
642 for (i = 1; i < d; i++)
643 if (a[i] != 0)
644 return 0;
645 return 1;
646 }
647
648 N_POLY_INLINE
_n_fq_is_ui(const mp_limb_t * a,slong d)649 int _n_fq_is_ui(const mp_limb_t * a, slong d)
650 {
651 slong i;
652 for (i = 1; i < d; i++)
653 if (a[i] != 0)
654 return 0;
655 return 1;
656 }
657
658 N_POLY_INLINE
n_fq_is_one(const mp_limb_t * a,const fq_nmod_ctx_t ctx)659 int n_fq_is_one(const mp_limb_t * a, const fq_nmod_ctx_t ctx)
660 {
661 return _n_fq_is_one(a, fq_nmod_ctx_degree(ctx));
662 }
663
664 N_POLY_INLINE
_n_fq_one(mp_limb_t * a,slong d)665 void _n_fq_one(mp_limb_t * a, slong d)
666 {
667 slong i;
668 a[0] = 1;
669 for (i = 1; i < d; i++)
670 a[i] = 0;
671 }
672
673 N_POLY_INLINE
_n_fq_set_nmod(mp_limb_t * a,mp_limb_t b,slong d)674 void _n_fq_set_nmod(mp_limb_t * a, mp_limb_t b, slong d)
675 {
676 slong i;
677 a[0] = b;
678 for (i = 1; i < d; i++)
679 a[i] = 0;
680 }
681
682 FLINT_DLL void n_fq_gen(
683 mp_limb_t * a,
684 const fq_nmod_ctx_t ctx);
685
686 N_POLY_INLINE
_n_fq_set(mp_limb_t * a,const mp_limb_t * b,slong d)687 void _n_fq_set(
688 mp_limb_t * a, /* length d */
689 const mp_limb_t * b, /* length d */
690 slong d)
691 {
692 slong i = 0;
693 do {
694 a[i] = b[i];
695 i++;
696 } while (i < d);
697 }
698
699 N_POLY_INLINE
_n_fq_swap(mp_limb_t * a,mp_limb_t * b,slong d)700 void _n_fq_swap(
701 mp_limb_t * a, /* length d */
702 mp_limb_t * b, /* length d */
703 slong d)
704 {
705 slong i = 0;
706 do {
707 MP_LIMB_SWAP(a[i], b[i]);
708 i++;
709 } while (i < d);
710 }
711
712 N_POLY_INLINE
_n_fq_equal(mp_limb_t * a,const mp_limb_t * b,slong d)713 int _n_fq_equal(
714 mp_limb_t * a, /* length d */
715 const mp_limb_t * b, /* length d */
716 slong d)
717 {
718 slong i = 0;
719 do {
720 if (a[i] != b[i])
721 return 0;
722 } while (++i < d);
723 return 1;
724 }
725
726 FLINT_DLL int n_fq_equal_fq_nmod(
727 const mp_limb_t * a,
728 const fq_nmod_t b,
729 const fq_nmod_ctx_t ctx);
730
731 FLINT_DLL int n_fq_is_canonical(
732 const mp_limb_t * a,
733 const fq_nmod_ctx_t ctx);
734
735 FLINT_DLL void n_fq_randtest_not_zero(
736 mp_limb_t * a,
737 flint_rand_t state,
738 const fq_nmod_ctx_t ctx);
739
740 FLINT_DLL char * n_fq_get_str_pretty(
741 const mp_limb_t * a,
742 const fq_nmod_ctx_t ctx);
743
744 FLINT_DLL int n_fq_fprint_pretty(
745 FILE * file,
746 const mp_limb_t * a,
747 const fq_nmod_ctx_t ctx);
748
749 FLINT_DLL void n_fq_print_pretty(
750 const mp_limb_t * a,
751 const fq_nmod_ctx_t ctx);
752
753 FLINT_DLL void n_fq_get_fq_nmod(
754 fq_nmod_t a,
755 const mp_limb_t * b,
756 const fq_nmod_ctx_t ctx);
757
758 FLINT_DLL void n_fq_set_fq_nmod(
759 mp_limb_t * a,
760 const fq_nmod_t b,
761 const fq_nmod_ctx_t ctx);
762
763 FLINT_DLL void n_fq_get_n_poly(
764 n_poly_t a,
765 const mp_limb_t * b,
766 const fq_nmod_ctx_t ctx);
767
768 FLINT_DLL void _n_fq_set_n_poly(
769 mp_limb_t * a,
770 const mp_limb_t * bcoeffs, slong blen,
771 const fq_nmod_ctx_t ctx);
772
773 FLINT_DLL void n_fq_add_si(
774 mp_limb_t * a,
775 const mp_limb_t * b,
776 slong c,
777 const fq_nmod_ctx_t ctx);
778
779 N_POLY_INLINE
n_fq_add(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,const fq_nmod_ctx_t ctx)780 void n_fq_add(
781 mp_limb_t * a, /* length d */
782 const mp_limb_t * b, /* length d */
783 const mp_limb_t * c, /* length d */
784 const fq_nmod_ctx_t ctx)
785 {
786 slong d = fq_nmod_ctx_degree(ctx);
787 FLINT_ASSERT(d > 0);
788 _nmod_vec_add(a, b, c, d, ctx->modulus->mod);
789 }
790
791 void n_fq_add_fq_nmod(
792 mp_limb_t * a,
793 const mp_limb_t * b,
794 const fq_nmod_t c,
795 const fq_nmod_ctx_t ctx);
796
797 void n_fq_sub_fq_nmod(
798 mp_limb_t * a,
799 const mp_limb_t * b,
800 const fq_nmod_t c,
801 const fq_nmod_ctx_t ctx);
802
803 N_POLY_INLINE
n_fq_sub(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,const fq_nmod_ctx_t ctx)804 void n_fq_sub(
805 mp_limb_t * a, /* length d */
806 const mp_limb_t * b, /* length d */
807 const mp_limb_t * c, /* length d */
808 const fq_nmod_ctx_t ctx)
809 {
810 slong d = fq_nmod_ctx_degree(ctx);
811 FLINT_ASSERT(d > 0);
812 _nmod_vec_sub(a, b, c, d, ctx->modulus->mod);
813 }
814
815 N_POLY_INLINE
_n_fq_add(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,slong d,nmod_t mod)816 void _n_fq_add(
817 mp_limb_t * a, /* length d */
818 const mp_limb_t * b, /* length d */
819 const mp_limb_t * c, /* length d */
820 slong d,
821 nmod_t mod)
822 {
823 FLINT_ASSERT(d > 0);
824 _nmod_vec_add(a, b, c, d, mod);
825 }
826
827 N_POLY_INLINE
_n_fq_sub(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,slong d,nmod_t mod)828 void _n_fq_sub(
829 mp_limb_t * a, /* length d */
830 const mp_limb_t * b, /* length d */
831 const mp_limb_t * c, /* length d */
832 slong d,
833 nmod_t mod)
834 {
835 FLINT_ASSERT(d > 0);
836 _nmod_vec_sub(a, b, c, d, mod);
837 }
838
839 N_POLY_INLINE
_n_fq_neg(mp_limb_t * a,const mp_limb_t * b,slong d,nmod_t mod)840 void _n_fq_neg(
841 mp_limb_t * a,
842 const mp_limb_t * b,
843 slong d,
844 nmod_t mod)
845 {
846 FLINT_ASSERT(d > 0);
847 _nmod_vec_neg(a, b, d, mod);
848 }
849
850 N_POLY_INLINE
_n_fq_mul_ui(mp_limb_t * a,const mp_limb_t * b,mp_limb_t c,slong d,nmod_t mod)851 void _n_fq_mul_ui(
852 mp_limb_t * a, /* length d */
853 const mp_limb_t * b, /* length d */
854 mp_limb_t c,
855 slong d,
856 nmod_t mod)
857 {
858 if (c >= mod.n)
859 NMOD_RED(c, c, mod);
860 _nmod_vec_scalar_mul_nmod(a, b, d, c, mod);
861 }
862
863 FLINT_DLL void _n_fq_madd2(
864 mp_limb_t * a, /* length 2d-1 */
865 const mp_limb_t * b, /* length d */
866 const mp_limb_t * c, /* length d */
867 const fq_nmod_ctx_t ctx,
868 mp_limb_t * t); /* length 2d */
869
870 FLINT_DLL void _n_fq_mul2(
871 mp_limb_t * t, /* length 2d-1 */
872 const mp_limb_t * b, /* length d */
873 const mp_limb_t * c, /* length d */
874 const fq_nmod_ctx_t ctx);
875
876 #define N_FQ_REDUCE_ITCH 2
877 FLINT_DLL void _n_fq_reduce(
878 mp_limb_t * a,
879 mp_limb_t * b, slong blen,
880 const fq_nmod_ctx_t ctx,
881 mp_limb_t * t);
882
883 /* same itch as reduce */
884 N_POLY_INLINE
_n_fq_reduce2(mp_limb_t * a,mp_limb_t * b,const fq_nmod_ctx_t ctx,mp_limb_t * t)885 void _n_fq_reduce2(
886 mp_limb_t * a, /* length d */
887 mp_limb_t * b, /* length 2d-1 */
888 const fq_nmod_ctx_t ctx,
889 mp_limb_t * t) /* length 2d */
890 {
891 slong blen = 2*fq_nmod_ctx_degree(ctx) - 1;
892
893 FLINT_ASSERT(a != b);
894
895 while (blen > 0 && b[blen - 1] == 0)
896 blen--;
897
898 _n_fq_reduce(a, b, blen, ctx, t);
899 }
900
901
902 #define N_FQ_MUL_ITCH 4
903 N_POLY_INLINE
_n_fq_mul(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,const fq_nmod_ctx_t ctx,mp_limb_t * t)904 void _n_fq_mul(
905 mp_limb_t * a, /* length d */
906 const mp_limb_t * b, /* length d */
907 const mp_limb_t * c, /* length d */
908 const fq_nmod_ctx_t ctx,
909 mp_limb_t * t) /* length 4d */
910 {
911 slong d = fq_nmod_ctx_degree(ctx);
912 _n_fq_mul2(t, b, c, ctx);
913 _n_fq_reduce2(a, t, ctx, t + 2*d);
914 }
915
916 N_POLY_INLINE
_n_fq_addmul(mp_limb_t * a,const mp_limb_t * b,const mp_limb_t * c,const mp_limb_t * e,const fq_nmod_ctx_t ctx,mp_limb_t * t)917 void _n_fq_addmul(
918 mp_limb_t * a, /* length d */
919 const mp_limb_t * b, /* length d */
920 const mp_limb_t * c, /* length d */
921 const mp_limb_t * e, /* length d */
922 const fq_nmod_ctx_t ctx,
923 mp_limb_t * t) /* length 4d */
924 {
925 slong d = fq_nmod_ctx_degree(ctx);
926 _n_fq_mul2(t, c, e, ctx);
927 _nmod_vec_add(t, t, b, d, ctx->mod);
928 _n_fq_reduce2(a, t, ctx, t + 2*d);
929 }
930
931 #define N_FQ_LAZY_ITCH 6
932 FLINT_DLL int _n_fq_dot_lazy_size(slong len, const fq_nmod_ctx_t ctx);
933
934 FLINT_DLL void _n_fq_reduce2_lazy1(
935 mp_limb_t * a, /* length 6d, 2d used */
936 slong d,
937 nmod_t ctx);
938
939 FLINT_DLL void _n_fq_madd2_lazy1(
940 mp_limb_t * a, /* length 6d, 2d used */
941 const mp_limb_t * b, /* length d */
942 const mp_limb_t * c, /* length d */
943 slong d);
944
945 FLINT_DLL void _n_fq_mul2_lazy1(
946 mp_limb_t * a, /* length 6d, 2d used */
947 const mp_limb_t * b, /* length d */
948 const mp_limb_t * c, /* length d */
949 slong d);
950
951 FLINT_DLL void _n_fq_reduce2_lazy2(
952 mp_limb_t * a, /* length 6d, 4d used */
953 slong d,
954 nmod_t ctx);
955
956 FLINT_DLL void _n_fq_madd2_lazy2(
957 mp_limb_t * a, /* length 6d, 4d used */
958 const mp_limb_t * b, /* length d */
959 const mp_limb_t * c, /* length d */
960 slong d);
961
962 FLINT_DLL void _n_fq_mul2_lazy2(
963 mp_limb_t * a, /* length 6d, 4d used */
964 const mp_limb_t * b, /* length d */
965 const mp_limb_t * c, /* length d */
966 slong d);
967
968 FLINT_DLL void _n_fq_reduce2_lazy3(
969 mp_limb_t * a, /* length 6d */
970 slong d,
971 nmod_t ctx);
972
973 FLINT_DLL void _n_fq_madd2_lazy3(
974 mp_limb_t * a, /* length 6d */
975 const mp_limb_t * b, /* length d */
976 const mp_limb_t * c, /* length d */
977 slong d);
978
979 FLINT_DLL void _n_fq_mul2_lazy3(
980 mp_limb_t * a, /* length 6d */
981 const mp_limb_t * b, /* length d */
982 const mp_limb_t * c, /* length d */
983 slong d);
984
985
986 #define N_FQ_INV_ITCH 1
987 FLINT_DLL void _n_fq_inv(
988 mp_limb_t * a,
989 const mp_limb_t * b,
990 const fq_nmod_ctx_t ctx,
991 mp_limb_t * t);
992
993 #define N_FQ_MUL_INV_ITCH FLINT_MAX(N_FQ_MUL_ITCH, N_FQ_INV_ITCH)
994
995 FLINT_DLL void _n_fq_pow_ui(
996 mp_limb_t * a,
997 const mp_limb_t * b,
998 ulong e,
999 const fq_nmod_ctx_t ctx);
1000
1001 FLINT_DLL void n_fq_pow_fmpz(
1002 mp_limb_t * a,
1003 const mp_limb_t * b,
1004 const fmpz_t e,
1005 const fq_nmod_ctx_t ctx);
1006
1007 FLINT_DLL void n_fq_mul(
1008 mp_limb_t * a,
1009 const mp_limb_t * b,
1010 const mp_limb_t * c,
1011 const fq_nmod_ctx_t ctx);
1012
1013 FLINT_DLL void n_fq_mul_fq_nmod(
1014 mp_limb_t * a,
1015 const mp_limb_t * b,
1016 const fq_nmod_t c,
1017 const fq_nmod_ctx_t ctx);
1018
1019 FLINT_DLL void n_fq_addmul(
1020 mp_limb_t * a,
1021 const mp_limb_t * b,
1022 const mp_limb_t * c,
1023 const mp_limb_t * d,
1024 const fq_nmod_ctx_t ctx);
1025
1026 FLINT_DLL void n_fq_inv(
1027 mp_limb_t * a,
1028 const mp_limb_t * b,
1029 const fq_nmod_ctx_t ctx);
1030
1031 FLINT_DLL void n_fq_pow_ui(
1032 mp_limb_t * a,
1033 const mp_limb_t * b,
1034 ulong e,
1035 const fq_nmod_ctx_t ctx);
1036
1037 /*****************************************************************************/
1038
1039 #define N_FQ_POLY_DIVREM_DIVCONQUER_CUTOFF 20
1040
1041 #define n_fq_poly_init n_poly_init
1042
1043 #define n_fq_poly_clear n_poly_clear
1044
1045 #define n_fq_poly_degree n_poly_degree
1046
1047 #define n_fq_poly_zero n_poly_zero
1048
1049 #define n_fq_poly_is_zero n_poly_is_zero
1050
1051 #define n_fq_poly_swap n_poly_swap
1052
1053 #define n_fq_bpoly_init n_bpoly_init
1054
1055 #define n_fq_bpoly_clear n_bpoly_clear
1056
1057 #define n_fq_bpoly_zero n_bpoly_zero
1058
1059 #define n_fq_bpoly_fit_length n_bpoly_fit_length
1060
1061 #define n_fq_bpoly_normalise n_bpoly_normalise
1062
1063 #define n_fq_polyun_init n_polyun_init
1064
1065 #define n_fq_polyun_clear n_polyun_clear
1066
1067 #define n_fq_bpoly_degree1 n_bpoly_degree1
1068
1069 #define n_fq_bpoly_degree0 n_bpoly_degree0
1070
1071 FLINT_DLL void n_fq_poly_init2(n_fq_poly_t A, slong alloc, const fq_nmod_ctx_t ctx);
1072
1073 FLINT_DLL void _n_fq_poly_one(n_fq_poly_t A, slong d);
1074
1075 N_POLY_INLINE
n_fq_poly_one(n_fq_poly_t A,const fq_nmod_ctx_t ctx)1076 void n_fq_poly_one(n_fq_poly_t A, const fq_nmod_ctx_t ctx)
1077 {
1078 _n_fq_poly_one(A, fq_nmod_ctx_degree(ctx));
1079 }
1080
1081 FLINT_DLL int n_fq_poly_is_one(n_fq_poly_t A, const fq_nmod_ctx_t ctx);
1082
1083 FLINT_DLL int n_fq_poly_is_canonical(
1084 const n_fq_poly_t a,
1085 const fq_nmod_ctx_t ctx);
1086
1087 N_POLY_INLINE
_n_fq_poly_normalise(n_fq_poly_t A,slong d)1088 void _n_fq_poly_normalise(n_fq_poly_t A, slong d)
1089 {
1090 while (A->length > 0 && _n_fq_is_zero(A->coeffs + d*(A->length - 1), d))
1091 A->length--;
1092 }
1093
1094 FLINT_DLL void n_fq_poly_print_pretty(
1095 const n_fq_poly_t A,
1096 const char * x,
1097 const fq_nmod_ctx_t ctx);
1098
1099 FLINT_DLL int n_fq_poly_equal(
1100 const n_fq_poly_t A,
1101 const n_fq_poly_t B,
1102 const fq_nmod_ctx_t ctx);
1103
1104 FLINT_DLL void n_fq_poly_set(
1105 n_fq_poly_t A,
1106 const n_fq_poly_t B,
1107 const fq_nmod_ctx_t ctx);
1108
1109 FLINT_DLL void n_fq_poly_randtest(
1110 n_fq_poly_t A,
1111 flint_rand_t state,
1112 slong len,
1113 const fq_nmod_ctx_t ctx);
1114
1115 FLINT_DLL void n_fq_poly_make_monic(
1116 n_fq_poly_t A,
1117 const n_poly_t B,
1118 const fq_nmod_ctx_t ctx);
1119
1120 FLINT_DLL void n_fq_poly_get_coeff_n_fq(
1121 mp_limb_t * c,
1122 const n_poly_t A,
1123 slong e,
1124 const fq_nmod_ctx_t ctx);
1125
1126 FLINT_DLL void n_fq_poly_get_coeff_fq_nmod(
1127 fq_nmod_t c,
1128 const n_poly_t A,
1129 slong e,
1130 const fq_nmod_ctx_t ctx);
1131
1132 FLINT_DLL void n_fq_poly_set_coeff_n_fq(
1133 n_poly_t A,
1134 slong j,
1135 const mp_limb_t * c,
1136 const fq_nmod_ctx_t ctx);
1137
1138 FLINT_DLL void n_fq_poly_set_coeff_fq_nmod(
1139 n_poly_t A,
1140 slong j,
1141 const fq_nmod_t c,
1142 const fq_nmod_ctx_t ctx);
1143
1144 FLINT_DLL void n_fq_poly_scalar_mul_n_fq(
1145 n_poly_t A,
1146 const n_poly_t B,
1147 const mp_limb_t * c,
1148 const fq_nmod_ctx_t ctx);
1149
1150 FLINT_DLL void n_fq_poly_scalar_mul_ui(
1151 n_poly_t A,
1152 const n_poly_t B,
1153 ulong c,
1154 const fq_nmod_ctx_t ctx);
1155
1156 FLINT_DLL void n_fq_poly_scalar_addmul_n_fq(
1157 n_fq_poly_t A,
1158 const n_fq_poly_t B,
1159 const n_fq_poly_t C,
1160 const mp_limb_t * d,
1161 const fq_nmod_ctx_t ctx);
1162
1163 FLINT_DLL void n_fq_poly_shift_left_scalar_submul(
1164 n_poly_t A,
1165 slong k,
1166 const mp_limb_t * c,
1167 const fq_nmod_ctx_t ctx);
1168
1169 FLINT_DLL void n_fq_poly_evaluate_fq_nmod(
1170 fq_nmod_t e,
1171 const n_poly_t A,
1172 const fq_nmod_t c,
1173 const fq_nmod_ctx_t ctx);
1174
1175 FLINT_DLL void n_fq_poly_evaluate_n_fq(
1176 mp_limb_t * e,
1177 const n_poly_t A,
1178 const mp_limb_t * c,
1179 const fq_nmod_ctx_t ctx);
1180
1181 FLINT_DLL void n_fq_poly_get_fq_nmod_poly(
1182 fq_nmod_poly_t A,
1183 const n_poly_t B,
1184 const fq_nmod_ctx_t ctx);
1185
1186 FLINT_DLL void n_fq_poly_set_fq_nmod_poly(
1187 n_poly_t A,
1188 const fq_nmod_poly_t B,
1189 const fq_nmod_ctx_t ctx);
1190
1191 FLINT_DLL void n_fq_poly_set_n_fq(
1192 n_poly_t A,
1193 const mp_limb_t * c,
1194 const fq_nmod_ctx_t ctx);
1195
1196 FLINT_DLL void n_fq_poly_set_fq_nmod(
1197 n_poly_t A,
1198 const fq_nmod_t c,
1199 const fq_nmod_ctx_t ctx);
1200
1201 FLINT_DLL void n_fq_poly_shift_right(
1202 n_poly_t A,
1203 const n_poly_t B,
1204 slong n,
1205 const fq_nmod_ctx_t ctx);
1206
1207 FLINT_DLL void n_fq_poly_shift_left(
1208 n_poly_t A,
1209 const n_poly_t B,
1210 slong n,
1211 const fq_nmod_ctx_t ctx);
1212
1213 FLINT_DLL void n_fq_poly_truncate(
1214 n_poly_t A,
1215 slong len,
1216 const fq_nmod_ctx_t ctx);
1217
1218 FLINT_DLL void n_fq_poly_add(
1219 n_poly_t A,
1220 const n_poly_t B,
1221 const n_poly_t C,
1222 const fq_nmod_ctx_t ctx);
1223
1224 FLINT_DLL void n_fq_poly_sub(
1225 n_poly_t A,
1226 const n_poly_t B,
1227 const n_poly_t C,
1228 const fq_nmod_ctx_t ctx);
1229
1230 FLINT_DLL void n_fq_poly_neg(
1231 n_poly_t A,
1232 const n_poly_t B,
1233 const fq_nmod_ctx_t ctx);
1234
1235 FLINT_DLL void n_fq_poly_add_si(
1236 n_poly_t A,
1237 const n_poly_t B,
1238 slong c,
1239 const fq_nmod_ctx_t ctx);
1240
1241 FLINT_DLL void _n_fq_poly_mul_(
1242 mp_limb_t * A,
1243 const mp_limb_t * B, slong Blen,
1244 const mp_limb_t * C, slong Clen,
1245 const fq_nmod_ctx_t ctx,
1246 n_poly_stack_t St);
1247
1248 FLINT_DLL void n_fq_poly_mul_(
1249 n_poly_t A,
1250 const n_poly_t B,
1251 const n_poly_t C,
1252 const fq_nmod_ctx_t ctx,
1253 n_poly_stack_t St);
1254
1255 FLINT_DLL void n_fq_poly_mul(
1256 n_poly_t A,
1257 const n_poly_t B,
1258 const n_poly_t C,
1259 const fq_nmod_ctx_t ctx);
1260
1261 FLINT_DLL void n_fq_poly_pow(
1262 n_poly_t A,
1263 const n_poly_t B,
1264 ulong e,
1265 const fq_nmod_ctx_t ctx);
1266
1267 FLINT_DLL ulong n_fq_poly_remove(
1268 n_poly_t f,
1269 const n_poly_t g,
1270 const fq_nmod_ctx_t ctx);
1271
1272 FLINT_DLL void n_fq_poly_divrem_divconquer_(
1273 n_poly_t Q,
1274 n_poly_t R,
1275 const n_poly_t A,
1276 const n_poly_t B,
1277 const fq_nmod_ctx_t ctx,
1278 n_poly_stack_t St);
1279
1280 N_POLY_INLINE
n_fq_poly_divrem_(n_poly_t Q,n_poly_t R,const n_poly_t A,const n_poly_t B,const fq_nmod_ctx_t ctx,n_poly_stack_t St)1281 void n_fq_poly_divrem_(
1282 n_poly_t Q,
1283 n_poly_t R,
1284 const n_poly_t A,
1285 const n_poly_t B,
1286 const fq_nmod_ctx_t ctx,
1287 n_poly_stack_t St)
1288 {
1289 n_fq_poly_divrem_divconquer_(Q, R, A, B, ctx, St);
1290 }
1291
1292 FLINT_DLL void n_fq_poly_divrem(
1293 n_poly_t Q,
1294 n_poly_t R,
1295 const n_poly_t A,
1296 const n_poly_t B,
1297 const fq_nmod_ctx_t ctx);
1298
1299 FLINT_DLL void n_fq_poly_gcd(
1300 n_poly_t G,
1301 const n_poly_t A,
1302 const n_poly_t B,
1303 const fq_nmod_ctx_t ctx);
1304
1305 FLINT_DLL void n_fq_poly_gcd_(
1306 n_poly_t G,
1307 const n_poly_t A,
1308 const n_poly_t B,
1309 const fq_nmod_ctx_t ctx,
1310 n_poly_stack_t St);
1311
1312 FLINT_DLL void n_fq_poly_xgcd(
1313 n_poly_t G,
1314 n_poly_t S,
1315 n_poly_t T,
1316 const n_poly_t B,
1317 const n_poly_t C,
1318 const fq_nmod_ctx_t ctx);
1319
1320 FLINT_DLL void n_fq_poly_mulmod(
1321 n_poly_t A,
1322 const n_poly_t B,
1323 const n_poly_t C,
1324 const n_poly_t M,
1325 const fq_nmod_ctx_t ctx);
1326
1327 FLINT_DLL void n_fq_poly_rem(
1328 n_poly_t R,
1329 const n_poly_t A,
1330 const n_poly_t B,
1331 const fq_nmod_ctx_t ctx);
1332
1333 FLINT_DLL void n_fq_poly_mullow(
1334 n_poly_t A,
1335 const n_poly_t B,
1336 const n_poly_t C,
1337 slong order,
1338 const fq_nmod_ctx_t ctx);
1339
1340 FLINT_DLL void n_fq_poly_inv_series(
1341 n_poly_t A,
1342 const n_poly_t B,
1343 slong order,
1344 const fq_nmod_ctx_t ctx);
1345
1346 FLINT_DLL void n_fq_poly_eval_pow(
1347 mp_limb_t * ev,
1348 const n_fq_poly_t A,
1349 n_fq_poly_t alphapow,
1350 const fq_nmod_ctx_t ctx);
1351
1352 /*****************************************************************************/
1353
1354 N_POLY_INLINE
n_bpoly_init(n_bpoly_t A)1355 void n_bpoly_init(n_bpoly_t A)
1356 {
1357 A->coeffs = NULL;
1358 A->alloc = 0;
1359 A->length = 0;
1360 }
1361
1362 FLINT_DLL void n_bpoly_clear(n_bpoly_t A);
1363
1364 N_POLY_INLINE
n_bpoly_swap(n_bpoly_t A,n_bpoly_t B)1365 void n_bpoly_swap(n_bpoly_t A, n_bpoly_t B)
1366 {
1367 n_bpoly_struct t = *A;
1368 *A = *B;
1369 *B = t;
1370 }
1371
1372 FLINT_DLL void n_bpoly_print_pretty(const n_bpoly_t A,
1373 const char * xvar, const char * yvar);
1374
1375 N_POLY_INLINE
n_bpoly_normalise(n_bpoly_t A)1376 void n_bpoly_normalise(n_bpoly_t A)
1377 {
1378 while (A->length > 0 && n_poly_is_zero(A->coeffs + A->length - 1))
1379 A->length--;
1380 }
1381
1382 FLINT_DLL void n_bpoly_realloc(n_bpoly_t A, slong len);
1383
1384 N_POLY_INLINE
n_bpoly_fit_length(n_bpoly_t A,slong len)1385 void n_bpoly_fit_length(n_bpoly_t A, slong len)
1386 {
1387 if (len > A->alloc)
1388 n_bpoly_realloc(A, len);
1389 }
1390
1391 N_POLY_INLINE
n_bpoly_zero(n_bpoly_t A)1392 void n_bpoly_zero(n_bpoly_t A)
1393 {
1394 A->length = 0;
1395 }
1396
1397 N_POLY_INLINE
n_bpoly_is_zero(const n_bpoly_t A)1398 int n_bpoly_is_zero(const n_bpoly_t A)
1399 {
1400 return A->length == 0;
1401 }
1402
1403 FLINT_DLL void _n_bpoly_set(n_bpoly_t A, const n_bpoly_t B);
1404
1405 N_POLY_INLINE
n_bpoly_set(n_bpoly_t A,const n_bpoly_t B)1406 void n_bpoly_set(n_bpoly_t A, const n_bpoly_t B)
1407 {
1408 if (A != B)
1409 _n_bpoly_set(A, B);
1410 }
1411
1412 FLINT_DLL void n_bpoly_one(n_bpoly_t A);
1413
1414 FLINT_DLL int n_bpoly_equal(const n_bpoly_t A, const n_bpoly_t B);
1415
1416 FLINT_DLL void n_bpoly_set_coeff(n_bpoly_t A, slong e0, slong e1, mp_limb_t c);
1417
1418 FLINT_DLL void n_bpoly_set_coeff_nonzero(n_bpoly_t A, slong e0, slong e1,
1419 mp_limb_t c);
1420
1421 FLINT_DLL void n_bpoly_mod_derivative_gen0(n_bpoly_t A, const n_bpoly_t B,
1422 nmod_t ctx);
1423
1424 N_POLY_INLINE
n_bpoly_get_coeff(const n_bpoly_t A,slong e0,slong e1)1425 mp_limb_t n_bpoly_get_coeff(const n_bpoly_t A, slong e0, slong e1)
1426 {
1427 if (e0 >= A->length)
1428 return 0;
1429 else
1430 return n_poly_get_coeff(A->coeffs + e0, e1);
1431 }
1432
1433 N_POLY_INLINE
n_bpoly_degree0(const n_bpoly_t A)1434 slong n_bpoly_degree0(const n_bpoly_t A)
1435 {
1436 return A->length - 1;
1437 }
1438
1439 FLINT_DLL slong n_bpoly_degree1(const n_bpoly_t A);
1440
1441 FLINT_DLL void n_bpoly_set_poly_gen1(n_bpoly_t A, const n_poly_t B);
1442
1443 FLINT_DLL void n_bpoly_set_poly_gen0(n_bpoly_t A, const n_poly_t B);
1444
1445 /*****************************************************************************/
1446
1447 FLINT_DLL int n_bpoly_mod_is_canonical(const n_bpoly_t A, nmod_t mod);
1448
1449 N_POLY_INLINE
n_bpoly_bidegree(const n_bpoly_t A)1450 ulong n_bpoly_bidegree(const n_bpoly_t A)
1451 {
1452 ulong x, y;
1453 FLINT_ASSERT(A->length > 0);
1454 x = A->length - 1;
1455 y = A->coeffs[x].length - 1;
1456 return (x << (FLINT_BITS/2)) + y;
1457 }
1458
1459 FLINT_DLL void n_bpoly_scalar_mul_nmod(n_bpoly_t A, mp_limb_t c, nmod_t ctx);
1460
1461 FLINT_DLL void n_bpoly_mod_content_last(n_poly_t g, const n_bpoly_t A, nmod_t ctx);
1462
1463 FLINT_DLL void n_bpoly_mod_divexact_last(n_bpoly_t A, const n_poly_t b, nmod_t ctx);
1464
1465 FLINT_DLL void n_bpoly_mod_mul_last(n_bpoly_t A, const n_poly_t b, nmod_t ctx);
1466
1467
1468 FLINT_DLL void n_bpoly_mod_taylor_shift_gen1(n_bpoly_t A, const n_bpoly_t B,
1469 mp_limb_t c, nmod_t ctx);
1470
1471 FLINT_DLL void n_bpoly_mod_taylor_shift_gen0(n_bpoly_t A, mp_limb_t c,
1472 nmod_t ctx);
1473
1474 FLINT_DLL void n_bpoly_mod_add(n_bpoly_t A, const n_bpoly_t B,
1475 const n_bpoly_t C, nmod_t ctx);
1476
1477 FLINT_DLL void n_bpoly_mod_sub(n_bpoly_t A, const n_bpoly_t B,
1478 const n_bpoly_t C, nmod_t ctx);
1479
1480 FLINT_DLL void n_bpoly_mod_make_primitive(n_poly_t g, n_bpoly_t A, nmod_t ctx);
1481
1482 FLINT_DLL void n_bpoly_mod_mul(n_bpoly_t A, const n_bpoly_t B,
1483 const n_bpoly_t C, nmod_t ctx);
1484
1485 FLINT_DLL int n_bpoly_mod_divides(n_bpoly_t Q, const n_bpoly_t A,
1486 const n_bpoly_t B, nmod_t ctx);
1487
1488 FLINT_DLL void n_bpoly_mod_mul_series(n_bpoly_t A, const n_bpoly_t B,
1489 const n_bpoly_t C, slong order, nmod_t ctx);
1490
1491 FLINT_DLL void n_bpoly_mod_divrem_series(n_bpoly_t Q, n_bpoly_t R,
1492 const n_bpoly_t A, const n_bpoly_t B, slong order, nmod_t ctx);
1493
1494 FLINT_DLL void n_bpoly_mod_interp_reduce_2sm_poly(n_poly_t Ap, n_poly_t Am,
1495 const n_bpoly_t A, n_poly_t alphapow, nmod_t mod);
1496
1497 FLINT_DLL void n_bpoly_mod_interp_lift_2sm_poly(slong * deg1, n_bpoly_t T,
1498 const n_poly_t A, const n_poly_t B, mp_limb_t alpha, nmod_t mod);
1499
1500 FLINT_DLL int n_bpoly_mod_interp_crt_2sm_poly(slong * deg1, n_bpoly_t F,
1501 n_bpoly_t T, n_poly_t A, n_poly_t B, const n_poly_t modulus,
1502 n_poly_t alphapow, nmod_t mod);
1503
1504 FLINT_DLL int n_bpoly_mod_gcd_brown_smprime(n_bpoly_t G, n_bpoly_t Abar,
1505 n_bpoly_t Bbar, n_bpoly_t A, n_bpoly_t B,
1506 nmod_t ctx, n_poly_bpoly_stack_t Sp);
1507
1508 FLINT_DLL int n_polyu1n_mod_gcd_brown_smprime(n_polyun_t G, n_polyun_t Abar,
1509 n_polyun_t Bbar,n_polyun_t A, n_polyun_t B,
1510 nmod_t ctx, n_poly_polyun_stack_t St);
1511
1512 /*****************************************************************************/
1513
1514 FLINT_DLL int n_fq_bpoly_equal(
1515 const n_bpoly_t A,
1516 const n_bpoly_t B,
1517 const fq_nmod_ctx_t ctx);
1518
1519 FLINT_DLL void n_fq_bpoly_get_coeff_n_fq(
1520 mp_limb_t * c,
1521 const n_bpoly_t A,
1522 slong e0,
1523 slong e1,
1524 const fq_nmod_ctx_t ctx);
1525
1526 FLINT_DLL void n_fq_bpoly_set_coeff_n_fq(
1527 n_fq_bpoly_t A,
1528 slong e0,
1529 slong e1,
1530 const mp_limb_t * c,
1531 const fq_nmod_ctx_t ctx);
1532
1533 FLINT_DLL void n_fq_bpoly_get_coeff_fq_nmod(
1534 fq_nmod_t c,
1535 const n_bpoly_t A,
1536 slong e0,
1537 slong e1,
1538 const fq_nmod_ctx_t ctx);
1539
1540 FLINT_DLL void n_fq_bpoly_set_fq_nmod_poly_gen0(
1541 n_bpoly_t A,
1542 const fq_nmod_poly_t B,
1543 const fq_nmod_ctx_t ctx);
1544
1545 FLINT_DLL void n_fq_bpoly_set_n_fq_poly_gen0(
1546 n_bpoly_t A,
1547 const n_poly_t B,
1548 const fq_nmod_ctx_t ctx);
1549
1550 FLINT_DLL void n_fq_bpoly_set_n_fq_poly_gen1(
1551 n_bpoly_t A,
1552 const n_poly_t B,
1553 const fq_nmod_ctx_t ctx);
1554
1555 FLINT_DLL void n_fq_bpoly_derivative_gen0(
1556 n_bpoly_t A,
1557 const n_bpoly_t B,
1558 const fq_nmod_ctx_t ctx);
1559
1560 FLINT_DLL void n_fq_bpoly_scalar_mul_n_fq(
1561 n_fq_bpoly_t A,
1562 const mp_limb_t * c,
1563 const fq_nmod_ctx_t ctx);
1564
1565 FLINT_DLL void n_fq_bpoly_taylor_shift_gen1_fq_nmod(
1566 n_bpoly_t A,
1567 const n_bpoly_t B,
1568 const fq_nmod_t c_,
1569 const fq_nmod_ctx_t ctx);
1570
1571 FLINT_DLL void n_fq_bpoly_taylor_shift_gen0_fq_nmod(
1572 n_bpoly_t A,
1573 const fq_nmod_t alpha,
1574 const fq_nmod_ctx_t ctx);
1575
1576 FLINT_DLL void n_fq_bpoly_taylor_shift_gen0_n_fq(
1577 n_fq_bpoly_t A,
1578 const mp_limb_t * alpha,
1579 const fq_nmod_ctx_t ctx);
1580
1581 FLINT_DLL int n_fq_bpoly_gcd_brown_smprime(
1582 n_fq_bpoly_t G,
1583 n_fq_bpoly_t Abar,
1584 n_fq_bpoly_t Bbar,
1585 n_fq_bpoly_t A,
1586 n_fq_bpoly_t B,
1587 const fq_nmod_ctx_t ctx,
1588 n_poly_bpoly_stack_t Sp);
1589
1590 FLINT_DLL void n_fq_bpoly_print_pretty(
1591 const n_fq_bpoly_t A,
1592 const char * xvar,
1593 const char * yvar,
1594 const fq_nmod_ctx_t ctx);
1595
1596 FLINT_DLL void n_fq_bpoly_one(n_fq_bpoly_t A, const fq_nmod_ctx_t ctx);
1597
1598 FLINT_DLL void n_fq_bpoly_set(n_fq_bpoly_t A, const n_fq_bpoly_t B, const fq_nmod_ctx_t ctx);
1599
1600 FLINT_DLL int n_fq_bpoly_is_canonical(const n_fq_bpoly_t A, const fq_nmod_ctx_t ctx);
1601
1602
1603 /*****************************************************************************/
1604
1605 N_POLY_INLINE
n_tpoly_init(n_tpoly_t A)1606 void n_tpoly_init(n_tpoly_t A)
1607 {
1608 A->coeffs = NULL;
1609 A->alloc = 0;
1610 A->length = 0;
1611 }
1612
1613 N_POLY_INLINE
n_tpoly_swap(n_tpoly_t A,n_tpoly_t B)1614 void n_tpoly_swap(n_tpoly_t A, n_tpoly_t B)
1615 {
1616 n_tpoly_struct t = *A;
1617 *A = *B;
1618 *B = t;
1619 }
1620
1621 FLINT_DLL void n_tpoly_fit_length(n_tpoly_t A, slong len);
1622
1623 FLINT_DLL void n_tpoly_clear(n_tpoly_t A);
1624
1625 /*****************************************************************************/
1626
1627 N_POLY_INLINE
n_polyu_init(n_polyu_t A)1628 void n_polyu_init(n_polyu_t A)
1629 {
1630 A->coeffs = NULL;
1631 A->exps = NULL;
1632 A->length = 0;
1633 A->alloc = 0;
1634 }
1635
1636 FLINT_DLL void n_polyu_clear(n_polyu_t A);
1637
1638 FLINT_DLL void n_polyu_realloc(n_polyu_t A, slong len);
1639
1640 N_POLY_INLINE
n_polyu_fit_length(n_polyu_t A,slong len)1641 void n_polyu_fit_length(n_polyu_t A, slong len)
1642 {
1643 FLINT_ASSERT(A->alloc >= 0);
1644 if (len > A->alloc)
1645 n_polyu_realloc(A, len);
1646 }
1647
1648 N_POLY_INLINE
n_polyu_swap(n_polyu_t A,n_polyu_t B)1649 void n_polyu_swap(n_polyu_t A, n_polyu_t B)
1650 {
1651 n_polyu_struct T = *B;
1652 *B = *A;
1653 *A = T;
1654 }
1655
1656 FLINT_DLL void n_polyu3_print_pretty(const n_polyu_t A, const char * gen0,
1657 const char * gen1, const char * var2);
1658
1659 FLINT_DLL void n_polyu3_degrees(slong * deg0, slong * deg1, slong * deg2,
1660 const n_polyu_t A);
1661
1662 /*****************************************************************************/
1663
1664 FLINT_DLL void nmod_pow_cache_start(mp_limb_t b, n_poly_t pos_direct, n_poly_t pos_bin,
1665 n_poly_t neg_direct);
1666
1667 FLINT_DLL mp_limb_t nmod_pow_cache_mulpow_ui(mp_limb_t a, ulong e, n_poly_t pos_direct,
1668 n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1669
1670 FLINT_DLL mp_limb_t nmod_pow_cache_mulpow_neg_ui(mp_limb_t a, ulong e, n_poly_t pos_direct,
1671 n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1672
1673 FLINT_DLL mp_limb_t nmod_pow_cache_mulpow_fmpz(mp_limb_t a, const fmpz_t e, n_poly_t pos_direct,
1674 n_poly_t pos_bin, n_poly_t neg_direct, nmod_t ctx);
1675
1676 FLINT_DLL void n_fq_pow_cache_start_n_fq(
1677 const mp_limb_t * b,
1678 n_poly_t pos_direct,
1679 n_poly_t pos_bin,
1680 n_poly_t neg_direct,
1681 const fq_nmod_ctx_t ctx);
1682
1683 FLINT_DLL void n_fq_pow_cache_start_fq_nmod(
1684 const fq_nmod_t b,
1685 n_poly_t pos_direct,
1686 n_poly_t pos_bin,
1687 n_poly_t neg_direct,
1688 const fq_nmod_ctx_t ctx);
1689
1690 FLINT_DLL void n_fq_pow_cache_mulpow_ui(
1691 mp_limb_t * r,
1692 const mp_limb_t * a,
1693 ulong e,
1694 n_poly_t pos_direct,
1695 n_poly_t pos_bin,
1696 n_poly_t neg_direct,
1697 const fq_nmod_ctx_t ctx);
1698
1699 FLINT_DLL void n_fq_pow_cache_mulpow_neg_ui(
1700 mp_limb_t * r,
1701 const mp_limb_t * a,
1702 ulong e,
1703 n_poly_t pos_direct,
1704 n_poly_t pos_bin,
1705 n_poly_t neg_direct,
1706 const fq_nmod_ctx_t ctx);
1707
1708 FLINT_DLL void n_fq_pow_cache_mulpow_fmpz(
1709 mp_limb_t * r,
1710 const mp_limb_t * a,
1711 const fmpz_t e,
1712 n_poly_t pos_direct,
1713 n_poly_t pos_bin,
1714 n_poly_t neg_direct,
1715 const fq_nmod_ctx_t ctx);
1716
1717 /*****************************************************************************/
1718
1719 typedef struct {
1720 mp_limb_t * M;
1721 mp_limb_t * T;
1722 mp_limb_t * Q;
1723 mp_limb_t * array;
1724 slong alloc;
1725 slong d;
1726 slong radix;
1727 mp_limb_t w;
1728 } nmod_eval_interp_struct;
1729
1730 typedef nmod_eval_interp_struct nmod_eval_interp_t[1];
1731
1732
1733 FLINT_DLL void nmod_eval_interp_init(nmod_eval_interp_t E);
1734
1735 FLINT_DLL void nmod_eval_interp_clear(nmod_eval_interp_t E);
1736
1737 FLINT_DLL int nmod_eval_interp_set_degree_modulus(
1738 nmod_eval_interp_t E,
1739 slong deg,
1740 nmod_t ctx);
1741
nmod_eval_interp_eval_length(nmod_eval_interp_t E)1742 N_POLY_INLINE slong nmod_eval_interp_eval_length(nmod_eval_interp_t E)
1743 {
1744 return 1 + E->radix*E->d;
1745 }
1746
1747 FLINT_DLL void nmod_eval_interp_to_coeffs_poly(
1748 n_poly_t a,
1749 const n_poly_t v,
1750 nmod_eval_interp_t E,
1751 nmod_t ctx);
1752
1753 FLINT_DLL void nmod_eval_interp_from_coeffs_poly(
1754 n_poly_t v,
1755 const n_poly_t a,
1756 nmod_eval_interp_t E,
1757 nmod_t ctx);
1758
1759 FLINT_DLL void nmod_eval_interp_to_coeffs_n_fq_poly(
1760 n_fq_poly_t a,
1761 const n_fq_poly_t v,
1762 nmod_eval_interp_t E,
1763 const fq_nmod_ctx_t ctx);
1764
1765 FLINT_DLL void nmod_eval_interp_from_coeffs_n_fq_poly(
1766 n_fq_poly_t v,
1767 const n_fq_poly_t a,
1768 nmod_eval_interp_t E,
1769 const fq_nmod_ctx_t ctx);
1770
1771
nmod_evals_zero(n_poly_t a)1772 N_POLY_INLINE void nmod_evals_zero(n_poly_t a)
1773 {
1774 a->length = 0;
1775 }
1776
1777 FLINT_DLL void nmod_evals_add_inplace(n_poly_t a, n_poly_t b, slong len,
1778 nmod_t ctx);
1779
1780 FLINT_DLL void nmod_evals_mul(n_poly_t a, n_poly_t b, n_poly_t c, slong len,
1781 nmod_t ctx);
1782
1783 FLINT_DLL void nmod_evals_addmul(n_poly_t a, n_poly_t b, n_poly_t c, slong len,
1784 nmod_t ctx);
1785
1786 FLINT_DLL void nmod_evals_fmma(n_poly_t a, n_poly_t b, n_poly_t c,
1787 n_poly_t d, n_poly_t e, slong len, nmod_t ctx);
1788
n_fq_evals_zero(n_fq_poly_t a)1789 N_POLY_INLINE void n_fq_evals_zero(n_fq_poly_t a)
1790 {
1791 a->length = 0;
1792 }
1793
1794 FLINT_DLL void n_fq_evals_add_inplace(n_fq_poly_t a, n_fq_poly_t b,
1795 slong len, const fq_nmod_ctx_t ctx);
1796
1797 FLINT_DLL void n_fq_evals_mul(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c,
1798 slong len, const fq_nmod_ctx_t ctx);
1799
1800 FLINT_DLL void n_fq_evals_addmul(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c,
1801 slong len, const fq_nmod_ctx_t ctx);
1802
1803 FLINT_DLL void n_fq_evals_fmma(n_fq_poly_t a, n_fq_poly_t b, n_fq_poly_t c,
1804 n_fq_poly_t f, n_fq_poly_t e, slong len, const fq_nmod_ctx_t ctx);
1805
1806 /*****************************************************************************/
1807
1808 N_POLY_INLINE
n_polyun_init(n_polyun_t A)1809 void n_polyun_init(n_polyun_t A)
1810 {
1811 A->coeffs = NULL;
1812 A->exps = NULL;
1813 A->length = 0;
1814 A->alloc = 0;
1815 }
1816
1817 FLINT_DLL int n_polyun_is_canonical(const n_polyun_t A);
1818
1819 FLINT_DLL void n_polyun_clear(n_polyun_t A);
1820
1821 FLINT_DLL void n_polyun_realloc(n_polyun_t A, slong len);
1822
1823 N_POLY_INLINE
n_polyun_fit_length(n_polyun_t A,slong len)1824 void n_polyun_fit_length(n_polyun_t A, slong len)
1825 {
1826 if (len > A->alloc)
1827 n_polyun_realloc(A, len);
1828 }
1829
1830 FLINT_DLL int n_polyun_mod_is_canonical(const n_polyun_t A, nmod_t mod);
1831
1832 N_POLY_INLINE
n_polyun_swap(n_polyun_t A,n_polyun_t B)1833 void n_polyun_swap(n_polyun_t A, n_polyun_t B)
1834 {
1835 n_polyun_struct t = *B;
1836 *B = *A;
1837 *A = t;
1838 }
1839
1840 FLINT_DLL void n_polyun_set(n_polyun_t A, const n_polyun_t B);
1841
1842 FLINT_DLL void n_polyu1n_print_pretty(const n_polyun_t A,
1843 const char * var0, const char * varlast);
1844
1845 FLINT_DLL void n_polyu2n_print_pretty(const n_polyun_t A, const char * gen0,
1846 const char * gen1, const char * varlast);
1847
1848 FLINT_DLL void n_polyu3n_print_pretty(const n_polyun_t A, const char * gen0,
1849 const char * gen1, const char * var2, const char * varlast);
1850
1851 FLINT_DLL void n_fq_polyun_set(n_fq_polyun_t A, const n_fq_polyun_t B,
1852 const fq_nmod_ctx_t ctx);
1853
1854
1855 FLINT_DLL int n_polyun_equal(const n_polyun_t A, const n_polyun_t B);
1856
1857 N_POLY_INLINE
n_polyun_one(n_polyun_t A)1858 void n_polyun_one(n_polyun_t A)
1859 {
1860 n_polyun_fit_length(A, 1);
1861 A->length = 1;
1862 A->exps[0] = 0;
1863 n_poly_one(A->coeffs + 0);
1864 }
1865
1866 N_POLY_INLINE
n_polyu1n_bidegree(n_polyun_t A)1867 ulong n_polyu1n_bidegree(n_polyun_t A)
1868 {
1869 ulong x = A->exps[0];
1870 ulong y = A->coeffs[0].length - 1;
1871 return (x << (FLINT_BITS/2)) + y;
1872 }
1873
1874 /*****************************************************************************/
1875
1876 FLINT_DLL void n_fq_poly_product_roots_n_fq(n_poly_t M, const mp_limb_t * H,
1877 slong length, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
1878
1879 FLINT_DLL slong n_polyun_product_roots(n_polyun_t M, const n_polyun_t H,
1880 nmod_t ctx);
1881
1882 FLINT_DLL slong n_fq_polyun_product_roots(n_fq_polyun_t M,
1883 const n_fq_polyun_t H, const fq_nmod_ctx_t ctx, n_poly_stack_t St);
1884
1885 FLINT_DLL mp_limb_t _nmod_zip_eval_step(mp_limb_t * cur,
1886 const mp_limb_t * inc, const mp_limb_t * coeffs,
1887 slong length, nmod_t ctx);
1888
1889 FLINT_DLL void _n_fq_zip_eval_step(mp_limb_t * res, mp_limb_t * cur,
1890 const mp_limb_t * inc, const mp_limb_t * coeffs,
1891 slong length, const fq_nmod_ctx_t ctx);
1892
1893 FLINT_DLL void _n_fqp_zip_eval_step(mp_limb_t * res, mp_limb_t * cur,
1894 const mp_limb_t * inc, const mp_limb_t * coeffs,
1895 slong length, slong d, nmod_t mod);
1896
1897 FLINT_DLL int _nmod_zip_vand_solve(mp_limb_t * coeffs,
1898 const mp_limb_t * monomials, slong mlength,
1899 const mp_limb_t * evals, slong elength,
1900 const mp_limb_t * master, mp_limb_t * scratch, nmod_t ctx);
1901
1902 FLINT_DLL int _n_fq_zip_vand_solve(mp_limb_t * coeffs,
1903 const mp_limb_t * monomials, slong mlength,
1904 const mp_limb_t * evals, slong elength,
1905 const mp_limb_t * master, mp_limb_t * scratch,
1906 const fq_nmod_ctx_t ctx);
1907
1908 FLINT_DLL int _n_fqp_zip_vand_solve(mp_limb_t * coeffs,
1909 const mp_limb_t * monomials, slong mlength,
1910 const mp_limb_t * evals, slong elength,
1911 const mp_limb_t * master, mp_limb_t * scratch,
1912 const fq_nmod_ctx_t ctx);
1913
1914 /*****************************************************************************/
1915
1916 FLINT_DLL void n_poly_stack_init(n_poly_stack_t S);
1917
1918 FLINT_DLL void n_poly_stack_clear(n_poly_stack_t S);
1919
1920 FLINT_DLL n_poly_struct ** n_poly_stack_fit_request(n_poly_stack_t S, slong k);
1921
1922 N_POLY_INLINE
n_poly_stack_vec_init(n_poly_stack_t S,slong len)1923 mp_limb_t * n_poly_stack_vec_init(n_poly_stack_t S, slong len)
1924 {
1925 n_poly_struct * poly_top;
1926 poly_top = n_poly_stack_fit_request(S, 1)[0];
1927 S->top += 1;
1928 n_poly_fit_length(poly_top, len);
1929 return poly_top->coeffs;
1930 }
1931
1932 N_POLY_INLINE
n_poly_stack_vec_clear(n_poly_stack_t S)1933 void n_poly_stack_vec_clear(n_poly_stack_t S)
1934 {
1935 FLINT_ASSERT(S->top >= 1);
1936 S->top -= 1;
1937 }
1938
1939 N_POLY_INLINE
n_poly_stack_request(n_poly_stack_t S,slong k)1940 n_poly_struct ** n_poly_stack_request(n_poly_stack_t S, slong k)
1941 {
1942 n_poly_struct ** poly_top;
1943 poly_top = n_poly_stack_fit_request(S, k);
1944 S->top += k;
1945 return poly_top;
1946 }
1947
1948 N_POLY_INLINE
n_poly_stack_take_top(n_poly_stack_t S)1949 n_poly_struct * n_poly_stack_take_top(n_poly_stack_t S)
1950 {
1951 /* assume the request for 1 has already been fitted */
1952 n_poly_struct ** poly_top;
1953 FLINT_ASSERT(S->top + 1 <= S->alloc);
1954 poly_top = S->array + S->top;
1955 S->top += 1;
1956 return poly_top[0];
1957 }
1958
1959 N_POLY_INLINE
n_poly_stack_give_back(n_poly_stack_t S,slong k)1960 void n_poly_stack_give_back(n_poly_stack_t S, slong k)
1961 {
1962 FLINT_ASSERT(S->top >= k);
1963 S->top -= k;
1964 }
1965
1966 N_POLY_INLINE
n_poly_stack_size(const n_poly_stack_t S)1967 slong n_poly_stack_size(const n_poly_stack_t S)
1968 {
1969 return S->top;
1970 }
1971
1972 /*****************************************************************************/
1973
1974 FLINT_DLL void n_bpoly_stack_init(n_bpoly_stack_t S);
1975
1976 FLINT_DLL void n_bpoly_stack_clear(n_bpoly_stack_t S);
1977
1978 FLINT_DLL n_bpoly_struct ** n_bpoly_stack_fit_request(n_bpoly_stack_t S, slong k);
1979
1980 N_POLY_INLINE
n_bpoly_stack_request(n_bpoly_stack_t S,slong k)1981 n_bpoly_struct ** n_bpoly_stack_request(n_bpoly_stack_t S, slong k)
1982 {
1983 n_bpoly_struct ** bpoly_top;
1984 bpoly_top = n_bpoly_stack_fit_request(S, k);
1985 S->top += k;
1986 return bpoly_top;
1987 }
1988
1989 N_POLY_INLINE
n_bpoly_stack_take_top(n_bpoly_stack_t S)1990 n_bpoly_struct * n_bpoly_stack_take_top(n_bpoly_stack_t S)
1991 {
1992 /* assume the request for 1 has already been fitted */
1993 n_bpoly_struct ** bpoly_top;
1994 FLINT_ASSERT(S->top + 1 <= S->alloc);
1995 bpoly_top = S->array + S->top;
1996 S->top += 1;
1997 return bpoly_top[0];
1998 }
1999
2000 N_POLY_INLINE
n_bpoly_stack_give_back(n_bpoly_stack_t S,slong k)2001 void n_bpoly_stack_give_back(n_bpoly_stack_t S, slong k)
2002 {
2003 FLINT_ASSERT(S->top >= k);
2004 S->top -= k;
2005 }
2006
2007 N_POLY_INLINE
n_bpoly_stack_size(const n_bpoly_stack_t S)2008 slong n_bpoly_stack_size(const n_bpoly_stack_t S)
2009 {
2010 return S->top;
2011 }
2012
2013 /*****************************************************************************/
2014
2015 FLINT_DLL void n_polyun_stack_init(n_polyun_stack_t S);
2016
2017 FLINT_DLL void n_polyun_stack_clear(n_polyun_stack_t S);
2018
2019 FLINT_DLL n_polyun_struct ** n_polyun_stack_fit_request(n_polyun_stack_t S, slong k);
2020
2021 N_POLY_INLINE
n_polyun_stack_request(n_polyun_stack_t S,slong k)2022 n_polyun_struct ** n_polyun_stack_request(n_polyun_stack_t S, slong k)
2023 {
2024 n_polyun_struct ** polyun_top;
2025 polyun_top = n_polyun_stack_fit_request(S, k);
2026 S->top += k;
2027 return polyun_top;
2028 }
2029
2030 N_POLY_INLINE
n_polyun_stack_take_top(n_polyun_stack_t S)2031 n_polyun_struct * n_polyun_stack_take_top(n_polyun_stack_t S)
2032 {
2033 /* assume the request for 1 has already been fitted */
2034 n_polyun_struct ** polyun_top;
2035 FLINT_ASSERT(S->top + 1 <= S->alloc);
2036 polyun_top = S->array + S->top;
2037 S->top += 1;
2038 return polyun_top[0];
2039 }
2040
2041 N_POLY_INLINE
n_polyun_stack_give_back(n_polyun_stack_t S,slong k)2042 void n_polyun_stack_give_back(n_polyun_stack_t S, slong k)
2043 {
2044 FLINT_ASSERT(S->top >= k);
2045 S->top -= k;
2046 }
2047
2048 N_POLY_INLINE
n_polyun_stack_size(const n_polyun_stack_t S)2049 slong n_polyun_stack_size(const n_polyun_stack_t S)
2050 {
2051 return S->top;
2052 }
2053
2054
2055 #ifdef __cplusplus
2056 }
2057 #endif
2058
2059 #endif
2060
2061