facFqFactorize.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqFactorize.cc
5  *
6  * This file implements functions for factoring a multivariate polynomial over
7  * a finite field.
8  *
9  * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
10  * L. Bernardin & M. Monagon. Precomputation of leading coefficients is
11  * described in "Sparse Hensel lifting" by E. Kaltofen
12  *
13  * @author Martin Lee
14  *
15  **/
16 /*****************************************************************************/
17 
18 
19 #include "config.h"
20 
21 
22 #include "cf_assert.h"
23 #include "debug.h"
24 #include "timing.h"
25 
26 #include "facFqFactorizeUtil.h"
27 #include "facFqFactorize.h"
28 #include "cf_random.h"
29 #include "facHensel.h"
30 #include "cf_irred.h"
31 #include "cf_map_ext.h"
32 #include "facSparseHensel.h"
33 #include "facMul.h"
34 #include "cfUnivarGcd.h"
35 
36 #ifdef HAVE_NTL
37 #include "NTLconvert.h"
38 
39 TIMING_DEFINE_PRINT(fac_fq_bi_factorizer)
40 TIMING_DEFINE_PRINT(fac_fq_hensel_lift)
41 TIMING_DEFINE_PRINT(fac_fq_factor_recombination)
42 TIMING_DEFINE_PRINT(fac_fq_shift_to_zero)
43 TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff)
44 TIMING_DEFINE_PRINT(fac_fq_evaluation)
45 TIMING_DEFINE_PRINT(fac_fq_recover_factors)
46 TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content)
47 TIMING_DEFINE_PRINT(fac_fq_bifactor_total)
48 TIMING_DEFINE_PRINT(fac_fq_luckswang)
49 TIMING_DEFINE_PRINT(fac_fq_lcheuristic)
50 TIMING_DEFINE_PRINT(fac_fq_content)
51 TIMING_DEFINE_PRINT(fac_fq_check_mainvar)
52 TIMING_DEFINE_PRINT(fac_fq_compress)
53 
54 
55 static inline
57 listGCD (const CFList& L);
58 
59 static inline
62 {
63  Variable x= Variable (1);
64  CanonicalForm G= swapvar (F, F.mvar(), x);
65  CFList L;
66  for (CFIterator i= G; i.hasTerms(); i++)
67  L.append (i.coeff());
68  if (L.length() == 2)
69  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
70  if (L.length() == 1)
71  return LC (F, x);
72  return swapvar (listGCD (L), F.mvar(), x);
73 }
74 
75 static inline
77 listGCD (const CFList& L)
78 {
79  if (L.length() == 0)
80  return 0;
81  if (L.length() == 1)
82  return L.getFirst();
83  if (L.length() == 2)
84  return gcd (L.getFirst(), L.getLast());
85  else
86  {
87  CFList lHi, lLo;
88  CanonicalForm resultHi, resultLo;
89  int length= L.length()/2;
90  int j= 0;
91  for (CFListIterator i= L; j < length; i++, j++)
92  lHi.append (i.getItem());
93  lLo= Difference (L, lHi);
94  resultHi= listGCD (lHi);
95  resultLo= listGCD (lLo);
96  if (resultHi.isOne() || resultLo.isOne())
97  return 1;
98  return gcd (resultHi, resultLo);
99  }
100 }
101 
102 static inline
104 myContent (const CanonicalForm& F, const Variable& x)
105 {
106  if (degree (F, x) <= 0)
107  return 1;
108  CanonicalForm G= F;
109  bool swap= false;
110  if (x != F.mvar())
111  {
112  swap= true;
113  G= swapvar (F, x, F.mvar());
114  }
115  CFList L;
116  Variable alpha;
117  for (CFIterator i= G; i.hasTerms(); i++)
118  L.append (i.coeff());
119  if (L.length() == 2)
120  {
121  if (swap)
122  return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
123  else
124  return gcd (L.getFirst(), L.getLast());
125  }
126  if (L.length() == 1)
127  {
128  return LC (F, x);
129  }
130  if (swap)
131  return swapvar (listGCD (L), F.mvar(), x);
132  else
133  return listGCD (L);
134 }
135 
137 {
138  int n= F.level();
139  int * degsf= NEW_ARRAY(int,n + 1);
140  int ** swap= new int* [n + 1];
141  for (int i= 0; i <= n; i++)
142  {
143  degsf[i]= 0;
144  swap [i]= new int [3];
145  swap [i] [0]= 0;
146  swap [i] [1]= 0;
147  swap [i] [2]= 0;
148  }
149  int i= 1;
150  n= 1;
151  degsf= degrees (F, degsf);
152 
154  while ( i <= F.level() )
155  {
156  while( degsf[i] == 0 ) i++;
157  swap[n][0]= i;
158  swap[n][1]= size (LC (F,i));
159  swap[n][2]= degsf [i];
160  if (i != n)
161  result= swapvar (result, Variable (n), Variable(i));
162  n++; i++;
163  }
164 
165  int buf1, buf2, buf3;
166  n--;
167 
168  for (i= 1; i < n; i++)
169  {
170  for (int j= 1; j < n - i + 1; j++)
171  {
172  if (swap[j][1] > swap[j + 1][1])
173  {
174  buf1= swap [j + 1] [0];
175  buf2= swap [j + 1] [1];
176  buf3= swap [j + 1] [2];
177  swap[j + 1] [0]= swap[j] [0];
178  swap[j + 1] [1]= swap[j] [1];
179  swap[j + 1] [2]= swap[j] [2];
180  swap[j][0]= buf1;
181  swap[j][1]= buf2;
182  swap[j][2]= buf3;
183  result= swapvar (result, Variable (j + 1), Variable (j));
184  }
185  else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
186  {
187  buf1= swap [j + 1] [0];
188  buf2= swap [j + 1] [1];
189  buf3= swap [j + 1] [2];
190  swap[j + 1] [0]= swap[j] [0];
191  swap[j + 1] [1]= swap[j] [1];
192  swap[j + 1] [2]= swap[j] [2];
193  swap[j][0]= buf1;
194  swap[j][1]= buf2;
195  swap[j][2]= buf3;
196  result= swapvar (result, Variable (j + 1), Variable (j));
197  }
198  }
199  }
200 
201  for (i= n; i > 0; i--)
202  {
203  if (i != swap[i] [0])
204  N.newpair (Variable (i), Variable (swap[i] [0]));
205  }
206 
207  for (i= F.level(); i >=0 ; i--)
208  delete [] swap[i];
209  delete [] swap;
210 
211  DELETE_ARRAY(degsf);
212 
213  return result;
214 }
215 
216 CFList
217 extFactorRecombination (const CFList& factors, const CanonicalForm& F,
218  const CFList& M, const ExtensionInfo& info,
219  const CFList& evaluation)
220 {
221  Variable alpha= info.getAlpha();
222  Variable beta= info.getBeta();
223  CanonicalForm gamma= info.getGamma();
224  CanonicalForm delta= info.getDelta();
225  int k= info.getGFDegree();
226  CFList source, dest;
227  if (factors.length() == 1)
228  {
229  CanonicalForm buf= reverseShift (F, evaluation);
230  return CFList (mapDown (buf, info, source, dest));
231  }
232  if (factors.length() < 1)
233  return CFList();
234 
235  int degMipoBeta= 1;
236  if (!k && beta.level() != 1)
237  degMipoBeta= degree (getMipo (beta));
238 
239  CFList T, S;
240  T= factors;
241 
242  int s= 1;
243  CFList result;
245 
246  buf= F;
247 
248  Variable x= Variable (1);
249  CanonicalForm g, LCBuf= LC (buf, x);
250  CanonicalForm buf2, quot;
251  int * v= new int [T.length()];
252  for (int i= 0; i < T.length(); i++)
253  v[i]= 0;
254  bool noSubset= false;
255  CFArray TT;
256  TT= copy (factors);
257  bool recombination= false;
258  bool trueFactor= false;
259  while (T.length() >= 2*s)
260  {
261  while (noSubset == false)
262  {
263  if (T.length() == s)
264  {
265  delete [] v;
266  if (recombination)
267  {
268  T.insert (LCBuf);
269  g= prodMod (T, M);
270  T.removeFirst();
271  result.append (g/myContent (g));
272  g= reverseShift (g, evaluation);
273  g /= Lc (g);
274  appendTestMapDown (result, g, info, source, dest);
275  return result;
276  }
277  else
278  {
279  buf= reverseShift (buf, evaluation);
280  return CFList (buf);
281  }
282  }
283 
284  S= subset (v, s, TT, noSubset);
285  if (noSubset) break;
286 
287  S.insert (LCBuf);
288  g= prodMod (S, M);
289  S.removeFirst();
290  g /= myContent (g);
291  if (fdivides (g, buf, quot))
292  {
293  buf2= reverseShift (g, evaluation);
294  buf2 /= Lc (buf2);
295  if (!k && beta == x)
296  {
297  if (degree (buf2, alpha) < degMipoBeta)
298  {
299  appendTestMapDown (result, buf2, info, source, dest);
300  buf= quot;
301  LCBuf= LC (buf, x);
302  recombination= true;
303  trueFactor= true;
304  }
305  }
306  else
307  {
308  if (!isInExtension (buf2, gamma, k, delta, source, dest))
309  {
310  appendTestMapDown (result, buf2, info, source, dest);
311  buf /= g;
312  LCBuf= LC (buf, x);
313  recombination= true;
314  trueFactor= true;
315  }
316  }
317 
318  if (trueFactor)
319  {
320  T= Difference (T, S);
321 
322  if (T.length() < 2*s || T.length() == s)
323  {
324  buf= reverseShift (buf, evaluation);
325  buf /= Lc (buf);
326  appendTestMapDown (result, buf, info, source, dest);
327  delete [] v;
328  return result;
329  }
330  trueFactor= false;
331  TT= copy (T);
332  indexUpdate (v, s, T.length(), noSubset);
333  if (noSubset) break;
334  }
335  }
336  }
337  s++;
338  if (T.length() < 2*s || T.length() == s)
339  {
340  buf= reverseShift (buf, evaluation);
341  appendTestMapDown (result, buf, info, source, dest);
342  delete [] v;
343  return result;
344  }
345  for (int i= 0; i < T.length(); i++)
346  v[i]= 0;
347  noSubset= false;
348  }
349  if (T.length() < 2*s)
350  {
351  buf= reverseShift (F, evaluation);
352  appendMapDown (result, buf, info, source, dest);
353  }
354 
355  delete [] v;
356  return result;
357 }
358 
359 CFList
360 factorRecombination (const CanonicalForm& F, const CFList& factors,
361  const CFList& M)
362 {
363  if (factors.length() == 1)
364  return CFList(F);
365  if (factors.length() < 1)
366  return CFList();
367 
368  CFList T, S;
369 
370  T= factors;
371 
372  int s= 1;
373  CFList result;
374  CanonicalForm LCBuf= LC (F, Variable (1));
375  CanonicalForm g, buf= F;
376  int * v= new int [T.length()];
377  for (int i= 0; i < T.length(); i++)
378  v[i]= 0;
379  bool noSubset= false;
380  CFArray TT;
381  TT= copy (factors);
382  Variable y= F.level() - 1;
383  bool recombination= false;
384  CanonicalForm h, quot;
385  while (T.length() >= 2*s)
386  {
387  while (noSubset == false)
388  {
389  if (T.length() == s)
390  {
391  delete [] v;
392  if (recombination)
393  {
394  T.insert (LC (buf));
395  g= prodMod (T, M);
396  result.append (g/myContent (g));
397  return result;
398  }
399  else
400  return CFList (F);
401  }
402  S= subset (v, s, TT, noSubset);
403  if (noSubset) break;
404  S.insert (LCBuf);
405  g= prodMod (S, M);
406  S.removeFirst();
407  g /= myContent (g);
408  if (fdivides (g, buf, quot))
409  {
410  recombination= true;
411  result.append (g);
412  buf= quot;
413  LCBuf= LC (buf, Variable(1));
414  T= Difference (T, S);
415  if (T.length() < 2*s || T.length() == s)
416  {
417  result.append (buf);
418  delete [] v;
419  return result;
420  }
421  TT= copy (T);
422  indexUpdate (v, s, T.length(), noSubset);
423  if (noSubset) break;
424  }
425  }
426  s++;
427  if (T.length() < 2*s || T.length() == s)
428  {
429  result.append (buf);
430  delete [] v;
431  return result;
432  }
433  for (int i= 0; i < T.length(); i++)
434  v[i]= 0;
435  noSubset= false;
436  }
437  if (T.length() < 2*s)
438  result.append (F);
439 
440  delete [] v;
441  return result;
442 }
443 
444 int
445 liftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
446  success, const int deg, const CFList& MOD, const int bound)
447 {
448  int adaptedLiftBound= 0;
449  CanonicalForm buf= F;
450  Variable y= F.mvar();
451  Variable x= Variable (1);
452  CanonicalForm LCBuf= LC (buf, x);
453  CanonicalForm g, quot;
454  CFList M= MOD;
455  M.append (power (y, deg));
456  int d= bound;
457  int e= 0;
458  int nBuf;
459  for (CFListIterator i= factors; i.hasItem(); i++)
460  {
461  g= mulMod (i.getItem(), LCBuf, M);
462  g /= myContent (g);
463  if (fdivides (g, buf, quot))
464  {
465  nBuf= degree (g, y) + degree (LC (g, 1), y);
466  d -= nBuf;
467  e= tmax (e, nBuf);
468  buf= quot;
469  LCBuf= LC (buf, x);
470  }
471  }
472  adaptedLiftBound= d;
473 
474  if (adaptedLiftBound < deg)
475  {
476  if (adaptedLiftBound < degree (F) + 1)
477  {
478  if (d == 1)
479  {
480  if (e + 1 > deg)
481  {
482  adaptedLiftBound= deg;
483  success= false;
484  }
485  else
486  {
487  success= true;
488  if (e + 1 < degree (F) + 1)
489  adaptedLiftBound= deg;
490  else
491  adaptedLiftBound= e + 1;
492  }
493  }
494  else
495  {
496  success= true;
497  adaptedLiftBound= deg;
498  }
499  }
500  else
501  {
502  success= true;
503  }
504  }
505  return adaptedLiftBound;
506 }
507 
508 int
509 extLiftBoundAdaption (const CanonicalForm& F, const CFList& factors, bool&
510  success, const ExtensionInfo& info, const CFList& eval,
511  const int deg, const CFList& MOD, const int bound)
512 {
513  Variable alpha= info.getAlpha();
514  Variable beta= info.getBeta();
515  CanonicalForm gamma= info.getGamma();
516  CanonicalForm delta= info.getDelta();
517  int k= info.getGFDegree();
518  int adaptedLiftBound= 0;
519  CanonicalForm buf= F;
520  Variable y= F.mvar();
521  Variable x= Variable (1);
522  CanonicalForm LCBuf= LC (buf, x);
523  CanonicalForm g, gg, quot;
524  CFList M= MOD;
525  M.append (power (y, deg));
526  adaptedLiftBound= 0;
527  int d= bound;
528  int e= 0;
529  int nBuf;
530  int degMipoBeta= 1;
531  if (!k && beta.level() != 1)
532  degMipoBeta= degree (getMipo (beta));
533 
534  CFList source, dest;
535  for (CFListIterator i= factors; i.hasItem(); i++)
536  {
537  g= mulMod (i.getItem(), LCBuf, M);
538  g /= myContent (g);
539  if (fdivides (g, buf, quot))
540  {
541  gg= reverseShift (g, eval);
542  gg /= Lc (gg);
543  if (!k && beta == x)
544  {
545  if (degree (gg, alpha) < degMipoBeta)
546  {
547  buf= quot;
548  nBuf= degree (g, y) + degree (LC (g, x), y);
549  d -= nBuf;
550  e= tmax (e, nBuf);
551  LCBuf= LC (buf, x);
552  }
553  }
554  else
555  {
556  if (!isInExtension (gg, gamma, k, delta, source, dest))
557  {
558  buf= quot;
559  nBuf= degree (g, y) + degree (LC (g, x), y);
560  d -= nBuf;
561  e= tmax (e, nBuf);
562  LCBuf= LC (buf, x);
563  }
564  }
565  }
566  }
567  adaptedLiftBound= d;
568 
569  if (adaptedLiftBound < deg)
570  {
571  if (adaptedLiftBound < degree (F) + 1)
572  {
573  if (d == 1)
574  {
575  if (e + 1 > deg)
576  {
577  adaptedLiftBound= deg;
578  success= false;
579  }
580  else
581  {
582  success= true;
583  if (e + 1 < degree (F) + 1)
584  adaptedLiftBound= deg;
585  else
586  adaptedLiftBound= e + 1;
587  }
588  }
589  else
590  {
591  success= true;
592  adaptedLiftBound= deg;
593  }
594  }
595  else
596  {
597  success= true;
598  }
599  }
600 
601  return adaptedLiftBound;
602 }
603 
604 CFList
605 earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
606  bool& success, const int deg, const CFList& MOD,
607  const int bound)
608 {
609  CFList result;
610  CFList T= factors;
611  CanonicalForm buf= F;
612  Variable y= F.mvar();
613  Variable x= Variable (1);
614  CanonicalForm LCBuf= LC (buf, x);
615  CanonicalForm g, quot;
616  CFList M= MOD;
617  M.append (power (y, deg));
618  adaptedLiftBound= 0;
619  int d= bound;
620  int e= 0;
621  int nBuf;
622  for (CFListIterator i= factors; i.hasItem(); i++)
623  {
624  g= mulMod (i.getItem(), LCBuf, M);
625  g /= myContent (g);
626  if (fdivides (g, buf, quot))
627  {
628  result.append (g);
629  nBuf= degree (g, y) + degree (LC (g, x), y);
630  d -= nBuf;
631  e= tmax (e, nBuf);
632  buf= quot;
633  LCBuf= LC (buf, x);
634  T= Difference (T, CFList (i.getItem()));
635  }
636  }
637  adaptedLiftBound= d;
638 
639  if (adaptedLiftBound < deg)
640  {
641  if (adaptedLiftBound < degree (F) + 1)
642  {
643  if (d == 1)
644  adaptedLiftBound= tmin (e + 1, deg);
645  else
646  adaptedLiftBound= deg;
647  }
648  factors= T;
649  F= buf;
650  success= true;
651  }
652  return result;
653 }
654 
655 CFList
656 extEarlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
657  bool& success, const ExtensionInfo& info, const CFList&
658  eval, const int deg, const CFList& MOD, const int bound)
659 {
660  Variable alpha= info.getAlpha();
661  Variable beta= info.getBeta();
662  CanonicalForm gamma= info.getGamma();
663  CanonicalForm delta= info.getDelta();
664  int k= info.getGFDegree();
665  CFList result;
666  CFList T= factors;
667  CanonicalForm buf= F;
668  Variable y= F.mvar();
669  Variable x= Variable (1);
670  CanonicalForm LCBuf= LC (buf, x);
671  CanonicalForm g, gg, quot;
672  CFList M= MOD;
673  M.append (power (y, deg));
674  adaptedLiftBound= 0;
675  int d= bound;
676  int e= 0;
677  int nBuf;
678  CFList source, dest;
679 
680  int degMipoBeta= 1;
681  if (!k && beta.level() != 1)
682  degMipoBeta= degree (getMipo (beta));
683 
684  for (CFListIterator i= factors; i.hasItem(); i++)
685  {
686  g= mulMod (i.getItem(), LCBuf, M);
687  g /= myContent (g);
688  if (fdivides (g, buf, quot))
689  {
690  gg= reverseShift (g, eval);
691  gg /= Lc (gg);
692  if (!k && beta == x)
693  {
694  if (degree (gg, alpha) < degMipoBeta)
695  {
696  appendTestMapDown (result, gg, info, source, dest);
697  buf= quot;
698  nBuf= degree (g, y) + degree (LC (g, x), y);
699  d -= nBuf;
700  e= tmax (e, nBuf);
701  LCBuf= LC (buf, x);
702  T= Difference (T, CFList (i.getItem()));
703  }
704  }
705  else
706  {
707  if (!isInExtension (gg, gamma, k, delta, source, dest))
708  {
709  appendTestMapDown (result, gg, info, source, dest);
710  buf= quot;
711  nBuf= degree (g, y) + degree (LC (g, x), y);
712  d -= nBuf;
713  e= tmax (e, nBuf);
714  LCBuf= LC (buf, x);
715  T= Difference (T, CFList (i.getItem()));
716  }
717  }
718  }
719  }
720  adaptedLiftBound= d;
721 
722  if (adaptedLiftBound < deg)
723  {
724  if (adaptedLiftBound < degree (F) + 1)
725  {
726  if (d == 1)
727  adaptedLiftBound= tmin (e + 1, deg);
728  else
729  adaptedLiftBound= deg;
730  }
731  success= true;
732  factors= T;
733  F= buf;
734  }
735  return result;
736 }
737 
738 #define CHAR_THRESHOLD 8
739 CFList
741  CFList& list, const bool& GF, bool& fail)
742 {
743  int k= F.level() - 1;
744  Variable x= Variable (1);
745  CanonicalForm LCF=LC (F, x);
746  CFList LCFeval;
747 
748  CFList result;
749  FFRandom genFF;
750  GFRandom genGF;
751  int p= getCharacteristic ();
752  if (p < CHAR_THRESHOLD)
753  {
754  if (!GF && alpha.level() == 1)
755  {
756  fail= true;
757  return CFList();
758  }
759  else if (!GF && alpha.level() != 1)
760  {
761  if ((p == 2 && degree (getMipo (alpha)) < 6) ||
762  (p == 3 && degree (getMipo (alpha)) < 4) ||
763  (p == 5 && degree (getMipo (alpha)) < 3))
764  {
765  fail= true;
766  return CFList();
767  }
768  }
769  }
770  double bound;
771  if (alpha != x)
772  {
773  bound= pow ((double) p, (double) degree (getMipo(alpha)));
774  bound *= (double) k;
775  }
776  else if (GF)
777  {
778  bound= pow ((double) p, (double) getGFDegree());
779  bound *= (double) k;
780  }
781  else
782  bound= pow ((double) p, (double) k);
783 
784  CanonicalForm random;
786  do
787  {
788  random= 0;
789  // possible overflow if list.length() does not fit into a int
790  if (list.length() >= bound)
791  {
792  fail= true;
793  break;
794  }
795  for (int i= 0; i < k; i++)
796  {
797  if (list.isEmpty())
798  result.append (0);
799  else if (GF)
800  {
801  result.append (genGF.generate());
802  random += result.getLast()*power (x, i);
803  }
804  else if (alpha.level() != 1)
805  {
806  AlgExtRandomF genAlgExt (alpha);
807  result.append (genAlgExt.generate());
808  random += result.getLast()*power (x, i);
809  }
810  else
811  {
812  result.append (genFF.generate());
813  random += result.getLast()*power (x, i);
814  }
815  }
816  if (find (list, random))
817  {
818  result= CFList();
819  continue;
820  }
821  int l= F.level();
822  eval.insert (F);
823  LCFeval.insert (LCF);
824  bool bad= false;
825  for (CFListIterator i= result; i.hasItem(); i++, l--)
826  {
827  eval.insert (eval.getFirst()(i.getItem(), l));
828  LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
829  if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
830  {
831  if (!find (list, random))
832  list.append (random);
833  result= CFList();
834  eval= CFList();
835  LCFeval= CFList();
836  bad= true;
837  break;
838  }
839  if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
840  {
841  if (!find (list, random))
842  list.append (random);
843  result= CFList();
844  eval= CFList();
845  LCFeval= CFList();
846  bad= true;
847  break;
848  }
849  }
850 
851  if (bad)
852  continue;
853 
854  if (degree (eval.getFirst()) != degree (F, 1))
855  {
856  if (!find (list, random))
857  list.append (random);
858  result= CFList();
859  LCFeval= CFList();
860  eval= CFList();
861  continue;
862  }
863 
864  deriv_x= deriv (eval.getFirst(), x);
865  gcd_deriv= gcd (eval.getFirst(), deriv_x);
866  if (degree (gcd_deriv) > 0)
867  {
868  if (!find (list, random))
869  list.append (random);
870  result= CFList();
871  LCFeval= CFList();
872  eval= CFList();
873  continue;
874  }
876  i++;
878  if (degree (contentx) > 0)
879  {
880  if (!find (list, random))
881  list.append (random);
882  result= CFList();
883  LCFeval= CFList();
884  eval= CFList();
885  continue;
886  }
887 
888  contentx= content (i.getItem());
889  if (degree (contentx) > 0)
890  {
891  if (!find (list, random))
892  list.append (random);
893  result= CFList();
894  LCFeval= CFList();
895  eval= CFList();
896  continue;
897  }
898 
899  if (list.length() >= bound)
900  {
901  fail= true;
902  break;
903  }
904  } while (find (list, random));
905 
906  if (!eval.isEmpty())
907  eval.removeFirst();
908 
909  return result;
910 }
911 
912 static inline
914  evaluation, const Variable& alpha, const int lev,
916  )
917 {
918  Variable x= Variable (1);
919  CanonicalForm derivI, buf;
920  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
921  int swapLevel= 0;
922  CFList list;
923  bool fail= false;
924  buf= A;
925  Aeval= CFList();
926  evaluation= CFList();
927  for (int i= lev; i <= A.level(); i++)
928  {
929  derivI= deriv (buf, Variable (i));
930  if (!derivI.isZero())
931  {
932  g= gcd (buf, derivI);
933  if (degree (g) > 0)
934  return -1;
935 
936  buf= swapvar (buf, x, Variable (i));
937  Aeval= CFList();
938  evaluation= CFList();
939  fail= false;
940  evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
941  if (!fail)
942  {
943  A= buf;
944  swapLevel= i;
945  break;
946  }
947  else
948  buf= A;
949  }
950  }
951  return swapLevel;
952 }
953 
955 {
956  int i= A.level();
958  contentAi.append (content (buf, i));
959  buf /= contentAi.getLast();
960  contentAi.append (content (buf, i - 1));
961  CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
962  for (i= i - 2; i > 0; i--)
963  {
964  contentAi.append (content (buf, i));
965  buf /= contentAi.getLast();
966  result= lcm (result, contentAi.getLast());
967  }
968  return result;
969 }
970 
971 CFList
972 henselLiftAndEarly (CanonicalForm& A, CFList& MOD, int*& liftBounds, bool&
973  earlySuccess, CFList& earlyFactors, const CFList& Aeval,
974  const CFList& biFactors, const CFList& evaluation,
975  const ExtensionInfo& info)
976 {
977  bool extension= info.isInExtension();
978  CFList bufFactors= biFactors;
979  bufFactors.insert (LC (Aeval.getFirst(), 1));
980 
981  sortList (bufFactors, Variable (1));
982 
983  CFList diophant;
984  CFArray Pi;
985  int smallFactorDeg= 11; //tunable parameter
986  CFList result;
987  int adaptedLiftBound= 0;
988  int liftBound= liftBounds[1];
989 
990  earlySuccess= false;
991  CFList earlyReconstFactors;
993  j++;
995  CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
996  MOD= CFList (power (Variable (2), liftBounds[0]));
997  if (smallFactorDeg >= liftBound)
998  {
999  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1000  }
1001  else if (smallFactorDeg >= degree (buf) + 1)
1002  {
1003  liftBounds[1]= degree (buf) + 1;
1004  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1005  if (Aeval.length() == 2)
1006  {
1007  if (!extension)
1008  earlyFactors= earlyFactorDetect
1009  (buf, result, adaptedLiftBound, earlySuccess,
1010  degree (buf) + 1, MOD, liftBound);
1011  else
1012  earlyFactors= extEarlyFactorDetect
1013  (buf, result, adaptedLiftBound, earlySuccess,
1014  info, evaluation, degree
1015  (buf) + 1, MOD, liftBound);
1016  }
1017  else
1018  {
1019  if (!extension)
1020  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1021  degree (buf) + 1, MOD, liftBound);
1022  else
1023  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1024  evaluation, degree (buf) + 1,
1025  MOD, liftBound);
1026  }
1027  if (!earlySuccess)
1028  {
1029  result.insert (LC (buf, 1));
1030  liftBounds[1]= adaptedLiftBound;
1031  liftBound= adaptedLiftBound;
1032  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1033  Pi, diophant, Mat, MOD);
1034  }
1035  else
1036  liftBounds[1]= adaptedLiftBound;
1037  }
1038  else if (smallFactorDeg < degree (buf) + 1)
1039  {
1040  liftBounds[1]= smallFactorDeg;
1041  result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
1042  if (Aeval.length() == 2)
1043  {
1044  if (!extension)
1045  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1046  earlySuccess, smallFactorDeg, MOD,
1047  liftBound);
1048  else
1049  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1050  earlySuccess, info, evaluation,
1051  smallFactorDeg, MOD, liftBound);
1052  }
1053  else
1054  {
1055  if (!extension)
1056  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1057  smallFactorDeg, MOD, liftBound);
1058  else
1059  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
1060  evaluation, smallFactorDeg, MOD,
1061  liftBound);
1062  }
1063 
1064  if (!earlySuccess)
1065  {
1066  result.insert (LC (buf, 1));
1067  henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
1068  Pi, diophant, Mat, MOD);
1069  if (Aeval.length() == 2)
1070  {
1071  if (!extension)
1072  earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
1073  earlySuccess, degree (buf) + 1,
1074  MOD, liftBound);
1075  else
1076  earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
1077  earlySuccess, info, evaluation,
1078  degree (buf) + 1, MOD,
1079  liftBound);
1080  }
1081  else
1082  {
1083  if (!extension)
1084  adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
1085  degree (buf) + 1, MOD,liftBound);
1086  else
1087  adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
1088  info, evaluation,
1089  degree (buf) + 1, MOD,
1090  liftBound);
1091  }
1092  if (!earlySuccess)
1093  {
1094  result.insert (LC (buf, 1));
1095  liftBounds[1]= adaptedLiftBound;
1096  liftBound= adaptedLiftBound;
1097  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1098  Pi, diophant, Mat, MOD);
1099  }
1100  else
1101  liftBounds[1]= adaptedLiftBound;
1102  }
1103  else
1104  liftBounds[1]= adaptedLiftBound;
1105  }
1106 
1107  MOD.append (power (Variable (3), liftBounds[1]));
1108 
1109  if (Aeval.length() > 2)
1110  {
1111  CFListIterator j= Aeval;
1112  j++;
1113  CFList bufEval;
1114  bufEval.append (j.getItem());
1115  j++;
1116  int liftBoundsLength= Aeval.getLast().level() - 1;
1117  for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
1118  {
1119  earlySuccess= false;
1120  result.insert (LC (bufEval.getFirst(), 1));
1121  bufEval.append (j.getItem());
1122  liftBound= liftBounds[i];
1123  Mat= CFMatrix (liftBounds[i], result.length() - 1);
1124 
1125  buf= j.getItem();
1126  if (smallFactorDeg >= liftBound)
1127  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1128  liftBounds[i - 1], liftBounds[i]);
1129  else if (smallFactorDeg >= degree (buf) + 1)
1130  {
1131  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1132  liftBounds[i - 1], degree (buf) + 1);
1133 
1134  if (Aeval.length() == i + 1)
1135  {
1136  if (!extension)
1137  earlyFactors= earlyFactorDetect
1138  (buf, result, adaptedLiftBound, earlySuccess,
1139  degree (buf) + 1, MOD, liftBound);
1140  else
1141  earlyFactors= extEarlyFactorDetect
1142  (buf, result, adaptedLiftBound, earlySuccess,
1143  info, evaluation, degree (buf) + 1, MOD, liftBound);
1144  }
1145  else
1146  {
1147  if (!extension)
1148  adaptedLiftBound= liftBoundAdaption
1149  (buf, result, earlySuccess, degree (buf)
1150  + 1, MOD, liftBound);
1151  else
1152  adaptedLiftBound= extLiftBoundAdaption
1153  (buf, result, earlySuccess, info, evaluation,
1154  degree (buf) + 1, MOD, liftBound);
1155  }
1156 
1157  if (!earlySuccess)
1158  {
1159  result.insert (LC (buf, 1));
1160  liftBounds[i]= adaptedLiftBound;
1161  liftBound= adaptedLiftBound;
1162  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1163  Pi, diophant, Mat, MOD);
1164  }
1165  else
1166  {
1167  liftBounds[i]= adaptedLiftBound;
1168  }
1169  }
1170  else if (smallFactorDeg < degree (buf) + 1)
1171  {
1172  result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
1173  liftBounds[i - 1], smallFactorDeg);
1174 
1175  if (Aeval.length() == i + 1)
1176  {
1177  if (!extension)
1178  earlyFactors= earlyFactorDetect
1179  (buf, result, adaptedLiftBound, earlySuccess,
1180  smallFactorDeg, MOD, liftBound);
1181  else
1182  earlyFactors= extEarlyFactorDetect
1183  (buf, result, adaptedLiftBound, earlySuccess,
1184  info, evaluation, smallFactorDeg, MOD, liftBound);
1185  }
1186  else
1187  {
1188  if (!extension)
1189  adaptedLiftBound= liftBoundAdaption
1190  (buf, result, earlySuccess,
1191  smallFactorDeg, MOD, liftBound);
1192  else
1193  adaptedLiftBound= extLiftBoundAdaption
1194  (buf, result, earlySuccess, info, evaluation,
1195  smallFactorDeg, MOD, liftBound);
1196  }
1197 
1198  if (!earlySuccess)
1199  {
1200  result.insert (LC (buf, 1));
1201  henselLiftResume (buf, result, smallFactorDeg,
1202  degree (buf) + 1, Pi, diophant, Mat, MOD);
1203  if (Aeval.length() == i + 1)
1204  {
1205  if (!extension)
1206  earlyFactors= earlyFactorDetect
1207  (buf, result, adaptedLiftBound, earlySuccess,
1208  degree (buf) + 1, MOD, liftBound);
1209  else
1210  earlyFactors= extEarlyFactorDetect
1211  (buf, result, adaptedLiftBound, earlySuccess,
1212  info, evaluation, degree (buf) + 1, MOD,
1213  liftBound);
1214  }
1215  else
1216  {
1217  if (!extension)
1218  adaptedLiftBound= liftBoundAdaption
1219  (buf, result, earlySuccess, degree
1220  (buf) + 1, MOD, liftBound);
1221  else
1222  adaptedLiftBound= extLiftBoundAdaption
1223  (buf, result, earlySuccess, info, evaluation,
1224  degree (buf) + 1, MOD, liftBound);
1225  }
1226 
1227  if (!earlySuccess)
1228  {
1229  result.insert (LC (buf, 1));
1230  liftBounds[i]= adaptedLiftBound;
1231  liftBound= adaptedLiftBound;
1232  henselLiftResume (buf, result, degree (buf) + 1, liftBound,
1233  Pi, diophant, Mat, MOD);
1234  }
1235  else
1236  liftBounds[i]= adaptedLiftBound;
1237  }
1238  else
1239  liftBounds[i]= adaptedLiftBound;
1240  }
1241  MOD.append (power (Variable (i + 2), liftBounds[i]));
1242  bufEval.removeFirst();
1243  }
1244  bufFactors= result;
1245  }
1246  else
1247  bufFactors= result;
1248 
1249  if (earlySuccess)
1250  A= buf;
1251  return result;
1252 }
1253 
1254 void
1256 {
1257  CanonicalForm g;
1258  int k= factors1.length();
1259  int l= factors2.length();
1260  int n= 0;
1261  int m;
1263  for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
1264  {
1265  m= 0;
1266  for (j= factors2; (m < l && j.hasItem()); j++, m++)
1267  {
1268  g= gcd (i.getItem().factor(), j.getItem().factor());
1269  if (degree (g,1) > 0)
1270  {
1271  j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
1272  i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
1273  factors1.append (CFFactor (g, i.getItem().exp()));
1274  factors2.append (CFFactor (g, j.getItem().exp()));
1275  }
1276  }
1277  }
1278 }
1279 
1280 CFList
1281 distributeContent (const CFList& L, const CFList* differentSecondVarFactors,
1282  int length
1283  )
1284 {
1285  CFList l= L;
1287 
1288  if (content.inCoeffDomain())
1289  return l;
1290 
1291  if (l.length() == 1)
1292  {
1293  CFList result;
1294  for (int i= 0; i < length; i++)
1295  {
1296  if (differentSecondVarFactors[i].isEmpty())
1297  continue;
1298  if (result.isEmpty())
1299  {
1300  result= differentSecondVarFactors[i];
1301  for (CFListIterator iter= result; iter.hasItem(); iter++)
1302  content /= iter.getItem();
1303  }
1304  else
1305  {
1306  CFListIterator iter1= result;
1307  for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
1308  iter2++, iter1++)
1309  {
1310  iter1.getItem() *= iter2.getItem();
1311  content /= iter2.getItem();
1312  }
1313  }
1314  }
1315  result.insert (content);
1316  return result;
1317  }
1318 
1319  Variable v;
1320  CFListIterator iter1, iter2;
1321  CanonicalForm tmp, g;
1322  CFList multiplier;
1323  for (int i= 0; i < length; i++)
1324  {
1325  if (differentSecondVarFactors[i].isEmpty())
1326  continue;
1327  iter1= l;
1328  iter1++;
1329 
1330  tmp= 1;
1331  for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
1332  iter2++, iter1++)
1333  {
1334  if (iter2.getItem().inCoeffDomain())
1335  {
1336  multiplier.append (1);
1337  continue;
1338  }
1339  v= iter2.getItem().mvar();
1340  if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
1341  {
1342  multiplier.append (1);
1343  continue;
1344  }
1345  g= gcd (iter2.getItem(), content);
1346  if (!g.inCoeffDomain())
1347  {
1348  tmp *= g;
1349  multiplier.append (g);
1350  }
1351  else
1352  multiplier.append (1);
1353  }
1354  if (!tmp.isOne() && fdivides (tmp, content))
1355  {
1356  iter1= l;
1357  iter1++;
1358  content /= tmp;
1359  for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
1360  iter1.getItem() *= iter2.getItem();
1361  }
1362  multiplier= CFList();
1363  }
1364 
1365  l.removeFirst();
1366  l.insert (content);
1367  return l;
1368 }
1369 
1370 int
1371 testFactors (const CanonicalForm& G, const CFList& uniFactors,
1372  const Variable& alpha, CanonicalForm& sqrfPartF, CFList& factors,
1373  CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
1374  const CFArray& evalPoint)
1375 {
1376  CanonicalForm F= G;
1377  CFFList sqrfFactorization;
1378  if (getCharacteristic() > 0)
1379  sqrfFactorization= squarefreeFactorization (F, alpha);
1380  else
1381  sqrfFactorization= sqrFree (F);
1382 
1383  sqrfPartF= 1;
1384  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
1385  sqrfPartF *= i.getItem().factor();
1386 
1387  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
1388 
1389  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
1390 
1391  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
1392  return 0;
1393 
1394  CFFList sqrfFactors;
1395  CanonicalForm tmp;
1396  CFList tmp2;
1397  int k= 0;
1398  factors= uniFactors;
1400  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1401  {
1402  tmp= 1;
1403  if (getCharacteristic() > 0)
1404  sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
1405  else
1406  sqrfFactors= sqrFree (i.getItem());
1407 
1408  for (iter= sqrfFactors; iter.hasItem(); iter++)
1409  {
1410  tmp2.append (iter.getItem().factor());
1411  tmp *= iter.getItem().factor();
1412  }
1413  i.getItem()= tmp/Lc(tmp);
1414  bufSqrfFactors [k]= sqrfFactors;
1415  }
1416 
1417  for (int i= 0; i < factors.length() - 1; i++)
1418  {
1419  for (k= i + 1; k < factors.length(); k++)
1420  {
1421  gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
1422  }
1423  }
1424 
1425  factors= CFList();
1426  for (int i= 0; i < uniFactors.length(); i++)
1427  {
1428  if (i == 0)
1429  {
1430  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1431  {
1432  if (iter.getItem().factor().inCoeffDomain())
1433  continue;
1434  iter.getItem()= CFFactor (iter.getItem().factor()/
1435  Lc (iter.getItem().factor()),
1436  iter.getItem().exp());
1437  factors.append (iter.getItem().factor());
1438  }
1439  }
1440  else
1441  {
1442  for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
1443  {
1444  if (iter.getItem().factor().inCoeffDomain())
1445  continue;
1446  iter.getItem()= CFFactor (iter.getItem().factor()/
1447  Lc (iter.getItem().factor()),
1448  iter.getItem().exp());
1449  if (!find (factors, iter.getItem().factor()))
1450  factors.append (iter.getItem().factor());
1451  }
1452  }
1453  }
1454 
1455  test= prod (factors);
1456  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
1457  if (test/Lc (test) != tmp/Lc (tmp))
1458  return 0;
1459  else
1460  return 1;
1461 }
1462 
1463 CFList
1464 precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
1465  const Variable& alpha, const CFList& evaluation,
1466  CFList* & differentSecondVarLCs, int lSecondVarLCs,
1467  Variable& y
1468  )
1469 {
1470  y= Variable (1);
1471  if (LCF.inCoeffDomain())
1472  {
1473  CFList result;
1474  for (int i= 1; i <= LCFFactors.length() + 1; i++)
1475  result.append (1);
1476  return result;
1477  }
1478 
1479  CFMap N, M;
1480  CFArray dummy= CFArray (2);
1481  dummy [0]= LCF;
1482  dummy [1]= Variable (2);
1483  compress (dummy, M, N);
1484  CanonicalForm F= M (LCF);
1485  if (LCF.isUnivariate())
1486  {
1487  CFList result;
1488  int LCFLevel= LCF.level();
1489  bool found= false;
1490  if (LCFLevel == 2)
1491  {
1492  //bivariate leading coefficients are already the true leading coefficients
1493  result= LCFFactors;
1494  found= true;
1495  }
1496  else
1497  {
1498  CFListIterator j;
1499  for (int i= 0; i < lSecondVarLCs; i++)
1500  {
1501  for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
1502  {
1503  if (j.getItem().level() == LCFLevel)
1504  {
1505  found= true;
1506  break;
1507  }
1508  }
1509  if (found)
1510  {
1511  result= differentSecondVarLCs [i];
1512  break;
1513  }
1514  }
1515  if (!found)
1516  result= LCFFactors;
1517  }
1518  if (found)
1519  result.insert (Lc (LCF));
1520  else
1521  result.insert (LCF);
1522 
1523  return result;
1524  }
1525 
1526  CFList factors= LCFFactors;
1527 
1528  for (CFListIterator i= factors; i.hasItem(); i++)
1529  i.getItem()= M (i.getItem());
1530 
1531  CanonicalForm sqrfPartF;
1532  CFFList * bufSqrfFactors= new CFFList [factors.length()];
1533  CFList evalSqrfPartF, bufFactors;
1534  CFArray evalPoint= CFArray (evaluation.length() - 1);
1535  CFArray buf= CFArray (evaluation.length());
1536  CFArray swap= CFArray (evaluation.length());
1538  CanonicalForm vars=getVars (LCF)*Variable (2);
1539  for (int i= evaluation.length() +1; i > 1; i--, iter++)
1540  {
1541  buf[i-2]=iter.getItem();
1542  if (degree (vars, i) > 0)
1543  swap[M(Variable (i)).level()-1]=buf[i-2];
1544  }
1545  buf= swap;
1546  for (int i= 0; i < evaluation.length() - 1; i++)
1547  evalPoint[i]= buf[i+1];
1548 
1549  int pass= testFactors (F, factors, alpha, sqrfPartF,
1550  bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
1551 
1552  bool foundDifferent= false;
1553  Variable z, x= y;
1554  int j= 0;
1555  if (!pass)
1556  {
1557  int lev= 0;
1558  // LCF is non-constant here
1559  CFList bufBufFactors;
1560  CanonicalForm bufF;
1561  for (int i= 0; i < lSecondVarLCs; i++)
1562  {
1563  if (!differentSecondVarLCs [i].isEmpty())
1564  {
1565  bool allConstant= true;
1566  for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
1567  {
1568  if (!iter.getItem().inCoeffDomain())
1569  {
1570  allConstant= false;
1571  y= Variable (iter.getItem().level());
1572  lev= M(y).level();
1573  }
1574  }
1575  if (allConstant)
1576  continue;
1577 
1578  bufFactors= differentSecondVarLCs [i];
1579  for (iter= bufFactors; iter.hasItem(); iter++)
1580  iter.getItem()= swapvar (iter.getItem(), x, y);
1581  bufF= F;
1582  z= Variable (lev);
1583  bufF= swapvar (bufF, x, z);
1584  bufBufFactors= bufFactors;
1585  evalPoint= CFArray (evaluation.length() - 1);
1586  for (int k= 1; k < evaluation.length(); k++)
1587  {
1588  if (N (Variable (k+1)).level() != y.level())
1589  evalPoint[k-1]= buf[k];
1590  else
1591  evalPoint[k-1]= buf[0];
1592  }
1593  pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
1594  bufSqrfFactors, evalSqrfPartF, evalPoint);
1595  if (pass)
1596  {
1597  foundDifferent= true;
1598  F= bufF;
1599  CFList l= factors;
1600  for (iter= l; iter.hasItem(); iter++)
1601  iter.getItem()= swapvar (iter.getItem(), x, y);
1602  differentSecondVarLCs [i]= l;
1603  j= i;
1604  break;
1605  }
1606  if (!pass && i == lSecondVarLCs - 1)
1607  {
1608  CFList result;
1609  result.append (LCF);
1610  for (int j= 1; j <= factors.length(); j++)
1611  result.append (1);
1612  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1613  y= Variable (1);
1614  delete [] bufSqrfFactors;
1615  return result;
1616  }
1617  }
1618  }
1619  }
1620  if (!pass)
1621  {
1622  CFList result;
1623  result.append (LCF);
1624  for (int j= 1; j <= factors.length(); j++)
1625  result.append (1);
1626  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1627  y= Variable (1);
1628  delete [] bufSqrfFactors;
1629  return result;
1630  }
1631  else
1632  factors= bufFactors;
1633 
1634  bufFactors= factors;
1635 
1636  CFMap MM, NN;
1637  dummy [0]= sqrfPartF;
1638  dummy [1]= 1;
1639  compress (dummy, MM, NN);
1640  sqrfPartF= MM (sqrfPartF);
1641  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
1642  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1643  iter.getItem()= MM (iter.getItem());
1644 
1645  CFList evaluation2;
1646  for (int i= 2; i <= varsSqrfPartF.level(); i++)
1647  evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
1648 
1649  CFList interMedResult;
1650  CanonicalForm oldSqrfPartF= sqrfPartF;
1651  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1652  if (factors.length() > 1)
1653  {
1654  CanonicalForm LC1= LC (oldSqrfPartF, 1);
1655  CFList leadingCoeffs;
1656  for (int i= 0; i < factors.length(); i++)
1657  leadingCoeffs.append (LC1);
1658 
1659  CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
1660  CFList oldFactors= factors;
1661  for (CFListIterator i= oldFactors; i.hasItem(); i++)
1662  i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
1663 
1664  bool success= false;
1665  CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
1666  CFList heuResult;
1667  if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
1668  LucksWangSparseHeuristic (oldSqrfPartFPowLC,
1669  oldFactors, 2, leadingCoeffs, heuResult))
1670  {
1671  interMedResult= recoverFactors (oldSqrfPartF, heuResult);
1672  if (oldFactors.length() == interMedResult.length())
1673  success= true;
1674  }
1675  if (!success)
1676  {
1677  LC1= LC (evalSqrfPartF.getFirst(), 1);
1678 
1679  CFArray leadingCoeffs= CFArray (factors.length());
1680  for (int i= 0; i < factors.length(); i++)
1681  leadingCoeffs[i]= LC1;
1682 
1683  for (CFListIterator i= factors; i.hasItem(); i++)
1684  i.getItem() *= LC1 (0,2)/Lc (i.getItem());
1685  factors.insert (1);
1686 
1688  newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
1689 
1690  int liftBound= degree (newSqrfPartF,2) + 1;
1691 
1692  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
1693  CFArray Pi;
1694  CFList diophant;
1695  nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
1696  leadingCoeffs, false);
1697 
1698  if (sqrfPartF.level() > 2)
1699  {
1700  int* liftBounds= new int [sqrfPartF.level() - 1];
1701  bool noOneToOne= false;
1702  CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
1703  LC1= LC (evalSqrfPartF.getLast(), 1);
1704  CFList LCs;
1705  for (int i= 0; i < factors.length(); i++)
1706  LCs.append (LC1);
1707  leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
1708  for (int i= sqrfPartF.level() - 1; i > 2; i--)
1709  {
1710  for (CFListIterator j= LCs; j.hasItem(); j++)
1711  j.getItem()= j.getItem() (0, i + 1);
1712  leadingCoeffs2 [i - 3]= LCs;
1713  }
1714  sqrfPartF *= power (LC1, factors.length()-1);
1715 
1716  int liftBoundsLength= sqrfPartF.level() - 1;
1717  for (int i= 0; i < liftBoundsLength; i++)
1718  liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
1719  evalSqrfPartF= evaluateAtZero (sqrfPartF);
1720  evalSqrfPartF.removeFirst();
1721  factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
1722  diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
1723  delete [] leadingCoeffs2;
1724  delete [] liftBounds;
1725  }
1726  for (CFListIterator iter= factors; iter.hasItem(); iter++)
1727  iter.getItem()= reverseShift (iter.getItem(), evaluation2);
1728 
1729  interMedResult=
1730  recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
1731  factors);
1732  }
1733  }
1734  else
1735  {
1736  CanonicalForm contF=content (oldSqrfPartF,1);
1737  factors= CFList (oldSqrfPartF/contF);
1738  interMedResult= recoverFactors (oldSqrfPartF, factors);
1739  }
1740 
1741  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
1742  iter.getItem()= NN (iter.getItem());
1743 
1744  CFList result;
1746  for (int i= 0; i < LCFFactors.length(); i++)
1747  {
1748  CanonicalForm tmp= 1;
1749  for (k= bufSqrfFactors[i]; k.hasItem(); k++)
1750  {
1751  int pos= findItem (bufFactors, k.getItem().factor());
1752  if (pos)
1753  tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
1754  }
1755  result.append (tmp);
1756  }
1757 
1758  for (CFListIterator i= result; i.hasItem(); i++)
1759  {
1760  F /= i.getItem();
1761  if (foundDifferent)
1762  i.getItem()= swapvar (i.getItem(), x, z);
1763  i.getItem()= N (i.getItem());
1764  }
1765 
1766  if (foundDifferent)
1767  {
1768  CFList l= differentSecondVarLCs [j];
1769  for (CFListIterator i= l; i.hasItem(); i++)
1770  i.getItem()= swapvar (i.getItem(), y, z);
1771  differentSecondVarLCs [j]= l;
1772  F= swapvar (F, x, z);
1773  }
1774 
1775  result.insert (N (F));
1776 
1777  result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
1778 
1779  if (!result.getFirst().inCoeffDomain())
1780  {
1781  // prepare input for recursion
1782  if (foundDifferent)
1783  {
1784  for (CFListIterator i= result; i.hasItem(); i++)
1785  i.getItem()= swapvar (i.getItem(), Variable (2), y);
1786  CFList l= differentSecondVarLCs [j];
1787  for (CFListIterator i= l; i.hasItem(); i++)
1788  i.getItem()= swapvar (i.getItem(), y, z);
1789  differentSecondVarLCs [j]= l;
1790  }
1791 
1792  F= result.getFirst();
1793  int level= 0;
1794  if (foundDifferent)
1795  {
1796  level= y.level() - 2;
1797  for (int i= y.level(); i > 1; i--)
1798  {
1799  if (degree (F,i) > 0)
1800  {
1801  if (y.level() == 3)
1802  level= 0;
1803  else
1804  level= i-3;
1805  }
1806  }
1807  }
1808 lcretry:
1809  if (lSecondVarLCs - level > 0)
1810  {
1811  CFList evaluation2= evaluation;
1812  int j= lSecondVarLCs+2;
1814  CFListIterator i;
1815  for (i= evaluation2; i.hasItem(); i++, j--)
1816  {
1817  if (j==y.level())
1818  {
1819  swap= i.getItem();
1820  i.getItem()= evaluation2.getLast();
1821  evaluation2.removeLast();
1822  evaluation2.append (swap);
1823  }
1824  }
1825 
1826  CFList newLCs= differentSecondVarLCs[level];
1827  if (newLCs.isEmpty())
1828  {
1829  if (degree (F, level+3) > 0)
1830  {
1831  delete [] bufSqrfFactors;
1832  return result; //TODO handle this case
1833  }
1834  level=level+1;
1835  goto lcretry;
1836  }
1837  i= newLCs;
1838  CFListIterator iter= result;
1839  iter++;
1840  CanonicalForm quot;
1841  for (;iter.hasItem(); iter++, i++)
1842  {
1843  swap= iter.getItem();
1844  if (degree (swap, level+3) > 0)
1845  {
1846  int count= evaluation.length()+1;
1847  for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
1848  count--)
1849  {
1850  if (count != level+3)
1851  swap= swap (iter2.getItem(), count);
1852  }
1853  if (fdivides (swap, i.getItem(), quot))
1854  i.getItem()= quot;
1855  }
1856  }
1857  CFList * differentSecondVarLCs2= new CFList [lSecondVarLCs - level - 1];
1858  for (int j= level+1; j < lSecondVarLCs; j++)
1859  {
1860  if (degree (F, j+3) > 0)
1861  {
1862  if (!differentSecondVarLCs[j].isEmpty())
1863  {
1864  differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[j];
1865  i= differentSecondVarLCs2[j-level - 1];
1866  iter=result;
1867  iter++;
1868  for (;iter.hasItem(); iter++, i++)
1869  {
1870  swap= iter.getItem();
1871  if (degree (swap, j+3) > 0)
1872  {
1873  int count= evaluation.length()+1;
1874  for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
1875  count--)
1876  {
1877  if (count != j+3)
1878  swap= swap (iter2.getItem(), count);
1879  }
1880  if (fdivides (swap, i.getItem(), quot))
1881  i.getItem()= quot;
1882  }
1883  }
1884  }
1885  }
1886  }
1887 
1888  for (int j= 0; j < level+1; j++)
1889  evaluation2.removeLast();
1890  Variable dummyvar= Variable (1);
1891 
1892  CanonicalForm newLCF= result.getFirst();
1893  newLCF=swapvar (newLCF, Variable (2), Variable (level+3));
1894  for (i=newLCs; i.hasItem(); i++)
1895  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1896  for (int j= 1; j < lSecondVarLCs-level;j++)
1897  {
1898  for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
1899  i.getItem()= swapvar (i.getItem(), Variable (2+j),
1900  Variable (level+3+j));
1901  newLCF= swapvar (newLCF, Variable (2+j), Variable (level+3+j));
1902  }
1903 
1904  CFList recursiveResult=
1905  precomputeLeadingCoeff (newLCF, newLCs, alpha, evaluation2,
1906  differentSecondVarLCs2, lSecondVarLCs - level - 1,
1907  dummyvar);
1908 
1909  if (dummyvar.level() != 1)
1910  {
1911  for (i= recursiveResult; i.hasItem(); i++)
1912  i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
1913  }
1914  for (i= recursiveResult; i.hasItem(); i++)
1915  {
1916  for (int j= lSecondVarLCs-level-1; j > 0; j--)
1917  i.getItem()=swapvar (i.getItem(), Variable (2+j),
1918  Variable (level+3+j));
1919  i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
1920  }
1921 
1922  if (recursiveResult.getFirst() == result.getFirst())
1923  {
1924  delete [] bufSqrfFactors;
1925  delete [] differentSecondVarLCs2;
1926  return result;
1927  }
1928  else
1929  {
1930  iter=recursiveResult;
1931  i= result;
1932  i.getItem()= iter.getItem();
1933  i++;
1934  iter++;
1935  for (; i.hasItem(); i++, iter++)
1936  i.getItem() *= iter.getItem();
1937  delete [] differentSecondVarLCs2;
1938  }
1939  }
1940  }
1941  else
1942  y= Variable (1);
1943 
1944  delete [] bufSqrfFactors;
1945 
1946  return result;
1947 }
1948 
1949 void
1951  const CanonicalForm& A)
1952 {
1953  CanonicalForm tmp;
1954  CFList tmp2;
1956  bool preserveDegree= true;
1957  Variable x= Variable (1);
1958  int j, degAi, degA1= degree (A,1);
1959  for (int i= A.level(); i > 2; i--)
1960  {
1961  tmp= A;
1962  tmp2= CFList();
1963  iter= evaluation;
1964  preserveDegree= true;
1965  degAi= degree (A,i);
1966  for (j= A.level(); j > 1; j--, iter++)
1967  {
1968  if (j == i)
1969  continue;
1970  else
1971  {
1972  tmp= tmp (iter.getItem(), j);
1973  tmp2.insert (tmp);
1974  if ((degree (tmp, i) != degAi) ||
1975  (degree (tmp, 1) != degA1))
1976  {
1977  preserveDegree= false;
1978  break;
1979  }
1980  }
1981  }
1982  if (!content(tmp,1).inCoeffDomain())
1983  preserveDegree= false;
1984  if (!content(tmp).inCoeffDomain())
1985  preserveDegree= false;
1986  if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
1987  preserveDegree= false;
1988  if (preserveDegree)
1989  Aeval [i - 3]= tmp2;
1990  else
1991  Aeval [i - 3]= CFList();
1992  }
1993 }
1994 
1995 #endif
1996 
1997 static inline
1999  const Variable& v)
2000 {
2001  CanonicalForm result= 1;
2002  for (CFListIterator i= l; i.hasItem(); i++)
2003  result *= i.getItem() (evalPoint, v);
2004  return result;
2005 }
2006 
2007 void
2009  CFList& l1, CFList& l2)
2010 {
2011  CanonicalForm g1= f1, g2;
2012  CFListIterator iter1= factors1, iter2= factors2;
2013  for (; iter1.hasItem(); iter1++, iter2++)
2014  {
2015  g2= gcd (g1, iter1.getItem());
2016  if (!g2.inCoeffDomain())
2017  {
2018  l1.append (iter1.getItem());
2019  l2.append (iter2.getItem());
2020  g1 /= g2;
2021  }
2022  }
2023  factors1= Difference (factors1, l1);
2024  factors2= Difference (factors2, l2);
2025 }
2026 
2027 /// check if univariate factors @a factors2 of @a factors3 coincide with
2028 /// univariate factors of @a factors1 and recombine if necessary.
2029 /// The recombined factors of @a factors1 are returned and @a factors3 is
2030 /// recombined accordingly.
2031 CFList
2032 checkOneToOne (const CFList& factors1, const CFList& factors2, CFList& factors3,
2033  const CanonicalForm& evalPoint, const Variable& x)
2034 {
2035  CFList uniFactorsOfFactors1;
2036  CFList result, result2;
2037  CFList bad1= factors2;
2038  CFListIterator iter, iter2, iter3;
2039  CanonicalForm tmp;
2040  int pos;
2041 
2042  for (iter= factors1; iter.hasItem(); iter++)
2043  {
2044  tmp= iter.getItem() (evalPoint, x);
2045  tmp /= Lc (tmp);
2046  if ((pos= findItem (factors2, tmp)))
2047  {
2048  result2.append (getItem (factors3, pos));
2049  result.append (iter.getItem());
2050  bad1= Difference (bad1, CFList (tmp));
2051  }
2052  else
2053  uniFactorsOfFactors1.append (tmp);
2054  }
2055 
2056  CFList bad2, bad3;
2057  bad2= Difference (factors1, result);
2058  bad3= Difference (factors3, result2);
2059  CFList tmp2, tmp3;
2060  CanonicalForm g1, g2, g3, g4;
2061 
2062  while (!uniFactorsOfFactors1.isEmpty())
2063  {
2064  tmp= uniFactorsOfFactors1.getFirst();
2065  checkHelper (tmp, bad1, bad3, tmp2, tmp3);
2066  g1= prod (tmp2);
2067  g2= prod (tmp3);
2068  tmp2= CFList();
2069  tmp3= CFList();
2070  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2071  g3= prod (tmp2);
2072  g4= prod (tmp3);
2073  tmp2= CFList();
2074  tmp3= CFList();
2075  do
2076  {
2077  checkHelper (g3, bad1, bad3, tmp2, tmp3);
2078  g1 *= prod (tmp2);
2079  g2 *= prod (tmp3);
2080  tmp2= CFList();
2081  tmp3= CFList();
2082  checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
2083  g3 *= prod (tmp2);
2084  g4 *= prod (tmp3);
2085  tmp2= CFList();
2086  tmp3= CFList();
2087  } while (!bad2.isEmpty() && !bad3.isEmpty());
2088  result.append (g4);
2089  result2.append (g2);
2090  }
2091 
2092  if (factors3.length() != result2.length())
2093  factors3= result2;
2094  return result;
2095 }
2096 
2097 //recombine bivariate factors in case one bivariate factorization yields less
2098 // factors than the other
2099 CFList
2100 recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
2101  const CanonicalForm& evalPoint, const Variable& x)
2102 {
2103  CFList T, S;
2104 
2105  T= factors1;
2106  CFList result;
2108  int * v= new int [T.length()];
2109  for (int i= 0; i < T.length(); i++)
2110  v[i]= 0;
2111  bool nosubset= false;
2112  CFArray TT;
2113  TT= copy (factors1);
2114  int recombinations= 0;
2115  while (T.length() >= 2*s && s <= thres)
2116  {
2117  while (nosubset == false)
2118  {
2119  if (T.length() == s)
2120  {
2121  delete [] v;
2122  if (recombinations == factors2.length() - 1)
2123  result.append (prod (T));
2124  else
2125  result= Union (result, T);
2126  return result;
2127  }
2128  S= subset (v, s, TT, nosubset);
2129  if (nosubset) break;
2130  buf= prodEval (S, evalPoint, x);
2131  buf /= Lc (buf);
2132  if (find (factors2, buf))
2133  {
2134  recombinations++;
2135  T= Difference (T, S);
2136  result.append (prod (S));
2137  TT= copy (T);
2138  indexUpdate (v, s, T.length(), nosubset);
2139  if (nosubset) break;
2140  }
2141  }
2142  s++;
2143  if (T.length() < 2*s || T.length() == s)
2144  {
2145  if (recombinations == factors2.length() - 1)
2146  result.append (prod (T));
2147  else
2148  result= Union (result, T);
2149  delete [] v;
2150  return result;
2151  }
2152  for (int i= 0; i < T.length(); i++)
2153  v[i]= 0;
2154  nosubset= false;
2155  }
2156 
2157  delete [] v;
2158  if (T.length() < 2*s)
2159  {
2160  result= Union (result, T);
2161  return result;
2162  }
2163 
2164  return result;
2165 }
2166 
2167 #ifdef HAVE_NTL
2168 void
2170  const ExtensionInfo& info,
2171  int& minFactorsLength, bool& irred)
2172 {
2173  Variable x= Variable (1);
2174  minFactorsLength= 0;
2175  irred= false;
2176  CFList factors;
2177  Variable v;
2178  for (int j= 0; j < A.level() - 2; j++)
2179  {
2180  if (!Aeval[j].isEmpty())
2181  {
2182  v= Variable (Aeval[j].getFirst().level());
2184  factors= GFBiSqrfFactorize (Aeval[j].getFirst());
2185  else if (info.getAlpha().level() == 1)
2186  factors= FpBiSqrfFactorize (Aeval[j].getFirst());
2187  else
2188  factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
2189 
2190  factors.removeFirst();
2191  if (minFactorsLength == 0)
2192  minFactorsLength= factors.length();
2193  else
2194  minFactorsLength= tmin (minFactorsLength, factors.length());
2195 
2196  if (factors.length() == 1)
2197  {
2198  irred= true;
2199  return;
2200  }
2201  sortList (factors, x);
2202  Aeval [j]= factors;
2203  }
2204  }
2205 }
2206 
2208 {
2209  CFList result;
2210  for (int i= A.max(); i >= A.min(); i--)
2211  result.insert (A[i]);
2212  return result;
2213 }
2214 
2215 
2217  )
2218 {
2220  CFList LCs;
2221  for (int j= 0; j < A.level() - 2; j++)
2222  {
2223  if (!Aeval[j].isEmpty())
2224  {
2225  LCs= CFList();
2226  for (iter= Aeval[j]; iter.hasItem(); iter++)
2227  LCs.append (LC (iter.getItem(), 1));
2228  //normalize (LCs);
2229  Aeval[j]= LCs;
2230  }
2231  }
2232 }
2233 
2234 void sortByUniFactors (CFList*& Aeval, int AevalLength,
2235  CFList& uniFactors, CFList& biFactors,
2236  const CFList& evaluation
2237  )
2238 {
2240  int i;
2241  CFListIterator iter, iter2;
2242  Variable v;
2243  CFList LCs, buf;
2244  CFArray l;
2245  int pos, index, checklength;
2246  bool leaveLoop=false;
2247 recurse:
2248  for (int j= 0; j < AevalLength; j++)
2249  {
2250  if (!Aeval[j].isEmpty())
2251  {
2252  i= evaluation.length() + 1;
2253  for (iter= evaluation; iter.hasItem(); iter++, i--)
2254  {
2255  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2256  {
2257  if (i == iter2.getItem().level())
2258  {
2259  evalPoint= iter.getItem();
2260  leaveLoop= true;
2261  break;
2262  }
2263  }
2264  if (leaveLoop)
2265  {
2266  leaveLoop= false;
2267  break;
2268  }
2269  }
2270 
2271  v= Variable (i);
2272  if (Aeval[j].length() > uniFactors.length())
2273  Aeval[j]= recombination (Aeval[j], uniFactors, 1,
2274  Aeval[j].length() - uniFactors.length() + 1,
2275  evalPoint, v);
2276 
2277  checklength= biFactors.length();
2278  Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
2279  if (checklength > biFactors.length())
2280  {
2281  uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
2282  Variable (2));
2283  goto recurse;
2284  }
2285 
2286  buf= buildUniFactors (Aeval[j], evalPoint, v);
2287  l= CFArray (uniFactors.length());
2288  index= 1;
2289  for (iter= buf; iter.hasItem(); iter++, index++)
2290  {
2291  pos= findItem (uniFactors, iter.getItem());
2292  if (pos)
2293  l[pos-1]= getItem (Aeval[j], index);
2294  }
2295  buf= conv (l);
2296  Aeval [j]= buf;
2297 
2298  buf= buildUniFactors (Aeval[j], evalPoint, v);
2299  }
2300  }
2301 }
2302 
2303 CFList
2304 buildUniFactors (const CFList& biFactors, const CanonicalForm& evalPoint,
2305  const Variable& y)
2306 {
2307  CFList result;
2308  CanonicalForm tmp;
2309  for (CFListIterator i= biFactors; i.hasItem(); i++)
2310  {
2311  tmp= mod (i.getItem(), y - evalPoint);
2312  tmp /= Lc (tmp);
2313  result.append (tmp);
2314  }
2315  return result;
2316 }
2317 
2318 void refineBiFactors (const CanonicalForm& A, CFList& biFactors,
2319  CFList* const& Aeval, const CFList& evaluation,
2320  int minFactorsLength)
2321 {
2322  CFListIterator iter, iter2;
2324  int i;
2325  Variable v;
2326  Variable y= Variable (2);
2327  CFList list;
2328  bool leaveLoop= false;
2329  for (int j= 0; j < A.level() - 2; j++)
2330  {
2331  if (Aeval[j].length() == minFactorsLength)
2332  {
2333  i= A.level();
2334 
2335  for (iter= evaluation; iter.hasItem(); iter++, i--)
2336  {
2337  for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
2338  {
2339  if (i == iter2.getItem().level())
2340  {
2341  evalPoint= iter.getItem();
2342  leaveLoop= true;
2343  break;
2344  }
2345  }
2346  if (leaveLoop)
2347  {
2348  leaveLoop= false;
2349  break;
2350  }
2351  }
2352 
2353  v= Variable (i);
2354  list= buildUniFactors (Aeval[j], evalPoint, v);
2355 
2356  biFactors= recombination (biFactors, list, 1,
2357  biFactors.length() - list.length() + 1,
2358  evaluation.getLast(), y);
2359  return;
2360  }
2361  }
2362 }
2363 
2364 void
2366  const CFList& leadingCoeffs, const CFList& biFactors,
2367  const CFList& evaluation)
2368 {
2369  CFList l= leadingCoeffs;
2370  LCs [n-3]= l;
2371  CFListIterator j;
2373  for (int i= n - 1; i > 2; i--, iter++)
2374  {
2375  for (j= l; j.hasItem(); j++)
2376  j.getItem()= j.getItem() (iter.getItem(), i + 1);
2377  LCs [i - 3]= l;
2378  }
2379  l= LCs [0];
2380  for (CFListIterator i= l; i.hasItem(); i++)
2381  i.getItem()= i.getItem() (iter.getItem(), 3);
2382  CFListIterator ii= biFactors;
2383  CFList normalizeFactor;
2384  for (CFListIterator i= l; i.hasItem(); i++, ii++)
2385  normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
2386  for (int i= 0; i < n-2; i++)
2387  {
2388  ii= normalizeFactor;
2389  for (j= LCs [i]; j.hasItem(); j++, ii++)
2390  j.getItem() *= ii.getItem();
2391  }
2392 
2393  Aeval= evaluateAtEval (A, evaluation, 2);
2394 
2395  CanonicalForm hh= 1/Lc (Aeval.getFirst());
2396 
2397  for (iter= Aeval; iter.hasItem(); iter++)
2398  iter.getItem() *= hh;
2399 
2400  A *= hh;
2401 }
2402 
2403 CFList
2405  const ExtensionInfo& info)
2406 {
2407  Variable alpha= info.getAlpha();
2408  Variable beta= info.getBeta();
2409  CanonicalForm gamma= info.getGamma();
2410  CanonicalForm delta= info.getDelta();
2411  int k= info.getGFDegree();
2412  CFList source, dest;
2413 
2414  int degMipoBeta= 1;
2415  if (!k && beta != Variable(1))
2416  degMipoBeta= degree (getMipo (beta));
2417 
2418  CFList T, S;
2419  T= factors;
2420  int s= 1;
2421  CFList result;
2422  CanonicalForm quot, buf= F;
2423 
2424  CanonicalForm g;
2426  int * v= new int [T.length()];
2427  for (int i= 0; i < T.length(); i++)
2428  v[i]= 0;
2429  bool noSubset= false;
2430  CFArray TT;
2431  TT= copy (factors);
2432  bool recombination= false;
2433  bool trueFactor= false;
2434  while (T.length() >= 2*s)
2435  {
2436  while (noSubset == false)
2437  {
2438  if (T.length() == s)
2439  {
2440  delete [] v;
2441  if (recombination)
2442  {
2443  g= prod (T);
2444  T.removeFirst();
2445  g /= myContent (g);
2446  g /= Lc (g);
2447  appendTestMapDown (result, g, info, source, dest);
2448  return result;
2449  }
2450  else
2451  return CFList (buf/myContent(buf));
2452  }
2453 
2454  S= subset (v, s, TT, noSubset);
2455  if (noSubset) break;
2456 
2457  g= prod (S);
2458  g /= myContent (g);
2459  if (fdivides (g, buf, quot))
2460  {
2461  buf2= g;
2462  buf2 /= Lc (buf2);
2463  if (!k && beta.level() == 1)
2464  {
2465  if (degree (buf2, alpha) < degMipoBeta)
2466  {
2467  appendTestMapDown (result, buf2, info, source, dest);
2468  buf= quot;
2469  recombination= true;
2470  trueFactor= true;
2471  }
2472  }
2473  else
2474  {
2475  if (!isInExtension (buf2, gamma, k, delta, source, dest))
2476  {
2477  appendTestMapDown (result, buf2, info, source, dest);
2478  buf= quot;
2479  recombination= true;
2480  trueFactor= true;
2481  }
2482  }
2483  if (trueFactor)
2484  {
2485  T= Difference (T, S);
2486 
2487  if (T.length() < 2*s || T.length() == s)
2488  {
2489  delete [] v;
2490  buf /= myContent (buf);
2491  buf /= Lc (buf);
2492  appendTestMapDown (result, buf, info, source, dest);
2493  return result;
2494  }
2495  trueFactor= false;
2496  TT= copy (T);
2497  indexUpdate (v, s, T.length(), noSubset);
2498  if (noSubset) break;
2499  }
2500  }
2501  }
2502  s++;
2503  if (T.length() < 2*s || T.length() == s)
2504  {
2505  delete [] v;
2506  buf /= myContent (buf);
2507  buf /= Lc (buf);
2508  appendTestMapDown (result, buf, info, source, dest);
2509  return result;
2510  }
2511  for (int i= 0; i < T.length(); i++)
2512  v[i]= 0;
2513  noSubset= false;
2514  }
2515  if (T.length() < 2*s)
2516  {
2517  buf= F/myContent (F);
2518  buf /= Lc (buf);
2519  appendMapDown (result, buf, info, source, dest);
2520  }
2521 
2522  delete [] v;
2523  return result;
2524 }
2525 
2526 void
2528  CFList*& oldAeval, int lengthAeval2,
2529  const CFList& uniFactors, const Variable& w)
2530 {
2531  Variable y= Variable (2);
2532  A= swapvar (A, y, w);
2533  int i= A.level();
2535  for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
2536  {
2537  if (i == w.level())
2538  {
2539  evalPoint= iter.getItem();
2540  iter.getItem()= evaluation.getLast();
2541  evaluation.removeLast();
2542  evaluation.append (evalPoint);
2543  break;
2544  }
2545  }
2546  for (i= 0; i < lengthAeval2; i++)
2547  {
2548  if (oldAeval[i].isEmpty())
2549  continue;
2550  if (oldAeval[i].getFirst().level() == w.level())
2551  {
2552  CFArray tmp= copy (oldAeval[i]);
2553  oldAeval[i]= biFactors;
2554  for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
2555  iter.getItem()= swapvar (iter.getItem(), w, y);
2556  for (int ii= 0; ii < tmp.size(); ii++)
2557  tmp[ii]= swapvar (tmp[ii], w, y);
2558  CFArray tmp2= CFArray (tmp.size());
2560  for (int ii= 0; ii < tmp.size(); ii++)
2561  {
2562  buf= tmp[ii] (evaluation.getLast(),y);
2563  buf /= Lc (buf);
2564  tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
2565  }
2566  biFactors= CFList();
2567  for (int j= 0; j < tmp2.size(); j++)
2568  biFactors.append (tmp2[j]);
2569  }
2570  }
2571 }
2572 
2573 void
2575  CFList& biFactors, const CFList& evaluation,
2576  const CanonicalForm& LCmultipler)
2577 {
2578  CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
2579  A *= tmp;
2580  tmp= LCmultipler;
2581  CFListIterator iter= leadingCoeffs;
2582  for (;iter.hasItem(); iter++)
2583  iter.getItem() *= LCmultipler;
2584  iter= evaluation;
2585  for (int i= A.level(); i > 2; i--, iter++)
2586  tmp= tmp (iter.getItem(), i);
2587  if (!tmp.inCoeffDomain())
2588  {
2589  for (CFListIterator i= biFactors; i.hasItem(); i++)
2590  {
2591  i.getItem() *= tmp/LC (i.getItem(), 1);
2592  i.getItem() /= Lc (i.getItem());
2593  }
2594  }
2595 }
2596 
2597 void
2598 LCHeuristic (CanonicalForm& A, const CanonicalForm& LCmultiplier,
2599  CFList& biFactors, CFList*& leadingCoeffs, const CFList* oldAeval,
2600  int lengthAeval, const CFList& evaluation,
2601  const CFList& oldBiFactors)
2602 {
2603  CFListIterator iter, iter2;
2604  int index;
2605  Variable xx;
2606  CFList vars1;
2607  CFFList sqrfMultiplier= sqrFree (LCmultiplier);
2608  if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
2609  sqrfMultiplier.removeFirst();
2610  sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
2611  xx= Variable (2);
2612  for (iter= oldBiFactors; iter.hasItem(); iter++)
2613  vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
2614  for (int i= 0; i < lengthAeval; i++)
2615  {
2616  if (oldAeval[i].isEmpty())
2617  continue;
2618  xx= oldAeval[i].getFirst().mvar();
2619  iter2= vars1;
2620  for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
2621  iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
2622  }
2623  CanonicalForm tmp, quot1, quot2, quot3;
2624  iter2= vars1;
2625  for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
2626  {
2627  tmp= iter.getItem()/LCmultiplier;
2628  for (int i=1; i <= tmp.level(); i++)
2629  {
2630  if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
2631  iter2.getItem() /= power (Variable (i), degree (tmp,i));
2632  }
2633  }
2634  int multi;
2635  for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
2636  {
2637  multi= 0;
2638  for (iter= vars1; iter.hasItem(); iter++)
2639  {
2640  tmp= iter.getItem();
2641  while (fdivides (myGetVars (ii.getItem().factor()), tmp))
2642  {
2643  multi++;
2644  tmp /= myGetVars (ii.getItem().factor());
2645  }
2646  }
2647  if (multi == ii.getItem().exp())
2648  {
2649  index= 1;
2650  for (iter= vars1; iter.hasItem(); iter++, index++)
2651  {
2652  while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2653  {
2654  int index2= 1;
2655  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
2656  index2++)
2657  {
2658  if (index2 == index)
2659  continue;
2660  else
2661  {
2662  tmp= ii.getItem().factor();
2663  if (fdivides (tmp, iter2.getItem(), quot1))
2664  {
2665  CFListIterator iter3= evaluation;
2666  for (int jj= A.level(); jj > 2; jj--, iter3++)
2667  tmp= tmp (iter3.getItem(), jj);
2668  if (!tmp.inCoeffDomain())
2669  {
2670  int index3= 1;
2671  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2672  {
2673  if (index3 == index2)
2674  {
2675  if (fdivides (tmp, iter3.getItem(), quot2))
2676  {
2677  if (fdivides (ii.getItem().factor(), A, quot3))
2678  {
2679  A = quot3;
2680  iter2.getItem() = quot2;
2681  iter3.getItem() = quot3;
2682  iter3.getItem() /= Lc (iter3.getItem());
2683  break;
2684  }
2685  }
2686  }
2687  }
2688  }
2689  }
2690  }
2691  }
2692  iter.getItem() /= getVars (ii.getItem().factor());
2693  }
2694  }
2695  }
2696  else
2697  {
2698  index= 1;
2699  for (iter= vars1; iter.hasItem(); iter++, index++)
2700  {
2701  if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
2702  {
2703  int index2= 1;
2704  for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
2705  index2++)
2706  {
2707  if (index2 == index)
2708  {
2709  tmp= power (ii.getItem().factor(), ii.getItem().exp());
2710  if (fdivides (tmp, A, quot1))
2711  {
2712  if (fdivides (tmp, iter2.getItem()))
2713  {
2714  CFListIterator iter3= evaluation;
2715  for (int jj= A.level(); jj > 2; jj--, iter3++)
2716  tmp= tmp (iter3.getItem(), jj);
2717  if (!tmp.inCoeffDomain())
2718  {
2719  int index3= 1;
2720  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
2721  {
2722  if (index3 == index2)
2723  {
2724  if (fdivides (tmp, iter3.getItem(), quot3))
2725  {
2726  A = quot1;
2727  iter2.getItem() = quot2;
2728  iter3.getItem() = quot3;
2729  iter3.getItem() /= Lc (iter3.getItem());
2730  break;
2731  }
2732  }
2733  }
2734  }
2735  }
2736  }
2737  }
2738  }
2739  }
2740  }
2741  }
2742  }
2743 }
2744 
2745 void
2746 LCHeuristicCheck (const CFList& LCs, const CFList& contents, CanonicalForm& A,
2747  const CanonicalForm& oldA, CFList& leadingCoeffs,
2748  bool& foundTrueMultiplier)
2749 {
2750  CanonicalForm pLCs= prod (LCs);
2751  if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
2752  {
2753  A= oldA;
2754  CFListIterator iter2= leadingCoeffs;
2755  for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
2756  iter2.getItem() /= iter.getItem();
2757  foundTrueMultiplier= true;
2758  }
2759 }
2760 
2761 void
2762 LCHeuristic2 (const CanonicalForm& LCmultiplier, const CFList& factors,
2763  CFList& leadingCoeffs, CFList& contents, CFList& LCs,
2764  bool& foundTrueMultiplier)
2765 {
2766  CanonicalForm cont;
2767  int index= 1;
2768  CFListIterator iter2;
2769  for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
2770  {
2771  cont= content (iter.getItem(), 1);
2772  cont= gcd (cont, LCmultiplier);
2773  contents.append (cont);
2774  if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
2775  {
2776  foundTrueMultiplier= true;
2777  int index2= 1;
2778  for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
2779  {
2780  if (index2 == index)
2781  continue;
2782  iter2.getItem() /= LCmultiplier;
2783  }
2784  break;
2785  }
2786  else
2787  LCs.append (LC (iter.getItem()/cont, 1));
2788  }
2789 }
2790 
2791 void
2792 LCHeuristic3 (const CanonicalForm& LCmultiplier, const CFList& factors,
2793  const CFList& oldBiFactors, const CFList& contents,
2794  const CFList* oldAeval, CanonicalForm& A, CFList*& leadingCoeffs,
2795  int lengthAeval, bool& foundMultiplier)
2796 {
2797  int index= 1;
2798  CFListIterator iter, iter2= factors;
2799  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2800  {
2801  if (fdivides (iter.getItem(), LCmultiplier))
2802  {
2803  if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
2804  !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
2805  {
2806  Variable xx= Variable (2);
2807  CanonicalForm vars;
2808  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2809  xx));
2810  for (int i= 0; i < lengthAeval; i++)
2811  {
2812  if (oldAeval[i].isEmpty())
2813  continue;
2814  xx= oldAeval[i].getFirst().mvar();
2815  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2816  xx));
2817  }
2818  if (vars.level() <= 2)
2819  {
2820  int index2= 1;
2821  for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
2822  iter3.hasItem(); iter3++, index2++)
2823  {
2824  if (index2 == index)
2825  {
2826  iter3.getItem() /= LCmultiplier;
2827  break;
2828  }
2829  }
2830  A /= LCmultiplier;
2831  foundMultiplier= true;
2832  iter.getItem()= 1;
2833  }
2834  }
2835  }
2836  }
2837 }
2838 
2839 void
2840 LCHeuristic4 (const CFList& oldBiFactors, const CFList* oldAeval,
2841  const CFList& contents, const CFList& factors,
2842  const CanonicalForm& testVars, int lengthAeval,
2843  CFList*& leadingCoeffs, CanonicalForm& A,
2844  CanonicalForm& LCmultiplier, bool& foundMultiplier)
2845 {
2846  int index=1;
2847  CFListIterator iter, iter2= factors;
2848  for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
2849  {
2850  if (!iter.getItem().isOne() &&
2851  fdivides (iter.getItem(), LCmultiplier))
2852  {
2853  if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
2854  {
2855  int index2= 1;
2856  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2857  iter2++, index2++)
2858  {
2859  if (index2 == index)
2860  {
2861  iter2.getItem() /= iter.getItem();
2862  foundMultiplier= true;
2863  break;
2864  }
2865  }
2866  A /= iter.getItem();
2867  LCmultiplier /= iter.getItem();
2868  iter.getItem()= 1;
2869  }
2870  else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
2871  {
2872  Variable xx= Variable (2);
2873  CanonicalForm vars;
2874  vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
2875  xx));
2876  for (int i= 0; i < lengthAeval; i++)
2877  {
2878  if (oldAeval[i].isEmpty())
2879  continue;
2880  xx= oldAeval[i].getFirst().mvar();
2881  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
2882  xx));
2883  }
2884  if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
2885  /myGetVars (LCmultiplier) == vars)
2886  {
2887  int index2= 1;
2888  for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2889  iter2++, index2++)
2890  {
2891  if (index2 == index)
2892  {
2893  iter2.getItem() /= LCmultiplier;
2894  foundMultiplier= true;
2895  break;
2896  }
2897  }
2898  A /= LCmultiplier;
2899  iter.getItem()= 1;
2900  }
2901  }
2902  }
2903  }
2904 }
2905 
2906 CFList
2907 extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
2908 
2909 CFList
2911 {
2912  if (F.inCoeffDomain())
2913  return CFList (F);
2914 
2915  TIMING_START (fac_fq_preprocess_and_content);
2916  // compress and find main Variable
2917  CFMap N;
2918  TIMING_START (fac_fq_compress)
2919  CanonicalForm A= myCompress (F, N);
2920  TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
2921 
2922  A /= Lc (A); // make monic
2923 
2924  Variable alpha= info.getAlpha();
2925  Variable beta= info.getBeta();
2926  CanonicalForm gamma= info.getGamma();
2927  CanonicalForm delta= info.getDelta();
2928  bool extension= info.isInExtension();
2929  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
2930  //univariate case
2931  if (F.isUnivariate())
2932  {
2933  if (extension == false)
2934  return uniFactorizer (F, alpha, GF);
2935  else
2936  {
2937  CFList source, dest;
2938  A= mapDown (F, info, source, dest);
2939  return uniFactorizer (A, beta, GF);
2940  }
2941  }
2942 
2943  //bivariate case
2944  if (A.level() == 2)
2945  {
2946  CFList buf= biSqrfFactorizeHelper (F, info);
2947  if (buf.getFirst().inCoeffDomain())
2948  buf.removeFirst();
2949  return buf;
2950  }
2951 
2952  Variable x= Variable (1);
2953  Variable y= Variable (2);
2954 
2955  // remove content
2956  TIMING_START (fac_fq_content);
2957  CFList contentAi;
2958  CanonicalForm lcmCont= lcmContent (A, contentAi);
2959  A /= lcmCont;
2960  TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
2961 
2962  // trivial after content removal
2963  CFList contentAFactors;
2964  if (A.inCoeffDomain())
2965  {
2966  for (CFListIterator i= contentAi; i.hasItem(); i++)
2967  {
2968  if (i.getItem().inCoeffDomain())
2969  continue;
2970  else
2971  {
2972  lcmCont /= i.getItem();
2973  contentAFactors=
2974  Union (multiFactorize (lcmCont, info),
2975  multiFactorize (i.getItem(), info));
2976  break;
2977  }
2978  }
2979  decompress (contentAFactors, N);
2980  if (!extension)
2981  normalize (contentAFactors);
2982  return contentAFactors;
2983  }
2984 
2985  // factorize content
2986  TIMING_START (fac_fq_content);
2987  contentAFactors= multiFactorize (lcmCont, info);
2988  TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
2989 
2990  // univariate after content removal
2991  CFList factors;
2992  if (A.isUnivariate ())
2993  {
2994  factors= uniFactorizer (A, alpha, GF);
2995  append (factors, contentAFactors);
2996  decompress (factors, N);
2997  return factors;
2998  }
2999 
3000  // check main variable
3001  TIMING_START (fac_fq_check_mainvar);
3002  int swapLevel= 0;
3003  CanonicalForm derivZ;
3004  CanonicalForm gcdDerivZ;
3005  CanonicalForm bufA= A;
3006  Variable z;
3007  for (int i= 1; i <= A.level(); i++)
3008  {
3009  z= Variable (i);
3010  derivZ= deriv (bufA, z);
3011  if (derivZ.isZero())
3012  {
3013  if (i == 1)
3014  swapLevel= 1;
3015  else
3016  continue;
3017  }
3018  else
3019  {
3020  gcdDerivZ= gcd (bufA, derivZ);
3021  if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
3022  {
3023  CanonicalForm g= bufA/gcdDerivZ;
3024  CFList factorsG=
3025  Union (multiFactorize (g, info),
3026  multiFactorize (gcdDerivZ, info));
3027  appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3028  if (!extension)
3029  normalize (factorsG);
3030  return factorsG;
3031  }
3032  else
3033  {
3034  if (swapLevel == 1)
3035  {
3036  swapLevel= i;
3037  bufA= swapvar (A, x, z);
3038  }
3039  A= bufA;
3040  break;
3041  }
3042  }
3043  }
3044  TIMING_END_AND_PRINT (fac_fq_check_mainvar,
3045  "time to check main var over Fq: ");
3046  TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
3047  "time to preprocess poly and extract content over Fq: ");
3048 
3049  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
3050  bool fail= false;
3051  int swapLevel2= 0;
3052  //int level;
3053  int factorNums= 3;
3054  CFList biFactors, bufBiFactors;
3055  CanonicalForm evalPoly;
3056  int lift, bufLift, lengthAeval2= A.level()-2;
3057  double logarithm= (double) ilog2 (totaldegree (A));
3058  logarithm /= log2exp;
3059  logarithm= ceil (logarithm);
3060  if (factorNums < (int) logarithm)
3061  factorNums= (int) logarithm;
3062  CFList* bufAeval2= new CFList [lengthAeval2];
3063  CFList* Aeval2= new CFList [lengthAeval2];
3064  int counter;
3065  int differentSecondVar= 0;
3066  // several bivariate factorizations
3067  TIMING_START (fac_fq_bifactor_total);
3068  for (int i= 0; i < factorNums; i++)
3069  {
3070  counter= 0;
3071  bufA= A;
3072  bufAeval= CFList();
3073  TIMING_START (fac_fq_evaluation);
3074  bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
3075  TIMING_END_AND_PRINT (fac_fq_evaluation,
3076  "time to find evaluation point over Fq: ");
3077  evalPoly= 0;
3078 
3079  if (fail && (i == 0))
3080  {
3081  /*if (!swapLevel) //uncomment to reenable search for new main variable
3082  level= 2;
3083  else
3084  level= swapLevel + 1;*/
3085 
3086  //CanonicalForm g;
3087  //swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
3088 
3089  /*if (!swapLevel2) // need to pass to an extension
3090  {*/
3091  factors= extFactorize (A, info);
3092  appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
3093  normalize (factors);
3094  delete [] bufAeval2;
3095  delete [] Aeval2;
3096  return factors;
3097  /*}
3098  else
3099  {
3100  if (swapLevel2 == -1)
3101  {
3102  CFList factorsG=
3103  Union (multiFactorize (g, info),
3104  multiFactorize (A/g, info));
3105  appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
3106  if (!extension)
3107  normalize (factorsG);
3108  delete [] bufAeval2;
3109  delete [] Aeval2;
3110  return factorsG;
3111  }
3112  fail= false;
3113  bufAeval= Aeval;
3114  bufA= A;
3115  bufEvaluation= evaluation;
3116  }*/ //end uncomment
3117  }
3118  else if (fail && (i > 0))
3119  break;
3120 
3121  TIMING_START (fac_fq_evaluation);
3122  evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
3123  TIMING_END_AND_PRINT (fac_fq_evaluation,
3124  "time for evaluation wrt diff second vars over Fq: ");
3125 
3126  for (int j= 0; j < lengthAeval2; j++)
3127  {
3128  if (!bufAeval2[j].isEmpty())
3129  counter++;
3130  }
3131 
3132  bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
3133 
3134  TIMING_START (fac_fq_bi_factorizer);
3135  if (!GF && alpha.level() == 1)
3136  bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
3137  else if (GF)
3138  bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
3139  else
3140  bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
3141  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3142  "time for bivariate factorization: ");
3143  bufBiFactors.removeFirst();
3144 
3145  if (bufBiFactors.length() == 1)
3146  {
3147  if (extension)
3148  {
3149  CFList source, dest;
3150  A= mapDown (A, info, source, dest);
3151  }
3152  factors.append (A);
3153  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3154  swapLevel2, x);
3155  if (!extension)
3156  normalize (factors);
3157  delete [] bufAeval2;
3158  delete [] Aeval2;
3159  return factors;
3160  }
3161 
3162  if (i == 0)
3163  {
3164  Aeval= bufAeval;
3165  evaluation= bufEvaluation;
3166  biFactors= bufBiFactors;
3167  lift= bufLift;
3168  for (int j= 0; j < lengthAeval2; j++)
3169  Aeval2 [j]= bufAeval2 [j];
3170  differentSecondVar= counter;
3171  }
3172  else
3173  {
3174  if (bufBiFactors.length() < biFactors.length() ||
3175  ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
3176  counter > differentSecondVar)
3177  {
3178  Aeval= bufAeval;
3179  evaluation= bufEvaluation;
3180  biFactors= bufBiFactors;
3181  lift= bufLift;
3182  for (int j= 0; j < lengthAeval2; j++)
3183  Aeval2 [j]= bufAeval2 [j];
3184  differentSecondVar= counter;
3185  }
3186  }
3187  int k= 0;
3188  for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
3189  evalPoly += j.getItem()*power (x, k);
3190  list.append (evalPoly);
3191  }
3192 
3193  delete [] bufAeval2;
3194 
3195  sortList (biFactors, x);
3196 
3197  int minFactorsLength;
3198  bool irred= false;
3199  TIMING_START (fac_fq_bi_factorizer);
3200  factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
3201  TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
3202  "time for bivariate factorization wrt diff second vars over Fq: ");
3203 
3204  TIMING_END_AND_PRINT (fac_fq_bifactor_total,
3205  "total time for eval and bivar factors over Fq: ");
3206  if (irred)
3207  {
3208  if (extension)
3209  {
3210  CFList source, dest;
3211  A= mapDown (A, info, source, dest);
3212  }
3213  factors.append (A);
3214  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3215  swapLevel2, x);
3216  if (!extension)
3217  normalize (factors);
3218  delete [] Aeval2;
3219  return factors;
3220  }
3221 
3222  if (minFactorsLength == 0)
3223  minFactorsLength= biFactors.length();
3224  else if (biFactors.length() > minFactorsLength)
3225  refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
3226  minFactorsLength= tmin (minFactorsLength, biFactors.length());
3227 
3228  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
3229 
3230  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
3231 
3232  minFactorsLength= tmin (minFactorsLength, biFactors.length());
3233 
3234  if (minFactorsLength == 1)
3235  {
3236  if (extension)
3237  {
3238  CFList source, dest;
3239  A= mapDown (A, info, source, dest);
3240  }
3241  factors.append (A);
3242  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3243  swapLevel2, x);
3244  if (!extension)
3245  normalize (factors);
3246  delete [] Aeval2;
3247  return factors;
3248  }
3249 
3250  if (differentSecondVar == lengthAeval2)
3251  {
3252  bool zeroOccured= false;
3253  for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
3254  {
3255  if (iter.getItem().isZero())
3256  {
3257  zeroOccured= true;
3258  break;
3259  }
3260  }
3261  if (!zeroOccured)
3262  {
3263  factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
3264  minFactorsLength);
3265  if (factors.length() == biFactors.length())
3266  {
3267  if (extension)
3268  factors= extNonMonicFactorRecombination (factors, A, info);
3269 
3270  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3271  swapLevel2, x);
3272  if (!extension)
3273  normalize (factors);
3274  delete [] Aeval2;
3275  return factors;
3276  }
3277  else
3278  factors= CFList();
3279  //TODO case where factors.length() > 0
3280  }
3281  }
3282 
3283  CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
3284  for (int i= 0; i < lengthAeval2; i++)
3285  oldAeval[i]= Aeval2[i];
3286 
3287  getLeadingCoeffs (A, Aeval2);
3288 
3289  CFList biFactorsLCs;
3290  for (CFListIterator i= biFactors; i.hasItem(); i++)
3291  biFactorsLCs.append (LC (i.getItem(), 1));
3292 
3293  Variable v;
3294  TIMING_START (fac_fq_precompute_leadcoeff);
3295  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
3296  evaluation, Aeval2, lengthAeval2, v);
3297 
3298  if (v.level() != 1)
3299  changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
3300  uniFactors, v);
3301 
3302  CanonicalForm oldA= A;
3303  CFList oldBiFactors= biFactors;
3304 
3305  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
3306  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
3307  leadingCoeffs.removeFirst();
3308 
3309  if (!LCmultiplierIsConst)
3310  distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
3311 
3312  //prepare leading coefficients
3313  CFList* leadingCoeffs2= new CFList [lengthAeval2];
3314  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
3315  biFactors, evaluation);
3316 
3318  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
3319  bufBiFactors= biFactors;
3320  bufA= A;
3321  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
3322  if (!LCmultiplierIsConst)
3323  {
3324  testVars= Variable (2);
3325  for (int i= 0; i < lengthAeval2; i++)
3326  {
3327  if (!oldAeval[i].isEmpty())
3328  testVars *= oldAeval[i].getFirst().mvar();
3329  }
3330  }
3331  TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
3332  "time to precompute LC over Fq: ");
3333 
3334  TIMING_START (fac_fq_luckswang);
3335  CFList bufFactors= CFList();
3336  bool LCheuristic= false;
3337  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
3338  factors))
3339  {
3340  int check= biFactors.length();
3341  int * index= new int [factors.length()];
3342  CFList oldFactors= factors;
3343  factors= recoverFactors (A, factors, index);
3344 
3345  if (check == factors.length())
3346  {
3347  if (extension)
3348  factors= extNonMonicFactorRecombination (factors, bufA, info);
3349 
3350  if (v.level() != 1)
3351  {
3352  for (iter= factors; iter.hasItem(); iter++)
3353  iter.getItem()= swapvar (iter.getItem(), v, y);
3354  }
3355 
3356  appendSwapDecompress (factors, contentAFactors, N, swapLevel,
3357  swapLevel2, x);
3358  if (!extension)
3359  normalize (factors);
3360  delete [] index;
3361  delete [] Aeval2;
3362  TIMING_END_AND_PRINT (fac_fq_luckswang,
3363  "time for successful LucksWang over Fq: ");
3364  return factors;
3365  }
3366  else if (factors.length() > 0)
3367  {
3368  int oneCount= 0;
3369  CFList l;
3370  for (int i= 0; i < check; i++)
3371  {
3372  if (index[i] == 1)
3373  {
3374  iter=biFactors;
3375  for (int j=1; j <= i-oneCount; j++)
3376  iter++;
3377  iter.remove (1);
3378  for (int j= 0; j < lengthAeval2; j++)
3379  {
3380  l= leadingCoeffs2[j];
3381  iter= l;
3382  for (int k=1; k <= i-oneCount; k++)
3383  iter++;
3384  iter.remove (1);
3385  leadingCoeffs2[j]=l;
3386  }
3387  oneCount++;
3388  }
3389  }
3390  bufFactors= factors;
3391  factors= CFList();
3392  }
3393  else if (!LCmultiplierIsConst && factors.length() == 0)
3394  {
3395  LCheuristic= true;
3396  factors= oldFactors;
3397  CFList contents, LCs;
3398  bool foundTrueMultiplier= false;
3399  LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
3400  contents, LCs, foundTrueMultiplier);
3401  if (foundTrueMultiplier)
3402  {
3403  A= oldA;
3404  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3405  for (int i= lengthAeval2-1; i > -1; i--)
3406  leadingCoeffs2[i]= CFList();
3407  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
3408  leadingCoeffs, biFactors, evaluation);
3409  }
3410  else
3411  {
3412  bool foundMultiplier= false;
3413  LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
3414  A, leadingCoeffs2, lengthAeval2, foundMultiplier);
3415 
3416  // coming from above: divide out more LCmultiplier if possible
3417  if (foundMultiplier)
3418  {
3419  foundMultiplier= false;
3420  LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
3421  lengthAeval2, leadingCoeffs2, A, LCmultiplier,
3422  foundMultiplier);
3423  }
3424  else
3425  {
3426  LCHeuristicCheck (LCs, contents, A, oldA,
3427  leadingCoeffs2[lengthAeval2-1], foundMultiplier);
3428  if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
3429  {
3430  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3431  lengthAeval2, evaluation, oldBiFactors);
3432  }
3433  }
3434 
3435  // patch everything together again
3436  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3437  for (int i= lengthAeval2-1; i > -1; i--)
3438  leadingCoeffs2[i]= CFList();
3439  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3440  biFactors, evaluation);
3441  }
3442  factors= CFList();
3443  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3444  {
3445  LCheuristic= false;
3446  A= bufA;
3447  biFactors= bufBiFactors;
3448  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3449  LCmultiplier= bufLCmultiplier;
3450  }
3451  }
3452  else
3453  factors= CFList();
3454  delete [] index;
3455  }
3456  TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
3457 
3458  TIMING_START (fac_fq_lcheuristic);
3459  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
3460  && fdivides (getVars (LCmultiplier), testVars))
3461  {
3462  LCheuristic= true;
3463  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
3464  lengthAeval2, evaluation, oldBiFactors);
3465 
3466  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
3467  for (int i= lengthAeval2-1; i > -1; i--)
3468  leadingCoeffs2[i]= CFList();
3469  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
3470  biFactors, evaluation);
3471 
3472  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
3473  {
3474  LCheuristic= false;
3475  A= bufA;
3476  biFactors= bufBiFactors;
3477  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3478  LCmultiplier= bufLCmultiplier;
3479  }
3480  }
3481  TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
3482 
3483 tryAgainWithoutHeu:
3484  TIMING_START (fac_fq_shift_to_zero);
3485  A= shift2Zero (A, Aeval, evaluation);
3486 
3487  for (iter= biFactors; iter.hasItem(); iter++)
3488  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3489 
3490  for (int i= 0; i < lengthAeval2-1; i++)
3491  leadingCoeffs2[i]= CFList();
3492  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
3493  {
3494  iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
3495  for (int i= A.level() - 4; i > -1; i--)
3496  {
3497  if (i + 1 == lengthAeval2-1)
3498  leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
3499  else
3500  leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
3501  }
3502  }
3503  TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
3504  "time to shift evaluation point to zero: ");
3505 
3506  CFArray Pi;
3507  CFList diophant;
3508  int* liftBounds= new int [A.level() - 1];
3509  int liftBoundsLength= A.level() - 1;
3510  for (int i= 0; i < liftBoundsLength; i++)
3511  liftBounds [i]= degree (A, i + 2) + 1;
3512 
3513  Aeval.removeFirst();
3514  bool noOneToOne= false;
3515  TIMING_START (fac_fq_hensel_lift);
3516  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
3517  Pi, liftBounds, liftBoundsLength, noOneToOne);
3518  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3519  "time for non monic hensel lifting over Fq: ");
3520 
3521  if (!noOneToOne)
3522  {
3523  int check= factors.length();
3524  A= oldA;
3525  TIMING_START (fac_fq_recover_factors);
3526  factors= recoverFactors (A, factors, evaluation);
3527  TIMING_END_AND_PRINT (fac_fq_recover_factors,
3528  "time to recover factors over Fq: ");
3529  if (check != factors.length())
3530  noOneToOne= true;
3531  else
3532  factors= Union (factors, bufFactors);
3533 
3534  if (extension && !noOneToOne)
3535  factors= extNonMonicFactorRecombination (factors, A, info);
3536  }
3537  if (noOneToOne)
3538  {
3539  if (!LCmultiplierIsConst && LCheuristic)
3540  {
3541  A= bufA;
3542  biFactors= bufBiFactors;
3543  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
3544  delete [] liftBounds;
3545  LCheuristic= false;
3546  goto tryAgainWithoutHeu;
3547  //something probably went wrong in the heuristic
3548  }
3549 
3550  A= shift2Zero (oldA, Aeval, evaluation);
3551  biFactors= oldBiFactors;
3552  for (iter= biFactors; iter.hasItem(); iter++)
3553  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
3554  CanonicalForm LCA= LC (Aeval.getFirst(), 1);
3555  CanonicalForm yToLift= power (y, lift);
3556  CFListIterator i= biFactors;
3557  lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
3558  i++;
3559 
3560  for (; i.hasItem(); i++)
3561  lift= tmax (lift,
3562  degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
3563 
3564  lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
3565 
3566  i= biFactors;
3567  yToLift= power (y, lift);
3568  CanonicalForm dummy;
3569  for (; i.hasItem(); i++)
3570  {
3571  LCA= LC (i.getItem(), 1);
3572  extgcd (LCA, yToLift, LCA, dummy);
3573  i.getItem()= mod (i.getItem()*LCA, yToLift);
3574  }
3575 
3576  liftBoundsLength= F.level() - 1;
3577  liftBounds= liftingBounds (A, lift);
3578 
3579  CFList MOD;
3580  bool earlySuccess;
3581  CFList earlyFactors, liftedFactors;
3582  TIMING_START (fac_fq_hensel_lift);
3583  liftedFactors= henselLiftAndEarly
3584  (A, MOD, liftBounds, earlySuccess, earlyFactors,
3585  Aeval, biFactors, evaluation, info);
3586  TIMING_END_AND_PRINT (fac_fq_hensel_lift,
3587  "time for hensel lifting over Fq: ");
3588 
3589  if (!extension)
3590  {
3591  TIMING_START (fac_fq_factor_recombination);
3592  factors= factorRecombination (A, liftedFactors, MOD);
3593  TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3594  "time for factor recombination: ");
3595  }
3596  else
3597  {
3598  TIMING_START (fac_fq_factor_recombination);
3599  factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
3600  TIMING_END_AND_PRINT (fac_fq_factor_recombination,
3601  "time for factor recombination: ");
3602  }
3603 
3604  if (earlySuccess)
3605  factors= Union (factors, earlyFactors);
3606  if (!extension)
3607  {
3608  for (CFListIterator i= factors; i.hasItem(); i++)
3609  {
3610  int kk= Aeval.getLast().level();
3611  for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
3612  {
3613  if (i.getItem().level() < kk)
3614  continue;
3615  i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
3616  }
3617  }
3618  }
3619  }
3620 
3621  if (v.level() != 1)
3622  {
3623  for (CFListIterator iter= factors; iter.hasItem(); iter++)
3624  iter.getItem()= swapvar (iter.getItem(), v, y);
3625  }
3626 
3627  swap (factors, swapLevel, swapLevel2, x);
3628  append (factors, contentAFactors);
3629  decompress (factors, N);
3630  if (!extension)
3631  normalize (factors);
3632 
3633  delete[] liftBounds;
3634 
3635  return factors;
3636 }
3637 
3638 /// multivariate factorization over an extension of the initial field
3639 CFList
3641 {
3642  CanonicalForm A= F;
3643 
3644  Variable alpha= info.getAlpha();
3645  Variable beta= info.getBeta();
3646  int k= info.getGFDegree();
3647  char cGFName= info.getGFName();
3648  CanonicalForm delta= info.getDelta();
3649  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
3650  Variable w= Variable (1);
3651 
3652  CFList factors;
3653  if (!GF && alpha == w) // we are in F_p
3654  {
3655  CFList factors;
3656  bool extension= true;
3657  int p= getCharacteristic();
3658  if (p < 7)
3659  {
3660  if (p == 2)
3662  else if (p == 3)
3664  else if (p == 5)
3666  ExtensionInfo info= ExtensionInfo (extension);
3667  A= A.mapinto();
3668  factors= multiFactorize (A, info);
3669 
3672  Variable vBuf= rootOf (mipo.mapinto());
3673  for (CFListIterator j= factors; j.hasItem(); j++)
3674  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3675  prune (vBuf);
3676  }
3677  else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
3678  {
3680  ExtensionInfo info= ExtensionInfo (extension);
3681  A= A.mapinto();
3682  factors= multiFactorize (A, info);
3683 
3686  Variable vBuf= rootOf (mipo.mapinto());
3687  for (CFListIterator j= factors; j.hasItem(); j++)
3688  j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
3689  prune (vBuf);
3690  }
3691  else // not able to pass to GF, pass to F_p(\alpha)
3692  {
3694  Variable v= rootOf (mipo);
3695  ExtensionInfo info= ExtensionInfo (v);
3696  factors= multiFactorize (A, info);
3697  prune (v);
3698  }
3699  return factors;
3700  }
3701  else if (!GF && (alpha != w)) // we are in F_p(\alpha)
3702  {
3703  if (k == 1) // need factorization over F_p
3704  {
3705  int extDeg= degree (getMipo (alpha));
3706  extDeg++;
3707  CanonicalForm mipo= randomIrredpoly (extDeg, w);
3708  Variable v= rootOf (mipo);
3709  ExtensionInfo info= ExtensionInfo (v);
3710  factors= multiFactorize (A, info);
3711  prune (v);
3712  }
3713  else
3714  {
3715  if (beta == w)
3716  {
3717  Variable v= chooseExtension (alpha, beta, k);
3718  CanonicalForm primElem, imPrimElem;
3719  bool primFail= false;
3720  Variable vBuf;
3721  primElem= primitiveElement (alpha, vBuf, primFail);
3722  ASSERT (!primFail, "failure in integer factorizer");
3723  if (primFail)
3724  ; //ERROR
3725  else
3726  imPrimElem= mapPrimElem (primElem, alpha, v);
3727 
3728  CFList source, dest;
3729  CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
3730  source, dest);
3731  ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
3732  factors= multiFactorize (bufA, info);
3733  prune (v);
3734  }
3735  else
3736  {
3737  Variable v= chooseExtension (alpha, beta, k);
3738  CanonicalForm primElem, imPrimElem;
3739  bool primFail= false;
3740  Variable vBuf;
3741  ASSERT (!primFail, "failure in integer factorizer");
3742  if (primFail)
3743  ; //ERROR
3744  else
3745  imPrimElem= mapPrimElem (delta, beta, v);
3746 
3747  CFList source, dest;
3748  CanonicalForm bufA= mapDown (A, info, source, dest);
3749  source= CFList();
3750  dest= CFList();
3751  bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
3752  ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
3753  factors= multiFactorize (bufA, info);
3754  prune (v);
3755  }
3756  }
3757  return factors;
3758  }
3759  else // we are in GF (p^k)
3760  {
3761  int p= getCharacteristic();
3762  int extensionDeg= getGFDegree();
3763  bool extension= true;
3764  if (k == 1) // need factorization over F_p
3765  {
3766  extensionDeg++;
3767  if (pow ((double) p, (double) extensionDeg) < (1<<16))
3768  // pass to GF(p^k+1)
3769  {
3771  setCharacteristic (p);
3772  Variable vBuf= rootOf (mipo.mapinto());
3773  A= GF2FalphaRep (A, vBuf);
3774  setCharacteristic (p, extensionDeg, 'Z');
3775  ExtensionInfo info= ExtensionInfo (extension);
3776  factors= multiFactorize (A.mapinto(), info);
3777  prune (vBuf);
3778  }
3779  else // not able to pass to another GF, pass to F_p(\alpha)
3780  {
3782  setCharacteristic (p);
3783  Variable vBuf= rootOf (mipo.mapinto());
3784  A= GF2FalphaRep (A, vBuf);
3785  Variable v= chooseExtension (vBuf, beta, k);
3786  ExtensionInfo info= ExtensionInfo (v, extension);
3787  factors= multiFactorize (A, info);
3788  prune (vBuf);
3789  }
3790  }
3791  else // need factorization over GF (p^k)
3792  {
3793  if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
3794  // pass to GF(p^2k)
3795  {
3796  setCharacteristic (p, 2*extensionDeg, 'Z');
3797  ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
3798  factors= multiFactorize (GFMapUp (A, extensionDeg), info);
3799  setCharacteristic (p, extensionDeg, cGFName);
3800  }
3801  else // not able to pass to GF (p^2k), pass to F_p (\alpha)
3802  {
3804  setCharacteristic (p);
3805  Variable v1= rootOf (mipo.mapinto());
3806  A= GF2FalphaRep (A, v1);
3807  Variable v2= chooseExtension (v1, v1, k);
3808  CanonicalForm primElem, imPrimElem;
3809  bool primFail= false;
3810  Variable vBuf;
3811  primElem= primitiveElement (v1, v1, primFail);
3812  if (primFail)
3813  ; //ERROR
3814  else
3815  imPrimElem= mapPrimElem (primElem, v1, v2);
3816  CFList source, dest;
3817  CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
3818  source, dest);
3819  ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
3820  factors= multiFactorize (bufA, info);
3821  setCharacteristic (p, k, cGFName);
3822  for (CFListIterator i= factors; i.hasItem(); i++)
3823  i.getItem()= Falpha2GFRep (i.getItem());
3824  prune (v1);
3825  }
3826  }
3827  return factors;
3828  }
3829 }
3830 
3831 #endif
3832 /* HAVE_NTL */
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void size_t count
Definition: si_signals.h:59
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
char getGFName() const
getter
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
void indexUpdate(int index [], const int &subsetSize, const int &setSize, bool &noSubset)
update index
List< CanonicalForm > CFList
Variable getAlpha() const
getter
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
Definition: gitfan.cc:549
CFList LCFeval
Definition: facFactorize.cc:54
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:170
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
static int newMainVariableSearch(CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
const CanonicalForm int s
Definition: facAbsFact.cc:55
generate random elements in GF
Definition: cf_random.h:31
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int j
Definition: facHensel.cc:105
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CFArray copy(const CFList &list)
write elements of list into an array
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
Conversion to and from NTL.
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
This file defines functions for Hensel lifting.
This file provides utility functions for multivariate factorization.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
int level(const CanonicalForm &f)
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
#define DELETE_ARRAY(P)
Definition: cf_defs.h:50
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
Matrix< CanonicalForm > CFMatrix
CanonicalForm LCF
Definition: facFactorize.cc:53
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
CanonicalForm getDelta() const
getter
CanonicalForm buf1
Definition: facFqBivar.cc:71
functions to print debug output
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
Definition: cfUnivarGcd.cc:173
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
int getGFDegree() const
getter
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
TIMING_START(fac_alg_resultant)
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
factory&#39;s class for variables
Definition: factory.h:117
bool bad
Definition: facFactorize.cc:65
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
VAR int check
Definition: libparse.cc:1106
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:156
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
CFFListIterator iter
Definition: facAbsBiFact.cc:54
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
factory&#39;s main class
Definition: canonicalform.h:77
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
assertions for Factory
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
Array< CanonicalForm > CFArray
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:92
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Variable alpha
Definition: facAbsBiFact.cc:52
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
This file provides functions for factorizing a multivariate polynomial over , or GF...
static const double log2exp
Definition: cfEzgcd.cc:39
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
void insert(const T &)
Definition: ftmpl_list.cc:193
const CFList & factors2
int min() const
Definition: ftmpl_array.cc:98
CanonicalForm Lc(const CanonicalForm &f)
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CanonicalForm generate() const
Definition: cf_random.cc:145
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
void setCharacteristic(int c)
Definition: cf_char.cc:23
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
#define CHAR_THRESHOLD
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
void prune(Variable &alpha)
Definition: variable.cc:261
void removeFirst()
Definition: ftmpl_list.cc:287
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
int size() const
Definition: ftmpl_array.cc:92
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm mapinto() const
This file implements functions to map between extensions of finite fields.
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
bool found
Definition: facFactorize.cc:56
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:49
#define M
Definition: sirandom.c:25
This file provides functions for sparse heuristic Hensel lifting.
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
void removeLast()
Definition: ftmpl_list.cc:317
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity ...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
int max() const
Definition: ftmpl_array.cc:104
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm generate() const
Definition: cf_random.cc:66
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:788
int * degsf
Definition: cfEzgcd.cc:52
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int status int void * buf
Definition: si_signals.h:59
This file defines functions for fast multiplication and division with remainder.
int level() const
Definition: factory.h:134
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:24
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition: facHensel.cc:1653
static CanonicalForm myContent(const CanonicalForm &F)
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
CanonicalForm generate() const
Definition: cf_random.cc:56
else L getLast()(0
CFList & eval
Definition: facFactorize.cc:48
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
Variable getBeta() const
getter
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
int m
Definition: cfEzgcd.cc:121
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53
generate random elements in F_p
Definition: cf_random.h:43
int i
Definition: cfEzgcd.cc:125
T getLast() const
Definition: ftmpl_list.cc:309
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
generate random integers, random elements of finite fields
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
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)
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
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 contentx
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm buf2
Definition: facFqBivar.cc:71
Variable beta
Definition: facAbsFact.cc:99
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
STATIC_VAR Poly * h
Definition: janet.cc:971
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
generate random irreducible univariate polynomials
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
static CanonicalForm listGCD(const CFList &L)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
generate random elements in F_p(alpha)
Definition: cf_random.h:70
int length() const
Definition: ftmpl_list.cc:273
static int gettype()
Definition: cf_factory.h:28
#define swap(_i, _j)
CanonicalForm mipo
Definition: facAlgExt.cc:57
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
CFList conv(const CFArray &A)
Factor< CanonicalForm > CFFactor
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
int gcd(int a, int b)
Definition: walkSupport.cc:836
fq_nmod_poly_t prod
Definition: facHensel.cc:95
bool isInExtension() const
getter
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
const CanonicalForm & w
Definition: facAbsFact.cc:55
int getGFDegree()
Definition: cf_char.cc:56
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition: facHensel.cc:1694
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:23
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
CanonicalForm deriv_x
Definition: facFactorize.cc:59
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted...
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
int level() const
level() returns the level of CO.
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
Definition: cf_irred.cc:42
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
int p
Definition: cfModGcd.cc:4019
int degree(const CanonicalForm &f)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
CanonicalForm LC(const CanonicalForm &f)
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
CanonicalForm getGamma() const
getter
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
Definition: facHensel.cc:2018
STATIC_VAR TreeM * G
Definition: janet.cc:31
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:93
return result
Definition: facAbsBiFact.cc:76
STATIC_VAR jList * T
Definition: janet.cc:30
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
TIMING_DEFINE_PRINT(fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition: facHensel.cc:1719
bool inCoeffDomain() const