source: git/factory/facFactorize.cc @ 41e77d

spielwiese
Last change on this file since 41e77d was 41e77d, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: minor bug in precomputeLeadingCoeff chg: normalize only if necessary
  • Property mode set to 100644
File size: 46.6 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.cc
5 *
6 * multivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13#include "config.h"
14
15#include "assert.h"
16#include "debug.h"
17#include "timing.h"
18
19#include "cf_algorithm.h"
20#include "facFqFactorizeUtil.h"
21#include "facFactorize.h"
22#include "facFqFactorize.h"
23#include "cf_random.h"
24#include "facHensel.h"
25#include "cf_gcd_smallp.h"
26#include "cf_map_ext.h"
27#include "algext.h"
28#include "cf_reval.h"
29#include "facSparseHensel.h"
30
31TIMING_DEFINE_PRINT(fac_bi_factorize)
32TIMING_DEFINE_PRINT(fac_hensel_lift)
33TIMING_DEFINE_PRINT(fac_factor_recombination)
34
35#ifdef HAVE_NTL
36CFList evalPoints (const CanonicalForm& F, CFList& eval, Evaluation& E)
37{
38  CFList result;
39  Variable x= Variable (1);
40
41  bool found= false;
42  bool allZero= true;
43  bool foundZero= false;
44  CanonicalForm deriv_x, gcd_deriv;
45  CFListIterator iter;
46  do
47  {
48    eval.insert (F);
49    bool bad= false;
50    for (int i= E.max(); i >= E.min(); i--)
51    {
52      eval.insert (eval.getFirst()( E [i], i));
53      result.append (E[i]);
54      if (!E[i].isZero())
55        allZero= false;
56      else
57        foundZero= true;
58      if (!allZero && foundZero)
59      {
60        result= CFList();
61        eval= CFList();
62        bad= true;
63        foundZero= false;
64        break;
65      }
66      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
67      {
68        result= CFList();
69        eval= CFList();
70        bad= true;
71        break;
72      }
73    }
74
75    if (bad)
76    {
77      E.nextpoint();
78      continue;
79    }
80
81    if (degree (eval.getFirst()) != degree (F, 1))
82    {
83      result= CFList();
84      eval= CFList();
85      E.nextpoint();
86      continue;
87    }
88
89    deriv_x= deriv (eval.getFirst(), x);
90    gcd_deriv= gcd (eval.getFirst(), deriv_x);
91    if (degree (gcd_deriv) > 0)
92    {
93      result= CFList();
94      eval= CFList();
95      E.nextpoint();
96      continue;
97    }
98    iter= eval;
99    iter++;
100    CanonicalForm contentx= content (iter.getItem(), x);
101    if (degree (contentx) > 0)
102    {
103      result= CFList();
104      eval= CFList();
105      E.nextpoint();
106      continue;
107    }
108    found= true;
109  }
110  while (!found);
111
112  if (!eval.isEmpty())
113    eval.removeFirst();
114  return result;
115}
116
117void
118factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
119                                     int& minFactorsLength, bool& irred,
120                                     const Variable& w)
121{
122  Variable x= Variable (1);
123  minFactorsLength= 0;
124  irred= false;
125  Variable v;
126  CFList factors;
127  CanonicalForm LCA= LC (A,1);
128  if (!LCA.inCoeffDomain())
129  {
130    for (int j= 0; j < A.level() - 2; j++)
131    {
132      if (!Aeval[j].isEmpty() && (degree (LCA, j+3) > 0))
133      {
134        v= Variable (Aeval[j].getFirst().level());
135
136        factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
137
138        if (factors.getFirst().inCoeffDomain())
139          factors.removeFirst();
140
141        if (minFactorsLength == 0)
142          minFactorsLength= factors.length();
143        else
144          minFactorsLength= tmin (minFactorsLength, factors.length());
145
146        if (factors.length() == 1)
147        {
148          irred= true;
149          return;
150        }
151        sortList (factors, x);
152        Aeval [j]= factors;
153      }
154      else if (!Aeval[j].isEmpty())
155      {
156        Aeval[j]=CFList();
157      }
158    }
159  }
160  else
161  {
162    for (int j= 0; j < A.level() - 2; j++)
163      Aeval[j]= CFList();
164  }
165}
166
167int
168testFactors (const CanonicalForm& G, const CFList& uniFactors,
169             CanonicalForm& sqrfPartF, CFList& factors,
170             CFFList*& bufSqrfFactors, CFList& evalSqrfPartF,
171             const CFArray& evalPoint)
172{
173  CanonicalForm tmp;
174  CFListIterator j;
175  for (CFListIterator i= uniFactors; i.hasItem(); i++)
176  {
177    tmp= i.getItem();
178    if (i.hasItem())
179      i++;
180    else
181      break;
182    for (j= i; j.hasItem(); j++)
183    {
184      if (tmp == j.getItem())
185        return 0;
186    }
187  }
188
189  CanonicalForm F= G;
190  CFFList sqrfFactorization= sqrFree (F);
191
192  sqrfPartF= 1;
193  for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
194    sqrfPartF *= i.getItem().factor();
195
196  evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
197
198  CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
199
200  if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
201    return 0;
202
203  CFFList sqrfFactors;
204  CFList tmp2;
205  int k= 0;
206  factors= uniFactors;
207  CFFListIterator iter;
208  for (CFListIterator i= factors; i.hasItem(); i++, k++)
209  {
210    tmp= 1;
211    sqrfFactors= sqrFree (i.getItem());
212
213    for (iter= sqrfFactors; iter.hasItem(); iter++)
214    {
215      tmp2.append (iter.getItem().factor());
216      tmp *= iter.getItem().factor();
217    }
218    i.getItem()= tmp/Lc(tmp);
219    bufSqrfFactors [k]= sqrfFactors;
220  }
221
222  for (int i= 0; i < factors.length() - 1; i++)
223  {
224    for (int k= i + 1; k < factors.length(); k++)
225    {
226      gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
227    }
228  }
229
230  factors= CFList();
231  for (int i= 0; i < uniFactors.length(); i++)
232  {
233    if (i == 0)
234    {
235      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
236      {
237        if (iter.getItem().factor().inCoeffDomain())
238          continue;
239        iter.getItem()= CFFactor (iter.getItem().factor()/
240                                  Lc (iter.getItem().factor()),
241                                  iter.getItem().exp());
242        factors.append (iter.getItem().factor());
243      }
244    }
245    else
246    {
247      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
248      {
249        if (iter.getItem().factor().inCoeffDomain())
250          continue;
251        iter.getItem()= CFFactor (iter.getItem().factor()/
252                               Lc (iter.getItem().factor()),
253                               iter.getItem().exp());
254        if (!find (factors, iter.getItem().factor()))
255          factors.append (iter.getItem().factor());
256      }
257    }
258  }
259
260  test= prod (factors);
261  tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
262  if (test/Lc (test) != tmp/Lc (tmp))
263    return 0;
264  else
265    return 1;
266}
267
268CFList
269precomputeLeadingCoeff (const CanonicalForm& LCF, const CFList& LCFFactors,
270                        const CFList& evaluation,CFList*& differentSecondVarLCs,
271                        int length, Variable& y
272                       )
273{
274  y= Variable (1);
275  if (LCF.inCoeffDomain())
276  {
277    CFList result;
278    for (int i= 1; i <= LCFFactors.length() + 1; i++)
279      result.append (1);
280    return result;
281  }
282
283  CFMap N, M;
284  CFArray dummy= CFArray (2);
285  dummy [0]= LCF;
286  dummy [1]= Variable (2);
287  compress (dummy, M, N);
288  CanonicalForm F= M (LCF);
289  if (LCF.isUnivariate())
290  {
291    CFList result;
292    int LCFLevel= LCF.level();
293    bool found= false;
294    if (LCFLevel == 2)
295    {
296    //bivariate leading coefficients are already the true leading coefficients
297      result= LCFFactors;
298      found= true;
299    }
300    else
301    {
302      CFListIterator j;
303      for (int i= 0; i < length; i++)
304      {
305        for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
306        {
307          if (j.getItem().level() == LCFLevel)
308          {
309            found= true;
310            break;
311          }
312        }
313        if (found)
314        {
315          result= differentSecondVarLCs [i];
316          break;
317        }
318      }
319      if (!found)
320        result= LCFFactors;
321    }
322    if (found)
323      result.insert (Lc (LCF));
324    else
325    {
326      for (CFListIterator i= result; i.hasItem(); i++)
327        i.getItem() *= LCF;
328      result.insert (LCF);
329    }
330    return result;
331  }
332
333  CFList factors= LCFFactors;
334
335  for (CFListIterator i= factors; i.hasItem(); i++)
336    i.getItem()= M (i.getItem());
337
338  CanonicalForm sqrfPartF;
339  CFFList * bufSqrfFactors= new CFFList [factors.length()];
340  CFList evalSqrfPartF, bufFactors;
341  CFArray evalPoint= CFArray (evaluation.length() - 1);
342  CFArray buf= CFArray (evaluation.length());
343  CFArray swap= CFArray (evaluation.length());
344  CFListIterator iter= evaluation;
345  CanonicalForm vars=getVars (LCF)*Variable (2);
346  for (int i= evaluation.length() +1; i > 1; i--, iter++)
347  {
348    buf[i-2]=iter.getItem();
349    if (degree (vars, i) > 0)
350      swap[M(Variable (i)).level()-1]=buf[i-2];
351  }
352  buf= swap;
353  for (int i= 0; i < evaluation.length() - 1; i++)
354    evalPoint[i]= buf[i+1];
355
356  //TODO sqrfPartF einmal berechnen nicht stÀndig
357  int pass= testFactors (F, factors, sqrfPartF,
358                         bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
359
360  bool foundDifferent= false;
361  Variable z;
362  Variable x= y;
363  int j= 0;
364  if (!pass)
365  {
366    int lev= 0;
367    CanonicalForm bufF;
368    CFList bufBufFactors;
369    for (int i= 0; i < length; i++)
370    {
371      if (!differentSecondVarLCs [i].isEmpty())
372      {
373        bool allConstant= true;
374        for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
375        {
376          if (!iter.getItem().inCoeffDomain())
377          {
378            allConstant= false;
379            y= Variable (iter.getItem().level());
380            lev= M(y).level();
381          }
382        }
383        if (allConstant)
384          continue;
385
386        bufFactors= differentSecondVarLCs [i];
387        for (iter= bufFactors; iter.hasItem(); iter++)
388          iter.getItem()= swapvar (iter.getItem(), x, y);
389        bufF= F;
390        z= Variable (lev);
391        bufF= swapvar (bufF, x, z);
392        bufBufFactors= bufFactors;
393        evalPoint= CFArray (evaluation.length() - 1);
394        for (int k= 0; k < evaluation.length()-1; k++)
395        {
396          if (N (Variable (k+1)).level() != y.level())
397            evalPoint[k]= buf[k+1];
398          else
399            evalPoint[k]= buf[0];
400        }
401        pass= testFactors (bufF, bufBufFactors, sqrfPartF, bufFactors,
402                           bufSqrfFactors, evalSqrfPartF, evalPoint);
403        if (pass)
404        {
405          foundDifferent= true;
406          F= bufF;
407          CFList l= factors;
408          for (iter= l; iter.hasItem(); iter++)
409            iter.getItem()= swapvar (iter.getItem(), x, y);
410          differentSecondVarLCs [i]= l;
411          j= i;
412          break;
413        }
414        if (!pass && i == length - 1)
415        {
416          CFList result;
417          result.append (LCF);
418          for (int j= 1; j <= factors.length(); j++)
419            result.append (1);
420          result= distributeContent (result, differentSecondVarLCs, length);
421          if (!result.getFirst().inCoeffDomain())
422          {
423            CFListIterator iter= result;
424            CanonicalForm tmp= iter.getItem();
425            iter++;
426            for (; iter.hasItem(); iter++)
427              iter.getItem() *= tmp;
428          }
429
430          y= Variable (1);
431          delete [] bufSqrfFactors;
432          return result;
433        }
434      }
435    }
436  }
437  if (!pass)
438  {
439    CFList result;
440    result.append (LCF);
441    for (int j= 1; j <= factors.length(); j++)
442      result.append (LCF);
443    y= Variable (1);
444    delete [] bufSqrfFactors;
445    return result;
446  }
447  else
448    factors= bufFactors;
449
450
451  bufFactors= factors;
452
453  CFMap MM, NN;
454  dummy [0]= sqrfPartF;
455  dummy [1]= 1;
456  compress (dummy, MM, NN);
457  sqrfPartF= MM (sqrfPartF);
458  CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
459  for (CFListIterator iter= factors; iter.hasItem(); iter++)
460    iter.getItem()= MM (iter.getItem());
461
462  CFList evaluation2;
463  for (int i= 2; i <= varsSqrfPartF.level(); i++)
464    evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
465
466  CFList interMedResult;
467  CanonicalForm oldSqrfPartF= sqrfPartF;
468  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
469  if (factors.length() > 1)
470  {
471    CanonicalForm LC1= LC (oldSqrfPartF, 1);
472    CFList leadingCoeffs;
473    for (int i= 0; i < factors.length(); i++)
474      leadingCoeffs.append (LC1);
475
476    CFList LC1eval= evaluateAtEval (LC1, evaluation2,2);
477    CFList oldFactors= factors;
478    for (CFListIterator i= oldFactors; i.hasItem(); i++)
479      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
480
481    bool success= false;
482    CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
483    CFList heuResult;
484    if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
485        LucksWangSparseHeuristic (oldSqrfPartFPowLC,
486                                  oldFactors, 2, leadingCoeffs, heuResult))
487    {
488      interMedResult= recoverFactors (oldSqrfPartF, heuResult);
489      if (oldFactors.length() == interMedResult.length())
490        success= true;
491    }
492    if (!success)
493    {
494      LC1= LC (evalSqrfPartF.getFirst(), 1);
495
496      CFArray leadingCoeffs= CFArray (factors.length());
497      for (int i= 0; i < factors.length(); i++)
498        leadingCoeffs[i]= LC1;
499
500      for (CFListIterator i= factors; i.hasItem(); i++)
501        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
502      factors.insert (1);
503
504      CanonicalForm
505      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
506
507      int liftBound= degree (newSqrfPartF,2) + 1;
508
509      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
510      CFArray Pi;
511      CFList diophant;
512      nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
513                            leadingCoeffs, false);
514
515      if (sqrfPartF.level() > 2)
516      {
517        int* liftBounds= new int [sqrfPartF.level() - 1];
518        liftBounds [0]= liftBound;
519        bool noOneToOne= false;
520        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
521        LC1= LC (evalSqrfPartF.getLast(), 1);
522        CFList LCs;
523        for (int i= 0; i < factors.length(); i++)
524          LCs.append (LC1);
525        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
526        for (int i= sqrfPartF.level() - 1; i > 2; i--)
527        {
528          for (CFListIterator j= LCs; j.hasItem(); j++)
529            j.getItem()= j.getItem() (0, i + 1);
530          leadingCoeffs2 [i - 3]= LCs;
531        }
532        sqrfPartF *= power (LC1, factors.length()-1);
533
534        int liftBoundsLength= sqrfPartF.level() - 1;
535        for (int i= 1; i < liftBoundsLength; i++)
536          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
537        evalSqrfPartF= evaluateAtZero (sqrfPartF);
538        evalSqrfPartF.removeFirst();
539        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
540                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
541        delete [] leadingCoeffs2;
542        delete [] liftBounds;
543      }
544      for (CFListIterator iter= factors; iter.hasItem(); iter++)
545        iter.getItem()= reverseShift (iter.getItem(), evaluation2);
546
547      interMedResult=
548      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
549                      factors);
550    }
551  }
552  else
553  {
554    CanonicalForm contF=content (oldSqrfPartF,1);
555    factors= CFList (oldSqrfPartF/contF);
556    interMedResult= recoverFactors (oldSqrfPartF, factors);
557  }
558
559  for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
560    iter.getItem()= NN (iter.getItem());
561
562  CFList result;
563  CFFListIterator k;
564  CanonicalForm tmp;
565  for (int i= 0; i < LCFFactors.length(); i++)
566  {
567    tmp= 1;
568    for (k= bufSqrfFactors[i]; k.hasItem(); k++)
569    {
570      int pos= findItem (bufFactors, k.getItem().factor());
571      if (pos)
572        tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
573    }
574    result.append (tmp);
575  }
576
577  for (CFListIterator i= result; i.hasItem(); i++)
578  {
579    F /= i.getItem();
580    if (foundDifferent)
581      i.getItem()= swapvar (i.getItem(), x, z);
582    i.getItem()= N (i.getItem());
583  }
584
585  if (foundDifferent)
586  {
587    CFList l= differentSecondVarLCs [j];
588    for (CFListIterator i= l; i.hasItem(); i++)
589      i.getItem()= swapvar (i.getItem(), y, z);
590    differentSecondVarLCs [j]= l;
591    F= swapvar (F, x, z);
592  }
593
594  result.insert (N (F));
595
596  result= distributeContent (result, differentSecondVarLCs, length);
597
598  if (!result.getFirst().inCoeffDomain())
599  {
600    CFListIterator i= result;
601    CanonicalForm tmp;
602    if (foundDifferent)
603      i.getItem()= swapvar (i.getItem(), Variable (2), y);
604
605    tmp= i.getItem();
606
607    i++;
608    for (; i.hasItem(); i++)
609    {
610      if (foundDifferent)
611        i.getItem()= swapvar (i.getItem(), Variable (2), y)*tmp;
612      else
613        i.getItem() *= tmp;
614    }
615  }
616  else
617    y= Variable (1);
618
619  delete [] bufSqrfFactors;
620
621  return result;
622}
623
624
625CFList
626multiFactorize (const CanonicalForm& F, const Variable& v)
627{
628  if (F.inCoeffDomain())
629    return CFList (F);
630
631  // compress and find main Variable
632  CFMap N;
633  CanonicalForm A= myCompress (F, N);
634
635  //univariate case
636  if (F.isUnivariate())
637  {
638    CFList result;
639    if (v.level() != 1)
640      result= conv (factorize (F, v));
641    else
642      result= conv (factorize (F,true));
643    if (result.getFirst().inCoeffDomain())
644      result.removeFirst();
645    return result;
646  }
647
648  //bivariate case
649  if (A.level() == 2)
650  {
651    CFList buf= biFactorize (F, v);
652    return buf;
653  }
654
655  Variable x= Variable (1);
656  Variable y= Variable (2);
657
658  // remove content
659  CFList contentAi;
660  CanonicalForm lcmCont= lcmContent (A, contentAi);
661  A /= lcmCont;
662
663  // trivial after content removal
664  CFList contentAFactors;
665  if (A.inCoeffDomain())
666  {
667    for (CFListIterator i= contentAi; i.hasItem(); i++)
668    {
669      if (i.getItem().inCoeffDomain())
670        continue;
671      else
672      {
673        lcmCont /= i.getItem();
674        contentAFactors=
675        Union (multiFactorize (lcmCont, v),
676               multiFactorize (i.getItem(), v));
677        break;
678      }
679    }
680    decompress (contentAFactors, N);
681    if (isOn (SW_RATIONAL))
682      normalize (contentAFactors);
683    return contentAFactors;
684  }
685
686  // factorize content
687  contentAFactors= multiFactorize (lcmCont, v);
688
689  // univariate after content removal
690  CFList factors;
691  if (A.isUnivariate ())
692  {
693    if (v.level() != 1)
694      factors= conv (factorize (A, v));
695    else
696      factors= conv (factorize (A,true));
697    append (factors, contentAFactors);
698    decompress (factors, N);
699    return factors;
700  }
701
702  A *= bCommonDen (A);
703  // check main variable
704  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
705  int factorNums= 3;
706  CanonicalForm bivarEval;
707  CFList biFactors, bufBiFactors;
708  CanonicalForm evalPoly;
709  int lift, bufLift, lengthAeval2= A.level()-2;
710  CFList* bufAeval2= new CFList [lengthAeval2];
711  CFList* Aeval2= new CFList [lengthAeval2];
712  int counter;
713  int differentSecondVar= 0;
714  CanonicalForm bufA;
715  // several bivariate factorizations
716  REvaluation E (2, A.level(), IntRandom (25));
717  for (int i= 0; i < factorNums; i++)
718  {
719    counter= 0;
720    bufA= A;
721    bufAeval= CFList();
722    bufEvaluation= evalPoints (bufA, bufAeval, E);
723    E.nextpoint();
724    evalPoly= 0;
725
726    bivarEval= bufEvaluation.getLast();
727
728    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
729
730    for (int j= 0; j < A.level() - 1; j++)
731    {
732      if (!bufAeval2[j].isEmpty())
733        counter++;
734    }
735
736    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
737
738    TIMING_START (fac_bi_factorize);
739    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
740    TIMING_END_AND_PRINT (fac_bi_factorize,
741                          "time for bivariate factorization: ");
742    bufBiFactors.removeFirst();
743
744    if (bufBiFactors.length() == 1)
745    {
746      factors.append (A);
747      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
748      if (isOn (SW_RATIONAL))
749        normalize (factors);
750      delete [] bufAeval2;
751      delete [] Aeval2;
752      return factors;
753    }
754
755    if (i == 0)
756    {
757      Aeval= bufAeval;
758      evaluation= bufEvaluation;
759      biFactors= bufBiFactors;
760      lift= bufLift;
761      for (int j= 0; j < lengthAeval2; j++)
762        Aeval2 [j]= bufAeval2 [j];
763      differentSecondVar= counter;
764    }
765    else
766    {
767      if (bufBiFactors.length() < biFactors.length() ||
768          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
769          counter > differentSecondVar)
770      {
771        Aeval= bufAeval;
772        evaluation= bufEvaluation;
773        biFactors= bufBiFactors;
774        lift= bufLift;
775        for (int j= 0; j < lengthAeval2; j++)
776          Aeval2 [j]= bufAeval2 [j];
777        differentSecondVar= counter;
778      }
779    }
780    int k= 0;
781    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
782      evalPoly += j.getItem()*power (x, k);
783    list.append (evalPoly);
784  }
785
786  delete [] bufAeval2;
787
788  sortList (biFactors, x);
789
790  int minFactorsLength;
791  bool irred= false;
792  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
793
794  if (irred)
795  {
796    factors.append (A);
797    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
798    if (isOn (SW_RATIONAL))
799      normalize (factors);
800    delete [] Aeval2;
801    return factors;
802  }
803
804  if (minFactorsLength == 0)
805    minFactorsLength= biFactors.length();
806  else if (biFactors.length() > minFactorsLength)
807    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
808
809  if (differentSecondVar == lengthAeval2 && getNumVars(LC(A,1)) == A.level()-1)
810  {
811    bool zeroOccured= false;
812    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
813    {
814      if (iter.getItem().isZero())
815      {
816        zeroOccured= true;
817        break;
818      }
819    }
820    if (!zeroOccured)
821    {
822      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
823                                minFactorsLength);
824      if (factors.length() == biFactors.length())
825      {
826        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
827        normalize (factors);
828        delete [] Aeval2;
829        return factors;
830      }
831      else
832        factors= CFList();
833      //TODO case where factors.length() > 0
834    }
835  }
836
837  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
838
839  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
840
841  CFList * oldAeval= new CFList [lengthAeval2];
842  for (int i= 0; i < lengthAeval2; i++)
843    oldAeval[i]= Aeval2[i];
844
845  getLeadingCoeffs (A, Aeval2, uniFactors, evaluation);
846
847  CFList biFactorsLCs;
848  for (CFListIterator i= biFactors; i.hasItem(); i++)
849    biFactorsLCs.append (LC (i.getItem(), 1));
850
851  Variable w;
852  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs,
853                                          evaluation, Aeval2, lengthAeval2, w);
854
855  if (w.level() != 1)
856  {
857    A= swapvar (A, y, w);
858    int i= A.level();
859    CanonicalForm evalPoint;
860    for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
861    {
862      if (i == w.level())
863      {
864        evalPoint= iter.getItem();
865        iter.getItem()= evaluation.getLast();
866        evaluation.removeLast();
867        evaluation.append (evalPoint);
868        break;
869      }
870    }
871    for (i= 0; i < lengthAeval2; i++)
872    {
873      if (oldAeval[i].isEmpty())
874        continue;
875      if (oldAeval[i].getFirst().level() == w.level())
876      {
877        CFArray tmp= copy (oldAeval[i]);
878        oldAeval[i]= biFactors; 
879        for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
880          iter.getItem()= swapvar (iter.getItem(), w, y);
881        for (int ii= 0; ii < tmp.size(); ii++)
882          tmp[ii]= swapvar (tmp[ii], w, y);
883        CFArray tmp2= CFArray (tmp.size());
884        CanonicalForm buf;
885        for (int ii= 0; ii < tmp.size(); ii++)
886        {
887          buf= tmp[ii] (evaluation.getLast(),y);
888          buf /= Lc (buf);
889          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
890        }
891        biFactors= CFList();
892        for (int j= 0; j < tmp2.size(); j++)
893          biFactors.append (tmp2[j]);
894      }
895    }
896  }
897
898  CFListIterator iter;
899  CanonicalForm oldA= A;
900  CFList oldBiFactors= biFactors;
901  if (!leadingCoeffs.getFirst().inCoeffDomain())
902  {
903    CanonicalForm tmp= power (leadingCoeffs.getFirst(), biFactors.length() - 1);
904    A *= tmp;
905    tmp= leadingCoeffs.getFirst();
906    iter= evaluation;
907    for (int i= A.level(); i > 2; i--, iter++)
908      tmp= tmp (iter.getItem(), i);
909    if (!tmp.inCoeffDomain())
910    {
911      for (CFListIterator i= biFactors; i.hasItem(); i++)
912      {
913        i.getItem() *= tmp/LC (i.getItem(), 1);
914        i.getItem() /= Lc (i.getItem());
915      }
916    }
917  }
918
919  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
920  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
921  leadingCoeffs.removeFirst();
922
923  //prepare leading coefficients
924  CFList* leadingCoeffs2= new CFList [lengthAeval2];
925  prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs, biFactors,
926                        evaluation);
927
928
929  Aeval= evaluateAtEval (A, evaluation, 2);
930
931  CanonicalForm hh= Lc (Aeval.getFirst());
932
933  for (iter= Aeval; iter.hasItem(); iter++)
934    iter.getItem() /= hh;
935
936  A /= hh;
937
938  CFListIterator iter2;
939  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
940  bufBiFactors= biFactors;
941  bufA= A;
942  CanonicalForm bufLCmultiplier= LCmultiplier;
943  CanonicalForm testVars;
944  if (!LCmultiplierIsConst)
945  {
946    testVars= Variable (2);
947    for (int i= 0; i < lengthAeval2; i++)
948    {
949      if (!oldAeval[i].isEmpty())
950        testVars *= oldAeval[i].getFirst().mvar();
951    }
952  }
953  CFList bufFactors= CFList();
954  bool LCheuristic= false;
955  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
956                                factors))
957  {
958    int check= biFactors.length();
959    int * index= new int [factors.length()];
960    CFList oldFactors= factors;
961    factors= recoverFactors (A, factors, index);
962
963    if (check == factors.length())
964    {
965      if (w.level() != 1)
966      {
967        for (iter= factors; iter.hasItem(); iter++)
968          iter.getItem()= swapvar (iter.getItem(), w, y);
969      }
970
971      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
972      normalize (factors);
973      delete [] index;
974      delete [] Aeval2;
975      return factors;
976    }
977    else if (factors.length() > 0)
978    {
979      int oneCount= 0;
980      CFList l;
981      for (int i= 0; i < check; i++)
982      {
983        if (index[i] == 1)
984        {
985          iter=biFactors;
986          for (int j=1; j <= i-oneCount; j++)
987            iter++;
988          iter.remove (1);
989          for (int j= 0; j < lengthAeval2; j++)
990          {
991            l= leadingCoeffs2[j];
992            iter= l;
993            for (int k=1; k <= i-oneCount; k++)
994              iter++;
995            iter.remove (1);
996            leadingCoeffs2[j]=l;
997          }
998          oneCount++;
999        }
1000      }
1001      bufFactors= factors;
1002      factors= CFList();
1003    }
1004    else if (!LCmultiplierIsConst && factors.length() == 0)
1005    {
1006      LCheuristic= true;
1007      factors= oldFactors;
1008      CanonicalForm cont;
1009      CFList contents, LCs;
1010      int index=1;
1011      bool foundTrueMultiplier= false;
1012      for (iter= factors; iter.hasItem(); iter++, index++)
1013      {
1014        cont= content (iter.getItem(), 1);
1015        cont= gcd (cont , LCmultiplier);
1016        contents.append (cont);
1017        if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
1018        {
1019          foundTrueMultiplier= true;
1020          int index2= 1;
1021          for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem(); iter2++,
1022                                                                    index2++)
1023          {
1024            if (index2 == index)
1025              continue;
1026            iter2.getItem() /= LCmultiplier;
1027          }
1028          A= oldA;
1029          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1030          for (int i= lengthAeval2-1; i > -1; i--)
1031            leadingCoeffs2[i]= CFList();
1032          prepareLeadingCoeffs (leadingCoeffs2, A.level(), leadingCoeffs,
1033                                biFactors, evaluation );
1034          Aeval= evaluateAtEval (A, evaluation, 2);
1035
1036          hh= Lc (Aeval.getFirst());
1037
1038          for (iter2= Aeval; iter2.hasItem(); iter2++)
1039            iter2.getItem() /= hh;
1040
1041          A /= hh;
1042          break;
1043        }
1044        else
1045          LCs.append (LC (iter.getItem()/cont, 1));
1046      }
1047      if (!foundTrueMultiplier)
1048      {
1049        index= 1;
1050        iter2= factors;
1051        bool foundMultiplier= false;
1052        for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1053        {
1054          if (fdivides (iter.getItem(), LCmultiplier))
1055          {
1056            if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
1057                !isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
1058            {
1059              int index2= 1;
1060              for (CFListIterator iter3= leadingCoeffs2[lengthAeval2-1];
1061                   iter3.hasItem(); iter3++, index2++)
1062              {
1063                if (index2 == index)
1064                {
1065                  iter3.getItem() /= LCmultiplier;
1066                  break;
1067                }
1068              }
1069              A /= LCmultiplier;
1070              foundMultiplier= true;
1071              iter.getItem()= 1;
1072            }
1073          }
1074        }
1075        // coming from above: divide out more LCmultiplier if possible
1076        if (foundMultiplier)
1077        {
1078          foundMultiplier= false;
1079          index=1;
1080          iter2= factors;
1081          for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
1082          {
1083            if (!iter.getItem().isOne() &&
1084                fdivides (iter.getItem(), LCmultiplier))
1085            {
1086              if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
1087              {
1088                int index2= 1;
1089                for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1090                     iter2++, index2++)
1091                {
1092                  if (index2 == index)
1093                  {
1094                    iter2.getItem() /= iter.getItem();
1095                    foundMultiplier= true;
1096                    break;
1097                  }
1098                }
1099                A /= iter.getItem();
1100                LCmultiplier /= iter.getItem();
1101                iter.getItem()= 1;
1102              }
1103              else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
1104              {
1105                Variable xx= Variable (2);
1106                CanonicalForm vars;
1107                vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
1108                                          xx));
1109                for (int i= 0; i < lengthAeval2; i++)
1110                {
1111                  if (oldAeval[i].isEmpty())
1112                    continue;
1113                  xx= oldAeval[i].getFirst().mvar();
1114                  vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
1115                                             xx));
1116                }
1117                if (myGetVars(content(getItem(leadingCoeffs2[lengthAeval2-1],index),1))
1118                    /myGetVars (LCmultiplier) == vars)
1119                {
1120                  int index2= 1;
1121                  for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1122                       iter2++, index2++)
1123                  {
1124                    if (index2 == index)
1125                    {
1126                      iter2.getItem() /= LCmultiplier;
1127                      foundMultiplier= true;
1128                      break;
1129                    }
1130                  }
1131                  A /= LCmultiplier;
1132                  iter.getItem()= 1;
1133                }
1134              }
1135            }
1136          }
1137        }
1138        else
1139        {
1140          CanonicalForm pLCs= prod (LCs);
1141          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
1142          {
1143            A= oldA;
1144            iter2= leadingCoeffs2[lengthAeval2-1];
1145            for (iter= contents; iter.hasItem(); iter++, iter2++)
1146              iter2.getItem() /= iter.getItem();
1147            foundMultiplier= true;
1148          }
1149          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
1150          {
1151            Variable xx;
1152            CFList vars1;
1153            CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1154            if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1155              sqrfMultiplier.removeFirst();
1156            sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1157            xx= Variable (2);
1158            for (iter= oldBiFactors; iter.hasItem(); iter++)
1159              vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1160            for (int i= 0; i < lengthAeval2; i++)
1161            {
1162              if (oldAeval[i].isEmpty())
1163                continue;
1164              xx= oldAeval[i].getFirst().mvar();
1165              iter2= vars1;
1166              for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1167                iter2.getItem() *= power(xx,degree (LC (iter.getItem(),1), xx));
1168            }
1169            CanonicalForm tmp;
1170            iter2= vars1;
1171            for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++,
1172                                                                    iter2++)
1173            {
1174              tmp= iter.getItem()/LCmultiplier;
1175              for (int i=1; i <= tmp.level(); i++)
1176              {
1177                if (degree (tmp, i) > 0)
1178                  iter2.getItem() /= power (Variable (i), degree (tmp,i));
1179              }
1180            }
1181            int multi;
1182            for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1183            {
1184              multi= 0;
1185              for (iter= vars1; iter.hasItem(); iter++)
1186              {
1187                tmp= iter.getItem();
1188                while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1189                {
1190                  multi++;
1191                  tmp /= myGetVars (ii.getItem().factor());
1192                }
1193              }
1194              if (multi == ii.getItem().exp())
1195              {
1196                index= 1;
1197                for (iter= vars1; iter.hasItem(); iter++, index++)
1198                {
1199                  while (fdivides (myGetVars(ii.getItem().factor()),
1200                                   iter.getItem()
1201                                  )
1202                        )
1203                  {
1204                    int index2= 1;
1205                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1206                         iter2++, index2++)
1207                    {
1208                      if (index2 == index)
1209                        continue;
1210                      else
1211                      {
1212                        tmp= ii.getItem().factor();
1213                        iter2.getItem() /= tmp;
1214                        CFListIterator iter3= evaluation;
1215                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1216                          tmp= tmp (iter3.getItem(), jj);
1217                        if (!tmp.inCoeffDomain())
1218                        {
1219                          int index3= 1;
1220                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1221                                                                  index3++)
1222                          {
1223                            if (index3 == index2)
1224                            {
1225                              iter3.getItem() /= tmp;
1226                              iter3.getItem() /= Lc (iter3.getItem());
1227                              break;
1228                            }
1229                          }
1230                        }
1231                        A /= ii.getItem().factor();
1232                      }
1233                    }
1234                    iter.getItem() /= getVars (ii.getItem().factor());
1235                  }
1236                }
1237              }
1238              else
1239              {
1240                index= 1;
1241                for (iter= vars1; iter.hasItem(); iter++, index++)
1242                {
1243                  if (!fdivides (myGetVars (ii.getItem().factor()),
1244                                 iter.getItem()
1245                                )
1246                     )
1247                  {
1248                    int index2= 1;
1249                    for (iter2= leadingCoeffs2[lengthAeval2-1]; iter2.hasItem();
1250                         iter2++, index2++)
1251                    {
1252                      if (index2 == index)
1253                      {
1254                        tmp= power (ii.getItem().factor(), ii.getItem().exp());
1255                        iter2.getItem() /= tmp;
1256                        A /= tmp;
1257                        CFListIterator iter3= evaluation;
1258                        for (int jj= A.level(); jj > 2; jj--, iter3++)
1259                          tmp= tmp (iter3.getItem(), jj);
1260                        if (!tmp.inCoeffDomain())
1261                        {
1262                          int index3= 1;
1263                          for (iter3= biFactors; iter3.hasItem(); iter3++,
1264                                                                  index3++)
1265                          {
1266                            if (index3 == index2)
1267                            {
1268                              iter3.getItem() /= tmp;
1269                              iter3.getItem() /= Lc (iter3.getItem());
1270                              break;
1271                            }
1272                          }
1273                        }
1274                      }
1275                    }
1276                  }
1277                }
1278              }
1279            }
1280          }
1281        }
1282
1283        // patch everything together again
1284        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1285        for (int i= lengthAeval2-1; i > -1; i--)
1286          leadingCoeffs2[i]= CFList();
1287        prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1288                              evaluation);
1289        Aeval= evaluateAtEval (A, evaluation, 2);
1290
1291        hh= Lc (Aeval.getFirst());
1292
1293        for (CFListIterator i= Aeval; i.hasItem(); i++)
1294          i.getItem() /= hh;
1295
1296        A /= hh;
1297      }
1298      factors= CFList();
1299      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
1300      {
1301        LCheuristic= false;
1302        A= bufA;
1303        biFactors= bufBiFactors;
1304        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1305        LCmultiplier= bufLCmultiplier;
1306      }
1307    }
1308    else
1309      factors= CFList();
1310    delete [] index;
1311  }
1312  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
1313      && fdivides (getVars (LCmultiplier), testVars))
1314  {
1315    LCheuristic= true;
1316    int index;
1317    Variable xx;
1318    CFList vars1;
1319    CFFList sqrfMultiplier= sqrFree (LCmultiplier);
1320    if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
1321      sqrfMultiplier.removeFirst();
1322    sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
1323    xx= Variable (2);
1324    for (iter= oldBiFactors; iter.hasItem(); iter++)
1325      vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
1326    for (int i= 0; i < lengthAeval2; i++)
1327    {
1328      if (oldAeval[i].isEmpty())
1329        continue;
1330      xx= oldAeval[i].getFirst().mvar();
1331      iter2= vars1;
1332      for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
1333        iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
1334    }
1335    CanonicalForm tmp;
1336    iter2= vars1;
1337    for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++, iter2++)
1338    {
1339      tmp= iter.getItem()/LCmultiplier;
1340      for (int i=1; i <= tmp.level(); i++)
1341      {
1342        if (degree (tmp, i) > 0)
1343          iter2.getItem() /= power (Variable (i), degree (tmp,i));
1344      }
1345    }
1346    int multi;
1347    for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
1348    {
1349      multi= 0;
1350      for (iter= vars1; iter.hasItem(); iter++)
1351      {
1352        tmp= iter.getItem();
1353        while (fdivides (myGetVars (ii.getItem().factor()), tmp))
1354        {
1355          multi++;
1356          tmp /= myGetVars (ii.getItem().factor());
1357        }
1358      }
1359      if (multi == ii.getItem().exp())
1360      {
1361        index= 1;
1362        for (iter= vars1; iter.hasItem(); iter++, index++)
1363        {
1364          while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1365          {
1366            int index2= 1;
1367            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1368                                                                      index2++)
1369            {
1370              if (index2 == index)
1371                continue;
1372              else
1373              {
1374                tmp= ii.getItem().factor();
1375                iter2.getItem() /= tmp;
1376                CFListIterator iter3= evaluation;
1377                for (int jj= A.level(); jj > 2; jj--, iter3++)
1378                  tmp= tmp (iter3.getItem(), jj);
1379                if (!tmp.inCoeffDomain())
1380                {
1381                  int index3= 1;
1382                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1383                  {
1384                    if (index3 == index2)
1385                    {
1386                      iter3.getItem() /= tmp;
1387                      iter3.getItem() /= Lc (iter3.getItem());
1388                      break;
1389                    }
1390                  }
1391                }
1392                A /= ii.getItem().factor();
1393              }
1394            }
1395            iter.getItem() /= getVars (ii.getItem().factor());
1396          }
1397        }
1398      }
1399      else
1400      {
1401        index= 1;
1402        for (iter= vars1; iter.hasItem(); iter++, index++)
1403        {
1404          if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
1405          {
1406            int index2= 1;
1407            for (iter2= leadingCoeffs2[lengthAeval2-1];iter2.hasItem();iter2++,
1408                                                                      index2++)
1409            {
1410              if (index2 == index)
1411              {
1412                tmp= power (ii.getItem().factor(), ii.getItem().exp());
1413                iter2.getItem() /= tmp;
1414                A /= tmp;
1415                CFListIterator iter3= evaluation;
1416                for (int jj= A.level(); jj > 2; jj--, iter3++)
1417                  tmp= tmp (iter3.getItem(), jj);
1418                if (!tmp.inCoeffDomain())
1419                {
1420                  int index3= 1;
1421                  for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
1422                  {
1423                    if (index3 == index2)
1424                    {
1425                      iter3.getItem() /= tmp;
1426                      iter3.getItem() /= Lc (iter3.getItem());
1427                      break;
1428                    }
1429                  }
1430                }
1431              }
1432            }
1433          }
1434        }
1435      }
1436    }
1437
1438    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
1439    for (int i= lengthAeval2-1; i > -1; i--)
1440      leadingCoeffs2[i]= CFList();
1441    prepareLeadingCoeffs (leadingCoeffs2,A.level(),leadingCoeffs, biFactors,
1442                          evaluation);
1443    Aeval= evaluateAtEval (A, evaluation, 2);
1444
1445    hh= Lc (Aeval.getFirst());
1446
1447    for (CFListIterator i= Aeval; i.hasItem(); i++)
1448      i.getItem() /= hh;
1449
1450    A /= hh;
1451  }
1452
1453tryAgainWithoutHeu:
1454  //shifting to zero
1455  A= shift2Zero (A, Aeval, evaluation);
1456
1457  for (iter= biFactors; iter.hasItem(); iter++)
1458    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1459
1460  for (int i= 0; i < lengthAeval2-1; i++)
1461    leadingCoeffs2[i]= CFList();
1462  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
1463  {
1464    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
1465    for (int i= A.level() - 4; i > -1; i--)
1466    {
1467      if (i + 1 == lengthAeval2-1)
1468        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
1469      else
1470        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
1471    }
1472  }
1473
1474  CFArray Pi;
1475  CFList diophant;
1476  int* liftBounds= new int [A.level() - 1];
1477  int liftBoundsLength= A.level() - 1;
1478  for (int i= 0; i < liftBoundsLength; i++)
1479    liftBounds [i]= degree (A, i + 2) + 1;
1480
1481  Aeval.removeFirst();
1482  bool noOneToOne= false;
1483
1484  CFList commonDenominators;
1485  for (iter=biFactors; iter.hasItem(); iter++)
1486    commonDenominators.append (bCommonDen (iter.getItem()));
1487  CanonicalForm tmp1, tmp2, tmp3=1;
1488  for (int i= 0; i < lengthAeval2; i++)
1489  {
1490    iter2= commonDenominators;
1491    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1492    {
1493      tmp1= bCommonDen (iter.getItem());
1494      Off (SW_RATIONAL);
1495      iter2.getItem()= lcm (iter2.getItem(), tmp1);
1496      On (SW_RATIONAL);
1497    }
1498  }
1499  tmp1= prod (commonDenominators);
1500  for (iter= Aeval; iter.hasItem(); iter++)
1501  {
1502    tmp2= bCommonDen (iter.getItem());
1503    Off (SW_RATIONAL);
1504    tmp3= lcm (tmp2,tmp3);
1505    On (SW_RATIONAL);
1506  }
1507  CanonicalForm multiplier;
1508  multiplier= tmp3/tmp1;
1509  iter2= commonDenominators;
1510  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
1511    iter.getItem() *= iter2.getItem()*multiplier;
1512
1513  for (iter= Aeval; iter.hasItem(); iter++)
1514    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1);
1515
1516  for (int i= 0; i < lengthAeval2; i++)
1517  {
1518    iter2= commonDenominators;
1519    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
1520      iter.getItem() *= iter2.getItem()*multiplier;
1521  }
1522
1523
1524  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
1525                               Pi, liftBounds, liftBoundsLength, noOneToOne);
1526
1527  if (!noOneToOne)
1528  {
1529    int check= factors.length();
1530    A= oldA;
1531    factors= recoverFactors (A, factors, evaluation);
1532    if (check != factors.length())
1533      noOneToOne= true;
1534    else
1535      factors= Union (factors, bufFactors);
1536  }
1537  if (noOneToOne)
1538  {
1539    if (!LCmultiplierIsConst && LCheuristic)
1540    {
1541      A= bufA;
1542      biFactors= bufBiFactors;
1543      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
1544      delete [] liftBounds;
1545      LCheuristic= false;
1546      goto tryAgainWithoutHeu;
1547      //something probably went wrong in the heuristic
1548    }
1549
1550    A= shift2Zero (oldA, Aeval, evaluation);
1551    biFactors= oldBiFactors;
1552    for (iter= biFactors; iter.hasItem(); iter++)
1553      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
1554    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
1555    CanonicalForm yToLift= power (y, lift);
1556    CFListIterator i= biFactors;
1557    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
1558    i++;
1559
1560    for (; i.hasItem(); i++)
1561      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
1562
1563    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
1564
1565    i= biFactors;
1566    yToLift= power (y, lift);
1567    CanonicalForm dummy;
1568    for (; i.hasItem(); i++)
1569    {
1570      LCA= LC (i.getItem(), 1);
1571      extgcd (LCA, yToLift, LCA, dummy);
1572      i.getItem()= mod (i.getItem()*LCA, yToLift);
1573    }
1574
1575    liftBoundsLength= F.level() - 1;
1576    liftBounds= liftingBounds (A, lift);
1577
1578    CFList MOD;
1579    bool earlySuccess;
1580    CFList earlyFactors;
1581    ExtensionInfo info= ExtensionInfo (false);
1582    CFList liftedFactors;
1583    TIMING_START (fac_hensel_lift);
1584    liftedFactors= henselLiftAndEarly
1585                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
1586                    Aeval, biFactors, evaluation, info);
1587    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
1588
1589    TIMING_START (fac_factor_recombination);
1590    factors= factorRecombination (A, liftedFactors, MOD);
1591    TIMING_END_AND_PRINT (fac_factor_recombination,
1592                          "time for factor recombination: ");
1593
1594    if (earlySuccess)
1595      factors= Union (factors, earlyFactors);
1596
1597    for (CFListIterator i= factors; i.hasItem(); i++)
1598    {
1599      int kk= Aeval.getLast().level();
1600      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
1601      {
1602        if (i.getItem().level() < kk)
1603          continue;
1604       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
1605      }
1606    }
1607  }
1608
1609  if (w.level() != 1)
1610  {
1611    for (CFListIterator iter= factors; iter.hasItem(); iter++)
1612      iter.getItem()= swapvar (iter.getItem(), w, y);
1613  }
1614
1615  swap (factors, 0, 0, x);
1616  append (factors, contentAFactors);
1617  decompress (factors, N);
1618  if (isOn (SW_RATIONAL))
1619    normalize (factors);
1620
1621  delete [] leadingCoeffs2;
1622  delete [] oldAeval;
1623  delete [] Aeval2;
1624  delete[] liftBounds;
1625
1626  return factors;
1627}
1628
1629#endif
Note: See TracBrowser for help on using the repository browser.