1 /*
2 Copyright (C) 2019 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 <http://www.gnu.org/licenses/>.
10 */
11
12 #include "fq_nmod_mpoly.h"
13
gcd_check(fq_nmod_mpoly_t g,fq_nmod_mpoly_t a,fq_nmod_mpoly_t b,const fq_nmod_mpoly_t gdiv,const fq_nmod_mpoly_ctx_t ctx,slong i,slong j,const char * name)14 void gcd_check(
15 fq_nmod_mpoly_t g,
16 fq_nmod_mpoly_t a,
17 fq_nmod_mpoly_t b,
18 const fq_nmod_mpoly_t gdiv,
19 const fq_nmod_mpoly_ctx_t ctx,
20 slong i,
21 slong j,
22 const char * name)
23 {
24 int res;
25 fq_nmod_mpoly_t ca, cb, cg;
26
27 fq_nmod_mpoly_init(ca, ctx);
28 fq_nmod_mpoly_init(cb, ctx);
29 fq_nmod_mpoly_init(cg, ctx);
30
31 res = fq_nmod_mpoly_gcd(g, a, b, ctx);
32 fq_nmod_mpoly_assert_canonical(g, ctx);
33
34 if (!res)
35 {
36 flint_printf("Check gcd can be computed\n"
37 "i = %wd, j = %wd, %s\n", i, j, name);
38 flint_abort();
39 }
40
41 if (!fq_nmod_mpoly_is_zero(gdiv, ctx))
42 {
43 if (!fq_nmod_mpoly_divides(ca, g, gdiv, ctx))
44 {
45 printf("FAIL\n");
46 flint_printf("Check divisor of gcd\n"
47 "i = %wd, j = %wd, %s\n", i, j, name);
48 flint_abort();
49 }
50 }
51
52 if (fq_nmod_mpoly_is_zero(g, ctx))
53 {
54 if (!fq_nmod_mpoly_is_zero(a, ctx) || !fq_nmod_mpoly_is_zero(b, ctx))
55 {
56 printf("FAIL\n");
57 flint_printf("Check zero gcd only results from zero inputs\n"
58 "i = %wd, j = %wd, %s\n", i, j, name);
59 flint_abort();
60 }
61 goto cleanup;
62 }
63
64 if (!fq_nmod_is_one(g->coeffs + 0, ctx->fqctx))
65 {
66 printf("FAIL\n");
67 flint_printf("Check gcd leading coefficient is one\n"
68 "i = %wd, j = %wd, %s\n", i, j, name);
69 flint_abort();
70 }
71
72 res = 1;
73 res = res && fq_nmod_mpoly_divides(ca, a, g, ctx);
74 res = res && fq_nmod_mpoly_divides(cb, b, g, ctx);
75 if (!res)
76 {
77 printf("FAIL\n");
78 flint_printf("Check divisibility\n"
79 "i = %wd, j = %wd, %s\n", i, j, name);
80 flint_abort();
81 }
82
83 res = fq_nmod_mpoly_gcd(cg, ca, cb, ctx);
84 fq_nmod_mpoly_assert_canonical(cg, ctx);
85
86 if (!res)
87 {
88 printf("FAIL\n");
89 flint_printf("Check gcd of cofactors can be computed\n"
90 "i = %wd, j = %wd, %s\n", i, j, name);
91 flint_abort();
92 }
93
94 if (!fq_nmod_mpoly_is_one(cg, ctx))
95 {
96 printf("FAIL\n");
97 flint_printf("Check gcd of cofactors is one\n"
98 "i = %wd, j = %wd, %s\n", i, j, name);
99 flint_abort();
100 }
101
102 cleanup:
103
104 fq_nmod_mpoly_clear(ca, ctx);
105 fq_nmod_mpoly_clear(cb, ctx);
106 fq_nmod_mpoly_clear(cg, ctx);
107 }
108
109 int
main(void)110 main(void)
111 {
112 slong i, j, k, tmul = 5;
113 FLINT_TEST_INIT(state);
114
115 flint_printf("gcd....");
116 fflush(stdout);
117
118 /* The gcd should always work when one input is a monomial */
119 for (i = 0; i < tmul * flint_test_multiplier(); i++)
120 {
121 fq_nmod_mpoly_ctx_t ctx;
122 fq_nmod_mpoly_t a, b, g, t;
123 slong len, len1, len2;
124 flint_bitcnt_t exp_bits, exp_bits1, exp_bits2;
125
126 fq_nmod_mpoly_ctx_init_rand(ctx, state, 10, FLINT_BITS, 5);
127
128 fq_nmod_mpoly_init(g, ctx);
129 fq_nmod_mpoly_init(a, ctx);
130 fq_nmod_mpoly_init(b, ctx);
131 fq_nmod_mpoly_init(t, ctx);
132
133 len = n_randint(state, 25);
134 len1 = n_randint(state, 50);
135 len2 = n_randint(state, 50);
136 if (n_randlimb(state) & UWORD(1))
137 len1 = FLINT_MIN(len1, WORD(1));
138 else
139 len2 = FLINT_MIN(len2, WORD(1));
140
141 exp_bits = n_randint(state, 70) + 2;
142 exp_bits1 = n_randint(state, 100) + 2;
143 exp_bits2 = n_randint(state, 100) + 2;
144
145 for (j = 0; j < 4; j++)
146 {
147 do {
148 fq_nmod_mpoly_randtest_bits(t, state, 1, exp_bits, ctx);
149 } while (t->length != 1);
150 fq_nmod_mpoly_randtest_bits(a, state, len1, exp_bits1, ctx);
151 fq_nmod_mpoly_randtest_bits(b, state, len2, exp_bits2, ctx);
152 fq_nmod_mpoly_mul(a, a, t, ctx);
153 fq_nmod_mpoly_mul(b, b, t, ctx);
154
155 fq_nmod_mpoly_randtest_bits(g, state, len, exp_bits, ctx);
156
157 gcd_check(g, a, b, t, ctx, i, j, "monomial");
158 }
159
160 fq_nmod_mpoly_clear(g, ctx);
161 fq_nmod_mpoly_clear(a, ctx);
162 fq_nmod_mpoly_clear(b, ctx);
163 fq_nmod_mpoly_clear(t, ctx);
164 fq_nmod_mpoly_ctx_clear(ctx);
165 }
166
167 /* The gcd should always work when both cofactors are monomials */
168 for (i = 0; i < tmul * flint_test_multiplier(); i++)
169 {
170 fq_nmod_mpoly_ctx_t ctx;
171 fq_nmod_mpoly_t a, b, g, t1, t2;
172 slong len, len1;
173 flint_bitcnt_t exp_bits, exp_bits1, exp_bits2;
174
175 fq_nmod_mpoly_ctx_init_rand(ctx, state, 10, FLINT_BITS, 5);
176
177 fq_nmod_mpoly_init(g, ctx);
178 fq_nmod_mpoly_init(a, ctx);
179 fq_nmod_mpoly_init(b, ctx);
180 fq_nmod_mpoly_init(t1, ctx);
181 fq_nmod_mpoly_init(t2, ctx);
182
183 len = n_randint(state, 25);
184 len1 = n_randint(state, 25);
185
186 exp_bits = n_randint(state, 70) + 2;
187 exp_bits1 = n_randint(state, 100) + 2;
188 exp_bits2 = n_randint(state, 100) + 2;
189
190 for (j = 0; j < 4; j++)
191 {
192 do {
193 fq_nmod_mpoly_randtest_bits(t1, state, 1, exp_bits1, ctx);
194 } while (t1->length != 1);
195 do {
196 fq_nmod_mpoly_randtest_bits(t2, state, 1, exp_bits2, ctx);
197 } while (t2->length != 1);
198 fq_nmod_mpoly_randtest_bits(a, state, len1, exp_bits, ctx);
199 fq_nmod_mpoly_mul(b, a, t1, ctx);
200 fq_nmod_mpoly_mul(t2, a, t2, ctx);
201
202 fq_nmod_mpoly_randtest_bits(g, state, len, exp_bits, ctx);
203
204 gcd_check(g, t2, b, a, ctx, i, j, "monomial cofactors");
205 }
206
207 fq_nmod_mpoly_clear(g, ctx);
208 fq_nmod_mpoly_clear(a, ctx);
209 fq_nmod_mpoly_clear(b, ctx);
210 fq_nmod_mpoly_clear(t1, ctx);
211 fq_nmod_mpoly_clear(t2, ctx);
212 fq_nmod_mpoly_ctx_clear(ctx);
213 }
214
215 /* sparse inputs */
216 for (i = 0; i < tmul * flint_test_multiplier(); i++)
217 {
218 fq_nmod_mpoly_ctx_t ctx;
219 fq_nmod_mpoly_t a, b, g, t;
220 slong len, len1, len2;
221 slong degbound;
222
223 fq_nmod_mpoly_ctx_init_rand(ctx, state, 5, FLINT_BITS, 4);
224 fq_nmod_mpoly_init(g, ctx);
225 fq_nmod_mpoly_init(a, ctx);
226 fq_nmod_mpoly_init(b, ctx);
227 fq_nmod_mpoly_init(t, ctx);
228
229 len = n_randint(state, 15) + 1;
230 len1 = n_randint(state, 20);
231 len2 = n_randint(state, 20);
232
233 degbound = 30/(2*ctx->minfo->nvars - 1);
234
235 for (j = 0; j < 4; j++)
236 {
237 do {
238 fq_nmod_mpoly_randtest_bound(t, state, len, degbound, ctx);
239 } while (t->length == 0);
240 fq_nmod_mpoly_randtest_bound(a, state, len1, degbound, ctx);
241 fq_nmod_mpoly_randtest_bound(b, state, len2, degbound, ctx);
242
243 fq_nmod_mpoly_mul(a, a, t, ctx);
244 fq_nmod_mpoly_mul(b, b, t, ctx);
245
246 fq_nmod_mpoly_randtest_bits(g, state, len, FLINT_BITS, ctx);
247
248 gcd_check(g, a, b, t, ctx, i, j, "sparse inputs");
249 }
250
251 fq_nmod_mpoly_clear(g, ctx);
252 fq_nmod_mpoly_clear(a, ctx);
253 fq_nmod_mpoly_clear(b, ctx);
254 fq_nmod_mpoly_clear(t, ctx);
255 fq_nmod_mpoly_ctx_clear(ctx);
256 }
257
258 /* sparse inputs with random repackings */
259 for (i = 0; i < tmul * flint_test_multiplier(); i++)
260 {
261 fq_nmod_mpoly_ctx_t ctx;
262 fq_nmod_mpoly_t a, b, g, t;
263 mp_limb_t rlimb;
264 flint_bitcnt_t newbits;
265 slong len, len1, len2;
266 slong degbound;
267
268 fq_nmod_mpoly_ctx_init_rand(ctx, state, 5, FLINT_BITS, 4);
269 fq_nmod_mpoly_init(g, ctx);
270 fq_nmod_mpoly_init(a, ctx);
271 fq_nmod_mpoly_init(b, ctx);
272 fq_nmod_mpoly_init(t, ctx);
273
274 len = n_randint(state, 15) + 1;
275 len1 = n_randint(state, 20);
276 len2 = n_randint(state, 20);
277
278 degbound = 30/(2*ctx->minfo->nvars - 1);
279
280 for (j = 0; j < 4; j++)
281 {
282 do {
283 fq_nmod_mpoly_randtest_bound(t, state, len, degbound, ctx);
284 } while (t->length == 0);
285 fq_nmod_mpoly_randtest_bound(a, state, len1, degbound, ctx);
286 fq_nmod_mpoly_randtest_bound(b, state, len2, degbound, ctx);
287 fq_nmod_mpoly_mul(a, a, t, ctx);
288 fq_nmod_mpoly_mul(b, b, t, ctx);
289
290 rlimb = n_randlimb(state);
291
292 if (rlimb & UWORD(3))
293 {
294 newbits = a->bits + n_randint(state, 2*FLINT_BITS);
295 newbits = mpoly_fix_bits(newbits, ctx->minfo);
296 fq_nmod_mpoly_repack_bits(a, a, newbits, ctx);
297 }
298
299 if (rlimb & UWORD(12))
300 {
301 newbits = b->bits + n_randint(state, 2*FLINT_BITS);
302 newbits = mpoly_fix_bits(newbits, ctx->minfo);
303 fq_nmod_mpoly_repack_bits(b, b, newbits, ctx);
304 }
305
306 fq_nmod_mpoly_randtest_bits(g, state, len, FLINT_BITS, ctx);
307
308 gcd_check(g, a, b, t, ctx, i, j, "sparse input with repacking");
309 }
310
311 fq_nmod_mpoly_clear(g, ctx);
312 fq_nmod_mpoly_clear(a, ctx);
313 fq_nmod_mpoly_clear(b, ctx);
314 fq_nmod_mpoly_clear(t, ctx);
315 fq_nmod_mpoly_ctx_clear(ctx);
316 }
317
318 /* sparse inputs with random inflations */
319 for (i = 0; i < tmul * flint_test_multiplier(); i++)
320 {
321 fq_nmod_mpoly_ctx_t ctx;
322 fq_nmod_mpoly_t a, b, g, t;
323 fmpz * shifts1, * shifts2, * strides;
324 flint_bitcnt_t stride_bits, shift_bits;
325 slong len, len1, len2;
326 slong degbound;
327
328 fq_nmod_mpoly_ctx_init_rand(ctx, state, 5, FLINT_BITS, 4);
329 fq_nmod_mpoly_init(g, ctx);
330 fq_nmod_mpoly_init(a, ctx);
331 fq_nmod_mpoly_init(b, ctx);
332 fq_nmod_mpoly_init(t, ctx);
333
334 len = n_randint(state, 15) + 1;
335 len1 = n_randint(state, 20);
336 len2 = n_randint(state, 20);
337
338 degbound = 30/(2*ctx->minfo->nvars - 1);
339
340 stride_bits = n_randint(state, 100) + 2;
341 shift_bits = n_randint(state, 100) + 2;
342
343 shifts1 = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
344 shifts2 = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
345 strides = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
346 for (k = 0; k < ctx->minfo->nvars; k++)
347 {
348 fmpz_init(shifts1 + k);
349 fmpz_init(shifts2 + k);
350 fmpz_init(strides + k);
351 }
352
353 for (j = 0; j < 4; j++)
354 {
355 do {
356 fq_nmod_mpoly_randtest_bound(t, state, len, degbound, ctx);
357 } while (t->length == 0);
358 fq_nmod_mpoly_randtest_bound(a, state, len1, degbound, ctx);
359 fq_nmod_mpoly_randtest_bound(b, state, len2, degbound, ctx);
360 fq_nmod_mpoly_mul(a, a, t, ctx);
361 fq_nmod_mpoly_mul(b, b, t, ctx);
362
363 fq_nmod_mpoly_randtest_bits(g, state, len, FLINT_BITS, ctx);
364
365 for (k = 0; k < ctx->minfo->nvars; k++)
366 {
367 fmpz_randtest_unsigned(shifts1 + k, state, shift_bits);
368 fmpz_randtest_unsigned(shifts2 + k, state, shift_bits);
369 fmpz_randtest_unsigned(strides + k, state, stride_bits);
370 }
371 fq_nmod_mpoly_inflate(a, a, shifts1, strides, ctx);
372 fq_nmod_mpoly_inflate(b, b, shifts2, strides, ctx);
373
374 for (k = 0; k < ctx->minfo->nvars; k++)
375 {
376 if (fmpz_cmp(shifts1 + k, shifts2 + k) > 0)
377 fmpz_set(shifts1 + k, shifts2 + k);
378 }
379 fq_nmod_mpoly_inflate(t, t, shifts1, strides, ctx);
380
381 gcd_check(g, a, b, t, ctx, i, j, "sparse input with inflation");
382 }
383
384 for (k = 0; k < ctx->minfo->nvars; k++)
385 {
386 fmpz_clear(shifts1 + k);
387 fmpz_clear(shifts2 + k);
388 fmpz_clear(strides + k);
389 }
390 flint_free(shifts1);
391 flint_free(shifts2);
392 flint_free(strides);
393
394 fq_nmod_mpoly_clear(g, ctx);
395 fq_nmod_mpoly_clear(a, ctx);
396 fq_nmod_mpoly_clear(b, ctx);
397 fq_nmod_mpoly_clear(t, ctx);
398 fq_nmod_mpoly_ctx_clear(ctx);
399 }
400
401 /* dense inputs */
402 for (i = 0; i < tmul * flint_test_multiplier(); i++)
403 {
404 fq_nmod_mpoly_ctx_t ctx;
405 fq_nmod_mpoly_t a, b, g, t;
406 slong len1, len2, len3, len4;
407 ulong degbounds1[4];
408 ulong degbounds2[4];
409 ulong degbounds3[4];
410 flint_bitcnt_t bits4;
411
412 fq_nmod_mpoly_ctx_init_rand(ctx, state, 4, FLINT_BITS, 4);
413 fq_nmod_mpoly_init(g, ctx);
414 fq_nmod_mpoly_init(a, ctx);
415 fq_nmod_mpoly_init(b, ctx);
416 fq_nmod_mpoly_init(t, ctx);
417
418 len1 = n_randint(state, 200) + 1;
419 len2 = n_randint(state, 200);
420 len3 = n_randint(state, 200);
421 len4 = n_randint(state, 200);
422
423 for (j = 0; j < ctx->minfo->nvars; j++)
424 {
425 degbounds1[j] = 2 + n_randint(state, 12/ctx->minfo->nvars);
426 degbounds2[j] = 1 + n_randint(state, 12/ctx->minfo->nvars);
427 degbounds3[j] = 1 + n_randint(state, 12/ctx->minfo->nvars);
428 }
429
430 bits4 = n_randint(state, 200);
431
432 for (j = 0; j < 4; j++)
433 {
434 do {
435 fq_nmod_mpoly_randtest_bounds(t, state, len1, degbounds1, ctx);
436 } while (t->length == 0);
437 fq_nmod_mpoly_randtest_bounds(a, state, len2, degbounds2, ctx);
438 fq_nmod_mpoly_randtest_bounds(b, state, len3, degbounds3, ctx);
439 fq_nmod_mpoly_mul(a, a, t, ctx);
440 fq_nmod_mpoly_mul(b, b, t, ctx);
441
442 fq_nmod_mpoly_randtest_bits(g, state, len4, bits4, ctx);
443
444 gcd_check(g, a, b, t, ctx, i, j, "dense input");
445 }
446
447 fq_nmod_mpoly_clear(g, ctx);
448 fq_nmod_mpoly_clear(a, ctx);
449 fq_nmod_mpoly_clear(b, ctx);
450 fq_nmod_mpoly_clear(t, ctx);
451 fq_nmod_mpoly_ctx_clear(ctx);
452 }
453
454 /* dense inputs with repacking */
455 for (i = 0; i < tmul * flint_test_multiplier(); i++)
456 {
457 fq_nmod_mpoly_ctx_t ctx;
458 fq_nmod_mpoly_t a, b, g, t;
459 mp_limb_t rlimb;
460 flint_bitcnt_t newbits;
461 slong len1, len2, len3, len4;
462 ulong degbounds1[4];
463 ulong degbounds2[4];
464 ulong degbounds3[4];
465 flint_bitcnt_t bits4;
466
467 fq_nmod_mpoly_ctx_init_rand(ctx, state, 4, FLINT_BITS, 4);
468 fq_nmod_mpoly_init(g, ctx);
469 fq_nmod_mpoly_init(a, ctx);
470 fq_nmod_mpoly_init(b, ctx);
471 fq_nmod_mpoly_init(t, ctx);
472
473 len1 = n_randint(state, 200) + 1;
474 len2 = n_randint(state, 200);
475 len3 = n_randint(state, 200);
476 len4 = n_randint(state, 200);
477
478 for (j = 0; j < ctx->minfo->nvars; j++)
479 {
480 degbounds1[j] = 2 + n_randint(state, 16/ctx->minfo->nvars);
481 degbounds2[j] = 1 + n_randint(state, 16/ctx->minfo->nvars);
482 degbounds3[j] = 1 + n_randint(state, 16/ctx->minfo->nvars);
483 }
484
485 bits4 = n_randint(state, 200);
486
487 for (j = 0; j < 4; j++)
488 {
489 do {
490 fq_nmod_mpoly_randtest_bounds(t, state, len1, degbounds1, ctx);
491 } while (t->length == 0);
492 fq_nmod_mpoly_randtest_bounds(a, state, len2, degbounds2, ctx);
493 fq_nmod_mpoly_randtest_bounds(b, state, len3, degbounds3, ctx);
494
495 fq_nmod_mpoly_mul(a, a, t, ctx);
496 fq_nmod_mpoly_mul(b, b, t, ctx);
497
498 rlimb = n_randlimb(state);
499
500 if (rlimb & UWORD(3))
501 {
502 newbits = a->bits + n_randint(state, 2*FLINT_BITS);
503 newbits = mpoly_fix_bits(newbits, ctx->minfo);
504 fq_nmod_mpoly_repack_bits(a, a, newbits, ctx);
505 }
506
507 if (rlimb & UWORD(12))
508 {
509 newbits = b->bits + n_randint(state, 2*FLINT_BITS);
510 newbits = mpoly_fix_bits(newbits, ctx->minfo);
511 fq_nmod_mpoly_repack_bits(b, b, newbits, ctx);
512 }
513
514 fq_nmod_mpoly_randtest_bits(g, state, len4, bits4, ctx);
515
516 gcd_check(g, a, b, t, ctx, i, j, "dense input with repacking");
517 }
518
519 fq_nmod_mpoly_clear(g, ctx);
520 fq_nmod_mpoly_clear(a, ctx);
521 fq_nmod_mpoly_clear(b, ctx);
522 fq_nmod_mpoly_clear(t, ctx);
523 fq_nmod_mpoly_ctx_clear(ctx);
524 }
525
526 /* dense inputs with random inflations */
527 for (i = 0; i < tmul * flint_test_multiplier(); i++)
528 {
529 fq_nmod_mpoly_ctx_t ctx;
530 fq_nmod_mpoly_t a, b, g, t;
531 fmpz * shifts1, * shifts2, * strides;
532 flint_bitcnt_t stride_bits, shift_bits;
533 slong len1, len2, len3, len4;
534 ulong degbounds1[4];
535 ulong degbounds2[4];
536 ulong degbounds3[4];
537 flint_bitcnt_t bits4;
538
539 fq_nmod_mpoly_ctx_init_rand(ctx, state, 4, FLINT_BITS, 4);
540 fq_nmod_mpoly_init(g, ctx);
541 fq_nmod_mpoly_init(a, ctx);
542 fq_nmod_mpoly_init(b, ctx);
543 fq_nmod_mpoly_init(t, ctx);
544
545 len1 = n_randint(state, 200) + 1;
546 len2 = n_randint(state, 200);
547 len3 = n_randint(state, 200);
548 len4 = n_randint(state, 200);
549
550 for (j = 0; j < ctx->minfo->nvars; j++)
551 {
552 degbounds1[j] = 2 + n_randint(state, 15/ctx->minfo->nvars);
553 degbounds2[j] = 1 + n_randint(state, 15/ctx->minfo->nvars);
554 degbounds3[j] = 1 + n_randint(state, 15/ctx->minfo->nvars);
555 }
556
557 bits4 = n_randint(state, 200);
558
559 stride_bits = n_randint(state, 100) + 2;
560 shift_bits = n_randint(state, 100) + 2;
561
562 shifts1 = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
563 shifts2 = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
564 strides = flint_malloc(ctx->minfo->nvars*sizeof(fmpz));
565 for (k = 0; k < ctx->minfo->nvars; k++)
566 {
567 fmpz_init(shifts1 + k);
568 fmpz_init(shifts2 + k);
569 fmpz_init(strides + k);
570 }
571
572 for (j = 0; j < 4; j++)
573 {
574 do {
575 fq_nmod_mpoly_randtest_bounds(t, state, len1, degbounds1, ctx);
576 } while (t->length == 0);
577 fq_nmod_mpoly_randtest_bounds(a, state, len2, degbounds2, ctx);
578 fq_nmod_mpoly_randtest_bounds(b, state, len3, degbounds3, ctx);
579 fq_nmod_mpoly_mul(a, a, t, ctx);
580 fq_nmod_mpoly_mul(b, b, t, ctx);
581
582 fq_nmod_mpoly_randtest_bits(g, state, len4, bits4, ctx);
583
584 for (k = 0; k < ctx->minfo->nvars; k++)
585 {
586 fmpz_randtest_unsigned(shifts1 + k, state, shift_bits);
587 fmpz_randtest_unsigned(shifts2 + k, state, shift_bits);
588 fmpz_randtest_unsigned(strides + k, state, stride_bits);
589 }
590 fq_nmod_mpoly_inflate(a, a, shifts1, strides, ctx);
591 fq_nmod_mpoly_inflate(b, b, shifts2, strides, ctx);
592
593 for (k = 0; k < ctx->minfo->nvars; k++)
594 {
595 if (fmpz_cmp(shifts1 + k, shifts2 + k) > 0)
596 fmpz_set(shifts1 + k, shifts2 + k);
597 }
598 fq_nmod_mpoly_inflate(t, t, shifts1, strides, ctx);
599
600 gcd_check(g, a, b, t, ctx, i, j, "dense input with inflation");
601 }
602
603 for (k = 0; k < ctx->minfo->nvars; k++)
604 {
605 fmpz_clear(shifts1 + k);
606 fmpz_clear(shifts2 + k);
607 fmpz_clear(strides + k);
608 }
609 flint_free(shifts1);
610 flint_free(shifts2);
611 flint_free(strides);
612
613 fq_nmod_mpoly_clear(g, ctx);
614 fq_nmod_mpoly_clear(a, ctx);
615 fq_nmod_mpoly_clear(b, ctx);
616 fq_nmod_mpoly_clear(t, ctx);
617 fq_nmod_mpoly_ctx_clear(ctx);
618 }
619
620 printf("PASS\n");
621 FLINT_TEST_CLEANUP(state);
622
623 return 0;
624 }
625