source: git/factory/facAbsBiFact.cc @ 8749841

spielwiese
Last change on this file since 8749841 was 8749841, checked in by Hans Schoenemann <hannes@…>, 4 years ago
factory: check for NTL/FLINT, p1
  • Property mode set to 100644
File size: 21.7 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#if defined(HAVE_NTL) || defined(HAVE_FLINT)
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          #ifdef HAVE_FLINT
116          // init
117          fmpz_t FLINTD1,FLINTD2;
118          fmpz_init(FLINTD1);
119          fmpz_init(FLINTD2);
120          fmpz_poly_t FLINTf1;
121          fmpz_poly_t FLINTf2;
122          // conversion
123          convertFacCF2Fmpz_poly_t(FLINTf1,f1);
124          convertFacCF2Fmpz_poly_t(FLINTf2,f2);
125          // discriminant
126          fmpz_poly_discriminant(FLINTD1,FLINTf1);
127          fmpz_poly_discriminant(FLINTD2,FLINTf2);
128          // conversion
129          CanonicalForm D1= convertFmpz2CF(FLINTD1);
130          CanonicalForm D2= convertFmpz2CF(FLINTD2);
131          // clean up
132          fmpz_poly_clear(FLINTf1);
133          fmpz_poly_clear(FLINTf2);
134          fmpz_clear(FLINTD1);
135          fmpz_clear(FLINTD2);
136          #elif defined(HAVE_NTL)
137          ZZX NTLf1= convertFacCF2NTLZZX (f1);
138          ZZX NTLf2= convertFacCF2NTLZZX (f2);
139          ZZ NTLD1= discriminant (NTLf1);
140          ZZ NTLD2= discriminant (NTLf2);
141          CanonicalForm D1= convertZZ2CF (NTLD1);
142          CanonicalForm D2= convertZZ2CF (NTLD2);
143          #else
144          factoryError("NTL/FLINT missing: choosePoint");
145          #endif
146          if ((!f.isZero()) &&
147              (abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
148          {
149            for (i= cf_getNumPrimes()-1; i >= 0; i--)
150            {
151              if (f % CanonicalForm (cf_getPrime (i)) == 0)
152              {
153                p= cf_getPrime(i);
154                Fp= mod (F,p);
155                if (totaldegree (Fp) == tdegF &&
156                    degree (mod (f2,p), 1) == degree (F,1) &&
157                    degree (mod (f1, p),2) == degree (F,2))
158                {
159                  if (mod (D1, p) != 0 && mod (D2, p) != 0)
160                  {
161                    eval[0]= E1[1];
162                    eval[1]= E2[2];
163                    return p;
164                  }
165                }
166              }
167            }
168          }
169          else if (!f.isZero())
170          {
171            for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
172            {
173              if (f % CanonicalForm (cf_getSmallPrime (i)) == 0)
174              {
175                p= cf_getSmallPrime (i);
176                Fp= mod (F,p);
177                if (totaldegree (Fp) == tdegF &&
178                    degree (mod (f2, p),1) == degree (F,1) &&
179                    degree (mod (f1,p),2) == degree (F,2))
180                {
181                  if (mod (D1, p) != 0 && mod (D2, p) != 0)
182                  {
183                    eval[0]= E1[1];
184                    eval[1]= E2[2];
185                    return p;
186                  }
187                }
188              }
189            }
190          }
191        }
192        E2.nextpoint();
193        On (SW_RATIONAL);
194      }
195    }
196    E1.nextpoint();
197    if (count == 2)
198    {
199      count= 0;
200      absValue++;
201      E1=REvaluation (1, 1, IntRandom (absValue));
202      E2=REvaluation (2, 2, IntRandom (absValue));
203      E1.nextpoint();
204      E2.nextpoint();
205    }
206  }
207  return 0;
208}
209
210#ifdef HAVE_NTL // henselLiftAndEarly
211//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
212CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full)
213{
214  CanonicalForm F= bCommonDen (G)*G;
215  bool isRat= isOn (SW_RATIONAL);
216  Off (SW_RATIONAL);
217  F /= icontent (F);
218  On (SW_RATIONAL);
219
220  mpz_t * M=new mpz_t [4];
221  mpz_init (M[0]);
222  mpz_init (M[1]);
223  mpz_init (M[2]);
224  mpz_init (M[3]);
225
226  mpz_t * S=new mpz_t [2];
227  mpz_init (S[0]);
228  mpz_init (S[1]);
229
230  F= compress (F, M, S);
231
232  if (F.isUnivariate())
233  {
234    if (degree (F) == 1)
235    {
236      mpz_clear (M[0]);
237      mpz_clear (M[1]);
238      mpz_clear (M[2]);
239      mpz_clear (M[3]);
240      delete [] M;
241
242      mpz_clear (S[0]);
243      mpz_clear (S[1]);
244      delete [] S;
245      if (!isRat)
246        Off (SW_RATIONAL);
247      return CFAFList (CFAFactor (G, 1, 1));
248    }
249    CFAFList result= uniAbsFactorize (F, full);
250    if (result.getFirst().factor().inCoeffDomain())
251      result.removeFirst();
252    for (CFAFListIterator iter=result; iter.hasItem(); iter++)
253      iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
254                                 iter.getItem().minpoly(),iter.getItem().exp());
255    mpz_clear (M[0]);
256    mpz_clear (M[1]);
257    mpz_clear (M[2]);
258    mpz_clear (M[3]);
259    delete [] M;
260
261    mpz_clear (S[0]);
262    mpz_clear (S[1]);
263    delete [] S;
264    if (!isRat)
265      Off (SW_RATIONAL);
266    return result;
267  }
268
269  if (degree (F, 1) == 1 || degree (F, 2) == 1)
270  {
271    mpz_clear (M[0]);
272    mpz_clear (M[1]);
273    mpz_clear (M[2]);
274    mpz_clear (M[3]);
275    delete [] M;
276
277    mpz_clear (S[0]);
278    mpz_clear (S[1]);
279    delete [] S;
280    if (!isRat)
281      Off (SW_RATIONAL);
282    return CFAFList (CFAFactor (G, 1, 1));
283  }
284  int minTdeg, tdegF= totaldegree (F);
285  CanonicalForm Fp, smallestFactor;
286  int p;
287  CFFList factors;
288  Variable alpha;
289  bool rec= false;
290  Variable x= Variable (1);
291  Variable y= Variable (2);
292  CanonicalForm bufF= F;
293  CFFListIterator iter;
294  CFArray eval= CFArray (2);
295  int absValue= 1;
296differentevalpoint:
297  while (1)
298  {
299    TIMING_START (fac_evalpoint);
300    p= choosePoint (F, tdegF, eval, rec, absValue);
301    TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
302
303    //after here isOn (SW_RATIONAL)==false
304    setCharacteristic (p);
305    Fp=F.mapinto();
306    factors= factorize (Fp);
307
308    if (factors.getFirst().factor().inCoeffDomain())
309      factors.removeFirst();
310
311    if (factors.length() == 1 && factors.getFirst().exp() == 1)
312    {
313      if (absIrredTest (Fp))
314      {
315        if (isRat)
316          On (SW_RATIONAL);
317        setCharacteristic(0);
318        mpz_clear (M[0]);
319        mpz_clear (M[1]);
320        mpz_clear (M[2]);
321        mpz_clear (M[3]);
322        delete [] M;
323
324        mpz_clear (S[0]);
325        mpz_clear (S[1]);
326        delete [] S;
327        return CFAFList (CFAFactor (G, 1, 1));
328      }
329      else
330      {
331        setCharacteristic (0);
332        if (modularIrredTestWithShift (F))
333        {
334          if (isRat)
335            On (SW_RATIONAL);
336          mpz_clear (M[0]);
337          mpz_clear (M[1]);
338          mpz_clear (M[2]);
339          mpz_clear (M[3]);
340          delete [] M;
341
342          mpz_clear (S[0]);
343          mpz_clear (S[1]);
344          delete [] S;
345          return CFAFList (CFAFactor (G, 1, 1));
346        }
347        rec= true;
348        continue;
349      }
350    }
351    iter= factors;
352    smallestFactor= iter.getItem().factor();
353    while (smallestFactor.isUnivariate() && iter.hasItem())
354    {
355      iter++;
356      if (!iter.hasItem())
357        break;
358      smallestFactor= iter.getItem().factor();
359    }
360
361    minTdeg= totaldegree (smallestFactor);
362    if (iter.hasItem())
363      iter++;
364    for (; iter.hasItem(); iter++)
365    {
366      if (!iter.getItem().factor().isUnivariate() &&
367          (totaldegree (iter.getItem().factor()) < minTdeg))
368      {
369        smallestFactor= iter.getItem().factor();
370        minTdeg= totaldegree (smallestFactor);
371      }
372    }
373    if (tdegF % minTdeg == 0)
374      break;
375    setCharacteristic(0);
376    rec=true;
377  }
378  CanonicalForm Gp= Fp/smallestFactor;
379  Gp= Gp /Lc (Gp);
380
381  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
382  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
383  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
384  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
385
386  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
387               !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
388  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
389               !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
390  if (!xValid || !yValid)
391  {
392    rec= true;
393    setCharacteristic (0);
394    goto differentevalpoint;
395  }
396
397  setCharacteristic (0);
398
399  CanonicalForm mipo;
400
401  CFArray mipos= CFArray (2);
402  CFFList mipoFactors;
403  for (int i= 1; i < 3; i++)
404  {
405    CanonicalForm Fi= F(eval[i-1],i);
406
407    int s= tdegF/minTdeg + 1;
408    CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
409    bound *= power (CanonicalForm (s),s-1);
410    bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
411
412    CanonicalForm B = p;
413    long k = 1L;
414    while ( B < bound ) {
415      B *= p;
416      k++;
417    }
418
419    //TODO take floor (log2(k))
420    k= k+1;
421#ifdef HAVE_FLINT
422    fmpz_poly_t FLINTFi;
423    convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
424    setCharacteristic (p);
425    nmod_poly_t FLINTFpi, FLINTGpi;
426    if (i == 2)
427    {
428      convertFacCF2nmod_poly_t (FLINTFpi,
429                                smallestFactorEvalx/lc (smallestFactorEvalx));
430      convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
431    }
432    else
433    {
434      convertFacCF2nmod_poly_t (FLINTFpi,
435                                smallestFactorEvaly/lc (smallestFactorEvaly));
436      convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
437    }
438    nmod_poly_factor_t nmodFactors;
439    nmod_poly_factor_init (nmodFactors);
440    nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
441    nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
442
443    // the following fix is due to interface changes from  FLINT 2.3 -> FLINT 2.4
444#   ifndef slong
445#          define slong long
446#   endif
447
448    slong * link= new slong [2];
449    fmpz_poly_t *v= new fmpz_poly_t[2];
450    fmpz_poly_t *w= new fmpz_poly_t[2];
451    fmpz_poly_init(v[0]);
452    fmpz_poly_init(v[1]);
453    fmpz_poly_init(w[0]);
454    fmpz_poly_init(w[1]);
455
456    fmpz_poly_factor_t liftedFactors;
457    fmpz_poly_factor_init (liftedFactors);
458    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
459                                  nmodFactors, k);
460
461    nmod_poly_factor_clear (nmodFactors);
462    nmod_poly_clear (FLINTFpi);
463    nmod_poly_clear (FLINTGpi);
464
465    setCharacteristic(0);
466    CanonicalForm liftedSmallestFactor=
467    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
468
469    CanonicalForm otherFactor=
470    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
471    modpk pk= modpk (p, k);
472#else
473    modpk pk= modpk (p, k);
474    ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
475    setCharacteristic (p);
476
477    if (fac_NTL_char != p)
478    {
479      fac_NTL_char= p;
480      zz_p::init (p);
481    }
482    zz_pX NTLFpi, NTLGpi;
483    if (i == 2)
484    {
485      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
486      NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
487    }
488    else
489    {
490      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
491      NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
492    }
493    vec_zz_pX modFactors;
494    modFactors.SetLength(2);
495    modFactors[0]= NTLFpi;
496    modFactors[1]= NTLGpi;
497    vec_ZZX liftedFactors;
498    MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
499    setCharacteristic(0);
500    CanonicalForm liftedSmallestFactor=
501                  convertNTLZZX2CF (liftedFactors[0], x);
502
503    CanonicalForm otherFactor=
504                  convertNTLZZX2CF (liftedFactors[1], x);
505#endif
506
507    Off (SW_SYMMETRIC_FF);
508    liftedSmallestFactor= pk (liftedSmallestFactor);
509    if (i == 2)
510      liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
511    else
512      liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
513
514    On (SW_SYMMETRIC_FF);
515    CFMatrix *M= new CFMatrix (s, s);
516    (*M)(s,s)= power (CanonicalForm (p), k);
517    for (int j= 1; j < s; j++)
518    {
519      (*M) (j,j)= 1;
520      (*M) (j+1,j)= -liftedSmallestFactor;
521    }
522
523    #ifdef HAVE_FLINT
524    fmpz_mat_t FLINTM;
525    convertFacCFMatrix2Fmpz_mat_t(FLINTM,*M);
526    fmpq_t delta,eta;
527    fmpq_init(delta); fmpq_set_si(delta,1,1);
528    fmpq_init(eta); fmpq_set_si(eta,3,4);
529    fmpz_mat_transpose(FLINTM,FLINTM);
530    fmpz_mat_lll_storjohann(FLINTM,delta,eta);
531    fmpz_mat_transpose(FLINTM,FLINTM);
532    delete M;
533    M=convertFmpz_mat_t2FacCFMatrix(FLINTM);
534    fmpz_mat_clear(FLINTM);
535    #elif defined(HAVE_NTL)
536    mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
537
538    ZZ det;
539
540    transpose (*NTLM, *NTLM);
541    (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
542    transpose (*NTLM, *NTLM);
543    delete M;
544    M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
545    delete NTLM;
546    #else
547    factoryError("NTL/FLINT missing: absBiFactorizeMain");
548    #endif
549
550    mipo= 0;
551    for (int j= 1; j <= s; j++)
552      mipo += (*M) (j,1)*power (x,s-j);
553
554    delete M;
555    mipoFactors= factorize (mipo);
556    if (mipoFactors.getFirst().factor().inCoeffDomain())
557      mipoFactors.removeFirst();
558
559#ifdef HAVE_FLINT
560    fmpz_poly_clear (v[0]);
561    fmpz_poly_clear (v[1]);
562    fmpz_poly_clear (w[0]);
563    fmpz_poly_clear (w[1]);
564    delete [] v;
565    delete [] w;
566    delete [] link;
567    fmpz_poly_factor_clear (liftedFactors);
568#endif
569
570    if (mipoFactors.length() > 1 ||
571        (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
572         mipo.inCoeffDomain())
573    {
574        rec=true;
575        goto differentevalpoint;
576    }
577    else
578      mipos[i-1]= mipo;
579  }
580
581  if (degree (mipos[0]) != degree (mipos[1]))
582  {
583    rec=true;
584    goto differentevalpoint;
585  }
586
587  On (SW_RATIONAL);
588  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
589    alpha= rootOf (mipos[0]);
590  else
591    alpha= rootOf (mipos[1]);
592
593  int wrongMipo= 0;
594
595  Variable beta;
596  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
597  {
598    mipoFactors= factorize (mipos[1], alpha);
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    wrongMipo= 0;
612    beta= rootOf (mipos[1]);
613    mipoFactors= factorize (mipos[0], beta);
614    if (mipoFactors.getFirst().factor().inCoeffDomain())
615      mipoFactors.removeFirst();
616    for (iter= mipoFactors; iter.hasItem(); iter++)
617    {
618      if (degree (iter.getItem().factor()) > 1)
619        wrongMipo++;
620    }
621    if (wrongMipo == mipoFactors.length())
622    {
623      rec=true;
624      goto differentevalpoint;
625    }
626  }
627  else
628  {
629    mipoFactors= factorize (mipos[0], alpha);
630    if (mipoFactors.getFirst().factor().inCoeffDomain())
631      mipoFactors.removeFirst();
632    for (iter= mipoFactors; iter.hasItem(); iter++)
633    {
634      if (degree (iter.getItem().factor()) > 1)
635        wrongMipo++;
636    }
637    if (wrongMipo == mipoFactors.length())
638    {
639      rec=true;
640      goto differentevalpoint;
641    }
642    wrongMipo= 0;
643    beta= rootOf (mipos[0]);
644    mipoFactors= factorize (mipos[1], beta);
645    if (mipoFactors.getFirst().factor().inCoeffDomain())
646      mipoFactors.removeFirst();
647    for (iter= mipoFactors; iter.hasItem(); iter++)
648    {
649      if (degree (iter.getItem().factor()) > 1)
650        wrongMipo++;
651    }
652    if (wrongMipo == mipoFactors.length())
653    {
654      rec=true;
655      goto differentevalpoint;
656    }
657  }
658
659
660  CanonicalForm F1;
661  if (degree (F,1) > minTdeg)
662    F1= F (eval[1], 2);
663  else
664    F1= F (eval[0], 1);
665
666  CFFList QaF1Factors;
667  bool swap= false;
668  if (F1.level() == 2)
669  {
670    swap= true;
671    F1=swapvar (F1, x, y);
672    F= swapvar (F, x, y);
673  }
674
675  wrongMipo= 0;
676  QaF1Factors= factorize (F1, alpha);
677  if (QaF1Factors.getFirst().factor().inCoeffDomain())
678    QaF1Factors.removeFirst();
679  for (iter= QaF1Factors; iter.hasItem(); iter++)
680  {
681    if (degree (iter.getItem().factor()) > minTdeg)
682      wrongMipo++;
683  }
684
685  if (wrongMipo == QaF1Factors.length())
686  {
687    rec= true;
688    F= bufF;
689    goto differentevalpoint;
690  }
691
692  CanonicalForm evaluation;
693  if (swap)
694    evaluation= eval[0];
695  else
696    evaluation= eval[1];
697
698  F *= bCommonDen (F);
699  F= F (y + evaluation, y);
700
701  int liftBound= degree (F,y) + 1;
702
703  modpk b= modpk();
704
705  CanonicalForm den= 1;
706
707  mipo= getMipo (alpha);
708
709  CFList uniFactors;
710  for (iter=QaF1Factors; iter.hasItem(); iter++)
711    uniFactors.append (iter.getItem().factor());
712
713  F /= Lc (F1);
714  #ifdef HAVE_FLINT
715  // init
716  fmpz_t FLINTf,FLINTD;
717  fmpz_init(FLINTf);
718  fmpz_init(FLINTD);
719  fmpz_poly_t FLINTmipo;
720  fmpz_poly_t FLINTLcf;
721  //conversion
722  convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
723  convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (F*bCommonDen (F)));
724  // resultant, discriminant
725  fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
726  fmpz_poly_discriminant(FLINTD,FLINTmipo);
727  fmpz_mul(FLINTf,FLINTD,FLINTf);
728  den= abs (convertFmpz2CF(FLINTf));
729  // clean up
730  fmpz_clear(FLINTf);
731   // FLINTD is used below
732  fmpz_poly_clear(FLINTLcf);
733  fmpz_poly_clear(FLINTmipo);
734  #elif defined(HAVE_NTL)
735  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
736  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
737  ZZ NTLf= resultant (NTLmipo, NTLLcf);
738  ZZ NTLD= discriminant (NTLmipo);
739  den= abs (convertZZ2CF (NTLD*NTLf));
740  #else
741  factoryError("NTL/FLINT missing: absBiFactorizeMain");
742  #endif
743
744  // make factors elements of Z(a)[x] disable for modularDiophant
745  CanonicalForm multiplier= 1;
746  for (CFListIterator i= uniFactors; i.hasItem(); i++)
747  {
748    multiplier *= bCommonDen (i.getItem());
749    i.getItem()= i.getItem()*bCommonDen(i.getItem());
750  }
751  F *= multiplier;
752  F *= bCommonDen (F);
753
754  Off (SW_RATIONAL);
755  int ii= 0;
756  #ifdef HAVE_FLINT
757  CanonicalForm discMipo= convertFmpz2CF(FLINTD);
758  fmpz_clear(FLINTD);
759  #elif defined(HAVE_NTL)
760  CanonicalForm discMipo= convertZZ2CF (NTLD);
761  #endif
762  findGoodPrime (bufF*discMipo,ii);
763  findGoodPrime (F1*discMipo,ii);
764  findGoodPrime (F*discMipo,ii);
765
766  int pp=cf_getBigPrime(ii);
767  b = coeffBound( F, pp, mipo );
768  modpk bb= coeffBound (F1, pp, mipo);
769  if (bb.getk() > b.getk() ) b=bb;
770    bb= coeffBound (F, pp, mipo);
771  if (bb.getk() > b.getk() ) b=bb;
772
773  ExtensionInfo dummy= ExtensionInfo (alpha, false);
774  DegreePattern degs= DegreePattern (uniFactors);
775
776  bool earlySuccess= false;
777  CFList earlyFactors;
778  uniFactors= henselLiftAndEarly
779              (F, earlySuccess, earlyFactors, degs, liftBound,
780               uniFactors, dummy, evaluation, b, den);
781
782  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
783
784  CanonicalForm MODl= power (y, liftBound);
785
786  On (SW_RATIONAL);
787  F *= bCommonDen (F);
788  Off (SW_RATIONAL);
789
790  CFList biFactors;
791
792  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
793                                  uniFactors.length()/2, b, den);
794
795  On (SW_RATIONAL);
796
797  if (earlySuccess)
798    biFactors= Union (earlyFactors, biFactors);
799  else if (!earlySuccess && degs.getLength() == 1)
800    biFactors= earlyFactors;
801
802  bool swap2= false;
803  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
804  if (isOn (SW_RATIONAL))
805    normalize (biFactors);
806
807  CFAFList result;
808  bool found= false;
809
810  for (CFListIterator i= biFactors; i.hasItem(); i++)
811  {
812    if (full)
813      result.append (CFAFactor (decompress (i.getItem(), M, S),
814                                getMipo (alpha), 1));
815
816    if (totaldegree (i.getItem()) == minTdeg)
817    {
818      if (!full)
819        result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
820                                     getMipo (alpha), 1));
821      found= true;
822
823      if (!full)
824        break;
825    }
826  }
827
828  if (!found)
829  {
830    rec= true;
831    F= bufF;
832    goto differentevalpoint;
833  }
834
835  if (isRat)
836    On (SW_RATIONAL);
837  else
838    Off (SW_RATIONAL);
839
840  mpz_clear (M[0]);
841  mpz_clear (M[1]);
842  mpz_clear (M[2]);
843  mpz_clear (M[3]);
844  delete [] M;
845
846  mpz_clear (S[0]);
847  mpz_clear (S[1]);
848  delete [] S;
849
850  return result;
851}
852#endif
853#endif
Note: See TracBrowser for help on using the repository browser.