source: git/factory/facAbsBiFact.cc @ fd68165

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