1 /*
2 Copyright (C) 2011 William Hart
3 Copyright (C) 2012 Sebastian Pancratz
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 "fmpz_vec.h"
15 #include "fmpz_mod_poly.h"
16
_fmpz_mod_poly_gcdinv(fmpz * G,fmpz * S,const fmpz * A,slong lenA,const fmpz * B,slong lenB,const fmpz_t p)17 slong _fmpz_mod_poly_gcdinv(fmpz *G, fmpz *S,
18 const fmpz *A, slong lenA, const fmpz *B, slong lenB,
19 const fmpz_t p)
20 {
21 fmpz *T;
22 fmpz_t inv;
23 slong ans;
24
25 fmpz_init(inv);
26 fmpz_invmod(inv, A + (lenA - 1), p);
27
28 if (lenB < 16)
29 {
30 ans = _fmpz_mod_poly_gcdinv_euclidean(G, S,
31 A, lenA, B, lenB, inv, p);
32 } else
33 {
34 T = _fmpz_vec_init(lenA - 1);
35
36 ans = _fmpz_mod_poly_xgcd(G, T, S, B, lenB, A, lenA, inv, p);
37
38 _fmpz_vec_clear(T, lenA - 1);
39 }
40
41 fmpz_clear(inv);
42
43 return ans;
44 }
45
fmpz_mod_poly_gcdinv(fmpz_mod_poly_t G,fmpz_mod_poly_t S,const fmpz_mod_poly_t A,const fmpz_mod_poly_t B)46 void fmpz_mod_poly_gcdinv(fmpz_mod_poly_t G, fmpz_mod_poly_t S,
47 const fmpz_mod_poly_t A, const fmpz_mod_poly_t B)
48 {
49 const slong lenA = A->length, lenB = B->length;
50
51 if (lenB < 2)
52 {
53 flint_printf("Exception (fmpz_mod_poly_gcdinv). lenB < 2.\n");
54 flint_abort();
55 }
56 if (lenA >= lenB)
57 {
58 fmpz_mod_poly_t T;
59
60 fmpz_mod_poly_init(T, &A->p);
61 fmpz_mod_poly_rem(T, A, B);
62 fmpz_mod_poly_gcdinv(G, S, T, B);
63 fmpz_mod_poly_clear(T);
64 return;
65 }
66
67 if (lenA == 0)
68 {
69 fmpz_mod_poly_zero(G);
70 fmpz_mod_poly_zero(S);
71 }
72 else
73 {
74 fmpz *g, *s;
75 slong lenG;
76
77 if (G == A || G == B)
78 {
79 g = _fmpz_vec_init(lenA);
80 }
81 else
82 {
83 fmpz_mod_poly_fit_length(G, lenA);
84 g = G->coeffs;
85 }
86 if (S == A || S == B)
87 {
88 s = _fmpz_vec_init(lenB - 1);
89 }
90 else
91 {
92 fmpz_mod_poly_fit_length(S, lenB - 1);
93 s = S->coeffs;
94 }
95
96 lenG = _fmpz_mod_poly_gcdinv(g, s,
97 A->coeffs, lenA, B->coeffs, lenB, &A->p);
98
99 if (G == A || G == B)
100 {
101 _fmpz_vec_clear(G->coeffs, G->alloc);
102 G->coeffs = g;
103 G->alloc = lenA;
104 }
105 if (S == A || S == B)
106 {
107 _fmpz_vec_clear(S->coeffs, S->alloc);
108 S->coeffs = s;
109 S->alloc = lenB - 1;
110 }
111
112 _fmpz_mod_poly_set_length(G, lenG);
113 _fmpz_mod_poly_set_length(S, lenB - lenG);
114 _fmpz_mod_poly_normalise(S);
115
116 if (!fmpz_is_one(fmpz_mod_poly_lead(G)))
117 {
118 fmpz_t inv;
119
120 fmpz_init(inv);
121 fmpz_invmod(inv, fmpz_mod_poly_lead(G), &A->p);
122 fmpz_mod_poly_scalar_mul_fmpz(G, G, inv);
123 fmpz_mod_poly_scalar_mul_fmpz(S, S, inv);
124 fmpz_clear(inv);
125 }
126 }
127 }
128
129