My Project  UNKNOWN_GIT_VERSION
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)
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 
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 {
223  CanonicalForm gamma= info.getGamma();
225  int k= info.getGFDegree();
226  CFList source, dest;
227  if (factors.length() == 1)
228  {
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));
273  g /= Lc (g);
274  appendTestMapDown (result, g, info, source, dest);
275  return result;
276  }
277  else
278  {
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  {
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  {
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  {
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  {
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 {
515  CanonicalForm gamma= info.getGamma();
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 {
662  CanonicalForm gamma= info.getGamma();
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
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);
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++;
877  CanonicalForm contentx= content (i.getItem(), x);
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++;
994  CanonicalForm buf= j.getItem();
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,
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  {
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;
1286  CanonicalForm content= l.getFirst();
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;
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
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 
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 
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 
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 {
2409  CanonicalForm gamma= info.getGamma();
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 
2926  CanonicalForm gamma= info.getGamma();
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  {
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);
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;
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,
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 
3646  int k= info.getGFDegree();
3647  char cGFName= info.getGFName();
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);
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);
3710  factors= multiFactorize (A, info);
3711  prune (v);
3712  }
3713  else
3714  {
3715  if (beta == w)
3716  {
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  {
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 */
prodMod
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3047
test
CanonicalForm test
Definition: cfModGcd.cc:4037
Matrix
Definition: ftmpl_matrix.h:20
timing.h
ExtensionInfo::getGFDegree
int getGFDegree() const
getter
Definition: ExtensionInfo.h:139
earlyFactorDetect
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...
Definition: facFqFactorize.cc:605
myContent
static CanonicalForm myContent(const CanonicalForm &F)
Definition: facFqFactorize.cc:61
nonMonicHenselLift
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
FFRandom
generate random elements in F_p
Definition: cf_random.h:44
ExtensionInfo::getBeta
Variable getBeta() const
getter
Definition: ExtensionInfo.h:118
distributeLCmultiplier
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...
Definition: facFqFactorize.cc:2574
reverseShift
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Definition: facFqFactorizeUtil.cc:148
gcd_deriv
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
j
int j
Definition: facHensel.cc:105
extFactorize
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
Definition: facFqFactorize.cc:3640
ExtensionInfo::isInExtension
bool isInExtension() const
getter
Definition: ExtensionInfo.h:153
extEarlyFactorDetect
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...
Definition: facFqFactorize.cc:656
k
int k
Definition: cfEzgcd.cc:92
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
recoverFactors
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
Definition: facFqFactorizeUtil.cc:238
squarefreeFactorization
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
Definition: facFqSquarefree.cc:181
result
return result
Definition: facAbsBiFact.cc:76
recombination
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...
Definition: facFqFactorize.cc:2100
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
evaluateAtEval
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
Definition: facFqFactorizeUtil.cc:206
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
liftBoundAdaption
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.
Definition: facFqFactorize.cc:445
uniFactorizer
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
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
evaluationWRTDifferentSecondVars
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...
Definition: facFqFactorize.cc:1950
irred
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
LCFeval
CFList LCFeval
Definition: facFactorize.cc:54
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
CFMap
class CFMap
Definition: cf_map.h:85
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
cf_irred.h
isOnlyLeadingCoeff
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
Definition: facFqFactorizeUtil.cc:162
LCHeuristic3
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 ...
Definition: facFqFactorize.cc:2792
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
appendTestMapDown
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
Definition: facFqBivarUtil.cc:223
AlgExtRandomF
generate random elements in F_p(alpha)
Definition: cf_random.h:70
GFRandom::generate
CanonicalForm generate() const
Definition: cf_random.cc:66
g
g
Definition: cfModGcd.cc:4031
bad
bool bad
Definition: facFactorize.cc:65
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
rootOf
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
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition: canonicalform.h:391
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
getLeadingCoeffs
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
Definition: facFqFactorize.cc:2216
cf_random.h
randomIrredpoly
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
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
FqBiSqrfFactorize
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
sparseHeuristic
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...
Definition: facSparseHensel.cc:155
primitiveElement
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
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
extgcd
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
henselLiftAndEarly
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
Definition: facFqFactorize.cc:972
facSparseHensel.h
cfUnivarGcd.h
facFqFactorizeUtil.h
lcmContent
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
Definition: facFqFactorize.cc:954
CanonicalForm
factory's main class
Definition: canonicalform.h:83
extNonMonicFactorRecombination
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
Definition: facFqFactorize.cc:2404
found
bool found
Definition: facFactorize.cc:56
evaluateAtZero
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
Definition: facFqFactorizeUtil.cc:193
LCHeuristicCheck
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,...
Definition: facFqFactorize.cc:2746
amp::ceil
const signed long ceil(const ampf< Precision > &x)
Definition: amp.h:789
gcdFreeBasis
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
Definition: facFqFactorize.cc:1255
newMainVariableSearch
static int newMainVariableSearch(CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
Definition: facFqFactorize.cc:913
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
distributeContent
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
Definition: facFqFactorize.cc:1281
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
factors2
const CFList & factors2
Definition: facFqBivarUtil.cc:42
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition: facFqFactorize.cc:2304
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
changeSecondVariable
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
Definition: facFqFactorize.cc:2527
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
nonMonicHenselLift12
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
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
listGCD
static CanonicalForm listGCD(const CFList &L)
Definition: facFqFactorize.cc:77
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
M
#define M
Definition: sirandom.c:24
myCompress
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
Definition: facFqFactorize.cc:136
buf
int status int void * buf
Definition: si_signals.h:59
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
factorRecombination
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
Definition: facFqFactorize.cc:360
appendSwapDecompress
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...
Definition: facFqBivarUtil.cc:70
Array::size
int size() const
Definition: ftmpl_array.cc:92
TIMING_START
TIMING_START(fac_alg_resultant)
sortCFFListByNumOfVars
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
Definition: facFqFactorizeUtil.cc:186
ExtensionInfo::getGamma
CanonicalForm getGamma() const
getter
Definition: ExtensionInfo.h:125
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
Aeval
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition: cfModResultant.cc:311
evalPoints
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...
Definition: facFqFactorize.cc:740
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
conv
CFList conv(const CFArray &A)
Definition: facFqFactorize.cc:2207
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
T
static jList * T
Definition: janet.cc:31
TIMING_DEFINE_PRINT
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)
ilog2
int ilog2(const CanonicalForm &a)
Definition: canonicalform.h:345
cf_map_ext.h
h
static Poly * h
Definition: janet.cc:972
henselLiftResume
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
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
NTLconvert.h
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
log2exp
static const double log2exp
Definition: cfEzgcd.cc:39
LucksWangSparseHeuristic
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Definition: facSparseHensel.cc:26
ExtensionInfo::getGFName
char getGFName() const
getter
Definition: ExtensionInfo.h:146
prune
void prune(Variable &alpha)
Definition: variable.cc:261
isInExtension
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)
Definition: facFqBivarUtil.cc:184
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
LCHeuristic
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...
Definition: facFqFactorize.cc:2598
buf1
CanonicalForm buf1
Definition: facFqBivar.cc:71
biSqrfFactorizeHelper
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:53
Variable::level
int level() const
Definition: factory.h:134
henselLift
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
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
prepareLeadingCoeffs
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 ...
Definition: facFqFactorize.cc:2365
LCHeuristic4
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...
Definition: facFqFactorize.cc:2840
eval
CFList & eval
Definition: facFactorize.cc:48
GFRandom
generate random elements in GF
Definition: cf_random.h:32
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition: cfNewtonPolygon.cc:853
beta
Variable beta
Definition: facAbsFact.cc:99
ExtensionInfo::getDelta
CanonicalForm getDelta() const
getter
Definition: ExtensionInfo.h:132
LCHeuristic2
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....
Definition: facFqFactorize.cc:2762
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
Factor
Definition: ftmpl_factor.h:18
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
deriv_x
CanonicalForm deriv_x
Definition: facFactorize.cc:59
ListIterator::remove
void remove(int moveright)
Definition: ftmpl_list.cc:526
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition: facFqBivarUtil.cc:373
List::length
int length() const
Definition: ftmpl_list.cc:273
testFactors
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
Definition: facFqFactorize.cc:1371
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Definition: facFqFactorize.cc:2910
FpBiSqrfFactorize
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
List::removeLast
void removeLast()
Definition: ftmpl_list.cc:317
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
degsf
int * degsf
Definition: cfEzgcd.cc:52
Variable
factory's class for variables
Definition: factory.h:118
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
prodEval
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
Definition: facFqFactorize.cc:1998
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
ExtensionInfo
Definition: ExtensionInfo.h:51
mapPrimElem
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
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
facHensel.h
refineBiFactors
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
Definition: facFqFactorize.cc:2318
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
appendMapDown
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
Definition: facFqBivarUtil.cc:267
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
FFRandom::generate
CanonicalForm generate() const
Definition: cf_random.cc:56
m
int m
Definition: cfEzgcd.cc:121
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
getLast
else L getLast()(0
check
int check
Definition: libparse.cc:1104
l
int l
Definition: cfEzgcd.cc:93
myGetVars
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
Definition: facFqFactorizeUtil.cc:168
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
liftingBounds
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
Definition: facFqFactorizeUtil.cc:118
cf_assert.h
contentx
CanonicalForm contentx
Definition: facFactorize.cc:129
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
sortByUniFactors
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...
Definition: facFqFactorize.cc:2234
extLiftBoundAdaption
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...
Definition: facFqFactorize.cc:509
AlgExtRandomF::generate
CanonicalForm generate() const
Definition: cf_random.cc:145
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
swap
#define swap(_i, _j)
CHAR_THRESHOLD
#define CHAR_THRESHOLD
Definition: facFqFactorize.cc:738
Falpha2GFRep
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
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:59
subset
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
precomputeLeadingCoeff
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,...
Definition: facFqFactorize.cc:1464
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
GF2FalphaRep
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
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition: facFqBivarUtil.cc:364
checkHelper
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
Definition: facFqFactorize.cc:2008
ExtensionInfo::getAlpha
Variable getAlpha() const
getter
Definition: ExtensionInfo.h:111
GFMapUp
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
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
factorizationWRTDifferentSecondVars
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
Definition: facFqFactorize.cc:2169
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
checkOneToOne
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...
Definition: facFqFactorize.cc:2032
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
buf2
CanonicalForm buf2
Definition: facFqBivar.cc:71
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
LCF
CanonicalForm LCF
Definition: facFactorize.cc:53
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition: facFqFactorizeUtil.cc:131
extFactorRecombination
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....
Definition: facFqFactorize.cc:217
debug.h
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
facMul.h
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
henselLift23
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
chooseExtension
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
mapDown
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
ListIterator
Definition: ftmpl_list.h:17
facFqFactorize.h