1 /*
2 Copyright (C) 2011 Fredrik Johansson
3 Copyright (C) 2015 Kushagra Singh
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <gmp.h>
16 #include "flint.h"
17 #include "fmpz.h"
18 #include "fmpz_poly.h"
19 #include "fmpz_mod_poly.h"
20 #include "ulong_extras.h"
21
22 void
_fmpz_mod_poly_product_roots_fmpz_vec(fmpz * poly,const fmpz * xs,slong n,const fmpz_t mod)23 _fmpz_mod_poly_product_roots_fmpz_vec(fmpz * poly, const fmpz * xs, slong n, const fmpz_t mod)
24 {
25 if (n == 0)
26 {
27 if (fmpz_is_one(mod))
28 fmpz_zero(poly);
29 else
30 fmpz_one(poly);
31 }
32 else if (n < 20)
33 {
34 slong i, j;
35
36 if (fmpz_is_one(mod))
37 fmpz_zero(poly + n);
38 else
39 fmpz_one(poly + n);
40
41 fmpz_negmod(poly + n - 1, xs, mod);
42
43 for (i = 1; i < n; i++)
44 {
45 fmpz_mul(poly + n - i - 1, poly + n - i, xs + i);
46 fmpz_mod(poly + n - i - 1, poly + n - i - 1, mod);
47
48 fmpz_negmod(poly + n - i - 1, poly + n - i - 1, mod);
49
50 for (j = 0; j < i - 1; j++)
51 {
52 fmpz_submul(poly + n - i + j, poly + n - i + j + 1, xs + i);
53 fmpz_mod(poly + n - i + j, poly + n - i + j, mod);
54 }
55 fmpz_sub(poly + n - 1, poly + n - 1, xs + i);
56 fmpz_mod(poly + n - 1, poly + n - 1, mod);
57 }
58 }
59 else
60 {
61 slong m;
62 fmpz * tmp;
63
64 m = (n + 1) / 2;
65
66 tmp = _fmpz_vec_init(n + 2);
67
68 _fmpz_mod_poly_product_roots_fmpz_vec(tmp, xs, m, mod);
69 _fmpz_mod_poly_product_roots_fmpz_vec(tmp + m + 1, xs + m, n - m, mod);
70 _fmpz_mod_poly_mul(poly, tmp, m + 1, tmp + m + 1, n - m + 1, mod);
71
72 _fmpz_vec_clear(tmp, n + 2);
73 }
74 }
75
fmpz_mod_poly_product_roots_fmpz_vec(fmpz_mod_poly_t poly,const fmpz * xs,slong xlen,const fmpz_mod_ctx_t ctx)76 void fmpz_mod_poly_product_roots_fmpz_vec(
77 fmpz_mod_poly_t poly,
78 const fmpz * xs, slong xlen,
79 const fmpz_mod_ctx_t ctx)
80 {
81 fmpz_mod_poly_fit_length(poly, xlen + 1, ctx);
82 _fmpz_mod_poly_product_roots_fmpz_vec(poly->coeffs, xs, xlen, fmpz_mod_ctx_modulus(ctx));
83 _fmpz_mod_poly_set_length(poly, xlen + 1);
84 }
85