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