1 /*
2 Copyright (C) 2013 Tom Bachmann
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 <http://www.gnu.org/licenses/>.
10 */
11
12 #include <iostream>
13 #include <sstream>
14 #include <string>
15
16 #include "fmpz_mod_polyxx.h"
17
18 #include "flintxx/test/helpers.h"
19
20 using namespace flint;
21
22 void
test_init()23 test_init()
24 {
25 fmpz_mod_polyxx p(fmpzxx(2003));
26 tassert(p.length() == 0);
27 tassert(p.modulus() == 2003);
28 tassert(fmpz_mod_polyxx::zero(fmpzxx(2003)).is_zero());
29 }
30
31 void
test_manipulation()32 test_manipulation()
33 {
34 fmpzxx M(1031);
35 fmpz_mod_polyxx p(M), q(M);
36 p.set_coeff(5, 17u + M);
37 tassert(p.degree() == 5);
38 q.set_coeff(5, fmpzxx(16) + fmpzxx(1));
39 tassert((q + fmpz_mod_polyxx(M)).get_coeff(5) == 17);
40 p.set_coeff(0, 1);
41 tassert(p != q);
42 p.set_coeff(0, 0);
43 tassert(p == q);
44
45 tassert((p + p).lead() == 2*p.lead());
46
47 q.lead() = 0;
48 q._normalise();
49 tassert(q.is_zero());
50
51 p.realloc(0);
52 tassert(p.is_zero());
53 }
54
55 void
test_assignment()56 test_assignment()
57 {
58 fmpzxx M(31);
59 fmpz_mod_polyxx p(M), q(M);
60 p.set_coeff(0, 1);
61 tassert(p != q);
62 p = q;
63 tassert(p == q);
64 }
65
66 void
test_conversion()67 test_conversion()
68 {
69 fmpzxx M(1031);
70 fmpz_mod_polyxx p(M);
71
72 p = 4u + 1031;
73 tassert(p.length() == 1 && p.get_coeff(0) == 4);
74
75 p = fmpzxx(5) + M;
76 tassert(p.length() == 1 && p.get_coeff(0) == 5);
77
78 frandxx rand;
79 fmpz_polyxx P = fmpz_polyxx::randtest(rand, 10, 20);
80 p = P;
81 for(slong i = 0;i < P.length();++i)
82 tassert(P.get_coeff(i) % M == p.get_coeff(i));
83 fmpz_polyxx Pp = p.to<fmpz_polyxx>();
84 for(slong i = 0;i < P.length();++i)
85 tassert(P.get_coeff(i) % M == Pp.get_coeff(i));
86 }
87
88 void
test_arithmetic()89 test_arithmetic()
90 {
91 fmpzxx M(1031);
92 fmpz_mod_polyxx g(M), h(M);
93 g.set_coeff(0, 17); h.set_coeff(0, 15u + M);
94 tassert((g + h).get_coeff(0) == 15 + 17);
95
96 frandxx state;
97 g.set_randtest(state, 10);
98 h.set_randtest(state, 10);
99
100 tassert(((-g) + g).is_zero());
101 tassert(g - h == g + (-h));
102
103 tassert(g*fmpzxx(3) == g + g + g);
104 tassert(g.make_monic() == g*g.lead().invmod(M));
105
106 fmpz_mod_polyxx f(M);f = 15u;
107 tassert(f*g == fmpzxx(15)*g);
108
109 f = h*g;f.truncate(7);
110 tassert(f == mullow(h, g, 7));
111
112 f = h / g;
113 tassert(f*g + (h % g) == h);
114 tassert(((h*g) % h).is_zero());
115
116 f.set_randtest(state, 10);
117 tassert(h.mulmod(g, f) == ((h*g) % f));
118
119 fmpz_mod_polyxx X(M);X.set_coeff(1, 1);
120 fmpz_mod_polyxx one(M);one.set_coeff(0, 1);
121 f = X*X + one;
122 fmpzxx x(7);
123 tassert(evaluate(f, x) == x*x + 1u);
124 tassert(f(x) == evaluate(f, x));
125
126 fmpz_mod_polyxx seven(M);
127 seven.set_coeff(0, x);
128 tassert(compose(f, seven).get_coeff(0) == f(x));
129 tassert(f(seven).length() == 1);
130 }
131
132 void
test_functions()133 test_functions()
134 {
135 fmpzxx M(1031);
136 fmpz_mod_polyxx g(M), res(M);
137
138 g.set_coeff(5, 15);
139
140 g.truncate(3);
141 tassert(g.is_zero());
142
143 g.set_coeff(15, 1);
144 fmpz_mod_polyxx one(M);one = 1u;
145 tassert(g.shift_right(15) == one);
146 tassert(g.shift_right(15).shift_left(15) == g);
147
148 frandxx rand;
149 g.set_randtest(rand, 15);
150 tassert(g.length() <= 15);
151 g.set_randtest_irreducible(rand, 15);
152 tassert(g.length() <= 15);
153 g.set_randtest_not_zero(rand, 15);
154 tassert(g.length() <= 15 && !g.is_zero());
155
156 g.set_coeff(15, 1);
157 g.zero_coeffs(14, 15);
158 tassert(g.get_coeff(14) == 0);
159
160
161 // multiplication, division, modulo tested in arithmetic
162
163 tassert(g.pow(3u) == g*g*g);
164
165 res = g.pow(15u);res.truncate(12);
166 tassert(res == g.pow_trunc(15u, 12));
167 tassert(res == g.pow_trunc_binexp(15u, 12));
168
169 fmpz_mod_polyxx f(M);f.set_randtest(rand, 10);
170 res = g.pow(10u) % f;
171 tassert(res == g.powmod_binexp(10u, f));
172 tassert(res == g.powmod_binexp(fmpzxx(10), f));
173
174 fmpz_mod_polyxx tmp(M);
175 ltupleref(res, tmp) = f.gcdinv(g);
176 tassert(res == gcd(f, g) && tmp*f % g == res);
177
178 g.set_randtest_irreducible(rand, 5);
179 tassert(f.invmod(g)*f % g == one);
180 assert_exception((f*g).invmod(g).evaluate());
181
182 res = g*f;
183 res.remove(f);
184 tassert(res == g);
185
186 fmpz_polyxx lift;
187 lift = "5 1 1 1 1 1";
188 res = lift;
189 tassert(res.derivative().to<fmpz_polyxx>().to_string() == "4 1 2 3 4");
190
191 tassert(f.divrem(g) == ltuple(f / g, f % g));
192 tassert(f.divrem_basecase(g) == f.divrem(g));
193 tassert(f.divrem_divconquer(g) == f.divrem(g));
194 tassert(f.divrem_f(g) == ltuple(1, f / g, f % g));
195
196 tassert(f.div_basecase(g) == f / g);
197 tassert(f.rem_basecase(g) == f % g);
198
199 f.set_coeff(0, 17);
200 res = f*f.inv_series_newton(15);res.truncate(15);
201 tassert(res == one);
202
203 tassert(f(g) == f.compose_divconquer(g));
204 tassert(f(g) == f.compose_horner(g));
205
206 fmpz_mod_polyxx h(M);
207 h.set_randtest(rand, 15);
208 tassert(f.compose_mod(g, h) == f(g) % h);
209 tassert(f.compose_mod(g, h) == f.compose_mod_horner(g, h));
210 tassert(f.compose_mod(g, h) == f.compose_mod_brent_kung(g, h));
211
212 h.set_randtest_irreducible(rand, 12);
213 tassert(h.gcd(f) == one);
214 tassert(f.gcd_euclidean(f) == f.make_monic());
215 tassert(f.gcd_f(g) == ltuple(1, f.gcd(g)));
216 tassert(f.gcd_euclidean_f(g) == ltuple(1, f.gcd(g)));
217
218 fmpz_mod_polyxx R(M), S(M);
219 ltupleref(res, R, S) = f.xgcd(g);
220 tassert(res == R*f + S*g && res == gcd(f, g));
221 tassert(f.xgcd(g) == f.xgcd_euclidean(g));
222
223 }
224
equiv_fac(const fmpz_mod_poly_factorxx & fac1,const fmpz_mod_poly_factorxx & fac2)225 bool equiv_fac(const fmpz_mod_poly_factorxx& fac1,
226 const fmpz_mod_poly_factorxx& fac2)
227 {
228 tassert(fac1.size() == 2);
229 if(fac1.exp(0) == fac1.exp(1))
230 {
231 if(fac2.exp(0) != fac1.exp(0) || fac2.exp(1) != fac1.exp(0))
232 return false;
233 return (fac1.p(0) == fac2.p(0) && fac1.p(1) == fac2.p(1))
234 || (fac1.p(1) == fac2.p(0) && fac1.p(0) == fac2.p(1));
235 }
236 if(fac1.size() != fac2.size())
237 return false;
238 if(fac1.exp(0) == fac2.exp(0))
239 return fac1.exp(1) == fac2.exp(1)
240 && fac1.p(0) == fac2.p(0)
241 && fac1.p(1) == fac2.p(1);
242 else
243 return fac1.exp(0) == fac2.exp(1)
244 && fac1.exp(1) == fac2.exp(0)
245 && fac1.p(0) == fac2.p(1)
246 && fac1.p(1) == fac2.p(0);
247 }
248 void
test_factoring()249 test_factoring()
250 {
251 fmpzxx M(1031);
252 fmpz_mod_polyxx f(M), g(M);
253 frandxx state;
254 f.set_randtest_irreducible(state, 4); f = f.make_monic();
255 g.set_randtest_irreducible(state, 5); g = g.make_monic();
256
257 fmpz_mod_poly_factorxx fac = factor(f*f*g);
258 tassert(fac.size() == 2);
259 if(fac.exp(0) == 1)
260 {
261 tassert(fac.p(0) == g);
262 tassert(fac.p(1) == f && fac.exp(1) == 2);
263 }
264 else
265 {
266 tassert(fac.p(0) == f && fac.exp(0) == 2);
267 tassert(fac.p(1) == g && fac.exp(1) == 1);
268 }
269
270 fmpz_mod_poly_factorxx fac2;fac2 = fac;fac2.pow(2);
271 fac.insert(g, 1);
272 fac.insert(f, 2);
273 tassert(fac == fac2);
274
275 fmpz_mod_polyxx prod(f*f*f*g*g);
276 fac = factor(prod);
277 tassert(equiv_fac(fac, factor_cantor_zassenhaus(prod)));
278 tassert(equiv_fac(factor(f*g), factor_berlekamp(f*g)));
279 tassert(equiv_fac(fac, factor_kaltofen_shoup(prod)));
280
281 std::vector<slong> degs(2);
282 fac.realloc(0);fac.set_factor_distinct_deg(f*g, degs);
283 tassert(degs.size() == 2);
284 tassert((degs[0] == f.degree() && degs[1] == g.degree())
285 || (degs[1] == f.degree() && degs[0] == g.degree()));
286
287 tassert(f.is_irreducible() && f.is_irreducible_ddf()
288 && f.is_irreducible_rabin());
289 tassert(f.is_squarefree());
290 // TODO test set_factor_equal_deg*
291
292 if(0)
293 print(fac); // test this compiles
294 }
295
296 void
test_randomisation()297 test_randomisation()
298 {
299 frandxx state, state2;
300 fmpzxx M(1031);
301 fmpz_mod_polyxx p(M);
302
303 p.set_randtest(state, 10);
304 tassert(p == fmpz_mod_polyxx::randtest(M, state2, 10));
305 p.set_randtest_irreducible(state, 10);
306 tassert(p == fmpz_mod_polyxx::randtest_irreducible(M, state2, 10));
307 p.set_randtest_not_zero(state, 10);
308 tassert(p == fmpz_mod_polyxx::randtest_not_zero(M, state2, 10));
309 }
310
311 void
test_radix()312 test_radix()
313 {
314 fmpzxx M(1031);
315 fmpz_mod_poly_vecxx v1(10, M), v2(10, M);
316 v1[0].set_coeff(7, 1);
317 tassert(v1 != v2);
318 fmpz_mod_poly_vecxx v3(v1);
319 tassert(v3 == v1);
320 v3[0].set_coeff(1, 1);
321 tassert(v3 != v1);
322 v2[0].set_coeff(7, 1);
323 tassert(v1 == v2);
324
325 frandxx rand;
326 fmpz_mod_polyxx F = fmpz_mod_polyxx::randtest(M, rand, 10);
327 fmpz_mod_polyxx R = fmpz_mod_polyxx::randtest(M, rand, 3);
328 fmpz_mod_poly_vecxx b(F.degree() / R.degree() + 1, M);
329 fmpz_mod_poly_radixxx rad(R, 15);
330 b = F.radix(rad);
331 tassert(b == F.radix(rad));
332
333 fmpz_mod_polyxx f(M);
334 for(slong i = 0;i < b.size();++i)
335 f += b[i]*R.pow(static_cast<ulong>(i));
336 tassert(f == F);
337 }
338
339 void
test_printing()340 test_printing()
341 {
342 frandxx state;
343 fmpz_mod_polyxx f = fmpz_mod_polyxx::randtest(fmpzxx(7), state, 4);
344 test_print_read(f);
345 f.set_zero();
346 f.set_coeff(0, 3);
347 f.set_coeff(1, 1);
348 tassert_fprint_pretty(f, "x", "x+3");
349 }
350
351 void
test_unified_access()352 test_unified_access()
353 {
354 fmpz_mod_polyxx p(fmpzxx(1031));
355 p.set_coeff(0, 1);
356 const fmpz_mod_polyxx& q = p;
357 tassert(q.lead() == 1);
358 }
359
360 int
main()361 main()
362 {
363 std::cout << "fmpz_mod_polyxx....";
364
365 test_init();
366 test_manipulation();
367 test_assignment();
368 test_conversion();
369 test_arithmetic();
370 test_functions();
371 test_factoring();
372 test_randomisation();
373 test_radix();
374 test_printing();
375 test_unified_access();
376
377 std::cout << "PASS" << std::endl;
378 return 0;
379 }
380
381