1 /*
2     Copyright (C) 2011 Fredrik Johansson
3     Copyright (C) 2012 Lina Kulakova
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 <http://www.gnu.org/licenses/>.
11 */
12 
13 #include <stdlib.h>
14 #include <gmp.h>
15 #include "flint.h"
16 #include "fmpz_vec.h"
17 #include "fmpz_mod_poly.h"
18 
_fmpz_mod_poly_mulmod(fmpz * res,const fmpz * poly1,slong len1,const fmpz * poly2,slong len2,const fmpz * f,slong lenf,const fmpz_t p)19 void _fmpz_mod_poly_mulmod(fmpz * res, const fmpz * poly1, slong len1,
20                            const fmpz * poly2, slong len2, const fmpz * f,
21                            slong lenf, const fmpz_t p)
22 {
23     fmpz * T, * Q;
24     fmpz_t invf;
25     slong lenT, lenQ;
26 
27     lenT = len1 + len2 - 1;
28     lenQ = lenT - lenf + 1;
29 
30     T = _fmpz_vec_init(lenT + lenQ);
31     Q = T + lenT;
32 
33     if (len1 >= len2)
34         _fmpz_mod_poly_mul(T, poly1, len1, poly2, len2, p);
35     else
36         _fmpz_mod_poly_mul(T, poly2, len2, poly1, len1, p);
37 
38     fmpz_init(invf);
39     fmpz_invmod(invf, f + lenf - 1, p);
40 
41     _fmpz_mod_poly_divrem(Q, res, T, lenT, f, lenf, invf, p);
42 
43     _fmpz_vec_clear(T, lenT + lenQ);
44     fmpz_clear(invf);
45 }
46 
47 void
fmpz_mod_poly_mulmod(fmpz_mod_poly_t res,const fmpz_mod_poly_t poly1,const fmpz_mod_poly_t poly2,const fmpz_mod_poly_t f)48 fmpz_mod_poly_mulmod(fmpz_mod_poly_t res, const fmpz_mod_poly_t poly1,
49                const fmpz_mod_poly_t poly2, const fmpz_mod_poly_t f)
50 {
51     slong len1, len2, lenf;
52     fmpz * fcoeffs;
53 
54     lenf = f->length;
55     len1 = poly1->length;
56     len2 = poly2->length;
57 
58     if (lenf == 0)
59     {
60         flint_printf("Exception (fmpz_mod_poly_mulmod). Divide by zero\n");
61         flint_abort();
62     }
63 
64     if (lenf == 1 || len1 == 0 || len2 == 0)
65     {
66         fmpz_mod_poly_zero(res);
67         return;
68     }
69 
70     if (len1 + len2 - lenf > 0)
71     {
72         if (f == res)
73         {
74             fcoeffs = _fmpz_vec_init(lenf);
75             _fmpz_vec_set(fcoeffs, f->coeffs, lenf);
76         }
77         else
78             fcoeffs = f->coeffs;
79 
80         fmpz_mod_poly_fit_length(res, len1 + len2 - 1);
81         _fmpz_mod_poly_mulmod(res->coeffs, poly1->coeffs, len1,
82                               poly2->coeffs, len2,
83                               fcoeffs, lenf,
84                               &res->p);
85         if (f == res)
86             _fmpz_vec_clear(fcoeffs, lenf);
87 
88         _fmpz_mod_poly_set_length(res, lenf - 1);
89         _fmpz_mod_poly_normalise(res);
90     }
91     else
92     {
93         fmpz_mod_poly_mul(res, poly1, poly2);
94     }
95 }
96