source: git/factory/facAbsBiFact.cc @ b7cc2b

spielwiese
Last change on this file since b7cc2b was b7cc2b, checked in by Hans Schoenemann <hannes@…>, 3 years ago
factory: FindRoot via FLINT
  • Property mode set to 100644
File size: 19.5 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facAbsBiFact.cc
5 *
6 * @author Martin Lee
7 *
8 **/
9/*****************************************************************************/
10
11
12#include "config.h"
13
14
15#include "timing.h"
16#include "debug.h"
17
18#include "facAbsBiFact.h"
19#include "facBivar.h"
20#include "facFqBivar.h"
21#include "cf_reval.h"
22#include "cf_primes.h"
23#include "cf_algorithm.h"
24#ifdef HAVE_FLINT
25#include "FLINTconvert.h"
26#include <flint/fmpz_poly_factor.h>
27#endif
28#ifdef HAVE_NTL
29#include "NTLconvert.h"
30#include <NTL/LLL.h>
31#endif
32
33#ifdef HAVE_NTL
34TIMING_DEFINE_PRINT(fac_Qa_factorize)
35TIMING_DEFINE_PRINT(fac_evalpoint)
36
37CFAFList uniAbsFactorize (const CanonicalForm& F, bool full)
38{
39  CFAFList result;
40  if (degree (F) == 1)
41  {
42    bool isRat= isOn (SW_RATIONAL);
43    On (SW_RATIONAL);
44    result= CFAFList (CFAFactor (F/Lc(F), 1, 1));
45    result.insert (CFAFactor (Lc (F), 1, 1));
46    if (!isRat)
47      Off (SW_RATIONAL);
48    return result;
49  }
50  CanonicalForm LcF= 1;
51  Variable alpha;
52  CFFList QaFactors;
53  CFFListIterator iter;
54  alpha= rootOf (F);
55  QaFactors= factorize (F, alpha);
56  iter= QaFactors;
57  if (iter.getItem().factor().inCoeffDomain())
58  {
59    LcF = iter.getItem().factor();
60    iter++;
61  }
62  for (;iter.hasItem(); iter++)
63  {
64    if (full)
65      result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
66                                iter.getItem().exp()));
67    if (!full && degree (iter.getItem().factor()) == 1)
68    {
69      result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
70                                iter.getItem().exp()));
71      break;
72    }
73  }
74  result.insert (CFAFactor (LcF, 1, 1));
75  return result;
76}
77
78//TODO optimize choice of p -> choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting)
79int
80choosePoint (const CanonicalForm& F, int tdegF, CFArray& eval, bool rec,
81             int absValue)
82{
83  REvaluation E1 (1, 1, IntRandom (absValue));
84  REvaluation E2 (2, 2, IntRandom (absValue));
85  if (rec)
86  {
87    E1.nextpoint();
88    E2.nextpoint();
89  }
90
91  CanonicalForm f, f1, f2, Fp;
92  int i, p;
93  CFFList f1Factors, f2Factors;
94  CFFListIterator iter;
95  int count= 0;
96  while (1)
97  {
98    count++;
99    f1= E1 (F);
100    if (!f1.isZero() && degree (f1) == degree (F,2))
101    {
102      f1Factors= factorize (f1);
103      if (f1Factors.getFirst().factor().inCoeffDomain())
104        f1Factors.removeFirst();
105      if (f1Factors.length() == 1 && f1Factors.getFirst().exp() == 1)
106      {
107        f= E2(f1);
108        f2= E2 (F);
109        f2Factors= factorize (f2);
110        Off (SW_RATIONAL);
111        if (f2Factors.getFirst().factor().inCoeffDomain())
112          f2Factors.removeFirst();
113        if (f2Factors.length() == 1 && f2Factors.getFirst().exp() == 1)
114        {
115          ZZX NTLf1= convertFacCF2NTLZZX (f1);
116          ZZX NTLf2= convertFacCF2NTLZZX (f2);
117          ZZ NTLD1= discriminant (NTLf1);
118          ZZ NTLD2= discriminant (NTLf2);
119          CanonicalForm D1= convertZZ2CF (NTLD1);
120          CanonicalForm D2= convertZZ2CF (NTLD2);
121          if ((!f.isZero()) &&
122              (abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
123          {
124            for (i= cf_getNumPrimes()-1; i >= 0; i--)
125            {
126              if (f % CanonicalForm (cf_getPrime (i)) == 0)
127              {
128                p= cf_getPrime(i);
129                Fp= mod (F,p);
130                if (totaldegree (Fp) == tdegF &&
131                    degree (mod (f2,p), 1) == degree (F,1) &&
132                    degree (mod (f1, p),2) == degree (F,2))
133                {
134                  if (mod (D1, p) != 0 && mod (D2, p) != 0)
135                  {
136                    eval[0]= E1[1];
137                    eval[1]= E2[2];
138                    return p;
139                  }
140                }
141              }
142            }
143          }
144          else if (!f.isZero())
145          {
146            for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
147            {
148              if (f % CanonicalForm (cf_getSmallPrime (i)) == 0)
149              {
150                p= cf_getSmallPrime (i);
151                Fp= mod (F,p);
152                if (totaldegree (Fp) == tdegF &&
153                    degree (mod (f2, p),1) == degree (F,1) &&
154                    degree (mod (f1,p),2) == degree (F,2))
155                {
156                  if (mod (D1, p) != 0 && mod (D2, p) != 0)
157                  {
158                    eval[0]= E1[1];
159                    eval[1]= E2[2];
160                    return p;
161                  }
162                }
163              }
164            }
165          }
166        }
167        E2.nextpoint();
168        On (SW_RATIONAL);
169      }
170    }
171    E1.nextpoint();
172    if (count == 2)
173    {
174      count= 0;
175      absValue++;
176      E1=REvaluation (1, 1, IntRandom (absValue));
177      E2=REvaluation (2, 2, IntRandom (absValue));
178      E1.nextpoint();
179      E2.nextpoint();
180    }
181  }
182  return 0;
183}
184
185//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
186CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full)
187{
188  CanonicalForm F= bCommonDen (G)*G;
189  bool isRat= isOn (SW_RATIONAL);
190  Off (SW_RATIONAL);
191  F /= icontent (F);
192  On (SW_RATIONAL);
193
194  mpz_t * M=new mpz_t [4];
195  mpz_init (M[0]);
196  mpz_init (M[1]);
197  mpz_init (M[2]);
198  mpz_init (M[3]);
199
200  mpz_t * S=new mpz_t [2];
201  mpz_init (S[0]);
202  mpz_init (S[1]);
203
204  F= compress (F, M, S);
205
206  if (F.isUnivariate())
207  {
208    if (degree (F) == 1)
209    {
210      mpz_clear (M[0]);
211      mpz_clear (M[1]);
212      mpz_clear (M[2]);
213      mpz_clear (M[3]);
214      delete [] M;
215
216      mpz_clear (S[0]);
217      mpz_clear (S[1]);
218      delete [] S;
219      if (!isRat)
220        Off (SW_RATIONAL);
221      return CFAFList (CFAFactor (G, 1, 1));
222    }
223    CFAFList result= uniAbsFactorize (F, full);
224    if (result.getFirst().factor().inCoeffDomain())
225      result.removeFirst();
226    for (CFAFListIterator iter=result; iter.hasItem(); iter++)
227      iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
228                                 iter.getItem().minpoly(),iter.getItem().exp());
229    mpz_clear (M[0]);
230    mpz_clear (M[1]);
231    mpz_clear (M[2]);
232    mpz_clear (M[3]);
233    delete [] M;
234
235    mpz_clear (S[0]);
236    mpz_clear (S[1]);
237    delete [] S;
238    if (!isRat)
239      Off (SW_RATIONAL);
240    return result;
241  }
242
243  if (degree (F, 1) == 1 || degree (F, 2) == 1)
244  {
245    mpz_clear (M[0]);
246    mpz_clear (M[1]);
247    mpz_clear (M[2]);
248    mpz_clear (M[3]);
249    delete [] M;
250
251    mpz_clear (S[0]);
252    mpz_clear (S[1]);
253    delete [] S;
254    if (!isRat)
255      Off (SW_RATIONAL);
256    return CFAFList (CFAFactor (G, 1, 1));
257  }
258  int minTdeg, tdegF= totaldegree (F);
259  CanonicalForm Fp, smallestFactor;
260  int p;
261  CFFList factors;
262  Variable alpha;
263  bool rec= false;
264  Variable x= Variable (1);
265  Variable y= Variable (2);
266  CanonicalForm bufF= F;
267  CFFListIterator iter;
268  CFArray eval= CFArray (2);
269  int absValue= 1;
270differentevalpoint:
271  while (1)
272  {
273    TIMING_START (fac_evalpoint);
274    p= choosePoint (F, tdegF, eval, rec, absValue);
275    TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
276
277    //after here isOn (SW_RATIONAL)==false
278    setCharacteristic (p);
279    Fp=F.mapinto();
280    factors= factorize (Fp);
281
282    if (factors.getFirst().factor().inCoeffDomain())
283      factors.removeFirst();
284
285    if (factors.length() == 1 && factors.getFirst().exp() == 1)
286    {
287      if (absIrredTest (Fp))
288      {
289        if (isRat)
290          On (SW_RATIONAL);
291        setCharacteristic(0);
292        mpz_clear (M[0]);
293        mpz_clear (M[1]);
294        mpz_clear (M[2]);
295        mpz_clear (M[3]);
296        delete [] M;
297
298        mpz_clear (S[0]);
299        mpz_clear (S[1]);
300        delete [] S;
301        return CFAFList (CFAFactor (G, 1, 1));
302      }
303      else
304      {
305        setCharacteristic (0);
306        if (modularIrredTestWithShift (F))
307        {
308          if (isRat)
309            On (SW_RATIONAL);
310          mpz_clear (M[0]);
311          mpz_clear (M[1]);
312          mpz_clear (M[2]);
313          mpz_clear (M[3]);
314          delete [] M;
315
316          mpz_clear (S[0]);
317          mpz_clear (S[1]);
318          delete [] S;
319          return CFAFList (CFAFactor (G, 1, 1));
320        }
321        rec= true;
322        continue;
323      }
324    }
325    iter= factors;
326    smallestFactor= iter.getItem().factor();
327    while (smallestFactor.isUnivariate() && iter.hasItem())
328    {
329      iter++;
330      if (!iter.hasItem())
331        break;
332      smallestFactor= iter.getItem().factor();
333    }
334
335    minTdeg= totaldegree (smallestFactor);
336    if (iter.hasItem())
337      iter++;
338    for (; iter.hasItem(); iter++)
339    {
340      if (!iter.getItem().factor().isUnivariate() &&
341          (totaldegree (iter.getItem().factor()) < minTdeg))
342      {
343        smallestFactor= iter.getItem().factor();
344        minTdeg= totaldegree (smallestFactor);
345      }
346    }
347    if (tdegF % minTdeg == 0)
348      break;
349    setCharacteristic(0);
350    rec=true;
351  }
352  CanonicalForm Gp= Fp/smallestFactor;
353  Gp= Gp /Lc (Gp);
354
355  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
356  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
357  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
358  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
359
360  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
361               !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
362  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
363               !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
364  if (!xValid || !yValid)
365  {
366    rec= true;
367    setCharacteristic (0);
368    goto differentevalpoint;
369  }
370
371  setCharacteristic (0);
372
373  CanonicalForm mipo;
374
375  CFArray mipos= CFArray (2);
376  CFFList mipoFactors;
377  for (int i= 1; i < 3; i++)
378  {
379    CanonicalForm Fi= F(eval[i-1],i);
380
381    int s= tdegF/minTdeg + 1;
382    CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
383    bound *= power (CanonicalForm (s),s-1);
384    bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
385
386    CanonicalForm B = p;
387    long k = 1L;
388    while ( B < bound ) {
389      B *= p;
390      k++;
391    }
392
393    //TODO take floor (log2(k))
394    k= k+1;
395#ifdef HAVE_FLINT
396    fmpz_poly_t FLINTFi;
397    convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
398    setCharacteristic (p);
399    nmod_poly_t FLINTFpi, FLINTGpi;
400    if (i == 2)
401    {
402      convertFacCF2nmod_poly_t (FLINTFpi,
403                                smallestFactorEvalx/lc (smallestFactorEvalx));
404      convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
405    }
406    else
407    {
408      convertFacCF2nmod_poly_t (FLINTFpi,
409                                smallestFactorEvaly/lc (smallestFactorEvaly));
410      convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
411    }
412    nmod_poly_factor_t nmodFactors;
413    nmod_poly_factor_init (nmodFactors);
414    nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
415    nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
416
417    // the following fix is due to interface changes from  FLINT 2.3 -> FLINT 2.4
418#   ifndef slong
419#          define slong long
420#   endif
421
422    slong * link= new slong [2];
423    fmpz_poly_t *v= new fmpz_poly_t[2];
424    fmpz_poly_t *w= new fmpz_poly_t[2];
425    fmpz_poly_init(v[0]);
426    fmpz_poly_init(v[1]);
427    fmpz_poly_init(w[0]);
428    fmpz_poly_init(w[1]);
429
430    fmpz_poly_factor_t liftedFactors;
431    fmpz_poly_factor_init (liftedFactors);
432    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
433                                  nmodFactors, k);
434
435    nmod_poly_factor_clear (nmodFactors);
436    nmod_poly_clear (FLINTFpi);
437    nmod_poly_clear (FLINTGpi);
438
439    setCharacteristic(0);
440    CanonicalForm liftedSmallestFactor=
441    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
442
443    CanonicalForm otherFactor=
444    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
445    modpk pk= modpk (p, k);
446#else
447    modpk pk= modpk (p, k);
448    ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
449    setCharacteristic (p);
450
451    if (fac_NTL_char != p)
452    {
453      fac_NTL_char= p;
454      zz_p::init (p);
455    }
456    zz_pX NTLFpi, NTLGpi;
457    if (i == 2)
458    {
459      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
460      NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
461    }
462    else
463    {
464      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
465      NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
466    }
467    vec_zz_pX modFactors;
468    modFactors.SetLength(2);
469    modFactors[0]= NTLFpi;
470    modFactors[1]= NTLGpi;
471    vec_ZZX liftedFactors;
472    MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
473    setCharacteristic(0);
474    CanonicalForm liftedSmallestFactor=
475                  convertNTLZZX2CF (liftedFactors[0], x);
476
477    CanonicalForm otherFactor=
478                  convertNTLZZX2CF (liftedFactors[1], x);
479#endif
480
481    Off (SW_SYMMETRIC_FF);
482    liftedSmallestFactor= pk (liftedSmallestFactor);
483    if (i == 2)
484      liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
485    else
486      liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
487
488    On (SW_SYMMETRIC_FF);
489    CFMatrix *M= new CFMatrix (s, s);
490    (*M)(s,s)= power (CanonicalForm (p), k);
491    for (int j= 1; j < s; j++)
492    {
493      (*M) (j,j)= 1;
494      (*M) (j+1,j)= -liftedSmallestFactor;
495    }
496
497    mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
498
499    ZZ det;
500
501    transpose (*NTLM, *NTLM);
502    (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
503    transpose (*NTLM, *NTLM);
504    delete M;
505    M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
506    delete NTLM;
507
508    mipo= 0;
509    for (int j= 1; j <= s; j++)
510      mipo += (*M) (j,1)*power (x,s-j);
511
512    delete M;
513    mipoFactors= factorize (mipo);
514    if (mipoFactors.getFirst().factor().inCoeffDomain())
515      mipoFactors.removeFirst();
516
517#ifdef HAVE_FLINT
518    fmpz_poly_clear (v[0]);
519    fmpz_poly_clear (v[1]);
520    fmpz_poly_clear (w[0]);
521    fmpz_poly_clear (w[1]);
522    delete [] v;
523    delete [] w;
524    delete [] link;
525    fmpz_poly_factor_clear (liftedFactors);
526#endif
527
528    if (mipoFactors.length() > 1 ||
529        (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
530         mipo.inCoeffDomain())
531    {
532        rec=true;
533        goto differentevalpoint;
534    }
535    else
536      mipos[i-1]= mipo;
537  }
538
539  if (degree (mipos[0]) != degree (mipos[1]))
540  {
541    rec=true;
542    goto differentevalpoint;
543  }
544
545  On (SW_RATIONAL);
546  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
547    alpha= rootOf (mipos[0]);
548  else
549    alpha= rootOf (mipos[1]);
550
551  int wrongMipo= 0;
552
553  Variable beta;
554  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
555  {
556    mipoFactors= factorize (mipos[1], alpha);
557    if (mipoFactors.getFirst().factor().inCoeffDomain())
558      mipoFactors.removeFirst();
559    for (iter= mipoFactors; iter.hasItem(); iter++)
560    {
561      if (degree (iter.getItem().factor()) > 1)
562        wrongMipo++;
563    }
564    if (wrongMipo == mipoFactors.length())
565    {
566      rec=true;
567      goto differentevalpoint;
568    }
569    wrongMipo= 0;
570    beta= rootOf (mipos[1]);
571    mipoFactors= factorize (mipos[0], beta);
572    if (mipoFactors.getFirst().factor().inCoeffDomain())
573      mipoFactors.removeFirst();
574    for (iter= mipoFactors; iter.hasItem(); iter++)
575    {
576      if (degree (iter.getItem().factor()) > 1)
577        wrongMipo++;
578    }
579    if (wrongMipo == mipoFactors.length())
580    {
581      rec=true;
582      goto differentevalpoint;
583    }
584  }
585  else
586  {
587    mipoFactors= factorize (mipos[0], alpha);
588    if (mipoFactors.getFirst().factor().inCoeffDomain())
589      mipoFactors.removeFirst();
590    for (iter= mipoFactors; iter.hasItem(); iter++)
591    {
592      if (degree (iter.getItem().factor()) > 1)
593        wrongMipo++;
594    }
595    if (wrongMipo == mipoFactors.length())
596    {
597      rec=true;
598      goto differentevalpoint;
599    }
600    wrongMipo= 0;
601    beta= rootOf (mipos[0]);
602    mipoFactors= factorize (mipos[1], beta);
603    if (mipoFactors.getFirst().factor().inCoeffDomain())
604      mipoFactors.removeFirst();
605    for (iter= mipoFactors; iter.hasItem(); iter++)
606    {
607      if (degree (iter.getItem().factor()) > 1)
608        wrongMipo++;
609    }
610    if (wrongMipo == mipoFactors.length())
611    {
612      rec=true;
613      goto differentevalpoint;
614    }
615  }
616
617
618  CanonicalForm F1;
619  if (degree (F,1) > minTdeg)
620    F1= F (eval[1], 2);
621  else
622    F1= F (eval[0], 1);
623
624  CFFList QaF1Factors;
625  bool swap= false;
626  if (F1.level() == 2)
627  {
628    swap= true;
629    F1=swapvar (F1, x, y);
630    F= swapvar (F, x, y);
631  }
632
633  wrongMipo= 0;
634  QaF1Factors= factorize (F1, alpha);
635  if (QaF1Factors.getFirst().factor().inCoeffDomain())
636    QaF1Factors.removeFirst();
637  for (iter= QaF1Factors; iter.hasItem(); iter++)
638  {
639    if (degree (iter.getItem().factor()) > minTdeg)
640      wrongMipo++;
641  }
642
643  if (wrongMipo == QaF1Factors.length())
644  {
645    rec= true;
646    F= bufF;
647    goto differentevalpoint;
648  }
649
650  CanonicalForm evaluation;
651  if (swap)
652    evaluation= eval[0];
653  else
654    evaluation= eval[1];
655
656  F *= bCommonDen (F);
657  F= F (y + evaluation, y);
658
659  int liftBound= degree (F,y) + 1;
660
661  modpk b= modpk();
662
663  CanonicalForm den= 1;
664
665  mipo= getMipo (alpha);
666
667  CFList uniFactors;
668  for (iter=QaF1Factors; iter.hasItem(); iter++)
669    uniFactors.append (iter.getItem().factor());
670
671  F /= Lc (F1);
672  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
673  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
674  ZZ NTLf= resultant (NTLmipo, NTLLcf);
675  ZZ NTLD= discriminant (NTLmipo);
676  den= abs (convertZZ2CF (NTLD*NTLf));
677
678  // make factors elements of Z(a)[x] disable for modularDiophant
679  CanonicalForm multiplier= 1;
680  for (CFListIterator i= uniFactors; i.hasItem(); i++)
681  {
682    multiplier *= bCommonDen (i.getItem());
683    i.getItem()= i.getItem()*bCommonDen(i.getItem());
684  }
685  F *= multiplier;
686  F *= bCommonDen (F);
687
688  Off (SW_RATIONAL);
689  int ii= 0;
690  CanonicalForm discMipo= convertZZ2CF (NTLD);
691  findGoodPrime (bufF*discMipo,ii);
692  findGoodPrime (F1*discMipo,ii);
693  findGoodPrime (F*discMipo,ii);
694
695  int pp=cf_getBigPrime(ii);
696  b = coeffBound( F, pp, mipo );
697  modpk bb= coeffBound (F1, pp, mipo);
698  if (bb.getk() > b.getk() ) b=bb;
699    bb= coeffBound (F, pp, mipo);
700  if (bb.getk() > b.getk() ) b=bb;
701
702  ExtensionInfo dummy= ExtensionInfo (alpha, false);
703  DegreePattern degs= DegreePattern (uniFactors);
704
705  bool earlySuccess= false;
706  CFList earlyFactors;
707  uniFactors= henselLiftAndEarly
708              (F, earlySuccess, earlyFactors, degs, liftBound,
709               uniFactors, dummy, evaluation, b, den);
710
711  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
712
713  CanonicalForm MODl= power (y, liftBound);
714
715  On (SW_RATIONAL);
716  F *= bCommonDen (F);
717  Off (SW_RATIONAL);
718
719  CFList biFactors;
720
721  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
722                                  uniFactors.length()/2, b, den);
723
724  On (SW_RATIONAL);
725
726  if (earlySuccess)
727    biFactors= Union (earlyFactors, biFactors);
728  else if (!earlySuccess && degs.getLength() == 1)
729    biFactors= earlyFactors;
730
731  bool swap2= false;
732  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
733  if (isOn (SW_RATIONAL))
734    normalize (biFactors);
735
736  CFAFList result;
737  bool found= false;
738
739  for (CFListIterator i= biFactors; i.hasItem(); i++)
740  {
741    if (full)
742      result.append (CFAFactor (decompress (i.getItem(), M, S),
743                                getMipo (alpha), 1));
744
745    if (totaldegree (i.getItem()) == minTdeg)
746    {
747      if (!full)
748        result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
749                                     getMipo (alpha), 1));
750      found= true;
751
752      if (!full)
753        break;
754    }
755  }
756
757  if (!found)
758  {
759    rec= true;
760    F= bufF;
761    goto differentevalpoint;
762  }
763
764  if (isRat)
765    On (SW_RATIONAL);
766  else
767    Off (SW_RATIONAL);
768
769  mpz_clear (M[0]);
770  mpz_clear (M[1]);
771  mpz_clear (M[2]);
772  mpz_clear (M[3]);
773  delete [] M;
774
775  mpz_clear (S[0]);
776  mpz_clear (S[1]);
777  delete [] S;
778
779  return result;
780}
781#endif
Note: See TracBrowser for help on using the repository browser.