facMul.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facMul.cc
5  *
6  * This file implements functions for fast multiplication and division with
7  * remainder.
8  *
9  * Nomenclature rules: kronSub* -> plain Kronecker substitution
10  * reverseSubst* -> reverse Kronecker substitution
11  * kronSubRecipro* -> reciprocal Kronecker substitution as
12  * described in D. Harvey "Faster
13  * polynomial multiplication via
14  * multipoint Kronecker substitution"
15  *
16  * @author Martin Lee
17  *
18  **/
19 /*****************************************************************************/
20 
21 #include "debug.h"
22 
23 #include "config.h"
24 
25 
26 #include "canonicalform.h"
27 #include "facMul.h"
28 #include "cf_util.h"
30 
31 #ifdef HAVE_NTL
32 #include <NTL/lzz_pEX.h>
33 #include "NTLconvert.h"
34 
35 #ifdef HAVE_FLINT
36 #include "FLINTconvert.h"
37 #endif
38 
39 // univariate polys
40 
41 #ifdef HAVE_FLINT
42 void kronSubQa (fmpz_poly_t result, const CanonicalForm& A, int d)
43 {
44  int degAy= degree (A);
45  fmpz_poly_init2 (result, d*(degAy + 1));
46  _fmpz_poly_set_length (result, d*(degAy + 1));
47  CFIterator j;
48  for (CFIterator i= A; i.hasTerms(); i++)
49  {
50  if (i.coeff().inBaseDomain())
51  convertCF2Fmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d), i.coeff());
52  else
53  for (j= i.coeff(); j.hasTerms(); j++)
54  convertCF2Fmpz (fmpz_poly_get_coeff_ptr (result, i.exp()*d+j.exp()),
55  j.coeff());
56  }
57  _fmpz_poly_normalise(result);
58 }
59 
60 
62 reverseSubstQa (const fmpz_poly_t F, int d, const Variable& x,
63  const Variable& alpha, const CanonicalForm& den)
64 {
66  int i= 0;
67  int degf= fmpz_poly_degree (F);
68  int k= 0;
69  int degfSubK;
70  int repLength;
71  fmpq_poly_t buf;
72  fmpq_poly_t mipo;
74  while (degf >= k)
75  {
76  degfSubK= degf - k;
77  if (degfSubK >= d)
78  repLength= d;
79  else
80  repLength= degfSubK + 1;
81 
82  fmpq_poly_init2 (buf, repLength);
83  _fmpq_poly_set_length (buf, repLength);
84  _fmpz_vec_set (buf->coeffs, F->coeffs + k, repLength);
85  _fmpq_poly_normalise (buf);
86  fmpq_poly_rem (buf, buf, mipo);
87 
89  fmpq_poly_clear (buf);
90  i++;
91  k= d*i;
92  }
93  fmpq_poly_clear (mipo);
94  result /= den;
95  return result;
96 }
97 
100  const Variable& alpha)
101 {
102  CanonicalForm A= F;
103  CanonicalForm B= G;
104 
105  CanonicalForm denA= bCommonDen (A);
106  CanonicalForm denB= bCommonDen (B);
107 
108  A *= denA;
109  B *= denB;
110  int degAa= degree (A, alpha);
111  int degBa= degree (B, alpha);
112  int d= degAa + 1 + degBa;
113 
114  fmpz_poly_t FLINTA,FLINTB;
115  kronSubQa (FLINTA, A, d);
116  kronSubQa (FLINTB, B, d);
117 
118  fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
119 
120  denA *= denB;
121  A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
122 
123  fmpz_poly_clear (FLINTA);
124  fmpz_poly_clear (FLINTB);
125  return A;
126 }
127 
130 {
131  CanonicalForm A= F;
132  CanonicalForm B= G;
133 
134  CanonicalForm denA= bCommonDen (A);
135  CanonicalForm denB= bCommonDen (B);
136 
137  A *= denA;
138  B *= denB;
139  fmpz_poly_t FLINTA,FLINTB;
140  convertFacCF2Fmpz_poly_t (FLINTA, A);
141  convertFacCF2Fmpz_poly_t (FLINTB, B);
142  fmpz_poly_mul (FLINTA, FLINTA, FLINTB);
143  denA *= denB;
144  A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
145  A /= denA;
146  fmpz_poly_clear (FLINTA);
147  fmpz_poly_clear (FLINTB);
148 
149  return A;
150 }
151 
152 /*CanonicalForm
153 mulFLINTQ2 (const CanonicalForm& F, const CanonicalForm& G)
154 {
155  CanonicalForm A= F;
156  CanonicalForm B= G;
157 
158  fmpq_poly_t FLINTA,FLINTB;
159  convertFacCF2Fmpq_poly_t (FLINTA, A);
160  convertFacCF2Fmpq_poly_t (FLINTB, B);
161 
162  fmpq_poly_mul (FLINTA, FLINTA, FLINTB);
163  A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
164  fmpq_poly_clear (FLINTA);
165  fmpq_poly_clear (FLINTB);
166  return A;
167 }*/
168 
171 {
172  CanonicalForm A= F;
173  CanonicalForm B= G;
174 
175  fmpq_poly_t FLINTA,FLINTB;
176  convertFacCF2Fmpq_poly_t (FLINTA, A);
177  convertFacCF2Fmpq_poly_t (FLINTB, B);
178 
179  fmpq_poly_div (FLINTA, FLINTA, FLINTB);
180  A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
181 
182  fmpq_poly_clear (FLINTA);
183  fmpq_poly_clear (FLINTB);
184  return A;
185 }
186 
189 {
190  CanonicalForm A= F;
191  CanonicalForm B= G;
192 
193  fmpq_poly_t FLINTA,FLINTB;
194  convertFacCF2Fmpq_poly_t (FLINTA, A);
195  convertFacCF2Fmpq_poly_t (FLINTB, B);
196 
197  fmpq_poly_rem (FLINTA, FLINTA, FLINTB);
198  A= convertFmpq_poly_t2FacCF (FLINTA, F.mvar());
199 
200  fmpq_poly_clear (FLINTA);
201  fmpq_poly_clear (FLINTB);
202  return A;
203 }
204 
207  const Variable& alpha, int m)
208 {
209  CanonicalForm A= F;
210  CanonicalForm B= G;
211 
212  CanonicalForm denA= bCommonDen (A);
213  CanonicalForm denB= bCommonDen (B);
214 
215  A *= denA;
216  B *= denB;
217 
218  int degAa= degree (A, alpha);
219  int degBa= degree (B, alpha);
220  int d= degAa + 1 + degBa;
221 
222  fmpz_poly_t FLINTA,FLINTB;
223  kronSubQa (FLINTA, A, d);
224  kronSubQa (FLINTB, B, d);
225 
226  int k= d*m;
227  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, k);
228 
229  denA *= denB;
230  A= reverseSubstQa (FLINTA, d, F.mvar(), alpha, denA);
231  fmpz_poly_clear (FLINTA);
232  fmpz_poly_clear (FLINTB);
233  return A;
234 }
235 
238 {
239  if (F.inCoeffDomain() && G.inCoeffDomain())
240  return F*G;
241  if (F.inCoeffDomain())
242  return mod (F*G, power (G.mvar(), m));
243  if (G.inCoeffDomain())
244  return mod (F*G, power (F.mvar(), m));
245  Variable alpha;
246  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
247  return mulFLINTQaTrunc (F, G, alpha, m);
248 
249  CanonicalForm A= F;
250  CanonicalForm B= G;
251 
252  CanonicalForm denA= bCommonDen (A);
253  CanonicalForm denB= bCommonDen (B);
254 
255  A *= denA;
256  B *= denB;
257  fmpz_poly_t FLINTA,FLINTB;
258  convertFacCF2Fmpz_poly_t (FLINTA, A);
259  convertFacCF2Fmpz_poly_t (FLINTB, B);
260  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, m);
261  denA *= denB;
262  A= convertFmpz_poly_t2FacCF (FLINTA, F.mvar());
263  A /= denA;
264  fmpz_poly_clear (FLINTA);
265  fmpz_poly_clear (FLINTB);
266 
267  return A;
268 }
269 
271 {
272  if (d == 0)
273  return F;
274  if (F.inCoeffDomain())
275  return F*power (x,d);
277  CFIterator i= F;
278  while (d - i.exp() < 0)
279  i++;
280 
281  for (; i.hasTerms() && (d - i.exp() >= 0); i++)
282  result += i.coeff()*power (x, d - i.exp());
283  return result;
284 }
285 
287 newtonInverse (const CanonicalForm& F, const int n, const Variable& x)
288 {
289  int l= ilog2(n);
290 
292  if (F.inCoeffDomain())
293  g= F;
294  else
295  g= F [0];
296 
297  if (!F.inCoeffDomain())
298  ASSERT (F.mvar() == x, "main variable of F and x differ");
299  ASSERT (!g.isZero(), "expected a unit");
300 
301  if (!g.isOne())
302  g = 1/g;
304  int exp= 0;
305  if (n & 1)
306  {
307  result= g;
308  exp= 1;
309  }
311 
312  for (int i= 1; i <= l; i++)
313  {
314  h= mulNTL (g, mod (F, power (x, (1 << i))));
315  h= mod (h, power (x, (1 << i)) - 1);
316  h= div (h, power (x, (1 << (i - 1))));
317  g -= power (x, (1 << (i - 1)))*
318  mulFLINTQTrunc (g, h, 1 << (i-1));
319 
320  if (n & (1 << i))
321  {
322  if (exp)
323  {
324  h= mulNTL (result, mod (F, power (x, exp + (1 << i))));
325  h= mod (h, power (x, exp + (1 << i)) - 1);
326  h= div (h, power (x, exp));
327  result -= power(x, exp)*mulFLINTQTrunc (g, h, 1 << i);
328  exp += (1 << i);
329  }
330  else
331  {
332  exp= (1 << i);
333  result= g;
334  }
335  }
336  }
337 
338  return result;
339 }
340 
341 void
343  CanonicalForm& R)
344 {
345  ASSERT (F.level() == G.level(), "F and G have different level");
346  CanonicalForm A= F;
347  CanonicalForm B= G;
348  Variable x= A.mvar();
349  int degA= degree (A);
350  int degB= degree (B);
351  int m= degA - degB;
352 
353  if (m < 0)
354  {
355  R= A;
356  Q= 0;
357  return;
358  }
359 
360  if (degB <= 1)
361  divrem (A, B, Q, R);
362  else
363  {
364  R= uniReverse (A, degA, x);
365 
366  CanonicalForm revB= uniReverse (B, degB, x);
367  revB= newtonInverse (revB, m + 1, x);
368  Q= mulFLINTQTrunc (R, revB, m + 1);
369  Q= uniReverse (Q, m, x);
370 
371  R= A - mulNTL (Q, B);
372  }
373 }
374 
375 void
377 {
378  ASSERT (F.level() == G.level(), "F and G have different level");
379  CanonicalForm A= F;
380  CanonicalForm B= G;
381  Variable x= A.mvar();
382  int degA= degree (A);
383  int degB= degree (B);
384  int m= degA - degB;
385 
386  if (m < 0)
387  {
388  Q= 0;
389  return;
390  }
391 
392  if (degB <= 1)
393  Q= div (A, B);
394  else
395  {
396  CanonicalForm R= uniReverse (A, degA, x);
397  CanonicalForm revB= uniReverse (B, degB, x);
398  revB= newtonInverse (revB, m + 1, x);
399  Q= mulFLINTQTrunc (R, revB, m + 1);
400  Q= uniReverse (Q, m, x);
401  }
402 }
403 
404 #endif
405 
407 mulNTL (const CanonicalForm& F, const CanonicalForm& G, const modpk& b)
408 {
410  return F*G;
411  if (getCharacteristic() == 0)
412  {
413  Variable alpha;
414  if ((!F.inCoeffDomain() && !G.inCoeffDomain()) &&
416  {
417  if (b.getp() != 0)
418  {
420  bool is_rat= isOn (SW_RATIONAL);
421  if (!is_rat)
422  On (SW_RATIONAL);
423  mipo *=bCommonDen (mipo);
424  if (!is_rat)
425  Off (SW_RATIONAL);
426 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
427  fmpz_t FLINTp;
428  fmpz_mod_poly_t FLINTmipo;
429  fq_ctx_t fq_con;
430  fq_poly_t FLINTF, FLINTG;
431 
432  fmpz_init (FLINTp);
433 
434  convertCF2Fmpz (FLINTp, b.getpk());
435 
436  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, mipo, FLINTp);
437 
438  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
439 
440  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
441  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
442 
443  fq_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
444 
446  alpha, fq_con);
447 
448  fmpz_clear (FLINTp);
449  fmpz_mod_poly_clear (FLINTmipo);
450  fq_poly_clear (FLINTF, fq_con);
451  fq_poly_clear (FLINTG, fq_con);
452  fq_ctx_clear (fq_con);
453  return b (result);
454 #else
455  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
456  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
457  ZZ_pE::init (NTLmipo);
458  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
459  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
460  mul (NTLf, NTLf, NTLg);
461 
462  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
463 #endif
464  }
465 #ifdef HAVE_FLINT
467  return result;
468 #else
469  return F*G;
470 #endif
471  }
472  else if (!F.inCoeffDomain() && !G.inCoeffDomain())
473  {
474 #ifdef HAVE_FLINT
475  if (b.getp() != 0)
476  {
477  fmpz_t FLINTpk;
478  fmpz_init (FLINTpk);
479  convertCF2Fmpz (FLINTpk, b.getpk());
480  fmpz_mod_poly_t FLINTF, FLINTG;
481  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
482  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
483  fmpz_mod_poly_mul (FLINTF, FLINTF, FLINTG);
485  fmpz_mod_poly_clear (FLINTG);
486  fmpz_mod_poly_clear (FLINTF);
487  fmpz_clear (FLINTpk);
488  return result;
489  }
490  return mulFLINTQ (F, G);
491 #else
492  if (b.getp() != 0)
493  {
494  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
495  ZZX ZZf= convertFacCF2NTLZZX (F);
496  ZZX ZZg= convertFacCF2NTLZZX (G);
497  ZZ_pX NTLf= to_ZZ_pX (ZZf);
498  ZZ_pX NTLg= to_ZZ_pX (ZZg);
499  mul (NTLf, NTLf, NTLg);
500  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
501  }
502  return F*G;
503 #endif
504  }
505  if (b.getp() != 0)
506  {
507  if (!F.inBaseDomain() && !G.inBaseDomain())
508  {
509  if (hasFirstAlgVar (G, alpha) || hasFirstAlgVar (F, alpha))
510  {
511 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
512  fmpz_t FLINTp;
513  fmpz_mod_poly_t FLINTmipo;
514  fq_ctx_t fq_con;
515 
516  fmpz_init (FLINTp);
517  convertCF2Fmpz (FLINTp, b.getpk());
518 
519  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
520 
521  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
522 
524 
525  if (F.inCoeffDomain() && !G.inCoeffDomain())
526  {
527  fq_poly_t FLINTG;
528  fmpz_poly_t FLINTF;
529  convertFacCF2Fmpz_poly_t (FLINTF, F);
530  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
531 
532  fq_poly_scalar_mul_fq (FLINTG, FLINTG, FLINTF, fq_con);
533 
534  result= convertFq_poly_t2FacCF (FLINTG, G.mvar(), alpha, fq_con);
535  fmpz_poly_clear (FLINTF);
536  fq_poly_clear (FLINTG, fq_con);
537  }
538  else if (!F.inCoeffDomain() && G.inCoeffDomain())
539  {
540  fq_poly_t FLINTF;
541  fmpz_poly_t FLINTG;
542 
543  convertFacCF2Fmpz_poly_t (FLINTG, G);
544  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
545 
546  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
547 
548  result= convertFq_poly_t2FacCF (FLINTF, F.mvar(), alpha, fq_con);
549  fmpz_poly_clear (FLINTG);
550  fq_poly_clear (FLINTF, fq_con);
551  }
552  else
553  {
554  fq_t FLINTF, FLINTG;
555 
556  convertFacCF2Fq_t (FLINTF, F, fq_con);
557  convertFacCF2Fq_t (FLINTG, G, fq_con);
558 
559  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
560 
561  result= convertFq_t2FacCF (FLINTF, alpha);
562  fq_clear (FLINTF, fq_con);
563  fq_clear (FLINTG, fq_con);
564  }
565 
566  fmpz_clear (FLINTp);
567  fmpz_mod_poly_clear (FLINTmipo);
568  fq_ctx_clear (fq_con);
569 
570  return b (result);
571 #else
572  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
573  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
574  ZZ_pE::init (NTLmipo);
575 
576  if (F.inCoeffDomain() && !G.inCoeffDomain())
577  {
578  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
579  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
580  mul (NTLg, to_ZZ_pE (NTLf), NTLg);
581  return b (convertNTLZZ_pEX2CF (NTLg, G.mvar(), alpha));
582  }
583  else if (!F.inCoeffDomain() && G.inCoeffDomain())
584  {
585  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
586  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
587  mul (NTLf, NTLf, to_ZZ_pE (NTLg));
588  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
589  }
590  else
591  {
592  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
593  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
594  ZZ_pE result;
595  mul (result, to_ZZ_pE (NTLg), to_ZZ_pE (NTLf));
596  return b (convertNTLZZpX2CF (rep (result), alpha));
597  }
598 #endif
599  }
600  }
601  return b (F*G);
602  }
603  return F*G;
604  }
605  else if (F.inCoeffDomain() || G.inCoeffDomain())
606  return F*G;
607  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
608  ASSERT (F.level() == G.level(), "expected polys of same level");
610  {
612  zz_p::init (getCharacteristic());
613  }
614  Variable alpha;
616  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
617  {
618  if (!getReduce (alpha))
619  {
620  result= 0;
621  for (CFIterator i= F; i.hasTerms(); i++)
622  result += i.coeff()*G*power (F.mvar(),i.exp());
623  return result;
624  }
625 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
626  nmod_poly_t FLINTmipo;
627  fq_nmod_ctx_t fq_con;
628 
629  nmod_poly_init (FLINTmipo, getCharacteristic());
630  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
631 
632  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
633 
634  fq_nmod_poly_t FLINTF, FLINTG;
635  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
637 
638  fq_nmod_poly_mul (FLINTF, FLINTF, FLINTG, fq_con);
639 
641 
642  fq_nmod_poly_clear (FLINTF, fq_con);
643  fq_nmod_poly_clear (FLINTG, fq_con);
644  nmod_poly_clear (FLINTmipo);
646 #else
647  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
648  zz_pE::init (NTLMipo);
649  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
650  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
651  mul (NTLF, NTLF, NTLG);
652  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
653 #endif
654  }
655  else
656  {
657 #ifdef HAVE_FLINT
658  nmod_poly_t FLINTF, FLINTG;
659  convertFacCF2nmod_poly_t (FLINTF, F);
660  convertFacCF2nmod_poly_t (FLINTG, G);
661  nmod_poly_mul (FLINTF, FLINTF, FLINTG);
662  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
663  nmod_poly_clear (FLINTF);
664  nmod_poly_clear (FLINTG);
665 #else
666  zz_pX NTLF= convertFacCF2NTLzzpX (F);
667  zz_pX NTLG= convertFacCF2NTLzzpX (G);
668  mul (NTLF, NTLF, NTLG);
669  result= convertNTLzzpX2CF(NTLF, F.mvar());
670 #endif
671  }
672  return result;
673 }
674 
676 modNTL (const CanonicalForm& F, const CanonicalForm& G, const modpk& b)
677 {
679  return mod (F, G);
680  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
681  {
682  if (b.getp() != 0)
683  return b(F);
684  return F;
685  }
686  else if (F.inCoeffDomain() && G.inCoeffDomain())
687  {
688  if (b.getp() != 0)
689  return b(F%G);
690  return mod (F, G);
691  }
692  else if (F.isUnivariate() && G.inCoeffDomain())
693  {
694  if (b.getp() != 0)
695  return b(F%G);
696  return mod (F,G);
697  }
698 
699  if (getCharacteristic() == 0)
700  {
701  Variable alpha;
702  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
703  {
704 #ifdef HAVE_FLINT
705  if (b.getp() != 0)
706  {
707  fmpz_t FLINTpk;
708  fmpz_init (FLINTpk);
709  convertCF2Fmpz (FLINTpk, b.getpk());
710  fmpz_mod_poly_t FLINTF, FLINTG;
711  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
712  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
713  fmpz_mod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
715  fmpz_mod_poly_clear (FLINTG);
716  fmpz_mod_poly_clear (FLINTF);
717  fmpz_clear (FLINTpk);
718  return result;
719  }
720  return modFLINTQ (F, G);
721 #else
722  if (b.getp() != 0)
723  {
724  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
725  ZZX ZZf= convertFacCF2NTLZZX (F);
726  ZZX ZZg= convertFacCF2NTLZZX (G);
727  ZZ_pX NTLf= to_ZZ_pX (ZZf);
728  ZZ_pX NTLg= to_ZZ_pX (ZZg);
729  rem (NTLf, NTLf, NTLg);
730  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
731  }
732  return mod (F, G);
733 #endif
734  }
735  else
736  {
737  if (b.getp() != 0)
738  {
739 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
740  fmpz_t FLINTp;
741  fmpz_mod_poly_t FLINTmipo;
742  fq_ctx_t fq_con;
743  fq_poly_t FLINTF, FLINTG;
744 
745  fmpz_init (FLINTp);
746 
747  convertCF2Fmpz (FLINTp, b.getpk());
748 
749  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
750 
751  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
752 
753  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
754  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
755 
756  fq_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
757 
759  alpha, fq_con);
760 
761  fmpz_clear (FLINTp);
762  fmpz_mod_poly_clear (FLINTmipo);
763  fq_poly_clear (FLINTF, fq_con);
764  fq_poly_clear (FLINTG, fq_con);
765  fq_ctx_clear (fq_con);
766 
767  return b(result);
768 #else
769  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
770  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
771  ZZ_pE::init (NTLmipo);
772  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
773  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
774  rem (NTLf, NTLf, NTLg);
775  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
776 #endif
777  }
778 #ifdef HAVE_FLINT
779  CanonicalForm Q, R;
780  newtonDivrem (F, G, Q, R);
781  return R;
782 #else
783  return mod (F,G);
784 #endif
785  }
786  }
787 
788  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
789  ASSERT (F.level() == G.level(), "expected polys of same level");
791  {
793  zz_p::init (getCharacteristic());
794  }
795  Variable alpha;
797  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
798  {
799 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
800  nmod_poly_t FLINTmipo;
801  fq_nmod_ctx_t fq_con;
802 
803  nmod_poly_init (FLINTmipo, getCharacteristic());
804  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
805 
806  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
807 
808  fq_nmod_poly_t FLINTF, FLINTG;
809  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
811 
812  fq_nmod_poly_rem (FLINTF, FLINTF, FLINTG, fq_con);
813 
815 
816  fq_nmod_poly_clear (FLINTF, fq_con);
817  fq_nmod_poly_clear (FLINTG, fq_con);
818  nmod_poly_clear (FLINTmipo);
820 #else
821  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
822  zz_pE::init (NTLMipo);
823  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
824  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
825  rem (NTLF, NTLF, NTLG);
826  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
827 #endif
828  }
829  else
830  {
831 #ifdef HAVE_FLINT
832  nmod_poly_t FLINTF, FLINTG;
833  convertFacCF2nmod_poly_t (FLINTF, F);
834  convertFacCF2nmod_poly_t (FLINTG, G);
835  nmod_poly_divrem (FLINTG, FLINTF, FLINTF, FLINTG);
836  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
837  nmod_poly_clear (FLINTF);
838  nmod_poly_clear (FLINTG);
839 #else
840  zz_pX NTLF= convertFacCF2NTLzzpX (F);
841  zz_pX NTLG= convertFacCF2NTLzzpX (G);
842  rem (NTLF, NTLF, NTLG);
843  result= convertNTLzzpX2CF(NTLF, F.mvar());
844 #endif
845  }
846  return result;
847 }
848 
850 divNTL (const CanonicalForm& F, const CanonicalForm& G, const modpk& b)
851 {
853  return div (F, G);
854  if (F.inCoeffDomain() && G.isUnivariate() && !G.inCoeffDomain())
855  {
856  return 0;
857  }
858  else if (F.inCoeffDomain() && G.inCoeffDomain())
859  {
860  if (b.getp() != 0)
861  {
862  if (!F.inBaseDomain() || !G.inBaseDomain())
863  {
864  Variable alpha;
865  hasFirstAlgVar (F, alpha);
867 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
868  fmpz_t FLINTp;
869  fmpz_mod_poly_t FLINTmipo;
870  fq_ctx_t fq_con;
871  fq_t FLINTF, FLINTG;
872 
873  fmpz_init (FLINTp);
874  convertCF2Fmpz (FLINTp, b.getpk());
875 
876  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
877 
878  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
879 
880  convertFacCF2Fq_t (FLINTF, F, fq_con);
881  convertFacCF2Fq_t (FLINTG, G, fq_con);
882 
883  fq_inv (FLINTG, FLINTG, fq_con);
884  fq_mul (FLINTF, FLINTF, FLINTG, fq_con);
885 
887 
888  fmpz_clear (FLINTp);
889  fmpz_mod_poly_clear (FLINTmipo);
890  fq_clear (FLINTF, fq_con);
891  fq_clear (FLINTG, fq_con);
892  fq_ctx_clear (fq_con);
893  return b (result);
894 #else
895  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
896  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
897  ZZ_pE::init (NTLmipo);
898  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
899  ZZ_pX NTLf= convertFacCF2NTLZZpX (F);
900  ZZ_pE result;
901  div (result, to_ZZ_pE (NTLf), to_ZZ_pE (NTLg));
902  return b (convertNTLZZpX2CF (rep (result), alpha));
903 #endif
904  }
905  return b(div (F,G));
906  }
907  return div (F, G);
908  }
909  else if (F.isUnivariate() && G.inCoeffDomain())
910  {
911  if (b.getp() != 0)
912  {
913  if (!G.inBaseDomain())
914  {
915  Variable alpha;
917 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
918  fmpz_t FLINTp;
919  fmpz_mod_poly_t FLINTmipo;
920  fq_ctx_t fq_con;
921  fq_poly_t FLINTF;
922  fq_t FLINTG;
923 
924  fmpz_init (FLINTp);
925  convertCF2Fmpz (FLINTp, b.getpk());
926 
927  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
928 
929  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
930 
931  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
932  convertFacCF2Fq_t (FLINTG, G, fq_con);
933 
934  fq_inv (FLINTG, FLINTG, fq_con);
935  fq_poly_scalar_mul_fq (FLINTF, FLINTF, FLINTG, fq_con);
936 
938  alpha, fq_con);
939 
940  fmpz_clear (FLINTp);
941  fmpz_mod_poly_clear (FLINTmipo);
942  fq_poly_clear (FLINTF, fq_con);
943  fq_clear (FLINTG, fq_con);
944  fq_ctx_clear (fq_con);
945  return b (result);
946 #else
947  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
948  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
949  ZZ_pE::init (NTLmipo);
950  ZZ_pX NTLg= convertFacCF2NTLZZpX (G);
951  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
952  div (NTLf, NTLf, to_ZZ_pE (NTLg));
953  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
954 #endif
955  }
956  return b(div (F,G));
957  }
958  return div (F, G);
959  }
960 
961  if (getCharacteristic() == 0)
962  {
963 
964  Variable alpha;
965  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G, alpha))
966  {
967 #ifdef HAVE_FLINT
968  if (b.getp() != 0)
969  {
970  fmpz_t FLINTpk;
971  fmpz_init (FLINTpk);
972  convertCF2Fmpz (FLINTpk, b.getpk());
973  fmpz_mod_poly_t FLINTF, FLINTG;
974  convertFacCF2Fmpz_mod_poly_t (FLINTF, F, FLINTpk);
975  convertFacCF2Fmpz_mod_poly_t (FLINTG, G, FLINTpk);
976  fmpz_mod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG);
978  fmpz_mod_poly_clear (FLINTG);
979  fmpz_mod_poly_clear (FLINTF);
980  fmpz_clear (FLINTpk);
981  return result;
982  }
983  return divFLINTQ (F,G);
984 #else
985  if (b.getp() != 0)
986  {
987  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
988  ZZX ZZf= convertFacCF2NTLZZX (F);
989  ZZX ZZg= convertFacCF2NTLZZX (G);
990  ZZ_pX NTLf= to_ZZ_pX (ZZf);
991  ZZ_pX NTLg= to_ZZ_pX (ZZg);
992  div (NTLf, NTLf, NTLg);
993  return b (convertNTLZZX2CF (to_ZZX (NTLf), F.mvar()));
994  }
995  return div (F, G);
996 #endif
997  }
998  else
999  {
1000  if (b.getp() != 0)
1001  {
1002 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1003  fmpz_t FLINTp;
1004  fmpz_mod_poly_t FLINTmipo;
1005  fq_ctx_t fq_con;
1006  fq_poly_t FLINTF, FLINTG;
1007 
1008  fmpz_init (FLINTp);
1009  convertCF2Fmpz (FLINTp, b.getpk());
1010 
1011  convertFacCF2Fmpz_mod_poly_t (FLINTmipo, getMipo (alpha), FLINTp);
1012 
1013  fq_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1014 
1015  convertFacCF2Fq_poly_t (FLINTF, F, fq_con);
1016  convertFacCF2Fq_poly_t (FLINTG, G, fq_con);
1017 
1018  fq_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1019 
1021  alpha, fq_con);
1022 
1023  fmpz_clear (FLINTp);
1024  fmpz_mod_poly_clear (FLINTmipo);
1025  fq_ctx_clear (fq_con);
1026  fq_poly_clear (FLINTF, fq_con);
1027  fq_poly_clear (FLINTG, fq_con);
1028  return b (result);
1029 #else
1030  ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
1031  ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
1032  ZZ_pE::init (NTLmipo);
1033  ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);
1034  ZZ_pEX NTLf= convertFacCF2NTLZZ_pEX (F, NTLmipo);
1035  div (NTLf, NTLf, NTLg);
1036  return b (convertNTLZZ_pEX2CF (NTLf, F.mvar(), alpha));
1037 #endif
1038  }
1039 #ifdef HAVE_FLINT
1040  CanonicalForm Q;
1041  newtonDiv (F, G, Q);
1042  return Q;
1043 #else
1044  return div (F,G);
1045 #endif
1046  }
1047  }
1048 
1049  ASSERT (F.isUnivariate() && G.isUnivariate(), "expected univariate polys");
1050  ASSERT (F.level() == G.level(), "expected polys of same level");
1052  {
1054  zz_p::init (getCharacteristic());
1055  }
1056  Variable alpha;
1058  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
1059  {
1060 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1061  nmod_poly_t FLINTmipo;
1062  fq_nmod_ctx_t fq_con;
1063 
1064  nmod_poly_init (FLINTmipo, getCharacteristic());
1065  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
1066 
1067  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
1068 
1069  fq_nmod_poly_t FLINTF, FLINTG;
1070  convertFacCF2Fq_nmod_poly_t (FLINTF, F, fq_con);
1072 
1073  fq_nmod_poly_divrem (FLINTF, FLINTG, FLINTF, FLINTG, fq_con);
1074 
1076 
1077  fq_nmod_poly_clear (FLINTF, fq_con);
1078  fq_nmod_poly_clear (FLINTG, fq_con);
1079  nmod_poly_clear (FLINTmipo);
1081 #else
1082  zz_pX NTLMipo= convertFacCF2NTLzzpX(getMipo (alpha));
1083  zz_pE::init (NTLMipo);
1084  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
1085  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
1086  div (NTLF, NTLF, NTLG);
1087  result= convertNTLzz_pEX2CF(NTLF, F.mvar(), alpha);
1088 #endif
1089  }
1090  else
1091  {
1092 #ifdef HAVE_FLINT
1093  nmod_poly_t FLINTF, FLINTG;
1094  convertFacCF2nmod_poly_t (FLINTF, F);
1095  convertFacCF2nmod_poly_t (FLINTG, G);
1096  nmod_poly_div (FLINTF, FLINTF, FLINTG);
1097  result= convertnmod_poly_t2FacCF (FLINTF, F.mvar());
1098  nmod_poly_clear (FLINTF);
1099  nmod_poly_clear (FLINTG);
1100 #else
1101  zz_pX NTLF= convertFacCF2NTLzzpX (F);
1102  zz_pX NTLG= convertFacCF2NTLzzpX (G);
1103  div (NTLF, NTLF, NTLG);
1104  result= convertNTLzzpX2CF(NTLF, F.mvar());
1105 #endif
1106  }
1107  return result;
1108 }
1109 
1110 // end univariate polys
1111 //*************************
1112 // bivariate polys
1113 
1114 #ifdef HAVE_FLINT
1115 void kronSubFp (nmod_poly_t result, const CanonicalForm& A, int d)
1116 {
1117  int degAy= degree (A);
1118  nmod_poly_init2 (result, getCharacteristic(), d*(degAy + 1));
1119  result->length= d*(degAy + 1);
1120  flint_mpn_zero (result->coeffs, d*(degAy+1));
1121 
1122  nmod_poly_t buf;
1123 
1124  int k;
1125  for (CFIterator i= A; i.hasTerms(); i++)
1126  {
1127  convertFacCF2nmod_poly_t (buf, i.coeff());
1128  k= i.exp()*d;
1129  flint_mpn_copyi (result->coeffs+k, buf->coeffs, nmod_poly_length(buf));
1130 
1131  nmod_poly_clear (buf);
1132  }
1133  _nmod_poly_normalise (result);
1134 }
1135 
1136 #if ( __FLINT_RELEASE >= 20400)
1137 void
1138 kronSubFq (fq_nmod_poly_t result, const CanonicalForm& A, int d,
1139  const fq_nmod_ctx_t fq_con)
1140 {
1141  int degAy= degree (A);
1142  fq_nmod_poly_init2 (result, d*(degAy + 1), fq_con);
1143  _fq_nmod_poly_set_length (result, d*(degAy + 1), fq_con);
1144  _fq_nmod_vec_zero (result->coeffs, d*(degAy + 1), fq_con);
1145 
1146  fq_nmod_poly_t buf1;
1147 
1148  nmod_poly_t buf2;
1149 
1150  int k;
1151 
1152  for (CFIterator i= A; i.hasTerms(); i++)
1153  {
1154  if (i.coeff().inCoeffDomain())
1155  {
1156  convertFacCF2nmod_poly_t (buf2, i.coeff());
1157  fq_nmod_poly_init2 (buf1, 1, fq_con);
1158  fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1160  }
1161  else
1163 
1164  k= i.exp()*d;
1165  _fq_nmod_vec_set (result->coeffs+k, buf1->coeffs,
1166  fq_nmod_poly_length (buf1, fq_con), fq_con);
1167 
1169  }
1170 
1171  _fq_nmod_poly_normalise (result, fq_con);
1172 }
1173 #endif
1174 
1175 /*void kronSubQa (fmpq_poly_t result, const CanonicalForm& A, int d1, int d2)
1176 {
1177  int degAy= degree (A);
1178  fmpq_poly_init2 (result, d1*(degAy + 1));
1179 
1180  fmpq_poly_t buf;
1181  fmpq_t coeff;
1182 
1183  int k, l, bufRepLength;
1184  CFIterator j;
1185  for (CFIterator i= A; i.hasTerms(); i++)
1186  {
1187  if (i.coeff().inCoeffDomain())
1188  {
1189  k= d1*i.exp();
1190  convertFacCF2Fmpq_poly_t (buf, i.coeff());
1191  bufRepLength= (int) fmpq_poly_length(buf);
1192  for (l= 0; l < bufRepLength; l++)
1193  {
1194  fmpq_poly_get_coeff_fmpq (coeff, buf, l);
1195  fmpq_poly_set_coeff_fmpq (result, l + k, coeff);
1196  }
1197  fmpq_poly_clear (buf);
1198  }
1199  else
1200  {
1201  for (j= i.coeff(); j.hasTerms(); j++)
1202  {
1203  k= d1*i.exp();
1204  k += d2*j.exp();
1205  convertFacCF2Fmpq_poly_t (buf, j.coeff());
1206  bufRepLength= (int) fmpq_poly_length(buf);
1207  for (l= 0; l < bufRepLength; l++)
1208  {
1209  fmpq_poly_get_coeff_fmpq (coeff, buf, l);
1210  fmpq_poly_set_coeff_fmpq (result, k + l, coeff);
1211  }
1212  fmpq_poly_clear (buf);
1213  }
1214  }
1215  }
1216  fmpq_clear (coeff);
1217  _fmpq_poly_normalise (result);
1218 }*/
1219 
1220 void kronSubQa (fmpz_poly_t result, const CanonicalForm& A, int d1, int d2)
1221 {
1222  int degAy= degree (A);
1223  fmpz_poly_init2 (result, d1*(degAy + 1));
1224  _fmpz_poly_set_length (result, d1*(degAy + 1));
1225 
1226  fmpz_poly_t buf;
1227 
1228  int k;
1229  CFIterator j;
1230  for (CFIterator i= A; i.hasTerms(); i++)
1231  {
1232  if (i.coeff().inCoeffDomain())
1233  {
1234  k= d1*i.exp();
1235  convertFacCF2Fmpz_poly_t (buf, i.coeff());
1236  _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1237  fmpz_poly_clear (buf);
1238  }
1239  else
1240  {
1241  for (j= i.coeff(); j.hasTerms(); j++)
1242  {
1243  k= d1*i.exp();
1244  k += d2*j.exp();
1245  convertFacCF2Fmpz_poly_t (buf, j.coeff());
1246  _fmpz_vec_set (result->coeffs + k, buf->coeffs, buf->length);
1247  fmpz_poly_clear (buf);
1248  }
1249  }
1250  }
1251  _fmpz_poly_normalise (result);
1252 }
1253 
1254 void
1255 kronSubReciproFp (nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm& A,
1256  int d)
1257 {
1258  int degAy= degree (A);
1259  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1260  nmod_poly_init2_preinv (subA1, getCharacteristic(), ninv, d*(degAy + 2));
1261  nmod_poly_init2_preinv (subA2, getCharacteristic(), ninv, d*(degAy + 2));
1262 
1263  nmod_poly_t buf;
1264 
1265  int k, kk, j, bufRepLength;
1266  for (CFIterator i= A; i.hasTerms(); i++)
1267  {
1268  convertFacCF2nmod_poly_t (buf, i.coeff());
1269 
1270  k= i.exp()*d;
1271  kk= (degAy - i.exp())*d;
1272  bufRepLength= (int) nmod_poly_length (buf);
1273  for (j= 0; j < bufRepLength; j++)
1274  {
1275  nmod_poly_set_coeff_ui (subA1, j + k,
1276  n_addmod (nmod_poly_get_coeff_ui (subA1, j+k),
1277  nmod_poly_get_coeff_ui (buf, j),
1279  )
1280  );
1281  nmod_poly_set_coeff_ui (subA2, j + kk,
1282  n_addmod (nmod_poly_get_coeff_ui (subA2, j + kk),
1283  nmod_poly_get_coeff_ui (buf, j),
1285  )
1286  );
1287  }
1288  nmod_poly_clear (buf);
1289  }
1290  _nmod_poly_normalise (subA1);
1291  _nmod_poly_normalise (subA2);
1292 }
1293 
1294 #if ( __FLINT_RELEASE >= 20400)
1295 void
1296 kronSubReciproFq (fq_nmod_poly_t subA1, fq_nmod_poly_t subA2,
1297  const CanonicalForm& A, int d, const fq_nmod_ctx_t fq_con)
1298 {
1299  int degAy= degree (A);
1300  fq_nmod_poly_init2 (subA1, d*(degAy + 2), fq_con);
1301  fq_nmod_poly_init2 (subA2, d*(degAy + 2), fq_con);
1302 
1303  _fq_nmod_poly_set_length (subA1, d*(degAy + 2), fq_con);
1304  _fq_nmod_vec_zero (subA1->coeffs, d*(degAy + 2), fq_con);
1305 
1306  _fq_nmod_poly_set_length (subA2, d*(degAy + 2), fq_con);
1307  _fq_nmod_vec_zero (subA2->coeffs, d*(degAy + 2), fq_con);
1308 
1309  fq_nmod_poly_t buf1;
1310 
1311  nmod_poly_t buf2;
1312 
1313  int k, kk;
1314  for (CFIterator i= A; i.hasTerms(); i++)
1315  {
1316  if (i.coeff().inCoeffDomain())
1317  {
1318  convertFacCF2nmod_poly_t (buf2, i.coeff());
1319  fq_nmod_poly_init2 (buf1, 1, fq_con);
1320  fq_nmod_poly_set_coeff (buf1, 0, buf2, fq_con);
1322  }
1323  else
1325 
1326  k= i.exp()*d;
1327  kk= (degAy - i.exp())*d;
1328  _fq_nmod_vec_add (subA1->coeffs+k, subA1->coeffs+k, buf1->coeffs,
1329  fq_nmod_poly_length(buf1, fq_con), fq_con);
1330  _fq_nmod_vec_add (subA2->coeffs+kk, subA2->coeffs+kk, buf1->coeffs,
1331  fq_nmod_poly_length(buf1, fq_con), fq_con);
1332 
1334  }
1335  _fq_nmod_poly_normalise (subA1, fq_con);
1336  _fq_nmod_poly_normalise (subA2, fq_con);
1337 }
1338 #endif
1339 
1340 void
1341 kronSubReciproQ (fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm& A,
1342  int d)
1343 {
1344  int degAy= degree (A);
1345  fmpz_poly_init2 (subA1, d*(degAy + 2));
1346  fmpz_poly_init2 (subA2, d*(degAy + 2));
1347 
1348  fmpz_poly_t buf;
1349 
1350  int k, kk;
1351  for (CFIterator i= A; i.hasTerms(); i++)
1352  {
1353  convertFacCF2Fmpz_poly_t (buf, i.coeff());
1354 
1355  k= i.exp()*d;
1356  kk= (degAy - i.exp())*d;
1357  _fmpz_vec_add (subA1->coeffs+k, subA1->coeffs + k, buf->coeffs, buf->length);
1358  _fmpz_vec_add (subA2->coeffs+kk, subA2->coeffs + kk, buf->coeffs, buf->length);
1359  fmpz_poly_clear (buf);
1360  }
1361 
1362  _fmpz_poly_normalise (subA1);
1363  _fmpz_poly_normalise (subA2);
1364 }
1365 
1366 CanonicalForm reverseSubstQ (const fmpz_poly_t F, int d)
1367 {
1368  Variable y= Variable (2);
1369  Variable x= Variable (1);
1370 
1371  fmpz_poly_t buf;
1372  CanonicalForm result= 0;
1373  int i= 0;
1374  int degf= fmpz_poly_degree(F);
1375  int k= 0;
1376  int degfSubK, repLength;
1377  while (degf >= k)
1378  {
1379  degfSubK= degf - k;
1380  if (degfSubK >= d)
1381  repLength= d;
1382  else
1383  repLength= degfSubK + 1;
1384 
1385  fmpz_poly_init2 (buf, repLength);
1386  _fmpz_poly_set_length (buf, repLength);
1387  _fmpz_vec_set (buf->coeffs, F->coeffs+k, repLength);
1388  _fmpz_poly_normalise (buf);
1389 
1391  i++;
1392  k= d*i;
1393  fmpz_poly_clear (buf);
1394  }
1395 
1396  return result;
1397 }
1398 
1399 /*CanonicalForm
1400 reverseSubstQa (const fmpq_poly_t F, int d1, int d2, const Variable& alpha,
1401  const fmpq_poly_t mipo)
1402 {
1403  Variable y= Variable (2);
1404  Variable x= Variable (1);
1405 
1406  fmpq_poly_t f;
1407  fmpq_poly_init (f);
1408  fmpq_poly_set (f, F);
1409 
1410  fmpq_poly_t buf;
1411  CanonicalForm result= 0, result2;
1412  int i= 0;
1413  int degf= fmpq_poly_degree(f);
1414  int k= 0;
1415  int degfSubK;
1416  int repLength;
1417  fmpq_t coeff;
1418  while (degf >= k)
1419  {
1420  degfSubK= degf - k;
1421  if (degfSubK >= d1)
1422  repLength= d1;
1423  else
1424  repLength= degfSubK + 1;
1425 
1426  fmpq_init (coeff);
1427  int j= 0;
1428  int l;
1429  result2= 0;
1430  while (j*d2 < repLength)
1431  {
1432  fmpq_poly_init2 (buf, d2);
1433  for (l= 0; l < d2; l++)
1434  {
1435  fmpq_poly_get_coeff_fmpq (coeff, f, k + j*d2 + l);
1436  fmpq_poly_set_coeff_fmpq (buf, l, coeff);
1437  }
1438  _fmpq_poly_normalise (buf);
1439  fmpq_poly_rem (buf, buf, mipo);
1440  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1441  j++;
1442  fmpq_poly_clear (buf);
1443  }
1444  if (repLength - j*d2 != 0 && j*d2 - repLength < d2)
1445  {
1446  j--;
1447  repLength -= j*d2;
1448  fmpq_poly_init2 (buf, repLength);
1449  j++;
1450  for (l= 0; l < repLength; l++)
1451  {
1452  fmpq_poly_get_coeff_fmpq (coeff, f, k + j*d2 + l);
1453  fmpq_poly_set_coeff_fmpq (buf, l, coeff);
1454  }
1455  _fmpq_poly_normalise (buf);
1456  fmpq_poly_rem (buf, buf, mipo);
1457  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1458  fmpq_poly_clear (buf);
1459  }
1460  fmpq_clear (coeff);
1461 
1462  result += result2*power (y, i);
1463  i++;
1464  k= d1*i;
1465  }
1466 
1467  fmpq_poly_clear (f);
1468  return result;
1469 }*/
1470 
1472 reverseSubstQa (const fmpz_poly_t F, int d1, int d2, const Variable& alpha,
1473  const fmpq_poly_t mipo)
1474 {
1475  Variable y= Variable (2);
1476  Variable x= Variable (1);
1477 
1478  fmpq_poly_t buf;
1479  CanonicalForm result= 0, result2;
1480  int i= 0;
1481  int degf= fmpz_poly_degree(F);
1482  int k= 0;
1483  int degfSubK;
1484  int repLength;
1485  while (degf >= k)
1486  {
1487  degfSubK= degf - k;
1488  if (degfSubK >= d1)
1489  repLength= d1;
1490  else
1491  repLength= degfSubK + 1;
1492 
1493  int j= 0;
1494  result2= 0;
1495  while (j*d2 < repLength)
1496  {
1497  fmpq_poly_init2 (buf, d2);
1498  _fmpq_poly_set_length (buf, d2);
1499  _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, d2);
1500  _fmpq_poly_normalise (buf);
1501  fmpq_poly_rem (buf, buf, mipo);
1502  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1503  j++;
1504  fmpq_poly_clear (buf);
1505  }
1506  if (repLength - j*d2 != 0 && j*d2 - repLength < d2)
1507  {
1508  j--;
1509  repLength -= j*d2;
1510  fmpq_poly_init2 (buf, repLength);
1511  _fmpq_poly_set_length (buf, repLength);
1512  j++;
1513  _fmpz_vec_set (buf->coeffs, F->coeffs + k + j*d2, repLength);
1514  _fmpq_poly_normalise (buf);
1515  fmpq_poly_rem (buf, buf, mipo);
1516  result2 += convertFmpq_poly_t2FacCF (buf, alpha)*power (x, j);
1517  fmpq_poly_clear (buf);
1518  }
1519 
1520  result += result2*power (y, i);
1521  i++;
1522  k= d1*i;
1523  }
1524 
1525  return result;
1526 }
1527 
1529 reverseSubstReciproFp (const nmod_poly_t F, const nmod_poly_t G, int d, int k)
1530 {
1531  Variable y= Variable (2);
1532  Variable x= Variable (1);
1533 
1534  nmod_poly_t f, g;
1535  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1536  nmod_poly_init_preinv (f, getCharacteristic(), ninv);
1537  nmod_poly_init_preinv (g, getCharacteristic(), ninv);
1538  nmod_poly_set (f, F);
1539  nmod_poly_set (g, G);
1540  int degf= nmod_poly_degree(f);
1541  int degg= nmod_poly_degree(g);
1542 
1543 
1544  nmod_poly_t buf1,buf2, buf3;
1545 
1546  if (nmod_poly_length (f) < (long) d*(k+1)) //zero padding
1547  nmod_poly_fit_length (f,(long)d*(k+1));
1548 
1549  CanonicalForm result= 0;
1550  int i= 0;
1551  int lf= 0;
1552  int lg= d*k;
1553  int degfSubLf= degf;
1554  int deggSubLg= degg-lg;
1555  int repLengthBuf2, repLengthBuf1, ind, tmp;
1556  while (degf >= lf || lg >= 0)
1557  {
1558  if (degfSubLf >= d)
1559  repLengthBuf1= d;
1560  else if (degfSubLf < 0)
1561  repLengthBuf1= 0;
1562  else
1563  repLengthBuf1= degfSubLf + 1;
1564  nmod_poly_init2_preinv (buf1, getCharacteristic(), ninv, repLengthBuf1);
1565 
1566  for (ind= 0; ind < repLengthBuf1; ind++)
1567  nmod_poly_set_coeff_ui (buf1, ind, nmod_poly_get_coeff_ui (f, ind+lf));
1568  _nmod_poly_normalise (buf1);
1569 
1570  repLengthBuf1= nmod_poly_length (buf1);
1571 
1572  if (deggSubLg >= d - 1)
1573  repLengthBuf2= d - 1;
1574  else if (deggSubLg < 0)
1575  repLengthBuf2= 0;
1576  else
1577  repLengthBuf2= deggSubLg + 1;
1578 
1579  nmod_poly_init2_preinv (buf2, getCharacteristic(), ninv, repLengthBuf2);
1580  for (ind= 0; ind < repLengthBuf2; ind++)
1581  nmod_poly_set_coeff_ui (buf2, ind, nmod_poly_get_coeff_ui (g, ind + lg));
1582 
1583  _nmod_poly_normalise (buf2);
1584  repLengthBuf2= nmod_poly_length (buf2);
1585 
1586  nmod_poly_init2_preinv (buf3, getCharacteristic(), ninv, repLengthBuf2 + d);
1587  for (ind= 0; ind < repLengthBuf1; ind++)
1588  nmod_poly_set_coeff_ui (buf3, ind, nmod_poly_get_coeff_ui (buf1, ind));
1589  for (ind= repLengthBuf1; ind < d; ind++)
1590  nmod_poly_set_coeff_ui (buf3, ind, 0);
1591  for (ind= 0; ind < repLengthBuf2; ind++)
1592  nmod_poly_set_coeff_ui (buf3, ind+d, nmod_poly_get_coeff_ui (buf2, ind));
1593  _nmod_poly_normalise (buf3);
1594 
1595  result += convertnmod_poly_t2FacCF (buf3, x)*power (y, i);
1596  i++;
1597 
1598 
1599  lf= i*d;
1600  degfSubLf= degf - lf;
1601 
1602  lg= d*(k-i);
1603  deggSubLg= degg - lg;
1604 
1605  if (lg >= 0 && deggSubLg > 0)
1606  {
1607  if (repLengthBuf2 > degfSubLf + 1)
1608  degfSubLf= repLengthBuf2 - 1;
1609  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1610  for (ind= 0; ind < tmp; ind++)
1611  nmod_poly_set_coeff_ui (g, ind + lg,
1612  n_submod (nmod_poly_get_coeff_ui (g, ind + lg),
1613  nmod_poly_get_coeff_ui (buf1, ind),
1615  )
1616  );
1617  }
1618  if (lg < 0)
1619  {
1622  nmod_poly_clear (buf3);
1623  break;
1624  }
1625  if (degfSubLf >= 0)
1626  {
1627  for (ind= 0; ind < repLengthBuf2; ind++)
1628  nmod_poly_set_coeff_ui (f, ind + lf,
1629  n_submod (nmod_poly_get_coeff_ui (f, ind + lf),
1630  nmod_poly_get_coeff_ui (buf2, ind),
1632  )
1633  );
1634  }
1637  nmod_poly_clear (buf3);
1638  }
1639 
1640  nmod_poly_clear (f);
1641  nmod_poly_clear (g);
1642 
1643  return result;
1644 }
1645 
1646 #if ( __FLINT_RELEASE >= 20400)
1648 reverseSubstReciproFq (const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d,
1649  int k, const Variable& alpha, const fq_nmod_ctx_t fq_con)
1650 {
1651  Variable y= Variable (2);
1652  Variable x= Variable (1);
1653 
1654  fq_nmod_poly_t f, g;
1655  int degf= fq_nmod_poly_degree(F, fq_con);
1656  int degg= fq_nmod_poly_degree(G, fq_con);
1657 
1658  fq_nmod_poly_t buf1,buf2, buf3;
1659 
1662  fq_nmod_poly_set (f, F, fq_con);
1663  fq_nmod_poly_set (g, G, fq_con);
1664  if (fq_nmod_poly_length (f, fq_con) < (long) d*(k + 1)) //zero padding
1665  fq_nmod_poly_fit_length (f, (long) d*(k + 1), fq_con);
1666 
1667  CanonicalForm result= 0;
1668  int i= 0;
1669  int lf= 0;
1670  int lg= d*k;
1671  int degfSubLf= degf;
1672  int deggSubLg= degg-lg;
1673  int repLengthBuf2, repLengthBuf1, tmp;
1674  while (degf >= lf || lg >= 0)
1675  {
1676  if (degfSubLf >= d)
1677  repLengthBuf1= d;
1678  else if (degfSubLf < 0)
1679  repLengthBuf1= 0;
1680  else
1681  repLengthBuf1= degfSubLf + 1;
1682  fq_nmod_poly_init2 (buf1, repLengthBuf1, fq_con);
1683  _fq_nmod_poly_set_length (buf1, repLengthBuf1, fq_con);
1684 
1685  _fq_nmod_vec_set (buf1->coeffs, f->coeffs + lf, repLengthBuf1, fq_con);
1686  _fq_nmod_poly_normalise (buf1, fq_con);
1687 
1688  repLengthBuf1= fq_nmod_poly_length (buf1, fq_con);
1689 
1690  if (deggSubLg >= d - 1)
1691  repLengthBuf2= d - 1;
1692  else if (deggSubLg < 0)
1693  repLengthBuf2= 0;
1694  else
1695  repLengthBuf2= deggSubLg + 1;
1696 
1697  fq_nmod_poly_init2 (buf2, repLengthBuf2, fq_con);
1698  _fq_nmod_poly_set_length (buf2, repLengthBuf2, fq_con);
1699  _fq_nmod_vec_set (buf2->coeffs, g->coeffs + lg, repLengthBuf2, fq_con);
1700 
1701  _fq_nmod_poly_normalise (buf2, fq_con);
1702  repLengthBuf2= fq_nmod_poly_length (buf2, fq_con);
1703 
1704  fq_nmod_poly_init2 (buf3, repLengthBuf2 + d, fq_con);
1705  _fq_nmod_poly_set_length (buf3, repLengthBuf2 + d, fq_con);
1706  _fq_nmod_vec_set (buf3->coeffs, buf1->coeffs, repLengthBuf1, fq_con);
1707  _fq_nmod_vec_set (buf3->coeffs + d, buf2->coeffs, repLengthBuf2, fq_con);
1708 
1709  _fq_nmod_poly_normalise (buf3, fq_con);
1710 
1712  i++;
1713 
1714 
1715  lf= i*d;
1716  degfSubLf= degf - lf;
1717 
1718  lg= d*(k - i);
1719  deggSubLg= degg - lg;
1720 
1721  if (lg >= 0 && deggSubLg > 0)
1722  {
1723  if (repLengthBuf2 > degfSubLf + 1)
1724  degfSubLf= repLengthBuf2 - 1;
1725  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1726  _fq_nmod_vec_sub (g->coeffs + lg, g->coeffs + lg, buf1-> coeffs,
1727  tmp, fq_con);
1728  }
1729  if (lg < 0)
1730  {
1733  fq_nmod_poly_clear (buf3, fq_con);
1734  break;
1735  }
1736  if (degfSubLf >= 0)
1737  _fq_nmod_vec_sub (f->coeffs + lf, f->coeffs + lf, buf2->coeffs,
1738  repLengthBuf2, fq_con);
1741  fq_nmod_poly_clear (buf3, fq_con);
1742  }
1743 
1746 
1747  return result;
1748 }
1749 #endif
1750 
1752 reverseSubstReciproQ (const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
1753 {
1754  Variable y= Variable (2);
1755  Variable x= Variable (1);
1756 
1757  fmpz_poly_t f, g;
1758  fmpz_poly_init (f);
1759  fmpz_poly_init (g);
1760  fmpz_poly_set (f, F);
1761  fmpz_poly_set (g, G);
1762  int degf= fmpz_poly_degree(f);
1763  int degg= fmpz_poly_degree(g);
1764 
1765  fmpz_poly_t buf1,buf2, buf3;
1766 
1767  if (fmpz_poly_length (f) < (long) d*(k+1)) //zero padding
1768  fmpz_poly_fit_length (f,(long)d*(k+1));
1769 
1770  CanonicalForm result= 0;
1771  int i= 0;
1772  int lf= 0;
1773  int lg= d*k;
1774  int degfSubLf= degf;
1775  int deggSubLg= degg-lg;
1776  int repLengthBuf2, repLengthBuf1, ind, tmp;
1777  fmpz_t tmp1, tmp2;
1778  while (degf >= lf || lg >= 0)
1779  {
1780  if (degfSubLf >= d)
1781  repLengthBuf1= d;
1782  else if (degfSubLf < 0)
1783  repLengthBuf1= 0;
1784  else
1785  repLengthBuf1= degfSubLf + 1;
1786 
1787  fmpz_poly_init2 (buf1, repLengthBuf1);
1788 
1789  for (ind= 0; ind < repLengthBuf1; ind++)
1790  {
1791  fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1792  fmpz_poly_set_coeff_fmpz (buf1, ind, tmp1);
1793  }
1794  _fmpz_poly_normalise (buf1);
1795 
1796  repLengthBuf1= fmpz_poly_length (buf1);
1797 
1798  if (deggSubLg >= d - 1)
1799  repLengthBuf2= d - 1;
1800  else if (deggSubLg < 0)
1801  repLengthBuf2= 0;
1802  else
1803  repLengthBuf2= deggSubLg + 1;
1804 
1805  fmpz_poly_init2 (buf2, repLengthBuf2);
1806 
1807  for (ind= 0; ind < repLengthBuf2; ind++)
1808  {
1809  fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1810  fmpz_poly_set_coeff_fmpz (buf2, ind, tmp1);
1811  }
1812 
1813  _fmpz_poly_normalise (buf2);
1814  repLengthBuf2= fmpz_poly_length (buf2);
1815 
1816  fmpz_poly_init2 (buf3, repLengthBuf2 + d);
1817  for (ind= 0; ind < repLengthBuf1; ind++)
1818  {
1819  fmpz_poly_get_coeff_fmpz (tmp1, buf1, ind);
1820  fmpz_poly_set_coeff_fmpz (buf3, ind, tmp1);
1821  }
1822  for (ind= repLengthBuf1; ind < d; ind++)
1823  fmpz_poly_set_coeff_ui (buf3, ind, 0);
1824  for (ind= 0; ind < repLengthBuf2; ind++)
1825  {
1826  fmpz_poly_get_coeff_fmpz (tmp1, buf2, ind);
1827  fmpz_poly_set_coeff_fmpz (buf3, ind + d, tmp1);
1828  }
1829  _fmpz_poly_normalise (buf3);
1830 
1831  result += convertFmpz_poly_t2FacCF (buf3, x)*power (y, i);
1832  i++;
1833 
1834 
1835  lf= i*d;
1836  degfSubLf= degf - lf;
1837 
1838  lg= d*(k-i);
1839  deggSubLg= degg - lg;
1840 
1841  if (lg >= 0 && deggSubLg > 0)
1842  {
1843  if (repLengthBuf2 > degfSubLf + 1)
1844  degfSubLf= repLengthBuf2 - 1;
1845  tmp= tmin (repLengthBuf1, deggSubLg + 1);
1846  for (ind= 0; ind < tmp; ind++)
1847  {
1848  fmpz_poly_get_coeff_fmpz (tmp1, g, ind + lg);
1849  fmpz_poly_get_coeff_fmpz (tmp2, buf1, ind);
1850  fmpz_sub (tmp1, tmp1, tmp2);
1851  fmpz_poly_set_coeff_fmpz (g, ind + lg, tmp1);
1852  }
1853  }
1854  if (lg < 0)
1855  {
1856  fmpz_poly_clear (buf1);
1857  fmpz_poly_clear (buf2);
1858  fmpz_poly_clear (buf3);
1859  break;
1860  }
1861  if (degfSubLf >= 0)
1862  {
1863  for (ind= 0; ind < repLengthBuf2; ind++)
1864  {
1865  fmpz_poly_get_coeff_fmpz (tmp1, f, ind + lf);
1866  fmpz_poly_get_coeff_fmpz (tmp2, buf2, ind);
1867  fmpz_sub (tmp1, tmp1, tmp2);
1868  fmpz_poly_set_coeff_fmpz (f, ind + lf, tmp1);
1869  }
1870  }
1871  fmpz_poly_clear (buf1);
1872  fmpz_poly_clear (buf2);
1873  fmpz_poly_clear (buf3);
1874  }
1875 
1876  fmpz_poly_clear (f);
1877  fmpz_poly_clear (g);
1878  fmpz_clear (tmp1);
1879  fmpz_clear (tmp2);
1880 
1881  return result;
1882 }
1883 
1884 #if ( __FLINT_RELEASE >= 20400)
1886 reverseSubstFq (const fq_nmod_poly_t F, int d, const Variable& alpha,
1887  const fq_nmod_ctx_t fq_con)
1888 {
1889  Variable y= Variable (2);
1890  Variable x= Variable (1);
1891 
1892  fq_nmod_poly_t buf;
1893  CanonicalForm result= 0;
1894  int i= 0;
1895  int degf= fq_nmod_poly_degree(F, fq_con);
1896  int k= 0;
1897  int degfSubK, repLength;
1898  while (degf >= k)
1899  {
1900  degfSubK= degf - k;
1901  if (degfSubK >= d)
1902  repLength= d;
1903  else
1904  repLength= degfSubK + 1;
1905 
1906  fq_nmod_poly_init2 (buf, repLength, fq_con);
1907  _fq_nmod_poly_set_length (buf, repLength, fq_con);
1908  _fq_nmod_vec_set (buf->coeffs, F->coeffs+k, repLength, fq_con);
1909  _fq_nmod_poly_normalise (buf, fq_con);
1910 
1912  i++;
1913  k= d*i;
1915  }
1916 
1917  return result;
1918 }
1919 #endif
1920 
1921 CanonicalForm reverseSubstFp (const nmod_poly_t F, int d)
1922 {
1923  Variable y= Variable (2);
1924  Variable x= Variable (1);
1925 
1926  mp_limb_t ninv= n_preinvert_limb (getCharacteristic());
1927 
1928  nmod_poly_t buf;
1929  CanonicalForm result= 0;
1930  int i= 0;
1931  int degf= nmod_poly_degree(F);
1932  int k= 0;
1933  int degfSubK, repLength, j;
1934  while (degf >= k)
1935  {
1936  degfSubK= degf - k;
1937  if (degfSubK >= d)
1938  repLength= d;
1939  else
1940  repLength= degfSubK + 1;
1941 
1942  nmod_poly_init2_preinv (buf, getCharacteristic(), ninv, repLength);
1943  for (j= 0; j < repLength; j++)
1944  nmod_poly_set_coeff_ui (buf, j, nmod_poly_get_coeff_ui (F, j + k));
1945  _nmod_poly_normalise (buf);
1946 
1948  i++;
1949  k= d*i;
1950  nmod_poly_clear (buf);
1951  }
1952 
1953  return result;
1954 }
1955 
1958  CanonicalForm& M)
1959 {
1960  int d1= degree (F, 1) + degree (G, 1) + 1;
1961  d1 /= 2;
1962  d1 += 1;
1963 
1964  nmod_poly_t F1, F2;
1965  kronSubReciproFp (F1, F2, F, d1);
1966 
1967  nmod_poly_t G1, G2;
1968  kronSubReciproFp (G1, G2, G, d1);
1969 
1970  int k= d1*degree (M);
1971  nmod_poly_mullow (F1, F1, G1, (long) k);
1972 
1973  int degtailF= degree (tailcoeff (F), 1);;
1974  int degtailG= degree (tailcoeff (G), 1);
1975  int taildegF= taildegree (F);
1976  int taildegG= taildegree (G);
1977 
1978  int b= nmod_poly_degree (F2) + nmod_poly_degree (G2) - k - degtailF - degtailG
1979  + d1*(2+taildegF + taildegG);
1980  nmod_poly_mulhigh (F2, F2, G2, b);
1981  nmod_poly_shift_right (F2, F2, b);
1982  int d2= tmax (nmod_poly_degree (F2)/d1, nmod_poly_degree (F1)/d1);
1983 
1984 
1985  CanonicalForm result= reverseSubstReciproFp (F1, F2, d1, d2);
1986 
1987  nmod_poly_clear (F1);
1988  nmod_poly_clear (F2);
1989  nmod_poly_clear (G1);
1990  nmod_poly_clear (G2);
1991  return result;
1992 }
1993 
1996  CanonicalForm& M)
1997 {
1998  CanonicalForm A= F;
1999  CanonicalForm B= G;
2000 
2001  int degAx= degree (A, 1);
2002  int degAy= degree (A, 2);
2003  int degBx= degree (B, 1);
2004  int degBy= degree (B, 2);
2005  int d1= degAx + 1 + degBx;
2006  int d2= tmax (degAy, degBy);
2007 
2008  if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2009  return mulMod2FLINTFpReci (A, B, M);
2010 
2011  nmod_poly_t FLINTA, FLINTB;
2012  kronSubFp (FLINTA, A, d1);
2013  kronSubFp (FLINTB, B, d1);
2014 
2015  int k= d1*degree (M);
2016  nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2017 
2018  A= reverseSubstFp (FLINTA, d1);
2019 
2020  nmod_poly_clear (FLINTA);
2021  nmod_poly_clear (FLINTB);
2022  return A;
2023 }
2024 
2025 #if ( __FLINT_RELEASE >= 20400)
2028  CanonicalForm& M, const Variable& alpha,
2029  const fq_nmod_ctx_t fq_con)
2030 {
2031  int d1= degree (F, 1) + degree (G, 1) + 1;
2032  d1 /= 2;
2033  d1 += 1;
2034 
2035  fq_nmod_poly_t F1, F2;
2036  kronSubReciproFq (F1, F2, F, d1, fq_con);
2037 
2038  fq_nmod_poly_t G1, G2;
2039  kronSubReciproFq (G1, G2, G, d1, fq_con);
2040 
2041  int k= d1*degree (M);
2042  fq_nmod_poly_mullow (F1, F1, G1, (long) k, fq_con);
2043 
2044  int degtailF= degree (tailcoeff (F), 1);
2045  int degtailG= degree (tailcoeff (G), 1);
2046  int taildegF= taildegree (F);
2047  int taildegG= taildegree (G);
2048 
2049  int b= k + degtailF + degtailG - d1*(2+taildegF + taildegG);
2050 
2051  fq_nmod_poly_reverse (F2, F2, fq_nmod_poly_length (F2, fq_con), fq_con);
2052  fq_nmod_poly_reverse (G2, G2, fq_nmod_poly_length (G2, fq_con), fq_con);
2053  fq_nmod_poly_mullow (F2, F2, G2, b+1, fq_con);
2054  fq_nmod_poly_reverse (F2, F2, b+1, fq_con);
2055 
2056  int d2= tmax (fq_nmod_poly_degree (F2, fq_con)/d1,
2057  fq_nmod_poly_degree (F1, fq_con)/d1);
2058 
2060 
2061  fq_nmod_poly_clear (F1, fq_con);
2062  fq_nmod_poly_clear (F2, fq_con);
2063  fq_nmod_poly_clear (G1, fq_con);
2064  fq_nmod_poly_clear (G2, fq_con);
2065  return result;
2066 }
2067 
2070  CanonicalForm& M, const Variable& alpha,
2071  const fq_nmod_ctx_t fq_con)
2072 {
2073  CanonicalForm A= F;
2074  CanonicalForm B= G;
2075 
2076  int degAx= degree (A, 1);
2077  int degAy= degree (A, 2);
2078  int degBx= degree (B, 1);
2079  int degBy= degree (B, 2);
2080  int d1= degAx + 1 + degBx;
2081  int d2= tmax (degAy, degBy);
2082 
2083  if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2084  return mulMod2FLINTFqReci (A, B, M, alpha, fq_con);
2085 
2086  fq_nmod_poly_t FLINTA, FLINTB;
2087  kronSubFq (FLINTA, A, d1, fq_con);
2088  kronSubFq (FLINTB, B, d1, fq_con);
2089 
2090  int k= d1*degree (M);
2091  fq_nmod_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k, fq_con);
2092 
2093  A= reverseSubstFq (FLINTA, d1, alpha, fq_con);
2094 
2095  fq_nmod_poly_clear (FLINTA, fq_con);
2096  fq_nmod_poly_clear (FLINTB, fq_con);
2097  return A;
2098 }
2099 #endif
2100 
2103  CanonicalForm& M)
2104 {
2105  int d1= degree (F, 1) + degree (G, 1) + 1;
2106  d1 /= 2;
2107  d1 += 1;
2108 
2109  fmpz_poly_t F1, F2;
2110  kronSubReciproQ (F1, F2, F, d1);
2111 
2112  fmpz_poly_t G1, G2;
2113  kronSubReciproQ (G1, G2, G, d1);
2114 
2115  int k= d1*degree (M);
2116  fmpz_poly_mullow (F1, F1, G1, (long) k);
2117 
2118  int degtailF= degree (tailcoeff (F), 1);;
2119  int degtailG= degree (tailcoeff (G), 1);
2120  int taildegF= taildegree (F);
2121  int taildegG= taildegree (G);
2122 
2123  int b= fmpz_poly_degree (F2) + fmpz_poly_degree (G2) - k - degtailF - degtailG
2124  + d1*(2+taildegF + taildegG);
2125  fmpz_poly_mulhigh_n (F2, F2, G2, b);
2126  fmpz_poly_shift_right (F2, F2, b);
2127  int d2= tmax (fmpz_poly_degree (F2)/d1, fmpz_poly_degree (F1)/d1);
2128 
2129  CanonicalForm result= reverseSubstReciproQ (F1, F2, d1, d2);
2130 
2131  fmpz_poly_clear (F1);
2132  fmpz_poly_clear (F2);
2133  fmpz_poly_clear (G1);
2134  fmpz_poly_clear (G2);
2135  return result;
2136 }
2137 
2139 mulMod2FLINTQ (const CanonicalForm& F, const CanonicalForm& G, const
2140  CanonicalForm& M)
2141 {
2142  CanonicalForm A= F;
2143  CanonicalForm B= G;
2144 
2145  int degAx= degree (A, 1);
2146  int degBx= degree (B, 1);
2147  int d1= degAx + 1 + degBx;
2148 
2149  CanonicalForm f= bCommonDen (F);
2151  A *= f;
2152  B *= g;
2153 
2154  fmpz_poly_t FLINTA, FLINTB;
2155  kronSubQa (FLINTA, A, d1);
2156  kronSubQa (FLINTB, B, d1);
2157  int k= d1*degree (M);
2158 
2159  fmpz_poly_mullow (FLINTA, FLINTA, FLINTB, (long) k);
2160  A= reverseSubstQ (FLINTA, d1);
2161  fmpz_poly_clear (FLINTA);
2162  fmpz_poly_clear (FLINTB);
2163  return A/(f*g);
2164 }
2165 
2166 /*CanonicalForm
2167 mulMod2FLINTQa (const CanonicalForm& F, const CanonicalForm& G,
2168  const CanonicalForm& M)
2169 {
2170  Variable a;
2171  if (!hasFirstAlgVar (F,a) && !hasFirstAlgVar (G, a))
2172  return mulMod2FLINTQ (F, G, M);
2173  CanonicalForm A= F;
2174 
2175  int degFx= degree (F, 1);
2176  int degFa= degree (F, a);
2177  int degGx= degree (G, 1);
2178  int degGa= degree (G, a);
2179 
2180  int d2= degFa+degGa+1;
2181  int d1= degFx + 1 + degGx;
2182  d1 *= d2;
2183 
2184  fmpq_poly_t FLINTF, FLINTG;
2185  kronSubQa (FLINTF, F, d1, d2);
2186  kronSubQa (FLINTG, G, d1, d2);
2187 
2188  fmpq_poly_mullow (FLINTF, FLINTF, FLINTG, d1*degree (M));
2189 
2190  fmpq_poly_t mipo;
2191  convertFacCF2Fmpq_poly_t (mipo, getMipo (a));
2192  CanonicalForm result= reverseSubstQa (FLINTF, d1, d2, a, mipo);
2193  fmpq_poly_clear (FLINTF);
2194  fmpq_poly_clear (FLINTG);
2195  return result;
2196 }*/
2197 
2200  const CanonicalForm& M)
2201 {
2202  Variable a;
2203  if (!hasFirstAlgVar (F,a) && !hasFirstAlgVar (G, a))
2204  return mulMod2FLINTQ (F, G, M);
2205  CanonicalForm A= F, B= G;
2206 
2207  int degFx= degree (F, 1);
2208  int degFa= degree (F, a);
2209  int degGx= degree (G, 1);
2210  int degGa= degree (G, a);
2211 
2212  int d2= degFa+degGa+1;
2213  int d1= degFx + 1 + degGx;
2214  d1 *= d2;
2215 
2216  CanonicalForm f= bCommonDen (F);
2218  A *= f;
2219  B *= g;
2220 
2221  fmpz_poly_t FLINTF, FLINTG;
2222  kronSubQa (FLINTF, A, d1, d2);
2223  kronSubQa (FLINTG, B, d1, d2);
2224 
2225  fmpz_poly_mullow (FLINTF, FLINTF, FLINTG, d1*degree (M));
2226 
2227  fmpq_poly_t mipo;
2229  A= reverseSubstQa (FLINTF, d1, d2, a, mipo);
2230  fmpz_poly_clear (FLINTF);
2231  fmpz_poly_clear (FLINTG);
2232  return A/(f*g);
2233 }
2234 
2235 #endif
2236 
2237 #ifndef HAVE_FLINT
2238 zz_pX kronSubFp (const CanonicalForm& A, int d)
2239 {
2240  int degAy= degree (A);
2241  zz_pX result;
2242  result.rep.SetLength (d*(degAy + 1));
2243 
2244  zz_p *resultp;
2245  resultp= result.rep.elts();
2246  zz_pX buf;
2247  zz_p *bufp;
2248  int j, k, bufRepLength;
2249 
2250  for (CFIterator i= A; i.hasTerms(); i++)
2251  {
2252  if (i.coeff().inCoeffDomain())
2253  buf= convertFacCF2NTLzzpX (i.coeff());
2254  else
2255  buf= convertFacCF2NTLzzpX (i.coeff());
2256 
2257  k= i.exp()*d;
2258  bufp= buf.rep.elts();
2259  bufRepLength= (int) buf.rep.length();
2260  for (j= 0; j < bufRepLength; j++)
2261  resultp [j + k]= bufp [j];
2262  }
2263  result.normalize();
2264 
2265  return result;
2266 }
2267 #endif
2268 
2269 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2270 zz_pEX kronSubFq (const CanonicalForm& A, int d, const Variable& alpha)
2271 {
2272  int degAy= degree (A);
2273  zz_pEX result;
2274  result.rep.SetLength (d*(degAy + 1));
2275 
2276  Variable v;
2277  zz_pE *resultp;
2278  resultp= result.rep.elts();
2279  zz_pEX buf1;
2280  zz_pE *buf1p;
2281  zz_pX buf2;
2282  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
2283  int j, k, buf1RepLength;
2284 
2285  for (CFIterator i= A; i.hasTerms(); i++)
2286  {
2287  if (i.coeff().inCoeffDomain())
2288  {
2289  buf2= convertFacCF2NTLzzpX (i.coeff());
2290  buf1= to_zz_pEX (to_zz_pE (buf2));
2291  }
2292  else
2293  buf1= convertFacCF2NTLzz_pEX (i.coeff(), NTLMipo);
2294 
2295  k= i.exp()*d;
2296  buf1p= buf1.rep.elts();
2297  buf1RepLength= (int) buf1.rep.length();
2298  for (j= 0; j < buf1RepLength; j++)
2299  resultp [j + k]= buf1p [j];
2300  }
2301  result.normalize();
2302 
2303  return result;
2304 }
2305 
2306 void
2307 kronSubReciproFq (zz_pEX& subA1, zz_pEX& subA2,const CanonicalForm& A, int d,
2308  const Variable& alpha)
2309 {
2310  int degAy= degree (A);
2311  subA1.rep.SetLength ((long) d*(degAy + 2));
2312  subA2.rep.SetLength ((long) d*(degAy + 2));
2313 
2314  Variable v;
2315  zz_pE *subA1p;
2316  zz_pE *subA2p;
2317  subA1p= subA1.rep.elts();
2318  subA2p= subA2.rep.elts();
2319  zz_pEX buf;
2320  zz_pE *bufp;
2321  zz_pX buf2;
2322  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
2323  int j, k, kk, bufRepLength;
2324 
2325  for (CFIterator i= A; i.hasTerms(); i++)
2326  {
2327  if (i.coeff().inCoeffDomain())
2328  {
2329  buf2= convertFacCF2NTLzzpX (i.coeff());
2330  buf= to_zz_pEX (to_zz_pE (buf2));
2331  }
2332  else
2333  buf= convertFacCF2NTLzz_pEX (i.coeff(), NTLMipo);
2334 
2335  k= i.exp()*d;
2336  kk= (degAy - i.exp())*d;
2337  bufp= buf.rep.elts();
2338  bufRepLength= (int) buf.rep.length();
2339  for (j= 0; j < bufRepLength; j++)
2340  {
2341  subA1p [j + k] += bufp [j];
2342  subA2p [j + kk] += bufp [j];
2343  }
2344  }
2345  subA1.normalize();
2346  subA2.normalize();
2347 }
2348 #endif
2349 
2350 #ifndef HAVE_FLINT
2351 void
2352 kronSubReciproFp (zz_pX& subA1, zz_pX& subA2, const CanonicalForm& A, int d)
2353 {
2354  int degAy= degree (A);
2355  subA1.rep.SetLength ((long) d*(degAy + 2));
2356  subA2.rep.SetLength ((long) d*(degAy + 2));
2357 
2358  zz_p *subA1p;
2359  zz_p *subA2p;
2360  subA1p= subA1.rep.elts();
2361  subA2p= subA2.rep.elts();
2362  zz_pX buf;
2363  zz_p *bufp;
2364  int j, k, kk, bufRepLength;
2365 
2366  for (CFIterator i= A; i.hasTerms(); i++)
2367  {
2368  buf= convertFacCF2NTLzzpX (i.coeff());
2369 
2370  k= i.exp()*d;
2371  kk= (degAy - i.exp())*d;
2372  bufp= buf.rep.elts();
2373  bufRepLength= (int) buf.rep.length();
2374  for (j= 0; j < bufRepLength; j++)
2375  {
2376  subA1p [j + k] += bufp [j];
2377  subA2p [j + kk] += bufp [j];
2378  }
2379  }
2380  subA1.normalize();
2381  subA2.normalize();
2382 }
2383 #endif
2384 
2385 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2387 reverseSubstReciproFq (const zz_pEX& F, const zz_pEX& G, int d, int k,
2388  const Variable& alpha)
2389 {
2390  Variable y= Variable (2);
2391  Variable x= Variable (1);
2392 
2393  zz_pEX f= F;
2394  zz_pEX g= G;
2395  int degf= deg(f);
2396  int degg= deg(g);
2397 
2398  zz_pEX buf1;
2399  zz_pEX buf2;
2400  zz_pEX buf3;
2401 
2402  zz_pE *buf1p;
2403  zz_pE *buf2p;
2404  zz_pE *buf3p;
2405  if (f.rep.length() < (long) d*(k+1)) //zero padding
2406  f.rep.SetLength ((long)d*(k+1));
2407 
2408  zz_pE *gp= g.rep.elts();
2409  zz_pE *fp= f.rep.elts();
2410  CanonicalForm result= 0;
2411  int i= 0;
2412  int lf= 0;
2413  int lg= d*k;
2414  int degfSubLf= degf;
2415  int deggSubLg= degg-lg;
2416  int repLengthBuf2, repLengthBuf1, ind, tmp;
2417  zz_pE zzpEZero= zz_pE();
2418 
2419  while (degf >= lf || lg >= 0)
2420  {
2421  if (degfSubLf >= d)
2422  repLengthBuf1= d;
2423  else if (degfSubLf < 0)
2424  repLengthBuf1= 0;
2425  else
2426  repLengthBuf1= degfSubLf + 1;
2427  buf1.rep.SetLength((long) repLengthBuf1);
2428 
2429  buf1p= buf1.rep.elts();
2430  for (ind= 0; ind < repLengthBuf1; ind++)
2431  buf1p [ind]= fp [ind + lf];
2432  buf1.normalize();
2433 
2434  repLengthBuf1= buf1.rep.length();
2435 
2436  if (deggSubLg >= d - 1)
2437  repLengthBuf2= d - 1;
2438  else if (deggSubLg < 0)
2439  repLengthBuf2= 0;
2440  else
2441  repLengthBuf2= deggSubLg + 1;
2442 
2443  buf2.rep.SetLength ((long) repLengthBuf2);
2444  buf2p= buf2.rep.elts();
2445  for (ind= 0; ind < repLengthBuf2; ind++)
2446  buf2p [ind]= gp [ind + lg];
2447  buf2.normalize();
2448 
2449  repLengthBuf2= buf2.rep.length();
2450 
2451  buf3.rep.SetLength((long) repLengthBuf2 + d);
2452  buf3p= buf3.rep.elts();
2453  buf2p= buf2.rep.elts();
2454  buf1p= buf1.rep.elts();
2455  for (ind= 0; ind < repLengthBuf1; ind++)
2456  buf3p [ind]= buf1p [ind];
2457  for (ind= repLengthBuf1; ind < d; ind++)
2458  buf3p [ind]= zzpEZero;
2459  for (ind= 0; ind < repLengthBuf2; ind++)
2460  buf3p [ind + d]= buf2p [ind];
2461  buf3.normalize();
2462 
2463  result += convertNTLzz_pEX2CF (buf3, x, alpha)*power (y, i);
2464  i++;
2465 
2466 
2467  lf= i*d;
2468  degfSubLf= degf - lf;
2469 
2470  lg= d*(k-i);
2471  deggSubLg= degg - lg;
2472 
2473  buf1p= buf1.rep.elts();
2474 
2475  if (lg >= 0 && deggSubLg > 0)
2476  {
2477  if (repLengthBuf2 > degfSubLf + 1)
2478  degfSubLf= repLengthBuf2 - 1;
2479  tmp= tmin (repLengthBuf1, deggSubLg + 1);
2480  for (ind= 0; ind < tmp; ind++)
2481  gp [ind + lg] -= buf1p [ind];
2482  }
2483 
2484  if (lg < 0)
2485  break;
2486 
2487  buf2p= buf2.rep.elts();
2488  if (degfSubLf >= 0)
2489  {
2490  for (ind= 0; ind < repLengthBuf2; ind++)
2491  fp [ind + lf] -= buf2p [ind];
2492  }
2493  }
2494 
2495  return result;
2496 }
2497 #endif
2498 
2499 #ifndef HAVE_FLINT
2501 reverseSubstReciproFp (const zz_pX& F, const zz_pX& G, int d, int k)
2502 {
2503  Variable y= Variable (2);
2504  Variable x= Variable (1);
2505 
2506  zz_pX f= F;
2507  zz_pX g= G;
2508  int degf= deg(f);
2509  int degg= deg(g);
2510 
2511  zz_pX buf1;
2512  zz_pX buf2;
2513  zz_pX buf3;
2514 
2515  zz_p *buf1p;
2516  zz_p *buf2p;
2517  zz_p *buf3p;
2518 
2519  if (f.rep.length() < (long) d*(k+1)) //zero padding
2520  f.rep.SetLength ((long)d*(k+1));
2521 
2522  zz_p *gp= g.rep.elts();
2523  zz_p *fp= f.rep.elts();
2524  CanonicalForm result= 0;
2525  int i= 0;
2526  int lf= 0;
2527  int lg= d*k;
2528  int degfSubLf= degf;
2529  int deggSubLg= degg-lg;
2530  int repLengthBuf2, repLengthBuf1, ind, tmp;
2531  zz_p zzpZero= zz_p();
2532  while (degf >= lf || lg >= 0)
2533  {
2534  if (degfSubLf >= d)
2535  repLengthBuf1= d;
2536  else if (degfSubLf < 0)
2537  repLengthBuf1= 0;
2538  else
2539  repLengthBuf1= degfSubLf + 1;
2540  buf1.rep.SetLength((long) repLengthBuf1);
2541 
2542  buf1p= buf1.rep.elts();
2543  for (ind= 0; ind < repLengthBuf1; ind++)
2544  buf1p [ind]= fp [ind + lf];
2545  buf1.normalize();
2546 
2547  repLengthBuf1= buf1.rep.length();
2548 
2549  if (deggSubLg >= d - 1)
2550  repLengthBuf2= d - 1;
2551  else if (deggSubLg < 0)
2552  repLengthBuf2= 0;
2553  else
2554  repLengthBuf2= deggSubLg + 1;
2555 
2556  buf2.rep.SetLength ((long) repLengthBuf2);
2557  buf2p= buf2.rep.elts();
2558  for (ind= 0; ind < repLengthBuf2; ind++)
2559  buf2p [ind]= gp [ind + lg];
2560 
2561  buf2.normalize();
2562 
2563  repLengthBuf2= buf2.rep.length();
2564 
2565 
2566  buf3.rep.SetLength((long) repLengthBuf2 + d);
2567  buf3p= buf3.rep.elts();
2568  buf2p= buf2.rep.elts();
2569  buf1p= buf1.rep.elts();
2570  for (ind= 0; ind < repLengthBuf1; ind++)
2571  buf3p [ind]= buf1p [ind];
2572  for (ind= repLengthBuf1; ind < d; ind++)
2573  buf3p [ind]= zzpZero;
2574  for (ind= 0; ind < repLengthBuf2; ind++)
2575  buf3p [ind + d]= buf2p [ind];
2576  buf3.normalize();
2577 
2578  result += convertNTLzzpX2CF (buf3, x)*power (y, i);
2579  i++;
2580 
2581 
2582  lf= i*d;
2583  degfSubLf= degf - lf;
2584 
2585  lg= d*(k-i);
2586  deggSubLg= degg - lg;
2587 
2588  buf1p= buf1.rep.elts();
2589 
2590  if (lg >= 0 && deggSubLg > 0)
2591  {
2592  if (repLengthBuf2 > degfSubLf + 1)
2593  degfSubLf= repLengthBuf2 - 1;
2594  tmp= tmin (repLengthBuf1, deggSubLg + 1);
2595  for (ind= 0; ind < tmp; ind++)
2596  gp [ind + lg] -= buf1p [ind];
2597  }
2598  if (lg < 0)
2599  break;
2600 
2601  buf2p= buf2.rep.elts();
2602  if (degfSubLf >= 0)
2603  {
2604  for (ind= 0; ind < repLengthBuf2; ind++)
2605  fp [ind + lf] -= buf2p [ind];
2606  }
2607  }
2608 
2609  return result;
2610 }
2611 #endif
2612 
2613 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2614 CanonicalForm reverseSubstFq (const zz_pEX& F, int d, const Variable& alpha)
2615 {
2616  Variable y= Variable (2);
2617  Variable x= Variable (1);
2618 
2619  zz_pEX f= F;
2620  zz_pE *fp= f.rep.elts();
2621 
2622  zz_pEX buf;
2623  zz_pE *bufp;
2624  CanonicalForm result= 0;
2625  int i= 0;
2626  int degf= deg(f);
2627  int k= 0;
2628  int degfSubK, repLength, j;
2629  while (degf >= k)
2630  {
2631  degfSubK= degf - k;
2632  if (degfSubK >= d)
2633  repLength= d;
2634  else
2635  repLength= degfSubK + 1;
2636 
2637  buf.rep.SetLength ((long) repLength);
2638  bufp= buf.rep.elts();
2639  for (j= 0; j < repLength; j++)
2640  bufp [j]= fp [j + k];
2641  buf.normalize();
2642 
2644  i++;
2645  k= d*i;
2646  }
2647 
2648  return result;
2649 }
2650 #endif
2651 
2652 #ifndef HAVE_FLINT
2653 CanonicalForm reverseSubstFp (const zz_pX& F, int d)
2654 {
2655  Variable y= Variable (2);
2656  Variable x= Variable (1);
2657 
2658  zz_pX f= F;
2659  zz_p *fp= f.rep.elts();
2660 
2661  zz_pX buf;
2662  zz_p *bufp;
2663  CanonicalForm result= 0;
2664  int i= 0;
2665  int degf= deg(f);
2666  int k= 0;
2667  int degfSubK, repLength, j;
2668  while (degf >= k)
2669  {
2670  degfSubK= degf - k;
2671  if (degfSubK >= d)
2672  repLength= d;
2673  else
2674  repLength= degfSubK + 1;
2675 
2676  buf.rep.SetLength ((long) repLength);
2677  bufp= buf.rep.elts();
2678  for (j= 0; j < repLength; j++)
2679  bufp [j]= fp [j + k];
2680  buf.normalize();
2681 
2682  result += convertNTLzzpX2CF (buf, x)*power (y, i);
2683  i++;
2684  k= d*i;
2685  }
2686 
2687  return result;
2688 }
2689 
2690 // assumes input to be reduced mod M and to be an element of Fp
2692 mulMod2NTLFpReci (const CanonicalForm& F, const CanonicalForm& G, const
2693  CanonicalForm& M)
2694 {
2695  int d1= degree (F, 1) + degree (G, 1) + 1;
2696  d1 /= 2;
2697  d1 += 1;
2698 
2699  zz_pX F1, F2;
2700  kronSubReciproFp (F1, F2, F, d1);
2701  zz_pX G1, G2;
2702  kronSubReciproFp (G1, G2, G, d1);
2703 
2704  int k= d1*degree (M);
2705  MulTrunc (F1, F1, G1, (long) k);
2706 
2707  int degtailF= degree (tailcoeff (F), 1);
2708  int degtailG= degree (tailcoeff (G), 1);
2709  int taildegF= taildegree (F);
2710  int taildegG= taildegree (G);
2711  int b= k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2712 
2713  reverse (F2, F2);
2714  reverse (G2, G2);
2715  MulTrunc (F2, F2, G2, b + 1);
2716  reverse (F2, F2, b);
2717 
2718  int d2= tmax (deg (F2)/d1, deg (F1)/d1);
2719  return reverseSubstReciproFp (F1, F2, d1, d2);
2720 }
2721 
2722 //Kronecker substitution
2724 mulMod2NTLFp (const CanonicalForm& F, const CanonicalForm& G, const
2725  CanonicalForm& M)
2726 {
2727  CanonicalForm A= F;
2728  CanonicalForm B= G;
2729 
2730  int degAx= degree (A, 1);
2731  int degAy= degree (A, 2);
2732  int degBx= degree (B, 1);
2733  int degBy= degree (B, 2);
2734  int d1= degAx + 1 + degBx;
2735  int d2= tmax (degAy, degBy);
2736 
2737  if (d1 > 128 && d2 > 160 && (degAy == degBy) && (2*degAy > degree (M)))
2738  return mulMod2NTLFpReci (A, B, M);
2739 
2740  zz_pX NTLA= kronSubFp (A, d1);
2741  zz_pX NTLB= kronSubFp (B, d1);
2742 
2743  int k= d1*degree (M);
2744  MulTrunc (NTLA, NTLA, NTLB, (long) k);
2745 
2746  A= reverseSubstFp (NTLA, d1);
2747 
2748  return A;
2749 }
2750 #endif
2751 
2752 #if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2753 // assumes input to be reduced mod M and to be an element of Fq not Fp
2755 mulMod2NTLFqReci (const CanonicalForm& F, const CanonicalForm& G, const
2756  CanonicalForm& M, const Variable& alpha)
2757 {
2758  int d1= degree (F, 1) + degree (G, 1) + 1;
2759  d1 /= 2;
2760  d1 += 1;
2761 
2762  zz_pEX F1, F2;
2763  kronSubReciproFq (F1, F2, F, d1, alpha);
2764  zz_pEX G1, G2;
2765  kronSubReciproFq (G1, G2, G, d1, alpha);
2766 
2767  int k= d1*degree (M);
2768  MulTrunc (F1, F1, G1, (long) k);
2769 
2770  int degtailF= degree (tailcoeff (F), 1);
2771  int degtailG= degree (tailcoeff (G), 1);
2772  int taildegF= taildegree (F);
2773  int taildegG= taildegree (G);
2774  int b= k + degtailF + degtailG - d1*(2+taildegF+taildegG);
2775 
2776  reverse (F2, F2);
2777  reverse (G2, G2);
2778  MulTrunc (F2, F2, G2, b + 1);
2779  reverse (F2, F2, b);
2780 
2781  int d2= tmax (deg (F2)/d1, deg (F1)/d1);
2782  return reverseSubstReciproFq (F1, F2, d1, d2, alpha);
2783 }
2784 #endif
2785 
2786 #ifdef HAVE_FLINT
2788 mulMod2FLINTFp (const CanonicalForm& F, const CanonicalForm& G, const
2789  CanonicalForm& M);
2790 #endif
2791 
2793 mulMod2NTLFq (const CanonicalForm& F, const CanonicalForm& G, const
2794  CanonicalForm& M)
2795 {
2796  Variable alpha;
2797  CanonicalForm A= F;
2798  CanonicalForm B= G;
2799 
2800  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
2801  {
2802 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2803  nmod_poly_t FLINTmipo;
2804  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
2805 
2806  fq_nmod_ctx_t fq_con;
2807  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
2808 
2809  A= mulMod2FLINTFq (A, B, M, alpha, fq_con);
2810  nmod_poly_clear (FLINTmipo);
2812 #else
2813  int degAx= degree (A, 1);
2814  int degAy= degree (A, 2);
2815  int degBx= degree (B, 1);
2816  int degBy= degree (B, 2);
2817  int d1= degAx + degBx + 1;
2818  int d2= tmax (degAy, degBy);
2820  {
2822  zz_p::init (getCharacteristic());
2823  }
2824  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
2825  zz_pE::init (NTLMipo);
2826 
2827  int degMipo= degree (getMipo (alpha));
2828  if ((d1 > 128/degMipo) && (d2 > 160/degMipo) && (degAy == degBy) &&
2829  (2*degAy > degree (M)))
2830  return mulMod2NTLFqReci (A, B, M, alpha);
2831 
2832  zz_pEX NTLA= kronSubFq (A, d1, alpha);
2833  zz_pEX NTLB= kronSubFq (B, d1, alpha);
2834 
2835  int k= d1*degree (M);
2836 
2837  MulTrunc (NTLA, NTLA, NTLB, (long) k);
2838 
2839  A= reverseSubstFq (NTLA, d1, alpha);
2840 #endif
2841  }
2842  else
2843  {
2844 #ifdef HAVE_FLINT
2845  A= mulMod2FLINTFp (A, B, M);
2846 #else
2847  A= mulMod2NTLFp (A, B, M);
2848 #endif
2849  }
2850  return A;
2851 }
2852 
2854  const CanonicalForm& M)
2855 {
2856  if (A.isZero() || B.isZero())
2857  return 0;
2858 
2859  ASSERT (M.isUnivariate(), "M must be univariate");
2860 
2861  CanonicalForm F= mod (A, M);
2862  CanonicalForm G= mod (B, M);
2863  if (F.inCoeffDomain())
2864  return G*F;
2865  if (G.inCoeffDomain())
2866  return F*G;
2867 
2868  Variable y= M.mvar();
2869  int degF= degree (F, y);
2870  int degG= degree (G, y);
2871 
2872  if ((degF < 1 && degG < 1) && (F.isUnivariate() && G.isUnivariate()) &&
2873  (F.level() == G.level()))
2874  {
2875  CanonicalForm result= mulNTL (F, G);
2876  return mod (result, M);
2877  }
2878  else if (degF <= 1 && degG <= 1)
2879  {
2880  CanonicalForm result= F*G;
2881  return mod (result, M);
2882  }
2883 
2884  int sizeF= size (F);
2885  int sizeG= size (G);
2886 
2887  int fallBackToNaive= 50;
2888  if (sizeF < fallBackToNaive || sizeG < fallBackToNaive)
2889  {
2890  if (sizeF < sizeG)
2891  return mod (G*F, M);
2892  else
2893  return mod (F*G, M);
2894  }
2895 
2896 #ifdef HAVE_FLINT
2897  if (getCharacteristic() == 0)
2898  return mulMod2FLINTQa (F, G, M);
2899 #endif
2900 
2902  (((degF-degG) < 50 && degF > degG) || ((degG-degF) < 50 && degF <= degG)))
2903  return mulMod2NTLFq (F, G, M);
2904 
2905  int m= (int) ceil (degree (M)/2.0);
2906  if (degF >= m || degG >= m)
2907  {
2908  CanonicalForm MLo= power (y, m);
2909  CanonicalForm MHi= power (y, degree (M) - m);
2910  CanonicalForm F0= mod (F, MLo);
2911  CanonicalForm F1= div (F, MLo);
2912  CanonicalForm G0= mod (G, MLo);
2913  CanonicalForm G1= div (G, MLo);
2914  CanonicalForm F0G1= mulMod2 (F0, G1, MHi);
2915  CanonicalForm F1G0= mulMod2 (F1, G0, MHi);
2916  CanonicalForm F0G0= mulMod2 (F0, G0, M);
2917  return F0G0 + MLo*(F0G1 + F1G0);
2918  }
2919  else
2920  {
2921  m= (int) ceil (tmax (degF, degG)/2.0);
2922  CanonicalForm yToM= power (y, m);
2923  CanonicalForm F0= mod (F, yToM);
2924  CanonicalForm F1= div (F, yToM);
2925  CanonicalForm G0= mod (G, yToM);
2926  CanonicalForm G1= div (G, yToM);
2927  CanonicalForm H00= mulMod2 (F0, G0, M);
2928  CanonicalForm H11= mulMod2 (F1, G1, M);
2929  CanonicalForm H01= mulMod2 (F0 + F1, G0 + G1, M);
2930  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
2931  }
2932  DEBOUTLN (cerr, "fatal end in mulMod2");
2933 }
2934 
2935 // end bivariate polys
2936 //**********************
2937 // multivariate polys
2938 
2940 {
2941  CanonicalForm A= F;
2942  for (CFListIterator i= M; i.hasItem(); i++)
2943  A= mod (A, i.getItem());
2944  return A;
2945 }
2946 
2948  const CFList& MOD)
2949 {
2950  if (A.isZero() || B.isZero())
2951  return 0;
2952 
2953  if (MOD.length() == 1)
2954  return mulMod2 (A, B, MOD.getLast());
2955 
2956  CanonicalForm M= MOD.getLast();
2957  CanonicalForm F= mod (A, M);
2958  CanonicalForm G= mod (B, M);
2959  if (F.inCoeffDomain())
2960  return G*F;
2961  if (G.inCoeffDomain())
2962  return F*G;
2963 
2964  int sizeF= size (F);
2965  int sizeG= size (G);
2966 
2967  if (sizeF / MOD.length() < 100 || sizeG / MOD.length() < 100)
2968  {
2969  if (sizeF < sizeG)
2970  return mod (G*F, MOD);
2971  else
2972  return mod (F*G, MOD);
2973  }
2974 
2975  Variable y= M.mvar();
2976  int degF= degree (F, y);
2977  int degG= degree (G, y);
2978 
2979  if ((degF <= 1 && F.level() <= M.level()) &&
2980  (degG <= 1 && G.level() <= M.level()))
2981  {
2982  CFList buf= MOD;
2983  buf.removeLast();
2984  if (degF == 1 && degG == 1)
2985  {
2986  CanonicalForm F0= mod (F, y);
2987  CanonicalForm F1= div (F, y);
2988  CanonicalForm G0= mod (G, y);
2989  CanonicalForm G1= div (G, y);
2990  if (degree (M) > 2)
2991  {
2992  CanonicalForm H00= mulMod (F0, G0, buf);
2993  CanonicalForm H11= mulMod (F1, G1, buf);
2994  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, buf);
2995  return H11*y*y + (H01 - H00 - H11)*y + H00;
2996  }
2997  else //here degree (M) == 2
2998  {
2999  buf.append (y);
3000  CanonicalForm F0G1= mulMod (F0, G1, buf);
3001  CanonicalForm F1G0= mulMod (F1, G0, buf);
3002  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3003  CanonicalForm result= F0G0 + y*(F0G1 + F1G0);
3004  return result;
3005  }
3006  }
3007  else if (degF == 1 && degG == 0)
3008  return mulMod (div (F, y), G, buf)*y + mulMod (mod (F, y), G, buf);
3009  else if (degF == 0 && degG == 1)
3010  return mulMod (div (G, y), F, buf)*y + mulMod (mod (G, y), F, buf);
3011  else
3012  return mulMod (F, G, buf);
3013  }
3014  int m= (int) ceil (degree (M)/2.0);
3015  if (degF >= m || degG >= m)
3016  {
3017  CanonicalForm MLo= power (y, m);
3018  CanonicalForm MHi= power (y, degree (M) - m);
3019  CanonicalForm F0= mod (F, MLo);
3020  CanonicalForm F1= div (F, MLo);
3021  CanonicalForm G0= mod (G, MLo);
3022  CanonicalForm G1= div (G, MLo);
3023  CFList buf= MOD;
3024  buf.removeLast();
3025  buf.append (MHi);
3026  CanonicalForm F0G1= mulMod (F0, G1, buf);
3027  CanonicalForm F1G0= mulMod (F1, G0, buf);
3028  CanonicalForm F0G0= mulMod (F0, G0, MOD);
3029  return F0G0 + MLo*(F0G1 + F1G0);
3030  }
3031  else
3032  {
3033  m= (int) ceil (tmin (degF, degG)/2.0);
3034  CanonicalForm yToM= power (y, m);
3035  CanonicalForm F0= mod (F, yToM);
3036  CanonicalForm F1= div (F, yToM);
3037  CanonicalForm G0= mod (G, yToM);
3038  CanonicalForm G1= div (G, yToM);
3039  CanonicalForm H00= mulMod (F0, G0, MOD);
3040  CanonicalForm H11= mulMod (F1, G1, MOD);
3041  CanonicalForm H01= mulMod (F0 + F1, G0 + G1, MOD);
3042  return H11*yToM*yToM + (H01 - H11 - H00)*yToM + H00;
3043  }
3044  DEBOUTLN (cerr, "fatal end in mulMod");
3045 }
3046 
3048 {
3049  if (L.isEmpty())
3050  return 1;
3051  int l= L.length();
3052  if (l == 1)
3053  return mod (L.getFirst(), M);
3054  else if (l == 2) {
3056  return result;
3057  }
3058  else
3059  {
3060  l /= 2;
3061  CFList tmp1, tmp2;
3062  CFListIterator i= L;
3064  for (int j= 1; j <= l; j++, i++)
3065  tmp1.append (i.getItem());
3066  tmp2= Difference (L, tmp1);
3067  buf1= prodMod (tmp1, M);
3068  buf2= prodMod (tmp2, M);
3070  return result;
3071  }
3072 }
3073 
3075 {
3076  if (L.isEmpty())
3077  return 1;
3078  else if (L.length() == 1)
3079  return L.getFirst();
3080  else if (L.length() == 2)
3081  return mulMod (L.getFirst(), L.getLast(), M);
3082  else
3083  {
3084  int l= L.length()/2;
3085  CFListIterator i= L;
3086  CFList tmp1, tmp2;
3088  for (int j= 1; j <= l; j++, i++)
3089  tmp1.append (i.getItem());
3090  tmp2= Difference (L, tmp1);
3091  buf1= prodMod (tmp1, M);
3092  buf2= prodMod (tmp2, M);
3093  return mulMod (buf1, buf2, M);
3094  }
3095 }
3096 
3097 // end multivariate polys
3098 //***************************
3099 // division
3100 
3102 {
3103  if (d == 0)
3104  return F;
3105  CanonicalForm A= F;
3106  Variable y= Variable (2);
3107  Variable x= Variable (1);
3108  if (degree (A, x) > 0)
3109  {
3110  A= swapvar (A, x, y);
3111  CanonicalForm result= 0;
3112  CFIterator i= A;
3113  while (d - i.exp() < 0)
3114  i++;
3115 
3116  for (; i.hasTerms() && (d - i.exp() >= 0); i++)
3117  result += swapvar (i.coeff(),x,y)*power (x, d - i.exp());
3118  return result;
3119  }
3120  else
3121  return A*power (x, d);
3122 }
3123 
3125 newtonInverse (const CanonicalForm& F, const int n, const CanonicalForm& M)
3126 {
3127  int l= ilog2(n);
3128 
3129  CanonicalForm g= mod (F, M)[0] [0];
3130 
3131  ASSERT (!g.isZero(), "expected a unit");
3132 
3133  Variable alpha;
3134 
3135  if (!g.isOne())
3136  g = 1/g;
3137  Variable x= Variable (1);
3139  int exp= 0;
3140  if (n & 1)
3141  {
3142  result= g;
3143  exp= 1;
3144  }
3145  CanonicalForm h;
3146 
3147  for (int i= 1; i <= l; i++)
3148  {
3149  h= mulMod2 (g, mod (F, power (x, (1 << i))), M);
3150  h= mod (h, power (x, (1 << i)) - 1);
3151  h= div (h, power (x, (1 << (i - 1))));
3152  h= mod (h, M);
3153  g -= power (x, (1 << (i - 1)))*
3154  mod (mulMod2 (g, h, M), power (x, (1 << (i - 1))));
3155 
3156  if (n & (1 << i))
3157  {
3158  if (exp)
3159  {
3160  h= mulMod2 (result, mod (F, power (x, exp + (1 << i))), M);
3161  h= mod (h, power (x, exp + (1 << i)) - 1);
3162  h= div (h, power (x, exp));
3163  h= mod (h, M);
3164  result -= power(x, exp)*mod (mulMod2 (g, h, M),
3165  power (x, (1 << i)));
3166  exp += (1 << i);
3167  }
3168  else
3169  {
3170  exp= (1 << i);
3171  result= g;
3172  }
3173  }
3174  }
3175 
3176  return result;
3177 }
3178 
3181  M)
3182 {
3183  ASSERT (getCharacteristic() > 0, "positive characteristic expected");
3184 
3185  CanonicalForm A= mod (F, M);
3186  CanonicalForm B= mod (G, M);
3187 
3188  Variable x= Variable (1);
3189  int degA= degree (A, x);
3190  int degB= degree (B, x);
3191  int m= degA - degB;
3192  if (m < 0)
3193  return 0;
3194 
3195  Variable v;
3196  CanonicalForm Q;
3197  if (degB < 1 || CFFactory::gettype() == GaloisFieldDomain)
3198  {
3199  CanonicalForm R;
3200  divrem2 (A, B, Q, R, M);
3201  }
3202  else
3203  {
3204  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3205  {
3206  CanonicalForm R= reverse (A, degA);
3207  CanonicalForm revB= reverse (B, degB);
3208  revB= newtonInverse (revB, m + 1, M);
3209  Q= mulMod2 (R, revB, M);
3210  Q= mod (Q, power (x, m + 1));
3211  Q= reverse (Q, m);
3212  }
3213  else
3214  {
3215  Variable y= Variable (2);
3216 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3217  nmod_poly_t FLINTmipo;
3218  fq_nmod_ctx_t fq_con;
3219 
3220  nmod_poly_init (FLINTmipo, getCharacteristic());
3221  convertFacCF2nmod_poly_t (FLINTmipo, M);
3222 
3223  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3224 
3225 
3226  fq_nmod_poly_t FLINTA, FLINTB;
3227  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3228  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3229 
3230  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3231 
3232  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3233 
3234  fq_nmod_poly_clear (FLINTA, fq_con);
3235  fq_nmod_poly_clear (FLINTB, fq_con);
3236  nmod_poly_clear (FLINTmipo);
3238 #else
3239  bool zz_pEbak= zz_pE::initialized();
3240  zz_pEBak bak;
3241  if (zz_pEbak)
3242  bak.save();
3243  zz_pX mipo= convertFacCF2NTLzzpX (M);
3244  zz_pEX NTLA, NTLB;
3245  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3246  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3247  div (NTLA, NTLA, NTLB);
3248  Q= convertNTLzz_pEX2CF (NTLA, x, y);
3249  if (zz_pEbak)
3250  bak.restore();
3251 #endif
3252  }
3253  }
3254 
3255  return Q;
3256 }
3257 
3258 void
3260  CanonicalForm& R, const CanonicalForm& M)
3261 {
3262  CanonicalForm A= mod (F, M);
3263  CanonicalForm B= mod (G, M);
3264  Variable x= Variable (1);
3265  int degA= degree (A, x);
3266  int degB= degree (B, x);
3267  int m= degA - degB;
3268 
3269  if (m < 0)
3270  {
3271  R= A;
3272  Q= 0;
3273  return;
3274  }
3275 
3276  Variable v;
3277  if (degB <= 1 || CFFactory::gettype() == GaloisFieldDomain)
3278  {
3279  divrem2 (A, B, Q, R, M);
3280  }
3281  else
3282  {
3283  if (hasFirstAlgVar (A, v) || hasFirstAlgVar (B, v))
3284  {
3285  R= reverse (A, degA);
3286 
3287  CanonicalForm revB= reverse (B, degB);
3288  revB= newtonInverse (revB, m + 1, M);
3289  Q= mulMod2 (R, revB, M);
3290 
3291  Q= mod (Q, power (x, m + 1));
3292  Q= reverse (Q, m);
3293 
3294  R= A - mulMod2 (Q, B, M);
3295  }
3296  else
3297  {
3298  Variable y= Variable (2);
3299 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3300  nmod_poly_t FLINTmipo;
3301  fq_nmod_ctx_t fq_con;
3302 
3303  nmod_poly_init (FLINTmipo, getCharacteristic());
3304  convertFacCF2nmod_poly_t (FLINTmipo, M);
3305 
3306  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3307 
3308  fq_nmod_poly_t FLINTA, FLINTB;
3309  convertFacCF2Fq_nmod_poly_t (FLINTA, swapvar (A, x, y), fq_con);
3310  convertFacCF2Fq_nmod_poly_t (FLINTB, swapvar (B, x, y), fq_con);
3311 
3312  fq_nmod_poly_divrem (FLINTA, FLINTB, FLINTA, FLINTB, fq_con);
3313 
3314  Q= convertFq_nmod_poly_t2FacCF (FLINTA, x, y, fq_con);
3315  R= convertFq_nmod_poly_t2FacCF (FLINTB, x, y, fq_con);
3316 
3317  fq_nmod_poly_clear (FLINTA, fq_con);
3318  fq_nmod_poly_clear (FLINTB, fq_con);
3319  nmod_poly_clear (FLINTmipo);
3321 #else
3322  zz_pX mipo= convertFacCF2NTLzzpX (M);
3323  zz_pEX NTLA, NTLB;
3324  NTLA= convertFacCF2NTLzz_pEX (swapvar (A, x, y), mipo);
3325  NTLB= convertFacCF2NTLzz_pEX (swapvar (B, x, y), mipo);
3326  zz_pEX NTLQ, NTLR;
3327  DivRem (NTLQ, NTLR, NTLA, NTLB);
3328  Q= convertNTLzz_pEX2CF (NTLQ, x, y);
3329  R= convertNTLzz_pEX2CF (NTLR, x, y);
3330 #endif
3331  }
3332  }
3333 }
3334 
3335 static inline
3336 CFList split (const CanonicalForm& F, const int m, const Variable& x)
3337 {
3338  CanonicalForm A= F;
3339  CanonicalForm buf= 0;
3340  bool swap= false;
3341  if (degree (A, x) <= 0)
3342  return CFList(A);
3343  else if (x.level() != A.level())
3344  {
3345  swap= true;
3346  A= swapvar (A, x, A.mvar());
3347  }
3348 
3349  int j= (int) floor ((double) degree (A)/ m);
3350  CFList result;
3351  CFIterator i= A;
3352  for (; j >= 0; j--)
3353  {
3354  while (i.hasTerms() && i.exp() - j*m >= 0)
3355  {
3356  if (swap)
3357  buf += i.coeff()*power (A.mvar(), i.exp() - j*m);
3358  else
3359  buf += i.coeff()*power (x, i.exp() - j*m);
3360  i++;
3361  }
3362  if (swap)
3363  result.append (swapvar (buf, x, F.mvar()));
3364  else
3365  result.append (buf);
3366  buf= 0;
3367  }
3368  return result;
3369 }
3370 
3371 static inline
3372 void divrem32 (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& Q,
3373  CanonicalForm& R, const CFList& M);
3374 
3375 static inline
3377  CanonicalForm& R, const CFList& M)
3378 {
3379  CanonicalForm A= mod (F, M);
3380  CanonicalForm B= mod (G, M);
3381  Variable x= Variable (1);
3382  int degB= degree (B, x);
3383  int degA= degree (A, x);
3384  if (degA < degB)
3385  {
3386  Q= 0;
3387  R= A;
3388  return;
3389  }
3390  if (degB < 1)
3391  {
3392  divrem (A, B, Q, R);
3393  Q= mod (Q, M);
3394  R= mod (R, M);
3395  return;
3396  }
3397  int m= (int) ceil ((double) (degB + 1)/2.0) + 1;
3398  ASSERT (4*m >= degA, "expected degree (F, 1) < 2*degree (G, 1)");
3399  CFList splitA= split (A, m, x);
3400  if (splitA.length() == 3)
3401  splitA.insert (0);
3402  if (splitA.length() == 2)
3403  {
3404  splitA.insert (0);
3405  splitA.insert (0);
3406  }
3407  if (splitA.length() == 1)
3408  {
3409  splitA.insert (0);
3410  splitA.insert (0);
3411  splitA.insert (0);
3412  }
3413 
3414  CanonicalForm xToM= power (x, m);
3415 
3416  CFListIterator i= splitA;
3417  CanonicalForm H= i.getItem();
3418  i++;
3419  H *= xToM;
3420  H += i.getItem();
3421  i++;
3422  H *= xToM;
3423  H += i.getItem();
3424  i++;
3425 
3426  divrem32 (H, B, Q, R, M);
3427 
3428  CFList splitR= split (R, m, x);
3429  if (splitR.length() == 1)
3430  splitR.insert (0);
3431 
3432  H= splitR.getFirst();
3433  H *= xToM;
3434  H += splitR.getLast();
3435  H *= xToM;
3436  H += i.getItem();
3437 
3438  CanonicalForm bufQ;
3439  divrem32 (H, B, bufQ, R, M);
3440 
3441  Q *= xToM;
3442  Q += bufQ;
3443  return;
3444 }
3445 
3446 static inline
3448  CanonicalForm& R, const CFList& M)
3449 {
3450  CanonicalForm A= mod (F, M);
3451  CanonicalForm B= mod (G, M);
3452  Variable x= Variable (1);
3453  int degB= degree (B, x);
3454  int degA= degree (A, x);
3455  if (degA < degB)
3456  {
3457  Q= 0;
3458  R= A;
3459  return;
3460  }
3461  if (degB < 1)
3462  {
3463  divrem (A, B, Q, R);
3464  Q= mod (Q, M);
3465  R= mod (R, M);
3466  return;
3467  }
3468  int m= (int) ceil ((double) (degB + 1)/ 2.0);
3469  ASSERT (3*m > degA, "expected degree (F, 1) < 3*degree (G, 1)");
3470  CFList splitA= split (A, m, x);
3471  CFList splitB= split (B, m, x);
3472 
3473  if (splitA.length() == 2)
3474  {
3475  splitA.insert (0);
3476  }
3477  if (splitA.length() == 1)
3478  {
3479  splitA.insert (0);
3480  splitA.insert (0);
3481  }
3482  CanonicalForm xToM= power (x, m);
3483 
3484  CanonicalForm H;
3485  CFListIterator i= splitA;
3486  i++;
3487 
3488  if (degree (splitA.getFirst(), x) < degree (splitB.getFirst(), x))
3489  {
3490  H= splitA.getFirst()*xToM + i.getItem();
3491  divrem21 (H, splitB.getFirst(), Q, R, M);
3492  }
3493  else
3494  {
3495  R= splitA.getFirst()*xToM + i.getItem() + splitB.getFirst() -
3496  splitB.getFirst()*xToM;
3497  Q= xToM - 1;
3498  }
3499 
3500  H= mulMod (Q, splitB.getLast(), M);
3501 
3502  R= R*xToM + splitA.getLast() - H;
3503 
3504  while (degree (R, x) >= degB)
3505  {
3506  xToM= power (x, degree (R, x) - degB);
3507  Q += LC (R, x)*xToM;
3508  R -= mulMod (LC (R, x), B, M)*xToM;
3509  Q= mod (Q, M);
3510  R= mod (R, M);
3511  }
3512 
3513  return;
3514 }
3515 
3517  CanonicalForm& R, const CanonicalForm& M)
3518 {
3519  CanonicalForm A= mod (F, M);
3520  CanonicalForm B= mod (G, M);
3521 
3522  if (B.inCoeffDomain())
3523  {
3524  divrem (A, B, Q, R);
3525  return;
3526  }
3527  if (A.inCoeffDomain() && !B.inCoeffDomain())
3528  {
3529  Q= 0;
3530  R= A;
3531  return;
3532  }
3533 
3534  if (B.level() < A.level())
3535  {
3536  divrem (A, B, Q, R);
3537  return;
3538  }
3539  if (A.level() > B.level())
3540  {
3541  R= A;
3542  Q= 0;
3543  return;
3544  }
3545  if (B.level() == 1 && B.isUnivariate())
3546  {
3547  divrem (A, B, Q, R);
3548  return;
3549  }
3550 
3551  Variable x= Variable (1);
3552  int degB= degree (B, x);
3553  if (degB > degree (A, x))
3554  {
3555  Q= 0;
3556  R= A;
3557  return;
3558  }
3559 
3560  CFList splitA= split (A, degB, x);
3561 
3562  CanonicalForm xToDegB= power (x, degB);
3563  CanonicalForm H, bufQ;
3564  Q= 0;
3565  CFListIterator i= splitA;
3566  H= i.getItem()*xToDegB;
3567  i++;
3568  H += i.getItem();
3569  CFList buf;
3570  while (i.hasItem())
3571  {
3572  buf= CFList (M);
3573  divrem21 (H, B, bufQ, R, buf);
3574  i++;
3575  if (i.hasItem())
3576  H= R*xToDegB + i.getItem();
3577  Q *= xToDegB;
3578  Q += bufQ;
3579  }
3580  return;
3581 }
3582 
3584  CanonicalForm& R, const CFList& MOD)
3585 {
3586  CanonicalForm A= mod (F, MOD);
3587  CanonicalForm B= mod (G, MOD);
3588  Variable x= Variable (1);
3589  int degB= degree (B, x);
3590  if (degB > degree (A, x))
3591  {
3592  Q= 0;
3593  R= A;
3594  return;
3595  }
3596 
3597  if (degB <= 0)
3598  {
3599  divrem (A, B, Q, R);
3600  Q= mod (Q, MOD);
3601  R= mod (R, MOD);
3602  return;
3603  }
3604  CFList splitA= split (A, degB, x);
3605 
3606  CanonicalForm xToDegB= power (x, degB);
3607  CanonicalForm H, bufQ;
3608  Q= 0;
3609  CFListIterator i= splitA;
3610  H= i.getItem()*xToDegB;
3611  i++;
3612  H += i.getItem();
3613  while (i.hasItem())
3614  {
3615  divrem21 (H, B, bufQ, R, MOD);
3616  i++;
3617  if (i.hasItem())
3618  H= R*xToDegB + i.getItem();
3619  Q *= xToDegB;
3620  Q += bufQ;
3621  }
3622  return;
3623 }
3624 
3625 bool
3627 {
3628  if (B.isZero())
3629  return true;
3630  if (A.isZero())
3631  return false;
3633  return fdivides (A, B);
3634  int p= getCharacteristic();
3635  if (A.inCoeffDomain() || B.inCoeffDomain())
3636  {
3637  if (A.inCoeffDomain())
3638  return true;
3639  else
3640  return false;
3641  }
3642  if (p > 0)
3643  {
3644  if (fac_NTL_char != p)
3645  {
3646  fac_NTL_char= p;
3647  zz_p::init (p);
3648  }
3649  Variable alpha;
3650  if (hasFirstAlgVar (A, alpha) || hasFirstAlgVar (B, alpha))
3651  {
3652 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3653  nmod_poly_t FLINTmipo;
3654  fq_nmod_ctx_t fq_con;
3655 
3656  nmod_poly_init (FLINTmipo, getCharacteristic());
3657  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
3658 
3659  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
3660 
3661  fq_nmod_poly_t FLINTA, FLINTB;
3664  int result= fq_nmod_poly_divides (FLINTA, FLINTB, FLINTA, fq_con);
3665  fq_nmod_poly_clear (FLINTA, fq_con);
3666  fq_nmod_poly_clear (FLINTB, fq_con);
3667  nmod_poly_clear (FLINTmipo);
3669  return result;
3670 #else
3671  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
3672  zz_pE::init (NTLMipo);
3673  zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
3674  zz_pEX NTLB= convertFacCF2NTLzz_pEX (B, NTLMipo);
3675  return divide (NTLB, NTLA);
3676 #endif
3677  }
3678 #ifdef HAVE_FLINT
3679  nmod_poly_t FLINTA, FLINTB;
3680  convertFacCF2nmod_poly_t (FLINTA, A);
3681  convertFacCF2nmod_poly_t (FLINTB, B);
3682  nmod_poly_divrem (FLINTB, FLINTA, FLINTB, FLINTA);
3683  bool result= nmod_poly_is_zero (FLINTA);
3684  nmod_poly_clear (FLINTA);
3685  nmod_poly_clear (FLINTB);
3686  return result;
3687 #else
3688  zz_pX NTLA= convertFacCF2NTLzzpX (A);
3689  zz_pX NTLB= convertFacCF2NTLzzpX (B);
3690  return divide (NTLB, NTLA);
3691 #endif
3692  }
3693 #ifdef HAVE_FLINT
3694  Variable alpha;
3695  bool isRat= isOn (SW_RATIONAL);
3696  if (!isRat)
3697  On (SW_RATIONAL);
3698  if (!hasFirstAlgVar (A, alpha) && !hasFirstAlgVar (B, alpha))
3699  {
3700  fmpq_poly_t FLINTA,FLINTB;
3701  convertFacCF2Fmpq_poly_t (FLINTA, A);
3702  convertFacCF2Fmpq_poly_t (FLINTB, B);
3703  fmpq_poly_rem (FLINTA, FLINTB, FLINTA);
3704  bool result= fmpq_poly_is_zero (FLINTA);
3705  fmpq_poly_clear (FLINTA);
3706  fmpq_poly_clear (FLINTB);
3707  if (!isRat)
3708  Off (SW_RATIONAL);
3709  return result;
3710  }
3711  CanonicalForm Q, R;
3712  newtonDivrem (B, A, Q, R);
3713  if (!isRat)
3714  Off (SW_RATIONAL);
3715  return R.isZero();
3716 #else
3717  bool isRat= isOn (SW_RATIONAL);
3718  if (!isRat)
3719  On (SW_RATIONAL);
3720  bool result= fdivides (A, B);
3721  if (!isRat)
3722  Off (SW_RATIONAL);
3723  return result; //maybe NTL?
3724 #endif
3725 }
3726 
3727 // end division
3728 
3729 #endif
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
CanonicalForm convertFq_t2FacCF(const fq_t poly, const Variable &alpha)
conversion of a FLINT element of F_q with non-word size p to a CanonicalForm with alg...
nmod_poly_init(FLINTmipo, getCharacteristic())
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:667
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
Definition: facMul.cc:62
Conversion to and from NTL.
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:574
const poly a
Definition: syzextra.cc:212
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm fp
Definition: cfModGcd.cc:4043
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3626
void convertCF2Fmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t
Definition: FLINTconvert.cc:61
int isEmpty() const
Definition: ftmpl_list.cc:267
void Off(int sw)
switches
CanonicalForm reverseSubstReciproFq(const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d, int k, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1648
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1138
CanonicalForm buf1
Definition: facFqBivar.cc:71
some useful template functions.
functions to print debug output
void convertFacCF2Fq_t(fq_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory element of F_q (for non-word size p) to a FLINT fq_t
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:1115
void divrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel...
Definition: facMul.cc:3583
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
Definition: NTLconvert.cc:246
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:1957
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
Definition: NTLconvert.cc:1039
factory&#39;s main class
Definition: canonicalform.h:75
nmod_poly_clear(FLINTmipo)
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
Definition: facMul.cc:1921
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:251
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:129
g
Definition: cfModGcd.cc:4031
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:688
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1255
#define Q
Definition: sirandom.c:25
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
Definition: facMul.cc:1366
CanonicalForm convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT poly over Fq to a CanonicalForm with alg. variable alpha and polynomial variabl...
static TreeM * G
Definition: janet.cc:38
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
static void divrem32(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3447
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm mulMod2FLINTQReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2102
fq_nmod_ctx_clear(fq_con)
T getFirst() const
Definition: ftmpl_list.cc:279
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:1995
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
Definition: facMul.cc:42
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:188
#define M
Definition: sirandom.c:24
int taildegree(const CanonicalForm &f)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
bool inBaseDomain() const
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory&#39;s default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f).
Definition: facMul.cc:407
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
Definition: facMul.cc:1529
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1117
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
Definition: NTLconvert.cc:62
int j
Definition: myNF.cc:70
CanonicalForm divNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a), if we are in GF factory&#39;s default multiplication is used. If b!= 0 and getCharacteristic() == 0 the input will be considered as elements over Z/p^k or Z/p^k[t]/(f); in this case invertiblity of Lc(G) is not checked
Definition: facMul.cc:850
The main handler for Singular numbers which are suitable for Singular polynomials.
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
Definition: si_signals.h:59
This file defines functions for fast multiplication and division with remainder.
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
Definition: facMul.cc:237
int level() const
Definition: factory.h:132
CanonicalForm modNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a)...
Definition: facMul.cc:676
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1066
bool isUnivariate() const
#define A
Definition: sirandom.c:23
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
const ring R
Definition: DebugPrint.cc:36
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
Definition: facMul.cc:99
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2853
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
CanonicalForm mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
Definition: facMul.cc:206
int m
Definition: cfEzgcd.cc:119
bool isOn(int sw)
switches
void On(int sw)
switches
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2199
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion, satisfying F=G*Q+R, deg(R) < deg(G)
Definition: facMul.cc:342
T getLast() const
Definition: ftmpl_list.cc:309
CanonicalForm H
Definition: facAbsFact.cc:64
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList tmp2
Definition: facFqBivar.cc:70
int ilog2(const CanonicalForm &a)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition: facMul.cc:376
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1886
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1094
CanonicalForm gp
Definition: cfModGcd.cc:4043
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm buf2
Definition: facFqBivar.cc:71
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
Definition: facMul.cc:3336
void divrem2(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel...
Definition: facMul.cc:3516
CanonicalForm mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2069
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
int length() const
Definition: ftmpl_list.cc:273
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
Definition: facMul.cc:3376
void convertFacCF2Fmpz_mod_poly_t(fmpz_mod_poly_t result, const CanonicalForm &f, const fmpz_t p)
conversion of a factory univariate poly over Z to a FLINT poly over Z/p (for non word size p) ...
static int gettype()
Definition: cf_factory.h:28
fq_nmod_poly_init(prod, fq_con)
#define swap(_i, _j)
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
Definition: facMul.cc:1752
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
CanonicalForm den(const CanonicalForm &f)
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:51
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
Definition: facMul.cc:1341
CFList tmp1
Definition: facFqBivar.cc:70
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2793
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
Definition: facMul.cc:2939
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
Definition: facMul.cc:170
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CanonicalForm tailcoeff(const CanonicalForm &f)
CanonicalForm convertFmpz_mod_poly_t2FacCF(const fmpz_mod_poly_t poly, const Variable &x, const modpk &b)
conversion of a FLINT poly over Z/p (for non word size p) to a CanonicalForm over Z ...
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
p exp[i]
Definition: DebugPrint.cc:39
CanonicalForm reverse(const CanonicalForm &F, int d)
Definition: facMul.cc:3101
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
mipo *int degg
Definition: facAlgExt.cc:61
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
Definition: facMul.cc:2139
void append(const T &)
Definition: ftmpl_list.cc:256
long fac_NTL_char
Definition: NTLconvert.cc:44
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
void convertFacCF2Fq_poly_t(fq_poly_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory univariate poly over F_q (for non-word size p) to a FLINT fq_poly_t ...
static Poly * h
Definition: janet.cc:978
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
Definition: facMul.cc:270
const poly b
Definition: syzextra.cc:213
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:2027
void kronSubReciproFq(fq_nmod_poly_t subA1, fq_nmod_poly_t subA2, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
Definition: facMul.cc:1296
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:281
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
Definition: facMul.cc:287
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
CanonicalForm convertFq_poly_t2FacCF(const fq_poly_t p, const Variable &x, const Variable &alpha, const fq_ctx_t ctx)
conversion of a FLINT poly over Fq (for non-word size p) to a CanonicalForm with alg. variable alpha and polynomial variable x
Header for factory&#39;s main class CanonicalForm.
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")