facAbsBiFact.h File Reference

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo More...

#include "canonicalform.h"

Go to the source code of this file.

Functions
CFAFList	absBiFactorizeMain (const CanonicalForm &F, bool full=false)
	main absolute factorization routine, expects bivariate poly which is irreducible over Q
static void	normalize (CFAFList &L)
	normalize factors, i.e. make factors monic
CFAFList	uniAbsFactorize (const CanonicalForm &F, bool full=false)
	univariate absolute factorization over Q

Detailed Description

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo

Author

Martin Lee

Definition in file facAbsBiFact.h.

Function Documentation

absBiFactorizeMain()

CFAFList absBiFactorizeMain	(	const CanonicalForm &	F,
		bool	full = false )

main absolute factorization routine, expects bivariate poly which is irreducible over Q

Returns

absBiFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

[in]	F	s.a.
[in]	full	true if all factors should be returned

Definition at line 212 of file facAbsBiFact.cc.

{
  CanonicalForm F= bCommonDen (G)*G;
  bool isRat= isOn (SW_RATIONAL);
  Off (SW_RATIONAL);
  F /= icontent (F);
  On (SW_RATIONAL);
 
  mpz_t * M=new mpz_t [4];
  mpz_init (M[0]);
  mpz_init (M[1]);
  mpz_init (M[2]);
  mpz_init (M[3]);
 
  mpz_t * S=new mpz_t [2];
  mpz_init (S[0]);
  mpz_init (S[1]);
 
  F= compress (F, M, S);
 
  if (F.isUnivariate())
  {
    if (degree (F) == 1)
    {
      mpz_clear (M[0]);
      mpz_clear (M[1]);
      mpz_clear (M[2]);
      mpz_clear (M[3]);
      delete [] M;
 
      mpz_clear (S[0]);
      mpz_clear (S[1]);
      delete [] S;
      if (!isRat)
        Off (SW_RATIONAL);
      return CFAFList (CFAFactor (G, 1, 1));
    }
    CFAFList result= uniAbsFactorize (F, full);
    if (result.getFirst().factor().inCoeffDomain())
      result.removeFirst();
    for (CFAFListIterator iter=result; iter.hasItem(); iter++)
      iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
                                 iter.getItem().minpoly(),iter.getItem().exp());
    mpz_clear (M[0]);
    mpz_clear (M[1]);
    mpz_clear (M[2]);
    mpz_clear (M[3]);
    delete [] M;
 
    mpz_clear (S[0]);
    mpz_clear (S[1]);
    delete [] S;
    if (!isRat)
      Off (SW_RATIONAL);
    return result;
  }
 
  if (degree (F, 1) == 1 || degree (F, 2) == 1)
  {
    mpz_clear (M[0]);
    mpz_clear (M[1]);
    mpz_clear (M[2]);
    mpz_clear (M[3]);
    delete [] M;
 
    mpz_clear (S[0]);
    mpz_clear (S[1]);
    delete [] S;
    if (!isRat)
      Off (SW_RATIONAL);
    return CFAFList (CFAFactor (G, 1, 1));
  }
  int minTdeg, tdegF= totaldegree (F);
  CanonicalForm Fp, smallestFactor;
  int p;
  CFFList factors;
  Variable alpha;
  bool rec= false;
  Variable x= Variable (1);
  Variable y= Variable (2);
  CanonicalForm bufF= F;
  CFFListIterator iter;
  CFArray eval= CFArray (2);
  int absValue= 1;
differentevalpoint:
  while (1)
  {
    TIMING_START (fac_evalpoint);
    p= choosePoint (F, tdegF, eval, rec, absValue);
    TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
 
    //after here isOn (SW_RATIONAL)==false
    setCharacteristic (p);
    Fp=F.mapinto();
    factors= factorize (Fp);
 
    if (factors.getFirst().factor().inCoeffDomain())
      factors.removeFirst();
 
    if (factors.length() == 1 && factors.getFirst().exp() == 1)
    {
      if (absIrredTest (Fp))
      {
        if (isRat)
          On (SW_RATIONAL);
        setCharacteristic(0);
        mpz_clear (M[0]);
        mpz_clear (M[1]);
        mpz_clear (M[2]);
        mpz_clear (M[3]);
        delete [] M;
 
        mpz_clear (S[0]);
        mpz_clear (S[1]);
        delete [] S;
        return CFAFList (CFAFactor (G, 1, 1));
      }
      else
      {
        setCharacteristic (0);
        if (modularIrredTestWithShift (F))
        {
          if (isRat)
            On (SW_RATIONAL);
          mpz_clear (M[0]);
          mpz_clear (M[1]);
          mpz_clear (M[2]);
          mpz_clear (M[3]);
          delete [] M;
 
          mpz_clear (S[0]);
          mpz_clear (S[1]);
          delete [] S;
          return CFAFList (CFAFactor (G, 1, 1));
        }
        rec= true;
        continue;
      }
    }
    iter= factors;
    smallestFactor= iter.getItem().factor();
    while (smallestFactor.isUnivariate() && iter.hasItem())
    {
      iter++;
      if (!iter.hasItem())
        break;
      smallestFactor= iter.getItem().factor();
    }
 
    minTdeg= totaldegree (smallestFactor);
    if (iter.hasItem())
      iter++;
    for (; iter.hasItem(); iter++)
    {
      if (!iter.getItem().factor().isUnivariate() &&
          (totaldegree (iter.getItem().factor()) < minTdeg))
      {
        smallestFactor= iter.getItem().factor();
        minTdeg= totaldegree (smallestFactor);
      }
    }
    if (tdegF % minTdeg == 0)
      break;
    setCharacteristic(0);
    rec=true;
  }
  CanonicalForm Gp= Fp/smallestFactor;
  Gp= Gp /Lc (Gp);
 
  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
 
  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
               !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
               !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
  if (!xValid || !yValid)
  {
    rec= true;
    setCharacteristic (0);
    goto differentevalpoint;
  }
 
  setCharacteristic (0);
 
  CanonicalForm mipo;
 
  CFArray mipos= CFArray (2);
  CFFList mipoFactors;
  for (int i= 1; i < 3; i++)
  {
    CanonicalForm Fi= F(eval[i-1],i);
 
    int s= tdegF/minTdeg + 1;
    CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
    bound *= power (CanonicalForm (s),s-1);
    bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
 
    CanonicalForm B = p;
    long k = 1L;
    while ( B < bound ) {
      B *= p;
      k++;
    }
 
    //TODO take floor (log2(k))
    k= k+1;
#ifdef HAVE_FLINT
    fmpz_poly_t FLINTFi;
    convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
    setCharacteristic (p);
    nmod_poly_t FLINTFpi, FLINTGpi;
    if (i == 2)
    {
      convertFacCF2nmod_poly_t (FLINTFpi,
                                smallestFactorEvalx/lc (smallestFactorEvalx));
      convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
    }
    else
    {
      convertFacCF2nmod_poly_t (FLINTFpi,
                                smallestFactorEvaly/lc (smallestFactorEvaly));
      convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
    }
    nmod_poly_factor_t nmodFactors;
    nmod_poly_factor_init (nmodFactors);
    nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
    nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
 
    // the following fix is due to interface changes from  FLINT 2.3 -> FLINT 2.4
#   ifndef slong
#          define slong long
#   endif
 
    slong * link= new slong [2];
    fmpz_poly_t *v= new fmpz_poly_t[2];
    fmpz_poly_t *w= new fmpz_poly_t[2];
    fmpz_poly_init(v[0]);
    fmpz_poly_init(v[1]);
    fmpz_poly_init(w[0]);
    fmpz_poly_init(w[1]);
 
    fmpz_poly_factor_t liftedFactors;
    fmpz_poly_factor_init (liftedFactors);
    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
                                  nmodFactors, k);
 
    nmod_poly_factor_clear (nmodFactors);
    nmod_poly_clear (FLINTFpi);
    nmod_poly_clear (FLINTGpi);
 
    setCharacteristic(0);
    CanonicalForm liftedSmallestFactor=
    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
 
    CanonicalForm otherFactor=
    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
    modpk pk= modpk (p, k);
#elif defined(HAVE_NTL)
    modpk pk= modpk (p, k);
    ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
    setCharacteristic (p);
 
    if (fac_NTL_char != p)
    {
      fac_NTL_char= p;
      zz_p::init (p);
    }
    zz_pX NTLFpi, NTLGpi;
    if (i == 2)
    {
      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
      NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
    }
    else
    {
      NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
      NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
    }
    vec_zz_pX modFactors;
    modFactors.SetLength(2);
    modFactors[0]= NTLFpi;
    modFactors[1]= NTLGpi;
    vec_ZZX liftedFactors;
    MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
    setCharacteristic(0);
    CanonicalForm liftedSmallestFactor=
                  convertNTLZZX2CF (liftedFactors[0], x);
 
    CanonicalForm otherFactor=
                  convertNTLZZX2CF (liftedFactors[1], x);
#else
   factoryError("absBiFactorizeMain: NTL/FLINT missing");
#endif
 
    Off (SW_SYMMETRIC_FF);
    liftedSmallestFactor= pk (liftedSmallestFactor);
    if (i == 2)
      liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
    else
      liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
 
    On (SW_SYMMETRIC_FF);
    CFMatrix *M= new CFMatrix (s, s);
    (*M)(s,s)= power (CanonicalForm (p), k);
    for (int j= 1; j < s; j++)
    {
      (*M) (j,j)= 1;
      (*M) (j+1,j)= -liftedSmallestFactor;
    }
 
    #ifdef HAVE_FLINT
    fmpz_mat_t FLINTM;
    convertFacCFMatrix2Fmpz_mat_t(FLINTM,*M);
    fmpq_t delta,eta;
    fmpq_init(delta); fmpq_set_si(delta,1,1);
    fmpq_init(eta); fmpq_set_si(eta,3,4);
    fmpz_mat_transpose(FLINTM,FLINTM);
    fmpz_mat_lll_storjohann(FLINTM,delta,eta);
    fmpz_mat_transpose(FLINTM,FLINTM);
    delete M;
    M=convertFmpz_mat_t2FacCFMatrix(FLINTM);
    fmpz_mat_clear(FLINTM);
    #elif defined(HAVE_NTL)
    mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
 
    ZZ det;
 
    transpose (*NTLM, *NTLM);
    (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
    transpose (*NTLM, *NTLM);
    delete M;
    M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
    delete NTLM;
    #else
    factoryError("NTL/FLINT missing: absBiFactorizeMain");
    #endif
 
    mipo= 0;
    for (int j= 1; j <= s; j++)
      mipo += (*M) (j,1)*power (x,s-j);
 
    delete M;
    mipoFactors= factorize (mipo);
    if (mipoFactors.getFirst().factor().inCoeffDomain())
      mipoFactors.removeFirst();
 
#ifdef HAVE_FLINT
    fmpz_poly_clear (v[0]);
    fmpz_poly_clear (v[1]);
    fmpz_poly_clear (w[0]);
    fmpz_poly_clear (w[1]);
    delete [] v;
    delete [] w;
    delete [] link;
    fmpz_poly_factor_clear (liftedFactors);
#endif
 
    if (mipoFactors.length() > 1 ||
        (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
         mipo.inCoeffDomain())
    {
        rec=true;
        goto differentevalpoint;
    }
    else
      mipos[i-1]= mipo;
  }
 
  if (degree (mipos[0]) != degree (mipos[1]))
  {
    rec=true;
    goto differentevalpoint;
  }
 
  On (SW_RATIONAL);
  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
    alpha= rootOf (mipos[0]);
  else
    alpha= rootOf (mipos[1]);
 
  int wrongMipo= 0;
 
  Variable beta;
  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
  {
    mipoFactors= factorize (mipos[1], alpha);
    if (mipoFactors.getFirst().factor().inCoeffDomain())
      mipoFactors.removeFirst();
    for (iter= mipoFactors; iter.hasItem(); iter++)
    {
      if (degree (iter.getItem().factor()) > 1)
        wrongMipo++;
    }
    if (wrongMipo == mipoFactors.length())
    {
      rec=true;
      goto differentevalpoint;
    }
    wrongMipo= 0;
    beta= rootOf (mipos[1]);
    mipoFactors= factorize (mipos[0], beta);
    if (mipoFactors.getFirst().factor().inCoeffDomain())
      mipoFactors.removeFirst();
    for (iter= mipoFactors; iter.hasItem(); iter++)
    {
      if (degree (iter.getItem().factor()) > 1)
        wrongMipo++;
    }
    if (wrongMipo == mipoFactors.length())
    {
      rec=true;
      goto differentevalpoint;
    }
  }
  else
  {
    mipoFactors= factorize (mipos[0], alpha);
    if (mipoFactors.getFirst().factor().inCoeffDomain())
      mipoFactors.removeFirst();
    for (iter= mipoFactors; iter.hasItem(); iter++)
    {
      if (degree (iter.getItem().factor()) > 1)
        wrongMipo++;
    }
    if (wrongMipo == mipoFactors.length())
    {
      rec=true;
      goto differentevalpoint;
    }
    wrongMipo= 0;
    beta= rootOf (mipos[0]);
    mipoFactors= factorize (mipos[1], beta);
    if (mipoFactors.getFirst().factor().inCoeffDomain())
      mipoFactors.removeFirst();
    for (iter= mipoFactors; iter.hasItem(); iter++)
    {
      if (degree (iter.getItem().factor()) > 1)
        wrongMipo++;
    }
    if (wrongMipo == mipoFactors.length())
    {
      rec=true;
      goto differentevalpoint;
    }
  }
 
 
  CanonicalForm F1;
  if (degree (F,1) > minTdeg)
    F1= F (eval[1], 2);
  else
    F1= F (eval[0], 1);
 
  CFFList QaF1Factors;
  bool swap= false;
  if (F1.level() == 2)
  {
    swap= true;
    F1=swapvar (F1, x, y);
    F= swapvar (F, x, y);
  }
 
  wrongMipo= 0;
  QaF1Factors= factorize (F1, alpha);
  if (QaF1Factors.getFirst().factor().inCoeffDomain())
    QaF1Factors.removeFirst();
  for (iter= QaF1Factors; iter.hasItem(); iter++)
  {
    if (degree (iter.getItem().factor()) > minTdeg)
      wrongMipo++;
  }
 
  if (wrongMipo == QaF1Factors.length())
  {
    rec= true;
    F= bufF;
    goto differentevalpoint;
  }
 
  CanonicalForm evaluation;
  if (swap)
    evaluation= eval[0];
  else
    evaluation= eval[1];
 
  F *= bCommonDen (F);
  F= F (y + evaluation, y);
 
  int liftBound= degree (F,y) + 1;
 
  modpk b= modpk();
 
  CanonicalForm den= 1;
 
  mipo= getMipo (alpha);
 
  CFList uniFactors;
  for (iter=QaF1Factors; iter.hasItem(); iter++)
    uniFactors.append (iter.getItem().factor());
 
  F /= Lc (F1);
  #ifdef HAVE_FLINT
  // init
  fmpz_t FLINTf,FLINTD;
  fmpz_init(FLINTf);
  fmpz_init(FLINTD);
  fmpz_poly_t FLINTmipo;
  fmpz_poly_t FLINTLcf;
  //conversion
  convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
  convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (F*bCommonDen (F)));
  // resultant, discriminant
  fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
  fmpz_poly_discriminant(FLINTD,FLINTmipo);
  fmpz_mul(FLINTf,FLINTD,FLINTf);
  den= abs (convertFmpz2CF(FLINTf));
  // clean up
  fmpz_clear(FLINTf);
   // FLINTD is used below
  fmpz_poly_clear(FLINTLcf);
  fmpz_poly_clear(FLINTmipo);
  #elif defined(HAVE_NTL)
  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
  ZZ NTLf= resultant (NTLmipo, NTLLcf);
  ZZ NTLD= discriminant (NTLmipo);
  den= abs (convertZZ2CF (NTLD*NTLf));
  #else
  factoryError("NTL/FLINT missing: absBiFactorizeMain");
  #endif
 
  // make factors elements of Z(a)[x] disable for modularDiophant
  CanonicalForm multiplier= 1;
  for (CFListIterator i= uniFactors; i.hasItem(); i++)
  {
    multiplier *= bCommonDen (i.getItem());
    i.getItem()= i.getItem()*bCommonDen(i.getItem());
  }
  F *= multiplier;
  F *= bCommonDen (F);
 
  Off (SW_RATIONAL);
  int ii= 0;
  #ifdef HAVE_FLINT
  CanonicalForm discMipo= convertFmpz2CF(FLINTD);
  fmpz_clear(FLINTD);
  #elif defined(HAVE_NTL)
  CanonicalForm discMipo= convertZZ2CF (NTLD);
  #endif
  findGoodPrime (bufF*discMipo,ii);
  findGoodPrime (F1*discMipo,ii);
  findGoodPrime (F*discMipo,ii);
 
  int pp=cf_getBigPrime(ii);
  b = coeffBound( F, pp, mipo );
  modpk bb= coeffBound (F1, pp, mipo);
  if (bb.getk() > b.getk() ) b=bb;
    bb= coeffBound (F, pp, mipo);
  if (bb.getk() > b.getk() ) b=bb;
 
  ExtensionInfo dummy= ExtensionInfo (alpha, false);
  DegreePattern degs= DegreePattern (uniFactors);
 
  bool earlySuccess= false;
  CFList earlyFactors;
  uniFactors= henselLiftAndEarly
              (F, earlySuccess, earlyFactors, degs, liftBound,
               uniFactors, dummy, evaluation, b, den);
 
  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
  CanonicalForm MODl= power (y, liftBound);
 
  On (SW_RATIONAL);
  F *= bCommonDen (F);
  Off (SW_RATIONAL);
 
  CFList biFactors;
 
  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
                                  uniFactors.length()/2, b, den);
 
  On (SW_RATIONAL);
 
  if (earlySuccess)
    biFactors= Union (earlyFactors, biFactors);
  else if (!earlySuccess && degs.getLength() == 1)
    biFactors= earlyFactors;
 
  bool swap2= false;
  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
  if (isOn (SW_RATIONAL))
    normalize (biFactors);
 
  CFAFList result;
  bool found= false;
 
  for (CFListIterator i= biFactors; i.hasItem(); i++)
  {
    if (full)
      result.append (CFAFactor (decompress (i.getItem(), M, S),
                                getMipo (alpha), 1));
 
    if (totaldegree (i.getItem()) == minTdeg)
    {
      if (!full)
        result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
                                     getMipo (alpha), 1));
      found= true;
 
      if (!full)
        break;
    }
  }
 
  if (!found)
  {
    rec= true;
    F= bufF;
    goto differentevalpoint;
  }
 
  if (isRat)
    On (SW_RATIONAL);
  else
    Off (SW_RATIONAL);
 
  mpz_clear (M[0]);
  mpz_clear (M[1]);
  mpz_clear (M[2]);
  mpz_clear (M[3]);
  delete [] M;
 
  mpz_clear (S[0]);
  mpz_clear (S[1]);
  delete [] S;
 
  return result;
}

normalize()

void normalize ( CFAFList & L )

inlinestatic

normalize factors, i.e. make factors monic

Definition at line 37 of file facAbsBiFact.h.

{
  for (CFAFListIterator i= L; i.hasItem(); i++)
    i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
                            i.getItem().minpoly(), i.getItem().exp());
}

uniAbsFactorize()

CFAFList uniAbsFactorize	(	const CanonicalForm &	F,
		bool	full = false )

univariate absolute factorization over Q

Returns

uniAbsFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

[in]	F	univariate poly irreducible over Q
[in]	full	true if all factors should be returned