1 /*
2 Copyright (C) 2020 Daniel Schultz
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <https://www.gnu.org/licenses/>.
10 */
11
12 #include "fmpz_mod_mpoly_factor.h"
13
14 /* check total number of factors with multiplicity is between lower and upper */
check_omega(slong lower,slong upper,const fmpz_mod_mpoly_t p,const fmpz_mod_mpoly_ctx_t ctx)15 void check_omega(slong lower, slong upper, const fmpz_mod_mpoly_t p, const fmpz_mod_mpoly_ctx_t ctx)
16 {
17 slong i;
18 fmpz_mod_mpoly_t q;
19 fmpz_mod_mpoly_factor_t g, h;
20 fmpz_t omega;
21
22 fmpz_init(omega);
23 fmpz_mod_mpoly_factor_init(g, ctx);
24 fmpz_mod_mpoly_factor_init(h, ctx);
25 fmpz_mod_mpoly_init(q, ctx);
26
27 if (!fmpz_mod_mpoly_factor_zassenhaus(g, p, ctx))
28 {
29 flint_printf("FAIL:\ncheck factorization 1 could be computed\n");
30 flint_abort();
31 }
32
33 if (!fmpz_mod_mpoly_factor(h, p, ctx))
34 {
35 flint_printf("check factorization 2 could be computed\n");
36 flint_abort();
37 }
38
39 for (i = 0; i < g->num; i++)
40 {
41 if (g->poly[i].length < 1 || g->poly[i].coeffs[0] != 1)
42 {
43 flint_printf("FAIL:\nfactorization is not unit normal\n");
44 flint_abort();
45 }
46 }
47
48 fmpz_zero(omega);
49 for (i = 0; i < g->num; i++)
50 fmpz_add(omega, omega, g->exp + i);
51
52 if (fmpz_cmp_si(omega, lower) < 0 || fmpz_cmp_si(omega, upper) > 0)
53 {
54 flint_printf("FAIL:\nfactorization has wrong number of factors\n");
55 flint_abort();
56 }
57
58 fmpz_mod_mpoly_factor_expand(q, g, ctx);
59 if (!fmpz_mod_mpoly_equal(q, p, ctx))
60 {
61 flint_printf("FAIL:\nfactorization does not match original polynomial\n");
62 flint_abort();
63 }
64
65 fmpz_mod_mpoly_factor_sort(g, ctx);
66 fmpz_mod_mpoly_factor_sort(h, ctx);
67 if (fmpz_mod_mpoly_factor_cmp(g, h, ctx) != 0)
68 {
69 flint_printf("factorizations do not match\n");
70 flint_abort();
71 }
72
73 for (i = 0; i < g->num; i++)
74 {
75 fmpz_mod_mpoly_factor(h, g->poly + i, ctx);
76 if (h->num != 1 || !fmpz_is_one(h->exp + 0))
77 {
78 flint_printf("FAIL:\nfactor is reducible\n");
79 flint_abort();
80 }
81 }
82
83 fmpz_mod_mpoly_clear(q, ctx);
84 fmpz_mod_mpoly_factor_clear(g, ctx);
85 fmpz_mod_mpoly_factor_clear(h, ctx);
86 fmpz_clear(omega);
87 }
88
89
90 int
main(void)91 main(void)
92 {
93 slong i, j, tmul = 30;
94 FLINT_TEST_INIT(state);
95
96 flint_printf("factor_zassenhaus....");
97 fflush(stdout);
98
99 for (i = 0; i < tmul * flint_test_multiplier(); i++)
100 {
101 slong lower;
102 fmpz_mod_mpoly_ctx_t ctx;
103 fmpz_mod_mpoly_t a, t;
104 slong nfacs, len;
105 ulong expbound, powbound, pow;
106
107 fmpz_mod_mpoly_ctx_init_rand_bits_prime(ctx, state, 5, 200);
108
109 fmpz_mod_mpoly_init(a, ctx);
110 fmpz_mod_mpoly_init(t, ctx);
111
112 nfacs = 1 + (6 + n_randint(state, 6))/ctx->minfo->nvars;
113 powbound = 1 + n_randint(state, 3);
114 powbound = 1 + n_randint(state, powbound);
115 expbound = 3 + 15/nfacs/ctx->minfo->nvars/powbound;
116
117 lower = 0;
118 fmpz_mod_mpoly_one(a, ctx);
119 for (j = 0; j < nfacs; j++)
120 {
121 len = 1 + n_randint(state, 10/powbound);
122 fmpz_mod_mpoly_randtest_bound(t, state, len, expbound, ctx);
123 if (fmpz_mod_mpoly_is_zero(t, ctx))
124 fmpz_mod_mpoly_one(t, ctx);
125 pow = 1 + n_randint(state, powbound);
126 if (!fmpz_mod_mpoly_is_fmpz(t, ctx))
127 lower += pow;
128 fmpz_mod_mpoly_pow_ui(t, t, pow, ctx);
129 fmpz_mod_mpoly_mul(a, a, t, ctx);
130 }
131
132 check_omega(lower, WORD_MAX, a, ctx);
133
134 fmpz_mod_mpoly_clear(t, ctx);
135 fmpz_mod_mpoly_clear(a, ctx);
136 fmpz_mod_mpoly_ctx_clear(ctx);
137 }
138
139 FLINT_TEST_CLEANUP(state);
140
141 flint_printf("PASS\n");
142 return 0;
143 }
144