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_f(fmpz_t f,fmpz * G,fmpz * S,const fmpz * A,slong lenA,const fmpz * B,slong lenB,const fmpz_t p)17 slong _fmpz_mod_poly_gcdinv_f(fmpz_t f, 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 = 0;
24
25 fmpz_init(inv);
26 fmpz_gcdinv(f, inv, A + (lenA - 1), p);
27
28 if (fmpz_is_one(f))
29 {
30 if (lenB < 16)
31 {
32 ans = _fmpz_mod_poly_gcdinv_euclidean_f(f, G, S,
33 A, lenA, B, lenB, inv, p);
34 } else
35 {
36 T = _fmpz_vec_init(lenA - 1);
37
38 ans = _fmpz_mod_poly_xgcd_f(f, G, T, S, B, lenB, A, lenA, inv, p);
39
40 _fmpz_vec_clear(T, lenA - 1);
41 }
42 }
43
44 fmpz_clear(inv);
45
46 return ans;
47 }
48
fmpz_mod_poly_gcdinv_f(fmpz_t f,fmpz_mod_poly_t G,fmpz_mod_poly_t S,const fmpz_mod_poly_t A,const fmpz_mod_poly_t B)49 void fmpz_mod_poly_gcdinv_f(fmpz_t f, fmpz_mod_poly_t G, fmpz_mod_poly_t S,
50 const fmpz_mod_poly_t A, const fmpz_mod_poly_t B)
51 {
52 const slong lenA = A->length, lenB = B->length;
53
54 if (lenB < 2)
55 {
56 flint_printf("Exception (fmpz_mod_poly_gcdinv). lenB < 2.\n");
57 flint_abort();
58 }
59 if (lenA >= lenB)
60 {
61 fmpz_mod_poly_t T;
62
63 fmpz_mod_poly_init(T, &A->p);
64 fmpz_mod_poly_rem_f(f, T, A, B);
65
66 if (fmpz_is_one(f))
67 fmpz_mod_poly_gcdinv_f(f, G, S, T, B);
68
69 fmpz_mod_poly_clear(T);
70
71 return;
72 }
73
74 if (lenA == 0)
75 {
76 fmpz_mod_poly_zero(G);
77 fmpz_mod_poly_zero(S);
78 fmpz_set_ui(f, 1);
79 }
80 else
81 {
82 fmpz *g, *s;
83 slong lenG;
84
85 if (G == A || G == B)
86 {
87 g = _fmpz_vec_init(lenA);
88 }
89 else
90 {
91 fmpz_mod_poly_fit_length(G, lenA);
92 g = G->coeffs;
93 }
94 if (S == A || S == B)
95 {
96 s = _fmpz_vec_init(lenB - 1);
97 }
98 else
99 {
100 fmpz_mod_poly_fit_length(S, lenB - 1);
101 s = S->coeffs;
102 }
103
104 lenG = _fmpz_mod_poly_gcdinv_f(f, g, s,
105 A->coeffs, lenA, B->coeffs, lenB, &A->p);
106
107 if (G == A || G == B)
108 {
109 _fmpz_vec_clear(G->coeffs, G->alloc);
110 G->coeffs = g;
111 G->alloc = lenA;
112 }
113 if (S == A || S == B)
114 {
115 _fmpz_vec_clear(S->coeffs, S->alloc);
116 S->coeffs = s;
117 S->alloc = lenB - 1;
118 }
119
120 if (fmpz_is_one(f))
121 {
122 _fmpz_mod_poly_set_length(G, lenG);
123 _fmpz_mod_poly_set_length(S, lenB - lenG);
124 _fmpz_mod_poly_normalise(S);
125
126 if (!fmpz_is_one(fmpz_mod_poly_lead(G)))
127 {
128 fmpz_t inv;
129
130 fmpz_init(inv);
131 fmpz_gcdinv(f, inv, fmpz_mod_poly_lead(G), &A->p);
132 fmpz_mod_poly_scalar_mul_fmpz(G, G, inv);
133 fmpz_mod_poly_scalar_mul_fmpz(S, S, inv);
134 fmpz_clear(inv);
135 }
136 }
137 }
138 }
139
140