Changeset 809d63 in git for factory/facAbsFact.cc


Ignore:
Timestamp:
Apr 19, 2013, 4:18:38 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
Children:
19440966f58621d18daa0987fbb4e8aa899440d7
Parents:
4553b124a4bec0578e5f5f8d00c2d61d8464a7d6
git-author:
Martin Lee <martinlee84@web.de>2013-04-19 16:18:38+02:00
git-committer:
Martin Lee <martinlee84@web.de>2013-05-02 11:42:39+02:00
Message:
chg: code clean up and optimizations
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/facAbsFact.cc

    r4553b1 r809d63  
    3333TIMING_DEFINE_PRINT(fac_evalpoint)
    3434
    35 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
    36 
    3735//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)
    3836int choosePoint (const CanonicalForm& F, int tdegF, CFArray& eval, bool rec)
    … …  
    4846  int i, p;
    4947  eval=CFArray (2);
    50   printf ("tdegF= %d\n", tdegF);
    51   out_cf ("F= ", F, "\n");
    52   printf ("getCharacteristic()= %d\n", getCharacteristic());
    5348  while (1)
    5449  {
    … …  
    5954      f= E2(f1);
    6055      f2= E2 (F);
    61       out_cf ("f= ", f, "\n");
    62       printf ("isOn (SW_RATIONAL)= %d\n", isOn (SW_RATIONAL));
    63       printf ("cf_getSmallPrime (cf_getNumSmallPrimes())= %d\n", cf_getSmallPrime (cf_getNumSmallPrimes()-1));
    64       if ((!f.isZero()) && (abs(f) > cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
     56      if ((!f.isZero()) && (abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
    6557      {
    66         printf ("hier0\n");
    6758        for (i= cf_getNumPrimes()-1; i >= 0; i--)
    6859        {
    … …  
    7162            p= cf_getPrime(i);
    7263            Fp= mod (F,p);
    73             out_cf ("Fp0= ", Fp, "\n");
    74             if (totaldegree (Fp) == tdegF && degree (mod (f2,p), 1) == degree (F,1) && degree (mod (f1, p),2) == degree (F,2))
     64            if (totaldegree (Fp) == tdegF &&
     65                degree (mod (f2,p), 1) == degree (F,1) &&
     66                degree (mod (f1, p),2) == degree (F,2))
    7567            {
    7668              eval[0]= E1[1];
    … …  
    8375      else if (!f.isZero())
    8476      {
    85         printf ("hier\n");
    8677        for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
    8778        {
    … …  
    9081            p= cf_getSmallPrime (i);
    9182            Fp= mod (F,p);
    92             out_cf ("Fp1= ", Fp, "\n");
    93             if (totaldegree (Fp) == tdegF && degree (mod (f2, p),1) == degree (F,1) && degree (mod (f1,p),2) == degree (F,2))
     83            if (totaldegree (Fp) == tdegF &&
     84                degree (mod (f2, p),1) == degree (F,1) &&
     85                degree (mod (f1,p),2) == degree (F,2))
    9486            {
    9587              eval[0]= E1[1];
    … …  
    10294      E2.nextpoint();
    10395      On (SW_RATIONAL);
    104       out_cf ("E2= ", E2[2], "\n");
    10596    }
    10697    E1.nextpoint();
    107     out_cf ("E1= ", E1[1], "\n");
    10898  }
    10999  return 0;
    110100}
    111101
    112 //TODO sowohl bzgl. x als auch y auswerten und minpoly berechnen
     102//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
    113103CFAFList absFactorizeMain (const CanonicalForm& G)
    114104{
    115   //F is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
    116 
    117   out_cf ("F= ", G, "\n");
    118105  CanonicalForm F= bCommonDen (G)*G;
    119106  Off (SW_RATIONAL);
    120107  F /= icontent (F);
    121   out_cf ("F after icontent= ", F, "\n");
    122108  On (SW_RATIONAL);
    123109  CFArray eval;
    … …  
    130116  Variable x= Variable (1);
    131117  Variable y= Variable (2);
     118  CanonicalForm bufF= F;
     119  CFFListIterator iter;
    132120differentevalpoint:
    133121  while (1)
    … …  
    141129    factors= factorize (Fp);
    142130
    143     for (CFFListIterator iter= factors; iter.hasItem(); iter++)
    144     {
    145       out_cf ("factors= ", iter.getItem().factor(), "\n");
    146       printf ("exp= %d\n", iter.getItem().exp());
    147     }
    148     printf ("p= %d\n", p);
    149131    if (factors.getFirst().factor().inCoeffDomain())
    150132      factors.removeFirst();
    151     printf ("factors.length()= %d\n", factors.length());
    152     printf ("factors.getFirst().exp()= %d\n", factors.getFirst().exp());
     133
    153134    if (factors.length() == 1 && factors.getFirst().exp() == 1)
    154135    {
    155       if (absIrredTest (Fp)) //TODO absIrredTest mit shift, modular absIrredTest
     136      if (absIrredTest (Fp))
    156137      {
    157         printf ("irred after test\n");
    158         printf ("absIrred\n");
    159138        setCharacteristic(0);
    160139        alpha= rootOf (x);
    161     out_cf ("G= ", G, "\n");
    162     out_cf ("getMipo (alpha)= ", getMipo (alpha), "\n");
    163 
    164140        return CFAFList (CFAFactor (G, getMipo (alpha), 1));
    165141      }
    … …  
    169145        if (modularIrredTestWithShift (F))
    170146        {
    171           printf ("irred after modular test\n");
    172147          alpha= rootOf (x);
    173148          return CFAFList (CFAFactor (G, getMipo (alpha), 1));
    … …  
    177152      }
    178153    }
    179     CFFListIterator iter= factors;
     154    iter= factors;
    180155    smallestFactor= iter.getItem().factor();
    181     out_cf ("smallestFactor before= ", smallestFactor, "\n");
    182156    while (smallestFactor.isUnivariate() && iter.hasItem())
    183157    {
    … …  
    185159      if (!iter.hasItem())
    186160        break;
    187       out_cf ("factors= ", iter.getItem().factor(), "\n");
    188       printf ("exp= %d\n", iter.getItem().exp());
    189161      smallestFactor= iter.getItem().factor();
    190162    }
    191     //TODO univariate Faktoren rausschmeißen!
     163
    192164    minTdeg= totaldegree (smallestFactor);
    193165    if (iter.hasItem())
    … …  
    195167    for (; iter.hasItem(); iter++)
    196168    {
    197       out_cf ("factors= ", iter.getItem().factor(), "\n");
    198       printf ("exp= %d\n", iter.getItem().exp());
    199       if (!iter.getItem().factor().isUnivariate() && (totaldegree (iter.getItem().factor()) < minTdeg))
     169      if (!iter.getItem().factor().isUnivariate() &&
     170          (totaldegree (iter.getItem().factor()) < minTdeg))
    200171      {
    201172        smallestFactor= iter.getItem().factor();
    … …  
    209180  }
    210181  CanonicalForm Gp= Fp/smallestFactor;
    211   out_cf ("Gp before= ", Gp, "\n");
    212   out_cf ("smallestFactor= ", smallestFactor, "\n");
    213   printf ("degree (Gp,1)= %d\n", degree (Gp, 1));
    214   printf ("degree smallestFactor= %d\n", degree (smallestFactor, 1));
    215   printf ("degree (Fp,1)= %d\n", degree (Fp,1));
    216   printf ("degree (F,1)= %d\n", degree (F,1));
    217   out_cf ("eval[1]= ", eval[1], "\n");
    218   out_cf ("eval[0]= ", eval[0], "\n");
    219   //printf ("Gp*smallestFactor==Fp ? %d\n", Gp*smallestFactor == Fp);
    220182  Gp= Gp /Lc (Gp);
    221183
    … …  
    223185  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
    224186  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
    225   out_cf ("Gp eval= ", Gp, "\n");
    226187  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
    227188
    228   out_cf ("smallestFactorEvalx= ", smallestFactorEvalx, "\n");
    229   out_cf ("gcd (Gpx, smallestFactorEvalx)= ", gcd (Gpx, smallestFactorEvalx), "\n");
    230   bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() || !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
    231   bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() || !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
     189  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
     190               !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
     191  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
     192              !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
    232193  if (!xValid && !yValid)
    233194  {
    234195    rec= true;
    235196    setCharacteristic (0);
    236     printf ("goto1\n");
    237197    goto differentevalpoint;
    238198  }
    … …  
    260220
    261221  CFArray mipos= CFArray (loop-i);
    262   printf ("loop= %d\n", loop);
    263   printf ("xValid= %d\n", xValid);
    264   printf ("yValid= %d\n", yValid);
    265 
    266222  for (; i < loop; i++)
    267223  {
    268224    CanonicalForm Fi= F(eval[i-1],i);
    269     //CanonicalForm Fx= F(eval[0],1);
    270     //CanonicalForm Fy= F(eval[1],2);
    271225
    272226    int s= tdegF/minTdeg + 1;
    … …  
    285239    k= k+1;
    286240    fmpz_poly_t FLINTFi;
    287     out_cf ("Fi= ", Fi, "\n");
    288241    convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
    289242    setCharacteristic (p);
    290     printf ("p= %d\n", p);
    291243    nmod_poly_t FLINTFpi, FLINTGpi;
    292244    if (i == 2)
    293245    {
    294       convertFacCF2nmod_poly_t (FLINTFpi, smallestFactorEvalx/lc (smallestFactorEvalx));
     246      convertFacCF2nmod_poly_t (FLINTFpi,
     247                                smallestFactorEvalx/lc (smallestFactorEvalx));
    295248      convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
    296249    }
    297250    else
    298251    {
    299       convertFacCF2nmod_poly_t (FLINTFpi, smallestFactorEvaly/lc (smallestFactorEvaly));
     252      convertFacCF2nmod_poly_t (FLINTFpi,
     253                                smallestFactorEvaly/lc (smallestFactorEvaly));
    300254      convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
    301255    }
    … …  
    305259    nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
    306260
    307     //out_cf ("Gpx= ", Gpx, "\n");
    308     //out_cf ("smallestFactorEvalx= ", smallestFactorEvalx, "\n");
    309261    long * link= new long [2];
    310262    fmpz_poly_t *v= new fmpz_poly_t[2];
    … …  
    315267    fmpz_poly_init(w[1]);
    316268
    317     printf ("k= %ld\n", k);
    318269    fmpz_poly_factor_t liftedFactors;
    319270    fmpz_poly_factor_init (liftedFactors);
    320     _fmpz_poly_hensel_start_lift(liftedFactors, link, v, w, FLINTFi, nmodFactors, k); //lift factors up to p^k
     271    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
     272                                  nmodFactors, k);
    321273
    322274    nmod_poly_factor_clear (nmodFactors);
    … …  
    326278    setCharacteristic(0);
    327279    modpk pk= modpk (p,k);
    328     CanonicalForm liftedSmallestFactor= convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],Variable (1));
    329 
    330     CanonicalForm otherFactor= convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],Variable (1));
     280    CanonicalForm liftedSmallestFactor=
     281    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],Variable (1));
     282
     283    CanonicalForm otherFactor=
     284    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],Variable (1));
    331285    CanonicalForm test= pk (otherFactor*liftedSmallestFactor);
    332286
    … …  
    378332      {
    379333        rec=true;
    380         printf ("goto2\n");
    381334        goto differentevalpoint;
    382         //TODO check if mipoFactors has length 1 and multiplicity 1 - if not choose a new point!
    383335      }
    384336    }
    … …  
    395347      alpha= rootOf (mipos[1]);
    396348  }
     349  else if (xValid && yValid)
     350  {
     351    if (mipos[0].isZero())
     352      alpha= rootOf (mipos[1]);
     353    else
     354      alpha= rootOf (mipos[0]);
     355  }
    397356  else
    398357    alpha= rootOf (mipo);
    399 
    400   for (i= 0; i < mipos.size(); i++)
    401   {
    402     out_cf ("mipos= ", mipos [i], "\n");
    403     out_cf ("maxNorm mipo= ", maxNorm (mipos[i]), "\n");
    404   }
    405358
    406359  CanonicalForm F1;
    … …  
    419372    F1= F (eval[0], 1);
    420373
     374  bool swap= false;
     375  if (F1.level() == 2)
     376  {
     377    swap= true;
     378    F1=swapvar (F1, x, y);
     379    F= swapvar (F, x, y);
     380  }
     381
    421382  QaF1Factors= factorize (F1, alpha);
    422383  if (QaF1Factors.getFirst().factor().inCoeffDomain())
    423384    QaF1Factors.removeFirst();
    424   out_cf ("mipo0= ", getMipo (alpha), "\n");
    425   for (CFFListIterator iter= QaF1Factors; iter.hasItem(); iter++)
    426   {
    427     out_cf ("QaF1Factors= ", iter.getItem().factor(), "\n");
     385  for (iter= QaF1Factors; iter.hasItem(); iter++)
     386  {
    428387    if (degree (iter.getItem().factor()) > minTdeg)
    429388      wrongMipo++;
    … …  
    432391  if (wrongMipo == QaF1Factors.length())
    433392  {
    434     if (xValid && yValid)
    435     {
    436       if (mipo==mipos[0])
     393    if (xValid && yValid && !mipos[0].isZero() && !mipos[1].isZero())
     394    {
     395      if (maxNorm (mipos[0]) < maxNorm (mipos[1])) //try the other minpoly
    437396        alpha= rootOf (mipos[1]);
    438397      else
    439398        alpha= rootOf (mipos[0]);
    440399    }
     400    else
     401    {
     402      rec= true;
     403      F= bufF;
     404      goto differentevalpoint;
     405    }
    441406
    442407    wrongMipo= 0;
    443     out_cf ("mipo1= ", getMipo (alpha), "\n");
    444408    QaF1Factors= factorize (F1, alpha);
    445409    if (QaF1Factors.getFirst().factor().inCoeffDomain())
    446410      QaF1Factors.removeFirst();
    447     for (CFFListIterator iter= QaF1Factors; iter.hasItem(); iter++)
    448     {
    449       out_cf ("QaF1Factors= ", iter.getItem().factor(), "\n");
     411    for (iter= QaF1Factors; iter.hasItem(); iter++)
     412    {
    450413      if (degree (iter.getItem().factor()) > minTdeg)
    451414        wrongMipo++;
    … …  
    454417    {
    455418      rec= true;
    456       printf ("goto30\n");
     419      F= bufF;
    457420      goto differentevalpoint;
    458421    }
    459422  }
    460423
    461   CanonicalForm A= F;
    462   CanonicalForm Aeval= F1;
    463 
    464   out_cf ("F1= ", F1, "\n");
    465   A *= bCommonDen (A);
    466   A= A (y + eval[1], y); //TODO find right evaluation point and swap if necessary
    467 
    468   out_cf ("A= ", A, "\n");
    469   out_cf ("A[0]= ", A(0,y), "\n");
    470   int liftBound= degree (A,y) + 1;
     424  CanonicalForm evaluation;
     425  if (swap)
     426    evaluation= eval[0];
     427  else
     428    evaluation= eval[1];
     429
     430  F *= bCommonDen (F);
     431  F= F (y + evaluation, y);
     432
     433  int liftBound= degree (F,y) + 1;
    471434
    472435  modpk b= modpk();
    473436
    474   //bool mipoHasDen= false;
    475437  CanonicalForm den= 1;
    476438
    … …  
    478440
    479441  CFList uniFactors;
    480   for (CFFListIterator iter=QaF1Factors; iter.hasItem(); iter++)
    481   {
     442  for (iter=QaF1Factors; iter.hasItem(); iter++)
    482443    uniFactors.append (iter.getItem().factor());
    483     out_cf ("uniFactors.getLast()= ", uniFactors.getLast(), "\n");
    484   }
    485 
    486 
    487     A /= Lc (Aeval);
    488     //mipoHasDen= !bCommonDen(mipo).isOne();
    489     //mipo *= bCommonDen (mipo);
    490     ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
    491     ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
    492     ZZ NTLf= resultant (NTLmipo, NTLLcf);
    493     ZZ NTLD= discriminant (NTLmipo);
    494     den= abs (convertZZ2CF (NTLD*NTLf));
    495 
    496     // make factors elements of Z(a)[x] disable for modularDiophant
    497     CanonicalForm multiplier= 1;
    498     for (CFListIterator i= uniFactors; i.hasItem(); i++)
    499     {
    500       multiplier *= bCommonDen (i.getItem());
    501       i.getItem()= i.getItem()*bCommonDen(i.getItem());
    502     }
    503     A *= multiplier;
    504     A *= bCommonDen (A);
    505 
    506     Off (SW_RATIONAL);
    507     int ii= 0;
    508     CanonicalForm discMipo= convertZZ2CF (NTLD);
    509     findGoodPrime (F*discMipo,ii);
    510     findGoodPrime (Aeval*discMipo,ii);
    511     findGoodPrime (A*discMipo,ii);
    512 
    513     int pp=cf_getBigPrime(ii);
    514     b = coeffBound( A, pp, mipo );
    515     modpk bb= coeffBound (Aeval, pp, mipo);
    516     if (bb.getk() > b.getk() ) b=bb;
    517       bb= coeffBound (F, pp, mipo);
    518     if (bb.getk() > b.getk() ) b=bb;
     444
     445  F /= Lc (F1);
     446  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
     447  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
     448  ZZ NTLf= resultant (NTLmipo, NTLLcf);
     449  ZZ NTLD= discriminant (NTLmipo);
     450  den= abs (convertZZ2CF (NTLD*NTLf));
     451
     452  // make factors elements of Z(a)[x] disable for modularDiophant
     453  CanonicalForm multiplier= 1;
     454  for (CFListIterator i= uniFactors; i.hasItem(); i++)
     455  {
     456    multiplier *= bCommonDen (i.getItem());
     457    i.getItem()= i.getItem()*bCommonDen(i.getItem());
     458  }
     459  F *= multiplier;
     460  F *= bCommonDen (F);
     461
     462  Off (SW_RATIONAL);
     463  int ii= 0;
     464  CanonicalForm discMipo= convertZZ2CF (NTLD);
     465  findGoodPrime (bufF*discMipo,ii);
     466  findGoodPrime (F1*discMipo,ii);
     467  findGoodPrime (F*discMipo,ii);
     468
     469  int pp=cf_getBigPrime(ii);
     470  b = coeffBound( F, pp, mipo );
     471  modpk bb= coeffBound (F1, pp, mipo);
     472  if (bb.getk() > b.getk() ) b=bb;
     473    bb= coeffBound (F, pp, mipo);
     474  if (bb.getk() > b.getk() ) b=bb;
    519475
    520476  ExtensionInfo dummy= ExtensionInfo (alpha, false);
    … …  
    525481  TIMING_START (fac_bi_hensel_lift);
    526482  uniFactors= henselLiftAndEarly
    527               (A, earlySuccess, earlyFactors, degs, liftBound,
    528                uniFactors, dummy, eval[1], b, den);
     483              (F, earlySuccess, earlyFactors, degs, liftBound,
     484               uniFactors, dummy, evaluation, b, den);
    529485  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
    530486                        "time for bivariate hensel lifting over Q: ");
    531487  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    532488
    533   CanonicalForm MODl= power (y, liftBound); //TODO
     489  CanonicalForm MODl= power (y, liftBound);
    534490
    535491  On (SW_RATIONAL);
    536   A *= bCommonDen (A);
     492  F *= bCommonDen (F);
    537493  Off (SW_RATIONAL);
    538494
    539   printf ("earlyFactors.length()= %d\n", earlyFactors.length());
    540495  CFList biFactors;
    541496
    542497  TIMING_START (fac_bi_factor_recombination);
    543   biFactors= factorRecombination (uniFactors, A, MODl, degs, 1,
     498  biFactors= factorRecombination (uniFactors, F, MODl, degs, 1,
    544499                                uniFactors.length()/2, b, den);
    545500  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
    … …  
    554509
    555510  for (CFListIterator i= biFactors; i.hasItem(); i++)
    556     i.getItem()= i.getItem() (y - eval[1], y); //TODO
    557 
    558   bool swap= false;
     511    i.getItem()= i.getItem() (y - evaluation, y);
     512
    559513  bool swap2= false;
    560514  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
    … …  
    565519  bool found= false;
    566520
    567   out_cf ("mipo= ", mipo, "\n");
    568   printf ("minTdeg= %d\n", minTdeg);
    569   for (CFListIterator iter= biFactors; iter.hasItem(); iter++)
    570   {
    571     out_cf ("biFactors= ", iter.getItem(), "\n");
    572     printf ("totaldegree ()= %d\n", totaldegree (iter.getItem()));
    573     if (totaldegree (iter.getItem()) == minTdeg)
    574     {
    575       result= CFAFList (CFAFactor (iter.getItem(), getMipo (alpha), 1));
     521  for (CFListIterator i= biFactors; i.hasItem(); i++)
     522  {
     523    if (totaldegree (i.getItem()) == minTdeg)
     524    {
     525      result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
    576526      found= true;
    577527      break;
    … …  
    579529  }
    580530
    581   if (found)
    582   {
    583     printf ("thisexitexit\n\n");
    584     return result;
    585   }
    586 
    587   /*  A *= bCommonDen (A);
    588   A= A (y + evaluation, y);
    589 
    590   int liftBound= degree (A, y) + 1;
    591 
    592   modpk b= modpk();
    593   bool mipoHasDen= false;
    594   CanonicalForm den= 1;
    595 
    596   if (!extension)
    597   {
    598     Off (SW_RATIONAL);
    599     int i= 0;
    600     findGoodPrime(F,i);
    601     findGoodPrime(Aeval,i);
    602     findGoodPrime(A,i);
    603     if (i >= cf_getNumBigPrimes())
    604       printf ("out of primes\n"); //TODO exit
    605 
    606     int p=cf_getBigPrime(i);
    607     b = coeffBound( A, p );
    608     modpk bb= coeffBound (Aeval, p);
    609     if (bb.getk() > b.getk() ) b=bb;
    610       bb= coeffBound (F, p);
    611     if (bb.getk() > b.getk() ) b=bb;
    612   }
    613   else
    614   {
    615     A /= Lc (Aeval);
    616     mipoHasDen= !bCommonDen(mipo).isOne();
    617     mipo *= bCommonDen (mipo);
    618     ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
    619     ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
    620     ZZ NTLf= resultant (NTLmipo, NTLLcf);
    621     ZZ NTLD= discriminant (NTLmipo);
    622     den= abs (convertZZ2CF (NTLD*NTLf));
    623 
    624     // make factors elements of Z(a)[x] disable for modularDiophant
    625     CanonicalForm multiplier= 1;
    626     for (CFListIterator i= uniFactors; i.hasItem(); i++)
    627     {
    628       multiplier *= bCommonDen (i.getItem());
    629       i.getItem()= i.getItem()*bCommonDen(i.getItem());
    630     }
    631     A *= multiplier;
    632     A *= bCommonDen (A);
    633 
    634     Off (SW_RATIONAL);
    635     int i= 0;
    636     CanonicalForm discMipo= convertZZ2CF (NTLD);
    637     findGoodPrime (F*discMipo,i);
    638     findGoodPrime (Aeval*discMipo,i);
    639     findGoodPrime (A*discMipo,i);
    640 
    641     int p=cf_getBigPrime(i);
    642     b = coeffBound( A, p, mipo );
    643     modpk bb= coeffBound (Aeval, p, mipo);
    644     if (bb.getk() > b.getk() ) b=bb;
    645       bb= coeffBound (F, p, mipo);
    646     if (bb.getk() > b.getk() ) b=bb;
    647   }
    648 
    649   ExtensionInfo dummy= ExtensionInfo (false);
    650   if (extension)
    651     dummy= ExtensionInfo (v, false);
    652   bool earlySuccess= false;
    653   CFList earlyFactors;
    654   TIMING_START (fac_bi_hensel_lift);
    655   uniFactors= henselLiftAndEarly
    656               (A, earlySuccess, earlyFactors, degs, liftBound,
    657                uniFactors, dummy, evaluation, b, den);
    658   TIMING_END_AND_PRINT (fac_bi_hensel_lift,
    659                         "time for bivariate hensel lifting over Q: ");
    660   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    661 
    662   CanonicalForm MODl= power (y, liftBound);
    663 
    664   if (mipoHasDen)
    665   {
    666     Variable vv;
    667     for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
    668       if (hasFirstAlgVar (iter.getItem(), vv))
    669         break;
    670     for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
    671       iter.getItem()= replacevar (iter.getItem(), vv, v);
    672   }
    673 
    674   On (SW_RATIONAL);
    675   A *= bCommonDen (A);
    676   Off (SW_RATIONAL);
    677 
    678   TIMING_START (fac_bi_factor_recombination);
    679   factors= factorRecombination (uniFactors, A, MODl, degs, 1,
    680                                 uniFactors.length()/2, b, den);
    681   TIMING_END_AND_PRINT (fac_bi_factor_recombination,
    682                         "time for bivariate factor recombination over Q: ");
    683 
    684   On (SW_RATIONAL);
    685 
    686   if (earlySuccess)
    687     factors= Union (earlyFactors, factors);
    688   else if (!earlySuccess && degs.getLength() == 1)
    689     factors= earlyFactors;
    690 
    691   for (CFListIterator i= factors; i.hasItem(); i++)
    692     i.getItem()= i.getItem() (y - evaluation, y);
    693 
    694   appendSwapDecompress (factors, conv (contentAxFactors),
    695                         conv (contentAyFactors), swap, swap2, N);
    696   if (isOn (SW_RATIONAL))
    697     normalize (factors);*/
    698 
    699   TIMING_START (fac_Qa_factorize);
    700   CFFList QaFactors= factorize (F, alpha); //TODO lift these factors
    701   TIMING_END_AND_PRINT (fac_Qa_factorize, "time to factorize over Qa: ");
    702 
    703   /*mipo= getMipo (alpha);
    704   out_cf ("maxNorm (mipo)= ", maxNorm (mipo), "\n");
    705   QaFactors.append (CFFactor (mipo, 1)); //last factor is the minimal polynomial that defines the extension
    706   if (degree (mipo) < 3)
    707     printf ("scheissescheissescheissescheisse\n");*/
    708   printf ("minTdeg= %d\n", minTdeg);
    709   //CFAFList result;
    710   //bool found= false;
    711   out_cf ("mipo= ", getMipo (alpha), "\n");
    712   for (CFFListIterator iter= QaFactors; iter.hasItem(); iter++)
    713   {
    714     out_cf ("QaFactors= ", iter.getItem().factor(), "\n");
    715     printf ("totaldegree ()= %d\n", totaldegree (iter.getItem().factor()));
    716     if (totaldegree (iter.getItem().factor()) == minTdeg)
    717     {
    718       result= CFAFList (CFAFactor (iter.getItem().factor(), getMipo (alpha), 1));
    719       found= true;
    720       break;
    721     }
    722   }
    723   if (!found && xValid && yValid)
    724   {
    725     if (mipo == mipos [0])
    726       mipo= mipos[1];
    727     else
    728       mipo= mipos[0];
    729     alpha= rootOf (mipo);
    730 
    731     QaFactors= factorize (F, alpha);
    732 
    733     for (CFFListIterator iter= QaFactors; iter.hasItem(); iter++)
    734     {
    735       out_cf ("QaFactors= ", iter.getItem().factor(), "\n");
    736       printf ("totaldegree ()= %d\n", totaldegree (iter.getItem().factor()));
    737       if (totaldegree (iter.getItem().factor()) == minTdeg)
    738       {
    739         result= CFAFList (CFAFactor (iter.getItem().factor(), getMipo (alpha), 1));
    740         found= true;
    741         break;
    742       }
    743     }
    744     if (!found)
    745     {
    746       rec= true;
    747       printf ("goto31\n");
    748       goto differentevalpoint;
    749     }
    750   }
    751   else if (!found)
     531  if (!found)
    752532  {
    753533    rec= true;
    754     printf ("goto32\n");
     534    F= bufF;
    755535    goto differentevalpoint;
    756536  }
    … …  
    758538  return result;
    759539}
     540
    760541#endif
    761542#endif
Note: See TracChangeset for help on using the changeset viewer.