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