source: git/factory/facAbsBiFact.cc @ b5f27dd

spielwiese
Last change on this file since b5f27dd was 7cb76d, checked in by Oleksandr Motsak <motsak@…>, 10 years ago
Adaptation to FLINT interface changes
  • 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#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    // the following fix is due to interface changes from  FLINT 2.3 -> FLINT 2.4
419#   ifndef slong
420#          define slong long
421#   endif
422
423    slong * link= new slong [2];
424    fmpz_poly_t *v= new fmpz_poly_t[2];
425    fmpz_poly_t *w= new fmpz_poly_t[2];
426    fmpz_poly_init(v[0]);
427    fmpz_poly_init(v[1]);
428    fmpz_poly_init(w[0]);
429    fmpz_poly_init(w[1]);
430
431    fmpz_poly_factor_t liftedFactors;
432    fmpz_poly_factor_init (liftedFactors);
433    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
434                                  nmodFactors, k);
435
436    nmod_poly_factor_clear (nmodFactors);
437    nmod_poly_clear (FLINTFpi);
438    nmod_poly_clear (FLINTGpi);
439
440    setCharacteristic(0);
441    CanonicalForm liftedSmallestFactor=
442    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
443
444    CanonicalForm otherFactor=
445    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
446    modpk pk= modpk (p, k);
447#else
448    modpk pk= modpk (p, k);
449    ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
450    setCharacteristic (p);
451
452    if (fac_NTL_char != p)
453    {
454      fac_NTL_char= p;
455      zz_p::init (p);
456    }
457    zz_pX NTLFpi, NTLGpi;
458    if (i == 2)
459    {
460      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
461      NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
462    }
463    else
464    {
465      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
466      NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
467    }
468    vec_zz_pX modFactors;
469    modFactors.SetLength(2);
470    modFactors[0]= NTLFpi;
471    modFactors[1]= NTLGpi;
472    vec_ZZX liftedFactors;
473    MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
474    setCharacteristic(0);
475    CanonicalForm liftedSmallestFactor=
476                  convertNTLZZX2CF (liftedFactors[0], x);
477
478    CanonicalForm otherFactor=
479                  convertNTLZZX2CF (liftedFactors[1], x);
480#endif
481
482    Off (SW_SYMMETRIC_FF);
483    liftedSmallestFactor= pk (liftedSmallestFactor);
484    if (i == 2)
485      liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
486    else
487      liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
488
489    On (SW_SYMMETRIC_FF);
490    CFMatrix *M= new CFMatrix (s, s);
491    (*M)(s,s)= power (CanonicalForm (p), k);
492    for (int j= 1; j < s; j++)
493    {
494      (*M) (j,j)= 1;
495      (*M) (j+1,j)= -liftedSmallestFactor;
496    }
497
498    mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
499
500    ZZ det;
501
502    transpose (*NTLM, *NTLM);
503    (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
504    transpose (*NTLM, *NTLM);
505    delete M;
506    M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
507    delete NTLM;
508
509    mipo= 0;
510    for (int j= 1; j <= s; j++)
511      mipo += (*M) (j,1)*power (x,s-j);
512
513    delete M;
514    mipoFactors= factorize (mipo);
515    if (mipoFactors.getFirst().factor().inCoeffDomain())
516      mipoFactors.removeFirst();
517
518#ifdef HAVE_FLINT
519    fmpz_poly_clear (v[0]);
520    fmpz_poly_clear (v[1]);
521    fmpz_poly_clear (w[0]);
522    fmpz_poly_clear (w[1]);
523    delete [] v;
524    delete [] w;
525    delete [] link;
526    fmpz_poly_factor_clear (liftedFactors);
527#endif
528
529    if (mipoFactors.length() > 1 ||
530        (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
531         mipo.inCoeffDomain())
532    {
533        rec=true;
534        goto differentevalpoint;
535    }
536    else
537      mipos[i-1]= mipo;
538  }
539
540  if (degree (mipos[0]) != degree (mipos[1]))
541  {
542    rec=true;
543    goto differentevalpoint;
544  }
545
546  On (SW_RATIONAL);
547  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
548    alpha= rootOf (mipos[0]);
549  else
550    alpha= rootOf (mipos[1]);
551
552  int wrongMipo= 0;
553
554  Variable beta;
555  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
556  {
557    mipoFactors= factorize (mipos[1], alpha);
558    if (mipoFactors.getFirst().factor().inCoeffDomain())
559      mipoFactors.removeFirst();
560    for (iter= mipoFactors; iter.hasItem(); iter++)
561    {
562      if (degree (iter.getItem().factor()) > 1)
563        wrongMipo++;
564    }
565    if (wrongMipo == mipoFactors.length())
566    {
567      rec=true;
568      goto differentevalpoint;
569    }
570    wrongMipo= 0;
571    beta= rootOf (mipos[1]);
572    mipoFactors= factorize (mipos[0], beta);
573    if (mipoFactors.getFirst().factor().inCoeffDomain())
574      mipoFactors.removeFirst();
575    for (iter= mipoFactors; iter.hasItem(); iter++)
576    {
577      if (degree (iter.getItem().factor()) > 1)
578        wrongMipo++;
579    }
580    if (wrongMipo == mipoFactors.length())
581    {
582      rec=true;
583      goto differentevalpoint;
584    }
585  }
586  else
587  {
588    mipoFactors= factorize (mipos[0], alpha);
589    if (mipoFactors.getFirst().factor().inCoeffDomain())
590      mipoFactors.removeFirst();
591    for (iter= mipoFactors; iter.hasItem(); iter++)
592    {
593      if (degree (iter.getItem().factor()) > 1)
594        wrongMipo++;
595    }
596    if (wrongMipo == mipoFactors.length())
597    {
598      rec=true;
599      goto differentevalpoint;
600    }
601    wrongMipo= 0;
602    beta= rootOf (mipos[0]);
603    mipoFactors= factorize (mipos[1], beta);
604    if (mipoFactors.getFirst().factor().inCoeffDomain())
605      mipoFactors.removeFirst();
606    for (iter= mipoFactors; iter.hasItem(); iter++)
607    {
608      if (degree (iter.getItem().factor()) > 1)
609        wrongMipo++;
610    }
611    if (wrongMipo == mipoFactors.length())
612    {
613      rec=true;
614      goto differentevalpoint;
615    }
616  }
617
618
619  CanonicalForm F1;
620  if (degree (F,1) > minTdeg)
621    F1= F (eval[1], 2);
622  else
623    F1= F (eval[0], 1);
624
625  CFFList QaF1Factors;
626  bool swap= false;
627  if (F1.level() == 2)
628  {
629    swap= true;
630    F1=swapvar (F1, x, y);
631    F= swapvar (F, x, y);
632  }
633
634  wrongMipo= 0;
635  QaF1Factors= factorize (F1, alpha);
636  if (QaF1Factors.getFirst().factor().inCoeffDomain())
637    QaF1Factors.removeFirst();
638  for (iter= QaF1Factors; iter.hasItem(); iter++)
639  {
640    if (degree (iter.getItem().factor()) > minTdeg)
641      wrongMipo++;
642  }
643
644  if (wrongMipo == QaF1Factors.length())
645  {
646    rec= true;
647    F= bufF;
648    goto differentevalpoint;
649  }
650
651  CanonicalForm evaluation;
652  if (swap)
653    evaluation= eval[0];
654  else
655    evaluation= eval[1];
656
657  F *= bCommonDen (F);
658  F= F (y + evaluation, y);
659
660  int liftBound= degree (F,y) + 1;
661
662  modpk b= modpk();
663
664  CanonicalForm den= 1;
665
666  mipo= getMipo (alpha);
667
668  CFList uniFactors;
669  for (iter=QaF1Factors; iter.hasItem(); iter++)
670    uniFactors.append (iter.getItem().factor());
671
672  F /= Lc (F1);
673  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
674  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
675  ZZ NTLf= resultant (NTLmipo, NTLLcf);
676  ZZ NTLD= discriminant (NTLmipo);
677  den= abs (convertZZ2CF (NTLD*NTLf));
678
679  // make factors elements of Z(a)[x] disable for modularDiophant
680  CanonicalForm multiplier= 1;
681  for (CFListIterator i= uniFactors; i.hasItem(); i++)
682  {
683    multiplier *= bCommonDen (i.getItem());
684    i.getItem()= i.getItem()*bCommonDen(i.getItem());
685  }
686  F *= multiplier;
687  F *= bCommonDen (F);
688
689  Off (SW_RATIONAL);
690  int ii= 0;
691  CanonicalForm discMipo= convertZZ2CF (NTLD);
692  findGoodPrime (bufF*discMipo,ii);
693  findGoodPrime (F1*discMipo,ii);
694  findGoodPrime (F*discMipo,ii);
695
696  int pp=cf_getBigPrime(ii);
697  b = coeffBound( F, pp, mipo );
698  modpk bb= coeffBound (F1, pp, mipo);
699  if (bb.getk() > b.getk() ) b=bb;
700    bb= coeffBound (F, pp, mipo);
701  if (bb.getk() > b.getk() ) b=bb;
702
703  ExtensionInfo dummy= ExtensionInfo (alpha, false);
704  DegreePattern degs= DegreePattern (uniFactors);
705
706  bool earlySuccess= false;
707  CFList earlyFactors;
708  uniFactors= henselLiftAndEarly
709              (F, earlySuccess, earlyFactors, degs, liftBound,
710               uniFactors, dummy, evaluation, b, den);
711
712  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
713
714  CanonicalForm MODl= power (y, liftBound);
715
716  On (SW_RATIONAL);
717  F *= bCommonDen (F);
718  Off (SW_RATIONAL);
719
720  CFList biFactors;
721
722  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
723                                  uniFactors.length()/2, b, den);
724
725  On (SW_RATIONAL);
726
727  if (earlySuccess)
728    biFactors= Union (earlyFactors, biFactors);
729  else if (!earlySuccess && degs.getLength() == 1)
730    biFactors= earlyFactors;
731
732  bool swap2= false;
733  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
734  if (isOn (SW_RATIONAL))
735    normalize (biFactors);
736
737  CFAFList result;
738  bool found= false;
739
740  for (CFListIterator i= biFactors; i.hasItem(); i++)
741  {
742    if (full)
743      result.append (CFAFactor (decompress (i.getItem(), M, S),
744                                getMipo (alpha), 1));
745
746    if (totaldegree (i.getItem()) == minTdeg)
747    {
748      if (!full)
749        result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
750                                     getMipo (alpha), 1));
751      found= true;
752
753      if (!full)
754        break;
755    }
756  }
757
758  if (!found)
759  {
760    rec= true;
761    F= bufF;
762    goto differentevalpoint;
763  }
764
765  if (isRat)
766    On (SW_RATIONAL);
767  else
768    Off (SW_RATIONAL);
769
770  mpz_clear (M[0]);
771  mpz_clear (M[1]);
772  mpz_clear (M[2]);
773  mpz_clear (M[3]);
774  delete [] M;
775
776  mpz_clear (S[0]);
777  mpz_clear (S[1]);
778  delete [] S;
779
780  return result;
781}
782
783#endif
784
785
Note: See TracBrowser for help on using the repository browser.