1 /*
2 Copyright (C) 2007 David Howden
3 Copyright (C) 2007, 2008, 2009, 2010 William Hart
4 Copyright (C) 2008 Richard Howell-Peak
5 Copyright (C) 2011 Fredrik Johansson
6 Copyright (C) 2012 Lina Kulakova
7
8 This file is part of FLINT.
9
10 FLINT is free software: you can redistribute it and/or modify it under
11 the terms of the GNU Lesser General Public License (LGPL) as published
12 by the Free Software Foundation; either version 2.1 of the License, or
13 (at your option) any later version. See <http://www.gnu.org/licenses/>.
14 */
15
16 #include "fmpz_mod_poly.h"
17 #include "ulong_extras.h"
18
19 int
fmpz_mod_poly_factor_equal_deg_prob(fmpz_mod_poly_t factor,flint_rand_t state,const fmpz_mod_poly_t pol,slong d)20 fmpz_mod_poly_factor_equal_deg_prob(fmpz_mod_poly_t factor,
21 flint_rand_t state,
22 const fmpz_mod_poly_t pol, slong d)
23 {
24 fmpz_mod_poly_t a, b, c, polinv;
25 fmpz_t exp, t, p;
26 int res = 1;
27 slong i;
28
29 if (pol->length <= 1)
30 {
31 flint_printf("Exception (fmpz_mod_poly_factor_equal_deg_prob): \n");
32 flint_printf("Input polynomial is linear.\n");
33 flint_abort();
34 }
35
36 fmpz_init_set(p, &pol->p);
37
38 fmpz_mod_poly_init(a, p);
39
40 do
41 {
42 fmpz_mod_poly_randtest(a, state, pol->length - 1);
43 } while (a->length <= 1);
44
45 fmpz_mod_poly_gcd(factor, a, pol);
46
47 if (factor->length != 1)
48 {
49 fmpz_mod_poly_clear(a);
50 return 1;
51 }
52
53 fmpz_mod_poly_init(b, p);
54 fmpz_mod_poly_init(polinv, p);
55
56 fmpz_mod_poly_reverse(polinv, pol, pol->length);
57 fmpz_mod_poly_inv_series_newton(polinv, polinv, polinv->length);
58
59 fmpz_init(exp);
60 if (fmpz_cmp_ui(p, 2) > 0)
61 {
62 /* compute a^{(p^d-1)/2} rem pol */
63 fmpz_pow_ui(exp, p, d);
64 fmpz_sub_ui(exp, exp, 1);
65 fmpz_fdiv_q_2exp(exp, exp, 1);
66
67 fmpz_mod_poly_powmod_fmpz_binexp_preinv(b, a, exp, pol, polinv);
68 }
69 else
70 {
71 /* compute b = (a^{2^{d-1}}+a^{2^{d-2}}+...+a^4+a^2+a) rem pol */
72 fmpz_mod_poly_rem(b, a, pol);
73 fmpz_mod_poly_init(c, p);
74 fmpz_mod_poly_set(c, b);
75 for (i = 1; i < d; i++)
76 {
77 /* c = a^{2^i} = (a^{2^{i-1}})^2 */
78 fmpz_mod_poly_powmod_ui_binexp_preinv(c, c, 2, pol, polinv);
79 fmpz_mod_poly_add(b, b, c);
80 }
81 fmpz_mod_poly_rem(b, b, pol);
82 fmpz_mod_poly_clear(c);
83 }
84 fmpz_clear(exp);
85
86 fmpz_init(t);
87 fmpz_sub_ui(t, &(b->coeffs[0]), 1);
88 fmpz_mod(t, t, p);
89 fmpz_mod_poly_set_coeff_fmpz(b, 0, t);
90 fmpz_clear(t);
91
92 fmpz_mod_poly_gcd(factor, b, pol);
93
94 if ((factor->length <= 1) || (factor->length == pol->length))
95 res = 0;
96
97 fmpz_mod_poly_clear(a);
98 fmpz_mod_poly_clear(b);
99 fmpz_mod_poly_clear(polinv);
100 fmpz_clear(p);
101
102 return res;
103 }
104