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 <https://www.gnu.org/licenses/>.
11 */
12
13 #include <stdlib.h>
14 #include "fmpz_mod_poly.h"
15
_fmpz_mod_poly_invmod_f(fmpz_t f,fmpz * A,const fmpz * B,slong lenB,const fmpz * P,slong lenP,const fmpz_t p)16 int _fmpz_mod_poly_invmod_f(fmpz_t f, fmpz *A,
17 const fmpz *B, slong lenB,
18 const fmpz *P, slong lenP, const fmpz_t p)
19 {
20 fmpz *G;
21 slong lenG;
22
23 FMPZ_VEC_NORM(B, lenB);
24
25 G = _fmpz_vec_init(lenB);
26
27 lenG = _fmpz_mod_poly_gcdinv_f(f, G, A, B, lenB, P, lenP, p);
28
29 if (fmpz_is_one(f) && lenG == 1 && !fmpz_is_one(G + 0))
30 {
31 fmpz_t invG;
32
33 fmpz_init(invG);
34 fmpz_gcdinv(f, invG, G + 0, p);
35 _fmpz_mod_poly_scalar_mul_fmpz(A, A, lenP - 1, invG, p);
36 fmpz_clear(invG);
37 }
38
39 _fmpz_vec_clear(G, lenB);
40
41 return (lenG == 1);
42 }
43
fmpz_mod_poly_invmod_f(fmpz_t f,fmpz_mod_poly_t A,const fmpz_mod_poly_t B,const fmpz_mod_poly_t P,const fmpz_mod_ctx_t ctx)44 int fmpz_mod_poly_invmod_f(fmpz_t f, fmpz_mod_poly_t A,
45 const fmpz_mod_poly_t B, const fmpz_mod_poly_t P,
46 const fmpz_mod_ctx_t ctx)
47 {
48 const slong lenB = B->length, lenP = P->length;
49 fmpz *t;
50 int ans;
51
52 if (lenP < 2)
53 {
54 flint_printf("Exception (fmpz_mod_poly_invmod). lenP < 2.\n");
55 flint_abort();
56 }
57 if (lenB == 0)
58 {
59 fmpz_mod_poly_zero(A, ctx);
60 fmpz_one(f);
61 return 0;
62 }
63 if (lenB >= lenP)
64 {
65 fmpz_mod_poly_t T;
66
67 fmpz_mod_poly_init(T, ctx);
68 fmpz_mod_poly_rem(T, B, P, ctx);
69 ans = fmpz_mod_poly_invmod_f(f, A, T, P, ctx);
70 fmpz_mod_poly_clear(T, ctx);
71 return ans;
72 }
73
74 if (A != B && A != P)
75 {
76 fmpz_mod_poly_fit_length(A, lenP - 1, ctx);
77 t = A->coeffs;
78 }
79 else
80 {
81 t = _fmpz_vec_init(lenP);
82 }
83
84 ans = _fmpz_mod_poly_invmod_f(f, t, B->coeffs, lenB,
85 P->coeffs, lenP, fmpz_mod_ctx_modulus(ctx));
86
87 if (A == B || A == P)
88 {
89 _fmpz_vec_clear(A->coeffs, A->alloc);
90 A->coeffs = t;
91 A->alloc = lenP - 1;
92 }
93
94 if (fmpz_is_one(f))
95 {
96 _fmpz_mod_poly_set_length(A, lenP - 1);
97 _fmpz_mod_poly_normalise(A);
98 }
99
100 return ans;
101 }
102
103