facFqBivar.h File Reference

This file provides functions for factorizing a bivariate polynomial over , or GF. More...

#include "timing.h"
#include "cf_assert.h"
#include "facFqBivarUtil.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "cfNewtonPolygon.h"
#include "fac_util.h"
#include "cf_algorithm.h"

Go to the source code of this file.

Functions
	TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
CFList	biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
	Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field. More...
CFList	biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info)
CFList	FpBiSqrfFactorize (const CanonicalForm &G)
	factorize a squarefree bivariate polynomial over . More...
CFList	FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
	factorize a squarefree bivariate polynomial over . More...
CFList	GFBiSqrfFactorize (const CanonicalForm &G)
	factorize a squarefree bivariate polynomial over GF More...
CFFList	FpBiFactorize (const CanonicalForm &G, bool substCheck=true)
	factorize a bivariate polynomial over More...
CFFList	FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
	factorize a bivariate polynomial over More...
CFFList	GFBiFactorize (const CanonicalForm &G, bool substCheck=true)
	factorize a bivariate polynomial over GF More...
CanonicalForm	prodMod0 (const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
	via divide-and-conquer More...
CanonicalForm	evalPoint (const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
	find an evaluation point p, s.t. F(p,y) is squarefree and . More...
CFList	uniFactorizer (const CanonicalForm &A, const Variable &alpha, const bool &GF)
	Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used. More...
CFList	extFactorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
	naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible. More...
CFList	factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
	naive factor recombination. Uses precomputed data to exclude combinations that are not possible. More...
Variable	chooseExtension (const Variable &alpha, const Variable &beta, int k)
	chooses a field extension. More...
int *	getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
	compute lifting precisions from the shape of the Newton polygon of F More...
void	earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=modpk())
	detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
void	extEarlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
	detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
CFList	henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
	hensel Lifting and early factor detection More...
CFList	henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval)
	hensel Lifting and early factor detection More...
CFList	extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
	Factorization over an extension of initial field. More...

Detailed Description

This file provides functions for factorizing a bivariate polynomial over , or GF.

Author

Martin Lee

Definition in file facFqBivar.h.

Function Documentation

biFactorize()

CFList biFactorize	(	const CanonicalForm &	F,
		const ExtensionInfo &	info
	)

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Returns

biFactorize returns a list of factors of F. If F is not monic its leading coefficient is not outputted.

See also

extBifactorize()

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Parameters

[in]	F	a sqrfree bivariate poly
[in]	info	information about extension

Definition at line 8303 of file facFqBivar.cc.

{
  if (F.inCoeffDomain())
    return CFList(F);
 
  CanonicalForm A= F;
  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
 
  Variable alpha= info.getAlpha();
  Variable beta= info.getBeta();
  CanonicalForm gamma= info.getGamma();
  CanonicalForm delta= info.getDelta();
  int k= info.getGFDegree();
  bool extension= info.isInExtension();
  if (A.isUnivariate())
  {
    if (extension == false)
      return uniFactorizer (F, alpha, GF);
    else
    {
      CFList source, dest;
      A= mapDown (A, info, source, dest);
      return uniFactorizer (A, beta, GF);
    }
  }
 
  CFMap N;
  A= compress (A, N);
  Variable y= A.mvar();
 
  if (y.level() > 2) return CFList (F);
  Variable x= Variable (1);
 
  //remove and factorize content
  CanonicalForm contentAx= content (A, x);
  CanonicalForm contentAy= content (A);
 
  A= A/(contentAx*contentAy);
  CFList contentAxFactors, contentAyFactors;
 
  if (!extension)
  {
    contentAxFactors= uniFactorizer (contentAx, alpha, GF);
    contentAyFactors= uniFactorizer (contentAy, alpha, GF);
  }
 
  //trivial case
  CFList factors;
  if (A.inCoeffDomain())
  {
    append (factors, contentAxFactors);
    append (factors, contentAyFactors);
    decompress (factors, N);
    return factors;
  }
  else if (A.isUnivariate())
  {
    factors= uniFactorizer (A, alpha, GF);
    append (factors, contentAxFactors);
    append (factors, contentAyFactors);
    decompress (factors, N);
    return factors;
  }
 
 
  //check trivial case
  if (degree (A) == 1 || degree (A, 1) == 1 ||
      (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
  {
    factors.append (A);
 
    appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                          false, false, N);
 
    if (!extension)
      normalize (factors);
    return factors;
  }
 
  // check derivatives
  bool derivXZero= false;
  CanonicalForm derivX= deriv (A, x);
  CanonicalForm gcdDerivX;
  if (derivX.isZero())
    derivXZero= true;
  else
  {
    gcdDerivX= gcd (A, derivX);
    if (degree (gcdDerivX) > 0)
    {
      CanonicalForm g= A/gcdDerivX;
      CFList factorsG=
      Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
      append (factorsG, contentAxFactors);
      append (factorsG, contentAyFactors);
      decompress (factorsG, N);
      if (!extension)
        normalize (factorsG);
      return factorsG;
    }
  }
  bool derivYZero= false;
  CanonicalForm derivY= deriv (A, y);
  CanonicalForm gcdDerivY;
  if (derivY.isZero())
    derivYZero= true;
  else
  {
    gcdDerivY= gcd (A, derivY);
    if (degree (gcdDerivY) > 0)
    {
      CanonicalForm g= A/gcdDerivY;
      CFList factorsG=
      Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
      append (factorsG, contentAxFactors);
      append (factorsG, contentAyFactors);
      decompress (factorsG, N);
      if (!extension)
        normalize (factorsG);
      return factorsG;
    }
  }
  //main variable is chosen s.t. the degree in x is minimal
  bool swap= false;
  if ((degree (A) > degree (A, x)) || derivXZero)
  {
    if (!derivYZero)
    {
      A= swapvar (A, y, x);
      swap= derivXZero;
      derivXZero= derivYZero;
      derivYZero= swap;
      swap= true;
    }
  }
 
  int boundsLength;
  bool isIrreducible= false;
  int * bounds= computeBounds (A, boundsLength, isIrreducible);
  if (isIrreducible)
  {
    delete [] bounds;
    factors.append (A);
 
    appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                          swap, false, N);
 
    if (!extension)
      normalize (factors);
    return factors;
  }
 
  int minBound= bounds[0];
  for (int i= 1; i < boundsLength; i++)
  {
    if (bounds[i] != 0)
      minBound= tmin (minBound, bounds[i]);
  }
 
  int boundsLength2;
  int * bounds2= computeBoundsWrtDiffMainvar (A, boundsLength2, isIrreducible);
  int minBound2= bounds2[0];
  for (int i= 1; i < boundsLength2; i++)
  {
    if (bounds2[i] != 0)
      minBound2= tmin (minBound2, bounds2[i]);
  }
 
 
  bool fail= false;
  CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
  CFList uniFactors, list, bufUniFactors;
  DegreePattern degs;
  DegreePattern bufDegs;
 
  bool fail2= false;
  CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
  CFList bufUniFactors2, list2, uniFactors2;
  DegreePattern degs2;
  DegreePattern bufDegs2;
  bool swap2= false;
 
  // several univariate factorizations to obtain more information about the
  // degree pattern therefore usually less combinations have to be tried during
  // the recombination process
  int factorNums= 3;
  int subCheck1= substituteCheck (A, x);
  int subCheck2= substituteCheck (A, y);
  bool symmetric= false;
 
  TIMING_START (fac_fq_uni_total);
  for (int i= 0; i < factorNums; i++)
  {
    bufAeval= A;
    TIMING_START (fac_fq_bi_evaluation);
    bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
    TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
    if (!derivXZero && !fail2 && !symmetric)
    {
      if (i == 0)
      {
        buf= swapvar (A, x, y);
        symmetric= (A/Lc (A) == buf/Lc (buf));
      }
      bufAeval2= buf;
      TIMING_START (fac_fq_bi_evaluation);
      bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
      TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
                            "time to find eval point wrt y: ");
    }
    // first try to change main variable if there is no valid evaluation point
    if (fail && (i == 0))
    {
      if (!derivXZero && !fail2 && !symmetric)
      {
        bufEvaluation= bufEvaluation2;
        int dummy= subCheck2;
        subCheck2= subCheck1;
        subCheck1= dummy;
        tmp= A;
        A= buf;
        buf= tmp;
        bufAeval= bufAeval2;
        swap2= true;
        fail= false;
      }
      else
        fail= true;
    }
 
    // if there is no valid evaluation point pass to a field extension
    if (fail && (i == 0))
    {
      factors= extBiFactorize (A, info);
      appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                            swap, swap2, N);
      normalize (factors);
      delete [] bounds;
      delete [] bounds2;
      return factors;
    }
 
    // there is at least one valid evaluation point
    // but we do not compute more univariate factorization over an extension
    if (fail && (i != 0))
      break;
 
    // univariate factorization
    TIMING_START (fac_fq_uni_factorizer);
    bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
    TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
                          "time for univariate factorization over Fq: ");
    DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
              (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
 
    if (!derivXZero && !fail2 && !symmetric)
    {
      TIMING_START (fac_fq_uni_factorizer);
      bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
      TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
                            "time for univariate factorization in y over Fq: ");
      DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
                (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
    }
 
    if (bufUniFactors.length() == 1 ||
        (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
    {
      if (extension)
      {
        CFList source, dest;
        appendMapDown (factors, A, info, source, dest);
      }
      else
        factors.append (A);
 
      appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                            swap, swap2, N);
 
      if (!extension)
        normalize (factors);
      delete [] bounds;
      delete [] bounds2;
      return factors;
    }
 
    if (i == 0 && !extension)
    {
      if (subCheck1 > 0)
      {
        int subCheck= substituteCheck (bufUniFactors);
 
        if (subCheck > 1 && (subCheck1%subCheck == 0))
        {
          CanonicalForm bufA= A;
          subst (bufA, bufA, subCheck, x);
          factors= biFactorize (bufA, info);
          reverseSubst (factors, subCheck, x);
          appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                                swap, swap2, N);
          if (!extension)
            normalize (factors);
          delete [] bounds;
          delete [] bounds2;
          return factors;
        }
      }
 
      if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
      {
        int subCheck= substituteCheck (bufUniFactors2);
 
        if (subCheck > 1 && (subCheck2%subCheck == 0))
        {
          CanonicalForm bufA= A;
          subst (bufA, bufA, subCheck, y);
          factors= biFactorize (bufA, info);
          reverseSubst (factors, subCheck, y);
          appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                                swap, swap2, N);
          if (!extension)
            normalize (factors);
          delete [] bounds;
          delete [] bounds2;
          return factors;
        }
      }
    }
 
    // degree analysis
    bufDegs = DegreePattern (bufUniFactors);
    if (!derivXZero && !fail2 && !symmetric)
      bufDegs2= DegreePattern (bufUniFactors2);
 
    if (i == 0)
    {
      Aeval= bufAeval;
      evaluation= bufEvaluation;
      uniFactors= bufUniFactors;
      degs= bufDegs;
      if (!derivXZero && !fail2 && !symmetric)
      {
        Aeval2= bufAeval2;
        evaluation2= bufEvaluation2;
        uniFactors2= bufUniFactors2;
        degs2= bufDegs2;
      }
    }
    else
    {
      degs.intersect (bufDegs);
      if (!derivXZero && !fail2 && !symmetric)
      {
        degs2.intersect (bufDegs2);
        if (bufUniFactors2.length() < uniFactors2.length())
        {
          uniFactors2= bufUniFactors2;
          Aeval2= bufAeval2;
          evaluation2= bufEvaluation2;
        }
      }
      if (bufUniFactors.length() < uniFactors.length())
      {
        uniFactors= bufUniFactors;
        Aeval= bufAeval;
        evaluation= bufEvaluation;
      }
    }
    list.append (bufEvaluation);
    if (!derivXZero && !fail2 && !symmetric)
      list2.append (bufEvaluation2);
  }
  TIMING_END_AND_PRINT (fac_fq_uni_total,
                        "total time for univariate factorizations: ");
 
  if (!derivXZero && !fail2 && !symmetric)
  {
    if ((uniFactors.length() > uniFactors2.length() && minBound2 <= minBound)||
        (uniFactors.length() == uniFactors2.length()
         && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
    {
      degs= degs2;
      uniFactors= uniFactors2;
      evaluation= evaluation2;
      Aeval= Aeval2;
      A= buf;
      swap2= true;
    }
  }
 
  if (degs.getLength() == 1) // A is irreducible
  {
    if (extension)
    {
      CFList source, dest;
      appendMapDown (factors, A, info, source, dest);
    }
    else
      factors.append (A);
    appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                            swap, swap2, N);
    if (!extension)
      normalize (factors);
    delete [] bounds;
    delete [] bounds2;
    return factors;
  }
 
  int liftBound= degree (A, y) + 1;
 
  if (swap2)
  {
    delete [] bounds;
    bounds= bounds2;
    minBound= minBound2;
  }
 
  TIMING_START (fac_fq_bi_shift_to_zero);
  A= A (y + evaluation, y);
  TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
                        "time to shift eval to zero: ");
 
  int degMipo= 1;
  if (extension && alpha.level() != 1 && k==1)
    degMipo= degree (getMipo (alpha));
 
  DEBOUTLN (cerr, "uniFactors= " << uniFactors);
 
  if ((GF && !extension) || (GF && extension && k != 1))
  {
    bool earlySuccess= false;
    CFList earlyFactors;
    TIMING_START (fac_fq_bi_hensel_lift);
    uniFactors= henselLiftAndEarly
               (A, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, info, evaluation);
    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
                          "time for bivariate hensel lifting over Fq: ");
    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
    CanonicalForm MODl= power (y, liftBound);
 
    TIMING_START (fac_fq_bi_factor_recombination);
    if (extension)
      factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
                                       evaluation, 1, uniFactors.length()/2);
    else
      factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
                                    uniFactors.length()/2);
    TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
                          "time for naive bivariate factor recombi over Fq: ");
 
    if (earlySuccess)
      factors= Union (earlyFactors, factors);
    else if (!earlySuccess && degs.getLength() == 1)
      factors= earlyFactors;
  }
  else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
  {
    TIMING_START (fac_fq_bi_hensel_lift);
    if (extension)
    {
      CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
                                                  evaluation
                                                 );
      factors= Union (lll, factors);
    }
    else if (alpha.level() == 1 && !GF)
    {
      CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
                                               symmetric, evaluation);
      factors= Union (lll, factors);
    }
    else if (!extension && (alpha != x || GF))
    {
      CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
                                               symmetric, evaluation);
      factors= Union (lll, factors);
    }
    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
                          "time to bivar lift and LLL recombi over Fq: ");
    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
  }
  else
  {
    bool earlySuccess= false;
    CFList earlyFactors;
    TIMING_START (fac_fq_bi_hensel_lift);
    uniFactors= henselLiftAndEarly
               (A, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, info, evaluation);
    TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
                          "time for bivar hensel lifting over Fq: ");
    DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
    CanonicalForm MODl= power (y, liftBound);
    if (!extension)
    {
      TIMING_START (fac_fq_bi_factor_recombination);
      factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1, 3);
      TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
                            "time for small subset naive recombi over Fq: ");
 
      int oldUniFactorsLength= uniFactors.length();
      if (degree (A) > 0)
      {
        CFList tmp;
        TIMING_START (fac_fq_bi_hensel_lift);
        if (alpha.level() == 1)
          tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
                                  liftBound, evaluation
                                 );
        else
        {
          if (degree (A) > getCharacteristic())
            tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
                                         1, alpha, liftBound, evaluation
                                        );
          else
            tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
                                    alpha, liftBound, evaluation
                                   );
        }
        TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
                              "time to increase precision: ");
        factors= Union (factors, tmp);
        if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
                                  && uniFactors.length() != oldUniFactorsLength)
           )
        {
          DegreePattern bufDegs= DegreePattern (uniFactors);
          degs.intersect (bufDegs);
          degs.refine ();
          factors= Union (factors, factorRecombination (uniFactors, A, MODl,
                                                        degs, evaluation, 4,
                                                        uniFactors.length()/2
                                                       )
                         );
        }
      }
    }
    else
    {
      if (beta.level() != 1 || k > 1)
      {
        if (k > 1)
        {
          factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
                                           evaluation, 1, uniFactors.length()/2
                                          );
        }
        else
        {
          factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
                                           evaluation, 1, 3
                                          );
          if (degree (A) > 0)
          {
            CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
            DegreePattern bufDegs= DegreePattern (tmp);
            degs.intersect (bufDegs);
            degs.refine ();
            factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
                                                             degs, evaluation,
                                                             1, tmp.length()/2
                                                            )
                           );
          }
        }
      }
      else
      {
        factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
                                         evaluation, 1, 3
                                        );
        int oldUniFactorsLength= uniFactors.length();
        if (degree (A) > 0)
        {
          int degMipo;
          ExtensionInfo info2= init4ext (info, evaluation, degMipo);
 
          CFList source, dest;
          CFList tmp= extIncreasePrecision (A, uniFactors, 0,
                                            uniFactors.length(), 1, evaluation,
                                            info2, source, dest, liftBound
                                           );
          factors= Union (factors, tmp);
          if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
                                  && uniFactors.length() != oldUniFactorsLength)
             )
          {
            DegreePattern bufDegs= DegreePattern (uniFactors);
            degs.intersect (bufDegs);
            degs.refine ();
            factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
                                                        info, degs, evaluation,
                                                        4, uniFactors.length()/2
                                                            )
                           );
          }
        }
      }
    }
 
    if (earlySuccess)
      factors= Union (earlyFactors, factors);
    else if (!earlySuccess && degs.getLength() == 1)
      factors= earlyFactors;
  }
 
  if (!swap2)
    delete [] bounds2;
  delete [] bounds;
 
  appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
                        swap, swap2, N);
  if (!extension)
    normalize (factors);
 
  return factors;
}

biSqrfFactorizeHelper()

CFList biSqrfFactorizeHelper ( const CanonicalForm &  G, const ExtensionInfo &  info  )

inline

Definition at line 55 of file facFqBivar.h.

{
  CFMap N;
  CanonicalForm F= compress (G, N);
  CanonicalForm contentX= content (F, 1);
  CanonicalForm contentY= content (F, 2);
  F /= (contentX*contentY);
  CFFList contentXFactors, contentYFactors;
  if (info.getAlpha().level() != 1)
  {
    contentXFactors= factorize (contentX, info.getAlpha());
    contentYFactors= factorize (contentY, info.getAlpha());
  }
  else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
  {
    contentXFactors= factorize (contentX);
    contentYFactors= factorize (contentY);
  }
  else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
  {
    CFList bufContentX, bufContentY;
    bufContentX= biFactorize (contentX, info);
    bufContentY= biFactorize (contentY, info);
    for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
      contentXFactors.append (CFFactor (iter.getItem(), 1));
    for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
      contentYFactors.append (CFFactor (iter.getItem(), 1));
  }
 
  if (contentXFactors.getFirst().factor().inCoeffDomain())
    contentXFactors.removeFirst();
  if (contentYFactors.getFirst().factor().inCoeffDomain())
    contentYFactors.removeFirst();
  if (F.inCoeffDomain())
  {
    CFList result;
    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
      result.append (N (i.getItem().factor()));
    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
      result.append (N (i.getItem().factor()));
    normalize (result);
    result.insert (Lc (G));
    return result;
  }
  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);
  CFList result= biFactorize (F, info);
  for (CFListIterator i= result; i.hasItem(); i++)
    i.getItem()= N (decompress (i.getItem(), M, S));
  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
    result.append (N(i.getItem().factor()));
  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
    result.append (N (i.getItem().factor()));
  normalize (result);
  result.insert (Lc(G));
 
  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;
}

chooseExtension()

Variable chooseExtension	(	const Variable &	alpha,
		const Variable &	beta,
		int	k
	)

chooses a field extension.

Returns

chooseExtension returns an extension specified by beta of appropiate size

Parameters

[in]	alpha	some algebraic variable
[in]	beta	some algebraic variable
[in]	k	some int

Definition at line 806 of file facFqBivar.cc.

{
  int i=1, m= 2;
  // extension of F_p needed
  if (alpha.level() == 1 && beta.level() == 1 && k == 1)
  {
    i= 1;
    m= 2;
  } //extension of F_p(alpha) needed but want to factorize over F_p
  else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
  {
    i= 1;
    m= degree (getMipo (alpha)) + 1;
  } //extension of F_p(alpha) needed for first time
  else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
  {
    i= 2;
    m= degree (getMipo (alpha));
  }
  else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
  {
    m= degree (getMipo (beta));
    i= degree (getMipo (alpha))/m + 1;
  }
  #if defined(HAVE_FLINT)
  nmod_poly_t Irredpoly;
  nmod_poly_init(Irredpoly,getCharacteristic());
  nmod_poly_randtest_monic_irreducible(Irredpoly,FLINTrandom,i*m+1);
  CanonicalForm newMipo= convertnmod_poly_t2FacCF(Irredpoly,Variable (1));
  #elif defined(HAVE_NTL)
  if (fac_NTL_char != getCharacteristic())
  {
    fac_NTL_char= getCharacteristic();
    zz_p::init (getCharacteristic());
  }
  zz_pX NTLIrredpoly;
  BuildIrred (NTLIrredpoly, i*m);
  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
  #else
  factoryError("NTL/FLINT missing: chooseExtension");
  #endif
  return rootOf (newMipo);
}

earlyFactorDetection()

void earlyFactorDetection	(	CFList &	reconstructedFactors,
		CanonicalForm &	F,
		CFList &	factors,
		int &	adaptedLiftBound,
		int *&	factorsFoundIndex,
		DegreePattern &	degs,
		bool &	success,
		int	deg,
		const CanonicalForm &	eval,
		const modpk &	b = modpk()
	)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also

factorRecombination(), extEarlyFactorDetection()

Parameters

[in,out]	reconstructedFactors	list of reconstructed factors
[in,out]	F	poly to be factored, returns poly divided by detected factors in case of success
[in,out]	factors	list of factors lifted up to deg, returns a list of factors without detected factors
[in,out]	adaptedLiftBound	adapted lift bound
[in,out]	factorsFoundIndex	factors already considered
[in,out]	degs	degree pattern, is updated whenever we find a factor
[in,out]	success	indicating success
[in]	deg	stage of Hensel lifting
[in]	eval	evaluation point
[in]	b	coeff bound

Definition at line 971 of file facFqBivar.cc.

{
  CanonicalForm den= 1;
  earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
                        factorsFoundIndex, degs, success, deg, eval, b, den);
}

evalPoint()

CanonicalForm evalPoint	(	const CanonicalForm &	F,
		CanonicalForm &	eval,
		const Variable &	alpha,
		CFList &	list,
		const bool &	GF,
		bool &	fail
	)

find an evaluation point p, s.t. F(p,y) is squarefree and .

Returns

evalPoint returns an evaluation point, which is valid if and only if fail == false.

Parameters

[in]	F	compressed, bivariate poly
[in,out]	eval	F (p, y)
[in]	alpha	algebraic variable
[in]	list	list of points already considered
[in]	GF	GaloisFieldDomain?
[in,out]	fail	equals true, if there is no valid evaluation point

Definition at line 84 of file facFqBivar.cc.

{
  fail= false;
  Variable x= Variable(2);
  Variable y= Variable(1);
  FFRandom genFF;
  GFRandom genGF;
  CanonicalForm random, mipo;
  double bound;
  int p= getCharacteristic ();
  if (alpha.level() != 1)
  {
    mipo= getMipo (alpha);
    int d= degree (mipo);
    bound= pow ((double) p, (double) d);
  }
  else if (GF)
  {
    int d= getGFDegree();
    bound= ipower (p, d);
  }
  else
    bound= p;
 
  random= 0;
  do
  {
    if (list.length() >= bound)
    {
      fail= true;
      break;
    }
    if (list.isEmpty())
      random= 0;
    else if (GF)
    {
      if (list.length() == 1)
        random= getGFGenerator();
      else
        random= genGF.generate();
    }
    else if (list.length() < p || alpha.level() == 1)
      random= genFF.generate();
    else if (alpha != x && list.length() >= p)
    {
      if (list.length() == p)
        random= alpha;
      else
      {
        AlgExtRandomF genAlgExt (alpha);
        random= genAlgExt.generate();
      }
    }
    if (find (list, random)) continue;
    eval= F (random, x);
    if (degree (eval) != degree (F, y))
    { //leading coeff vanishes
      if (!find (list, random))
        list.append (random);
      continue;
    }
    if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
    { //evaluated polynomial is not squarefree
      if (!find (list, random))
        list.append (random);
      continue;
    }
  } while (find (list, random));
 
  return random;
}

extBiFactorize()

CFList extBiFactorize	(	const CanonicalForm &	F,
		const ExtensionInfo &	info
	)

Factorization over an extension of initial field.

Returns

extBiFactorize returns factorization of F over initial field

See also

biFactorize()

Parameters

[in]	F	poly to be factored
[in]	info	info about extension

Definition at line 8928 of file facFqBivar.cc.

{
 
  CanonicalForm A= F;
  Variable alpha= info.getAlpha();
  Variable beta= info.getBeta();
  int k= info.getGFDegree();
  char cGFName= info.getGFName();
  CanonicalForm delta= info.getDelta();
 
  bool GF= (CFFactory::gettype() == GaloisFieldDomain);
  Variable x= Variable (1);
  CFList factors;
  if (!GF && alpha == x)  // we are in F_p
  {
    bool extension= true;
    int p= getCharacteristic();
    if (p*p < (1<<16)) // pass to GF if possible
    {
      setCharacteristic (getCharacteristic(), 2, 'Z');
      A= A.mapinto();
      ExtensionInfo info2= ExtensionInfo (extension);
      factors= biFactorize (A, info2);
 
      CanonicalForm mipo= gf_mipo;
      setCharacteristic (getCharacteristic());
      Variable vBuf= rootOf (mipo.mapinto());
      for (CFListIterator j= factors; j.hasItem(); j++)
        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
      prune (vBuf);
    }
    else // not able to pass to GF, pass to F_p(\alpha)
    {
      CanonicalForm mipo= randomIrredpoly (2, x);
      Variable v= rootOf (mipo);
      ExtensionInfo info2= ExtensionInfo (v);
      factors= biFactorize (A, info2);
      prune (v);
    }
    return factors;
  }
  else if (!GF && (alpha != x)) // we are in F_p(\alpha)
  {
    if (k == 1) // need factorization over F_p
    {
      int extDeg= degree (getMipo (alpha));
      extDeg++;
      CanonicalForm mipo= randomIrredpoly (extDeg, x);
      Variable v= rootOf (mipo);
      ExtensionInfo info2= ExtensionInfo (v);
      factors= biFactorize (A, info2);
      prune (v);
    }
    else
    {
      if (beta == x)
      {
        Variable v= chooseExtension (alpha, beta, k);
        CanonicalForm primElem, imPrimElem;
        bool primFail= false;
        Variable vBuf;
        primElem= primitiveElement (alpha, vBuf, primFail);
        ASSERT (!primFail, "failure in integer factorizer");
        if (primFail)
          ; //ERROR
        else
          imPrimElem= mapPrimElem (primElem, alpha, v);
 
        CFList source, dest;
        CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
                                   source, dest);
        ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
        factors= biFactorize (bufA, info2);
        prune (v);
      }
      else
      {
        Variable v= chooseExtension (alpha, beta, k);
        CanonicalForm primElem, imPrimElem;
        bool primFail= false;
        Variable vBuf;
        ASSERT (!primFail, "failure in integer factorizer");
        if (primFail)
          ; //ERROR
        else
          imPrimElem= mapPrimElem (delta, beta, v);
 
        CFList source, dest;
        CanonicalForm bufA= mapDown (A, info, source, dest);
        source= CFList();
        dest= CFList();
        bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
        ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
        factors= biFactorize (bufA, info2);
        prune (v);
      }
    }
    return factors;
  }
  else // we are in GF (p^k)
  {
    int p= getCharacteristic();
    int extensionDeg= getGFDegree();
    bool extension= true;
    if (k == 1) // need factorization over F_p
    {
      extensionDeg++;
      if (ipower (p, extensionDeg) < (1<<16))
      // pass to GF(p^k+1)
      {
        CanonicalForm mipo= gf_mipo;
        setCharacteristic (p);
        Variable vBuf= rootOf (mipo.mapinto());
        A= GF2FalphaRep (A, vBuf);
        setCharacteristic (p, extensionDeg, 'Z');
        ExtensionInfo info2= ExtensionInfo (extension);
        factors= biFactorize (A.mapinto(), info2);
        prune (vBuf);
      }
      else // not able to pass to another GF, pass to F_p(\alpha)
      {
        CanonicalForm mipo= gf_mipo;
        setCharacteristic (p);
        Variable vBuf= rootOf (mipo.mapinto());
        A= GF2FalphaRep (A, vBuf);
        Variable v= chooseExtension (vBuf, beta, k);
        ExtensionInfo info2= ExtensionInfo (v, extension);
        factors= biFactorize (A, info2);
        prune (vBuf);
      }
    }
    else // need factorization over GF (p^k)
    {
      if (ipower (p, 2*extensionDeg) < (1<<16))
      // pass to GF (p^2k)
      {
        setCharacteristic (p, 2*extensionDeg, 'Z');
        ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
        factors= biFactorize (GFMapUp (A, extensionDeg), info2);
        setCharacteristic (p, extensionDeg, cGFName);
      }
      else // not able to pass to GF (p^2k), pass to F_p (\alpha)
      {
        CanonicalForm mipo= gf_mipo;
        setCharacteristic (p);
        Variable v1= rootOf (mipo.mapinto());
        A= GF2FalphaRep (A, v1);
        Variable v2= chooseExtension (v1, v1, k);
        CanonicalForm primElem, imPrimElem;
        bool primFail= false;
        Variable vBuf;
        primElem= primitiveElement (v1, vBuf, primFail);
        ASSERT (!primFail, "failure in integer factorizer");
        if (primFail)
          ; //ERROR
        else
          imPrimElem= mapPrimElem (primElem, v1, v2);
 
        CFList source, dest;
        CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
                                     source, dest);
        ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
        factors= biFactorize (bufA, info2);
        setCharacteristic (p, k, cGFName);
        for (CFListIterator i= factors; i.hasItem(); i++)
          i.getItem()= Falpha2GFRep (i.getItem());
        prune (v1);
      }
    }
    return factors;
  }
}

extEarlyFactorDetection()

void extEarlyFactorDetection	(	CFList &	reconstructedFactors,
		CanonicalForm &	F,
		CFList &	factors,
		int &	adaptedLiftBound,
		int *&	factorsFoundIndex,
		DegreePattern &	degs,
		bool &	success,
		const ExtensionInfo &	info,
		const CanonicalForm &	eval,
		int	deg
	)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also

factorRecombination(), earlyFactorDetection()

Parameters

[in,out]	reconstructedFactors	list of reconstructed factors
[in,out]	F	poly to be factored, returns poly divided by detected factors in case of success
[in,out]	factors	list of factors lifted up to deg, returns a list of factors without detected factors
[in,out]	adaptedLiftBound	adapted lift bound
[in,out]	factorsFoundIndex	factors already considered
[in,out]	degs	degree pattern, is updated whenever we find a factor
[in,out]	success	indicating success
[in]	info	information about extension
[in]	eval	evaluation point
[in]	deg	stage of Hensel lifting

Definition at line 982 of file facFqBivar.cc.

{
  Variable alpha= info.getAlpha();
  Variable beta= info.getBeta();
  CanonicalForm gamma= info.getGamma();
  CanonicalForm delta= info.getDelta();
  int k= info.getGFDegree();
  DegreePattern bufDegs1= degs, bufDegs2;
  CFList result;
  CFList T= factors;
  Variable y= F.mvar();
  Variable x= Variable (1);
  CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
  CanonicalForm M= power (y, deg);
  adaptedLiftBound= 0;
  bool trueFactor= false;
  int d= degree (F), l= 0;
  CFList source, dest;
  int degMipoBeta= 1;
  if (!k && beta.level() != 1)
    degMipoBeta= degree (getMipo (beta));
  CanonicalForm quot;
  for (CFListIterator i= factors; i.hasItem(); i++, l++)
  {
    if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
      continue;
    else
    {
      g= mulMod2 (i.getItem(), LCBuf, M);
      g /= content (g, x);
      if (fdivides (g, buf, quot))
      {
        buf2= g (y - eval, y);
        buf2 /= Lc (buf2);
 
        if (!k && beta == x)
        {
          if (degree (buf2, alpha) < degMipoBeta)
          {
            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
            factorsFoundIndex[l]= 1;
            buf= quot;
            d -= degree (g);
            LCBuf= LC (buf, x);
            trueFactor= true;
          }
        }
        else
        {
          if (!isInExtension (buf2, gamma, k, delta, source, dest))
          {
            appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
            factorsFoundIndex[l]= 1;
            buf= quot;
            d -= degree (g);
            LCBuf= LC (buf, x);
            trueFactor= true;
          }
        }
        if (trueFactor)
        {
          T= Difference (T, CFList (i.getItem()));
          F= buf;
 
          // compute new possible degree pattern
          bufDegs2= DegreePattern (T);
          bufDegs1.intersect (bufDegs2);
          bufDegs1.refine ();
          trueFactor= false;
          if (bufDegs1.getLength() <= 1)
          {
            if (!buf.inCoeffDomain())
            {
              buf= buf (y - eval, y);
              buf /= Lc (buf);
              appendMapDown (reconstructedFactors, buf, info, source, dest);
              F= 1;
            }
            break;
          }
        }
      }
    }
  }
  adaptedLiftBound= d + 1;
  if (adaptedLiftBound < deg)
  {
    degs= bufDegs1;
    success= true;
  }
  if (bufDegs1.getLength() <= 1)
    degs= bufDegs1;
}

extFactorRecombination()

CFList extFactorRecombination	(	CFList &	factors,
		CanonicalForm &	F,
		const CanonicalForm &	N,
		const ExtensionInfo &	info,
		DegreePattern &	degs,
		const CanonicalForm &	eval,
		int	s,
		int	thres
	)

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Returns

extFactorRecombination returns a list of factors over the initial field, whose shift to zero is reversed.

See also

factorRecombination(), extEarlyFactorDetection()

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Parameters

[in,out]	factors	list of lifted factors that are monic wrt Variable (1), original factors-factors found
[in,out]	F	poly to be factored, F/factors found
[in]	N	Variable (2)^liftBound
[in]	info	contains information about extension
[in]	eval	evaluation point
[in]	s	algorithm starts checking subsets of size s
[in]	thres	threshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2

Definition at line 370 of file facFqBivar.cc.

{
  if (factors.length() == 0)
  {
    F= 1;
    return CFList();
  }
  if (F.inCoeffDomain())
    return CFList();
 
  Variable alpha= info.getAlpha();
  Variable beta= info.getBeta();
  CanonicalForm gamma= info.getGamma();
  CanonicalForm delta= info.getDelta();
  int k= info.getGFDegree();
 
  CanonicalForm M= N;
  int l= degree (N);
  Variable y= F.mvar();
  Variable x= Variable (1);
  CFList source, dest;
  if (degs.getLength() <= 1 || factors.length() == 1)
  {
    CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
    F= 1;
    return result;
  }
 
  DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
            (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
  int degMipoBeta= 1;
  if (!k && beta.level() != 1)
    degMipoBeta= degree (getMipo (beta));
 
  CFList T, S, Diff;
  T= factors;
 
  CFList result;
  CanonicalForm buf, buf2, quot;
 
  buf= F;
 
  CanonicalForm g, LCBuf= LC (buf, x);
  int * v= new int [T.length()];
  for (int i= 0; i < T.length(); i++)
    v[i]= 0;
 
  CFArray TT;
  DegreePattern bufDegs1, bufDegs2;
  bufDegs1= degs;
  int subsetDeg;
  TT= copy (factors);
  bool nosubset= false;
  bool recombination= false;
  bool trueFactor= false;
  CanonicalForm test;
  CanonicalForm buf0= buf (0, x)*LCBuf;
  while (T.length() >= 2*s && s <= thres)
  {
    while (nosubset == false)
    {
      if (T.length() == s)
      {
        delete [] v;
        if (recombination)
        {
          T.insert (LCBuf);
          g= prodMod (T, M);
          T.removeFirst();
          g /= content(g);
          g= g (y - eval, y);
          g /= Lc (g);
          appendTestMapDown (result, g, info, source, dest);
          F= 1;
          return result;
        }
        else
        {
          appendMapDown (result, F (y - eval, y), info, source, dest);
          F= 1;
          return result;
        }
      }
      S= subset (v, s, TT, nosubset);
      if (nosubset) break;
      subsetDeg= subsetDegree (S);
      // skip those combinations that are not possible
      if (!degs.find (subsetDeg))
        continue;
      else
      {
        test= prodMod0 (S, M);
        test *= LCBuf;
        test = mod (test, M);
        if (fdivides (test, buf0))
        {
          S.insert (LCBuf);
          g= prodMod (S, M);
          S.removeFirst();
          g /= content (g, x);
          if (fdivides (g, buf, quot))
          {
            buf2= g (y - eval, y);
            buf2 /= Lc (buf2);
 
            if (!k && beta.level() == 1)
            {
              if (degree (buf2, alpha) < degMipoBeta)
              {
                buf= quot;
                LCBuf= LC (buf, x);
                recombination= true;
                appendTestMapDown (result, buf2, info, source, dest);
                trueFactor= true;
              }
            }
            else
            {
              if (!isInExtension (buf2, gamma, k, delta, source, dest))
              {
                buf= quot;
                LCBuf= LC (buf, x);
                recombination= true;
                appendTestMapDown (result, buf2, info, source, dest);
                trueFactor= true;
              }
            }
            if (trueFactor)
            {
              T= Difference (T, S);
              l -= degree (g);
              M= power (y, l);
              buf0= buf (0, x)*LCBuf;
 
              // compute new possible degree pattern
              bufDegs2= DegreePattern (T);
              bufDegs1.intersect (bufDegs2);
              bufDegs1.refine ();
              if (T.length() < 2*s || T.length() == s ||
                  bufDegs1.getLength() == 1)
              {
                delete [] v;
                if (recombination)
                {
                  buf= buf (y-eval,y);
                  buf /= Lc (buf);
                  appendTestMapDown (result, buf, info, source,
                                      dest);
                  F= 1;
                  return result;
                }
                else
                {
                  appendMapDown (result, F (y - eval, y), info, source, dest);
                  F= 1;
                  return result;
                }
              }
              trueFactor= false;
              TT= copy (T);
              indexUpdate (v, s, T.length(), nosubset);
              if (nosubset) break;
            }
          }
        }
      }
    }
    s++;
    if (T.length() < 2*s || T.length() == s)
    {
      delete [] v;
      if (recombination)
      {
        buf= buf (y-eval,y);
        buf /= Lc (buf);
        appendTestMapDown (result, buf, info, source, dest);
        F= 1;
        return result;
      }
      else
      {
        appendMapDown (result, F (y - eval, y), info, source, dest);
        F= 1;
        return result;
      }
    }
    for (int i= 0; i < T.length(); i++)
      v[i]= 0;
    nosubset= false;
  }
  if (T.length() < 2*s)
  {
    appendMapDown (result, F (y - eval, y), info, source, dest);
    F= 1;
    delete [] v;
    return result;
  }
 
  if (s > thres)
  {
    factors= T;
    F= buf;
    degs= bufDegs1;
  }
 
  delete [] v;
  return result;
}

factorRecombination()

CFList factorRecombination	(	CFList &	factors,
		CanonicalForm &	F,
		const CanonicalForm &	N,
		DegreePattern &	degs,
		const CanonicalForm &	eval,
		int	s,
		int	thres,
		const modpk &	b,
		const CanonicalForm &	den
	)

naive factor recombination. Uses precomputed data to exclude combinations that are not possible.

Returns

factorRecombination returns a list of factors of F.

See also

extFactorRecombination(), earlyFactorDetectection()

naive factor recombination. Uses precomputed data to exclude combinations that are not possible.

Parameters

[in,out]	factors	list of lifted factors that are monic wrt Variable (1)
[in,out]	F	poly to be factored
[in]	N	Variable (2)^liftBound
[in]	degs	degree pattern
[in]	eval	evaluation point
[in]	s	algorithm starts checking subsets of size s
[in]	thres	threshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2
[in]	b	coeff bound
[in]	den	bound on the den if over Q (a)

Definition at line 586 of file facFqBivar.cc.

{
  if (factors.length() == 0)
  {
    F= 1;
    return CFList ();
  }
  if (F.inCoeffDomain())
    return CFList();
  Variable y= Variable (2);
  if (degs.getLength() <= 1 || factors.length() == 1)
  {
    CFList result= CFList (F(y-eval,y));
    F= 1;
    return result;
  }
#ifdef DEBUGOUTPUT
  if (b.getp() == 0)
    DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
              (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
  else
    DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
              (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
#endif
 
  CFList T, S;
 
  CanonicalForm M= N;
  int l= degree (N);
  T= factors;
  CFList result;
  Variable x= Variable (1);
  CanonicalForm denom= den, denQuot;
  CanonicalForm LCBuf= LC (F, x)*denom;
  CanonicalForm g, quot, buf= F;
  int * v= new int [T.length()];
  for (int i= 0; i < T.length(); i++)
    v[i]= 0;
  bool nosubset= false;
  CFArray TT;
  DegreePattern bufDegs1, bufDegs2;
  bufDegs1= degs;
  int subsetDeg;
  TT= copy (factors);
  bool recombination= false;
  CanonicalForm test;
  bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
               getCharacteristic() > 0;
  if (!isRat)
    On (SW_RATIONAL);
  CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
  if (!isRat)
    Off (SW_RATIONAL);
  while (T.length() >= 2*s && s <= thres)
  {
    while (nosubset == false)
    {
      if (T.length() == s)
      {
        delete [] v;
        if (recombination)
        {
          T.insert (LCBuf);
          g= prodMod (T, M);
          if (b.getp() != 0)
            g= b(g);
          T.removeFirst();
          g /= content (g,x);
          result.append (g(y-eval,y));
          F= 1;
          return result;
        }
        else
        {
          result= CFList (F(y-eval,y));
          F= 1;
          return result;
        }
      }
      S= subset (v, s, TT, nosubset);
      if (nosubset) break;
      subsetDeg= subsetDegree (S);
      // skip those combinations that are not possible
      if (!degs.find (subsetDeg))
        continue;
      else
      {
        if (!isRat)
          On (SW_RATIONAL);
        test= prodMod0 (S, M);
        if (!isRat)
        {
          test *= bCommonDen (test);
          Off (SW_RATIONAL);
        }
        test= mulNTL (test, LCBuf, b);
        test= mod (test, M);
        if (uniFdivides (test, buf0))
        {
          if (!isRat)
            On (SW_RATIONAL);
          S.insert (LCBuf);
          g= prodMod (S, M);
          S.removeFirst();
          if (!isRat)
          {
            g *= bCommonDen(g);
            Off (SW_RATIONAL);
          }
          if (b.getp() != 0)
            g= b(g);
          if (!isRat)
            On (SW_RATIONAL);
          g /= content (g, x);
          if (!isRat)
          {
            On (SW_RATIONAL);
            if (!Lc (g).inBaseDomain())
              g /= Lc (g);
            g *= bCommonDen (g);
            Off (SW_RATIONAL);
            g /= icontent (g);
            On (SW_RATIONAL);
          }
          if (fdivides (g, buf, quot))
          {
            denom *= abs (lc (g));
            recombination= true;
            result.append (g (y-eval,y));
            if (b.getp() != 0)
            {
              denQuot= bCommonDen (quot);
              buf= quot*denQuot;
              Off (SW_RATIONAL);
              denom /= gcd (denom, denQuot);
              On (SW_RATIONAL);
            }
            else
              buf= quot;
            LCBuf= LC (buf, x)*denom;
            T= Difference (T, S);
            l -= degree (g);
            M= power (y, l);
            buf0= mulNTL (buf (0, x), LCBuf);
            if (!isRat)
              Off (SW_RATIONAL);
            // compute new possible degree pattern
            bufDegs2= DegreePattern (T);
            bufDegs1.intersect (bufDegs2);
            bufDegs1.refine ();
            if (T.length() < 2*s || T.length() == s ||
                bufDegs1.getLength() == 1)
            {
              delete [] v;
              if (recombination)
              {
                result.append (buf (y-eval,y));
                F= 1;
                return result;
              }
              else
              {
                result= CFList (F (y-eval,y));
                F= 1;
                return result;
              }
            }
            TT= copy (T);
            indexUpdate (v, s, T.length(), nosubset);
            if (nosubset) break;
          }
          if (!isRat)
            Off (SW_RATIONAL);
        }
      }
    }
    s++;
    if (T.length() < 2*s || T.length() == s)
    {
      delete [] v;
      if (recombination)
      {
        result.append (buf(y-eval,y));
        F= 1;
        return result;
      }
      else
      {
        result= CFList (F(y-eval,y));
        F= 1;
        return result;
      }
    }
    for (int i= 0; i < T.length(); i++)
      v[i]= 0;
    nosubset= false;
  }
  delete [] v;
  if (T.length() < 2*s)
  {
    result.append (F(y-eval,y));
    F= 1;
    return result;
  }
 
  if (s > thres)
  {
    factors= T;
    F= buf;
    degs= bufDegs1;
  }
 
  return result;
}

FpBiFactorize()

CFFList FpBiFactorize ( const CanonicalForm &  G, bool  substCheck = true  )

inline

factorize a bivariate polynomial over

Returns

FpBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

See also

FqBiFactorize(), GFBiFactorize()

Parameters

[in]	G	a bivariate poly
[in]	substCheck	enables substitute check

Definition at line 190 of file facFqBivar.h.

{
  ExtensionInfo info= ExtensionInfo (false);
  CFMap N;
  CanonicalForm F= compress (G, N);
 
  if (substCheck)
  {
    bool foundOne= false;
    int * substDegree= NEW_ARRAY(int,F.level());
    for (int i= 1; i <= F.level(); i++)
    {
      substDegree[i-1]= substituteCheck (F, Variable (i));
      if (substDegree [i-1] > 1)
      {
        foundOne= true;
        subst (F, F, substDegree[i-1], Variable (i));
      }
    }
    if (foundOne)
    {
      CFFList result= FpBiFactorize (F, false);
      CFFList newResult, tmp;
      CanonicalForm tmp2;
      newResult.insert (result.getFirst());
      result.removeFirst();
      for (CFFListIterator i= result; i.hasItem(); i++)
      {
        tmp2= i.getItem().factor();
        for (int j= 1; j <= F.level(); j++)
        {
          if (substDegree[j-1] > 1)
            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
        }
        tmp= FpBiFactorize (tmp2, false);
        tmp.removeFirst();
        for (CFFListIterator j= tmp; j.hasItem(); j++)
          newResult.append (CFFactor (j.getItem().factor(),
                                      j.getItem().exp()*i.getItem().exp()));
      }
      decompress (newResult, N);
      DELETE_ARRAY(substDegree);
      return newResult;
    }
    DELETE_ARRAY(substDegree);
  }
 
  CanonicalForm LcF= Lc (F);
  CanonicalForm contentX= content (F, 1);
  CanonicalForm contentY= content (F, 2);
  F /= (contentX*contentY);
  CFFList contentXFactors, contentYFactors;
  contentXFactors= factorize (contentX);
  contentYFactors= factorize (contentY);
  if (contentXFactors.getFirst().factor().inCoeffDomain())
    contentXFactors.removeFirst();
  if (contentYFactors.getFirst().factor().inCoeffDomain())
    contentYFactors.removeFirst();
  decompress (contentXFactors, N);
  decompress (contentYFactors, N);
  CFFList result;
  if (F.inCoeffDomain())
  {
    result= Union (contentXFactors, contentYFactors);
    normalize (result);
    result.insert (CFFactor (LcF, 1));
    return result;
  }
  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);
 
  TIMING_START (fac_fq_bi_sqrf);
  CFFList sqrf= FpSqrf (F, false);
  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
                       "time for bivariate sqrf factors over Fp: ");
  CFList bufResult;
  sqrf.removeFirst();
  CFListIterator i;
  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
  {
    TIMING_START (fac_fq_bi_factor_sqrf);
    bufResult= biFactorize (iter.getItem().factor(), info);
    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
                          "time to factor bivariate sqrf factors over Fp: ");
    for (i= bufResult; i.hasItem(); i++)
      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
                               iter.getItem().exp()));
  }
 
  result= Union (result, contentXFactors);
  result= Union (result, contentYFactors);
  normalize (result);
  result.insert (CFFactor (LcF, 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;
 
  return result;
}

FpBiSqrfFactorize()

CFList FpBiSqrfFactorize ( const CanonicalForm &  G )

inline

factorize a squarefree bivariate polynomial over .

Returns

FpBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

See also

FqBiSqrfFactorize(), GFBiSqrfFactorize()

Parameters

[in]

G

a bivariate poly

Definition at line 141 of file facFqBivar.h.

{
  ExtensionInfo info= ExtensionInfo (false);
  return biSqrfFactorizeHelper (G, info);
}

FqBiFactorize()

CFFList FqBiFactorize ( const CanonicalForm &  G, const Variable &  alpha, bool  substCheck = true  )

inline

factorize a bivariate polynomial over

Returns

FqBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

See also

FpBiFactorize(), FqBiFactorize()

Parameters

[in]	G	a bivariate poly
[in]	alpha	algebraic variable
[in]	substCheck	enables substitute check

Definition at line 317 of file facFqBivar.h.

{
  ExtensionInfo info= ExtensionInfo (alpha, false);
  CFMap N;
  CanonicalForm F= compress (G, N);
 
  if (substCheck)
  {
    bool foundOne= false;
    int * substDegree= NEW_ARRAY(int,F.level());
    for (int i= 1; i <= F.level(); i++)
    {
      substDegree[i-1]= substituteCheck (F, Variable (i));
      if (substDegree [i-1] > 1)
      {
        foundOne= true;
        subst (F, F, substDegree[i-1], Variable (i));
      }
    }
    if (foundOne)
    {
      CFFList result= FqBiFactorize (F, alpha, false);
      CFFList newResult, tmp;
      CanonicalForm tmp2;
      newResult.insert (result.getFirst());
      result.removeFirst();
      for (CFFListIterator i= result; i.hasItem(); i++)
      {
        tmp2= i.getItem().factor();
        for (int j= 1; j <= F.level(); j++)
        {
          if (substDegree[j-1] > 1)
            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
        }
        tmp= FqBiFactorize (tmp2, alpha, false);
        tmp.removeFirst();
        for (CFFListIterator j= tmp; j.hasItem(); j++)
          newResult.append (CFFactor (j.getItem().factor(),
                                      j.getItem().exp()*i.getItem().exp()));
      }
      decompress (newResult, N);
      DELETE_ARRAY(substDegree);
      return newResult;
    }
    DELETE_ARRAY(substDegree);
  }
 
  CanonicalForm LcF= Lc (F);
  CanonicalForm contentX= content (F, 1);
  CanonicalForm contentY= content (F, 2);
  F /= (contentX*contentY);
  CFFList contentXFactors, contentYFactors;
  contentXFactors= factorize (contentX, alpha);
  contentYFactors= factorize (contentY, alpha);
  if (contentXFactors.getFirst().factor().inCoeffDomain())
    contentXFactors.removeFirst();
  if (contentYFactors.getFirst().factor().inCoeffDomain())
    contentYFactors.removeFirst();
  decompress (contentXFactors, N);
  decompress (contentYFactors, N);
  CFFList result;
  if (F.inCoeffDomain())
  {
    result= Union (contentXFactors, contentYFactors);
    normalize (result);
    result.insert (CFFactor (LcF, 1));
    return result;
  }
 
  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);
 
  TIMING_START (fac_fq_bi_sqrf);
  CFFList sqrf= FqSqrf (F, alpha, false);
  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
                       "time for bivariate sqrf factors over Fq: ");
  CFList bufResult;
  sqrf.removeFirst();
  CFListIterator i;
  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
  {
    TIMING_START (fac_fq_bi_factor_sqrf);
    bufResult= biFactorize (iter.getItem().factor(), info);
    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
                          "time to factor bivariate sqrf factors over Fq: ");
    for (i= bufResult; i.hasItem(); i++)
      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
                               iter.getItem().exp()));
  }
 
  result= Union (result, contentXFactors);
  result= Union (result, contentYFactors);
  normalize (result);
  result.insert (CFFactor (LcF, 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;
 
  return result;
}

FqBiSqrfFactorize()

CFList FqBiSqrfFactorize ( const CanonicalForm &  G, const Variable &  alpha  )

inline

factorize a squarefree bivariate polynomial over .

Returns

FqBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

See also

FpBiSqrfFactorize(), GFBiSqrfFactorize()

Parameters

[in]	G	a bivariate poly
[in]	alpha	algebraic variable

Definition at line 156 of file facFqBivar.h.

{
  ExtensionInfo info= ExtensionInfo (alpha, false);
  return biSqrfFactorizeHelper (G, info);
}

getLiftPrecisions()

int * getLiftPrecisions	(	const CanonicalForm &	F,
		int &	sizeOfOutput,
		int	degreeLC
	)

compute lifting precisions from the shape of the Newton polygon of F

Returns

getLiftPrecisions returns lifting precisions computed from the shape of the Newton polygon of F

Parameters

[in]	F	a bivariate poly
[in,out]	sizeOfOutput	size of the output
[in]	degreeLC	degree of the leading coeff [in] of F wrt. Variable (1)

Definition at line 1120 of file facFqBivar.cc.

{
  int sizeOfNewtonPoly;
  int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
  int sizeOfRightSide;
  int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
  int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
                                degreeLC);
  delete [] rightSide;
  for (int i= 0; i < sizeOfNewtonPoly; i++)
    delete [] newtonPolyg[i];
  delete [] newtonPolyg;
  return result;
}

GFBiFactorize()

CFFList GFBiFactorize ( const CanonicalForm &  G, bool  substCheck = true  )

inline

factorize a bivariate polynomial over GF

Returns

GFBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

See also

FpBiFactorize(), FqBiFactorize()

Parameters

[in]	G	a bivariate poly
[in]	substCheck	enables substitute check

Definition at line 446 of file facFqBivar.h.

{
  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
          "GF as base field expected");
  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
  CFMap N;
  CanonicalForm F= compress (G, N);
 
  if (substCheck)
  {
    bool foundOne= false;
    int * substDegree=NEW_ARRAY(int,F.level());
    for (int i= 1; i <= F.level(); i++)
    {
      substDegree[i-1]= substituteCheck (F, Variable (i));
      if (substDegree [i-1] > 1)
      {
        foundOne= true;
        subst (F, F, substDegree[i-1], Variable (i));
      }
    }
    if (foundOne)
    {
      CFFList result= GFBiFactorize (F, false);
      CFFList newResult, tmp;
      CanonicalForm tmp2;
      newResult.insert (result.getFirst());
      result.removeFirst();
      for (CFFListIterator i= result; i.hasItem(); i++)
      {
        tmp2= i.getItem().factor();
        for (int j= 1; j <= F.level(); j++)
        {
          if (substDegree[j-1] > 1)
            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
        }
        tmp= GFBiFactorize (tmp2, false);
        tmp.removeFirst();
        for (CFFListIterator j= tmp; j.hasItem(); j++)
          newResult.append (CFFactor (j.getItem().factor(),
                                      j.getItem().exp()*i.getItem().exp()));
      }
      decompress (newResult, N);
      DELETE_ARRAY(substDegree);
      return newResult;
    }
    DELETE_ARRAY(substDegree);
  }
 
  CanonicalForm LcF= Lc (F);
  CanonicalForm contentX= content (F, 1);
  CanonicalForm contentY= content (F, 2);
  F /= (contentX*contentY);
  CFFList contentXFactors, contentYFactors;
  contentXFactors= factorize (contentX);
  contentYFactors= factorize (contentY);
  if (contentXFactors.getFirst().factor().inCoeffDomain())
    contentXFactors.removeFirst();
  if (contentYFactors.getFirst().factor().inCoeffDomain())
    contentYFactors.removeFirst();
  decompress (contentXFactors, N);
  decompress (contentYFactors, N);
  CFFList result;
  if (F.inCoeffDomain())
  {
    result= Union (contentXFactors, contentYFactors);
    normalize (result);
    result.insert (CFFactor (LcF, 1));
    return result;
  }
 
  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);
 
  TIMING_START (fac_fq_bi_sqrf);
  CFFList sqrf= GFSqrf (F, false);
  TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
                       "time for bivariate sqrf factors over GF: ");
  CFList bufResult;
  sqrf.removeFirst();
  CFListIterator i;
  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
  {
    TIMING_START (fac_fq_bi_factor_sqrf);
    bufResult= biFactorize (iter.getItem().factor(), info);
    TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
                          "time to factor bivariate sqrf factors over GF: ");
    for (i= bufResult; i.hasItem(); i++)
      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
                               iter.getItem().exp()));
  }
 
  result= Union (result, contentXFactors);
  result= Union (result, contentYFactors);
  normalize (result);
  result.insert (CFFactor (LcF, 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;
 
  return result;
}

GFBiSqrfFactorize()

CFList GFBiSqrfFactorize ( const CanonicalForm &  G )

inline

factorize a squarefree bivariate polynomial over GF

Returns

GFBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

See also

FpBiSqrfFactorize(), FqBiSqrfFactorize()

Parameters

[in]

G

a bivariate poly

Definition at line 172 of file facFqBivar.h.

{
  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
          "GF as base field expected");
  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
  return biSqrfFactorizeHelper (G, info);
}

henselLiftAndEarly() [1/2]

CFList henselLiftAndEarly	(	CanonicalForm &	A,
		bool &	earlySuccess,
		CFList &	earlyFactors,
		DegreePattern &	degs,
		int &	liftBound,
		const CFList &	uniFactors,
		const ExtensionInfo &	info,
		const CanonicalForm &	eval
	)

hensel Lifting and early factor detection

Returns

henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting

See also

earlyFactorDetection(), extEarlyFactorDetection()

Parameters

[in,out]	A	poly to be factored, returns poly divided by detected factors in case of success
[in,out]	earlySuccess	indicating success
[in,out]	earlyFactors	list of factors detected at early stage of Hensel lifting
[in,out]	degs	degree pattern
[in,out]	liftBound	(adapted) lift bound
[in]	uniFactors	univariate factors
[in]	info	information about extension
[in]	eval	evaluation point

Definition at line 1455 of file facFqBivar.cc.

{
  modpk dummy= modpk();
  CanonicalForm den= 1;
  return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
                             uniFactors, info, eval, dummy, den);
}

henselLiftAndEarly() [2/2]

CFList henselLiftAndEarly	(	CanonicalForm &	A,
		bool &	earlySuccess,
		CFList &	earlyFactors,
		DegreePattern &	degs,
		int &	liftBound,
		const CFList &	uniFactors,
		const ExtensionInfo &	info,
		const CanonicalForm &	eval,
		modpk &	b,
		CanonicalForm &	den
	)

hensel Lifting and early factor detection

Returns

henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting

See also

earlyFactorDetection(), extEarlyFactorDetection()

Parameters

[in,out]	A	poly to be factored, returns poly divided by detected factors in case of success
[in,out]	earlySuccess	indicating success
[in,out]	earlyFactors	list of factors detected at early stage of Hensel lifting
[in,out]	degs	degree pattern
[in,out]	liftBound	(adapted) lift bound
[in]	uniFactors	univariate factors
[in]	info	information about extension
[in]	eval	evaluation point
[in]	b	coeff bound
[in]	den	bound on the den if over Q(a)

Definition at line 1152 of file facFqBivar.cc.

{
  Variable alpha= info.getAlpha();
  Variable beta= info.getBeta();
  CanonicalForm gamma= info.getGamma();
  CanonicalForm delta= info.getDelta();
  bool extension= info.isInExtension();
 
  int sizeOfLiftPre;
  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
 
  Variable x= Variable (1);
  Variable y= Variable (2);
  CFArray Pi;
  CFList diophant;
  CFList bufUniFactors= uniFactors;
  On (SW_RATIONAL);
  CanonicalForm bufA= A;
  if (!Lc (A).inBaseDomain())
  {
    bufA /= Lc (A);
    CanonicalForm denBufA= bCommonDen (bufA);
    bufA *= denBufA;
    Off (SW_RATIONAL);
    den /= gcd (den, denBufA);
  }
  else
  {
    bufA= A;
    Off (SW_RATIONAL);
    den /= gcd (den, Lc (A));
  }
  CanonicalForm lcA0= 0;
  bool mipoHasDen= false;
  if (getCharacteristic() == 0 && b.getp() != 0)
  {
    if (alpha.level() == 1)
    {
      lcA0= lc (A (0, 2));
      A *= b.inverse (lcA0);
      A= b (A);
      for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
        i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
    }
    else
    {
      lcA0= Lc (A (0,2));
      On (SW_RATIONAL);
      mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
      Off (SW_RATIONAL);
      CanonicalForm lcA0inverse= b.inverse (lcA0);
      A *= lcA0inverse;
      A= b (A);
      // Lc of bufUniFactors is in Z
      for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
        i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
    }
  }
  bufUniFactors.insert (LC (A, x));
  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
  earlySuccess= false;
  int newLiftBound= 0;
 
  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
  int dummy;
  int * factorsFoundIndex= new int [uniFactors.length()];
  for (int i= 0; i < uniFactors.length(); i++)
    factorsFoundIndex [i]= 0;
 
  CFList bufBufUniFactors;
  Variable v= alpha;
  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
    henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
  {
    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
    if (mipoHasDen)
    {
      for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
        if (hasFirstAlgVar (iter.getItem(), v))
          break;
      if (v != alpha)
      {
        bufBufUniFactors= bufUniFactors;
        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
          iter.getItem()= replacevar (iter.getItem(), v, alpha);
        A= replacevar (A, alpha, v);
      }
    }
 
    if (!extension)
    {
      if (v==alpha)
        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                              factorsFoundIndex, degs, earlySuccess,
                              smallFactorDeg, eval, b, den);
      else
        earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
                             factorsFoundIndex, degs, earlySuccess,
                             smallFactorDeg, eval, b, den);
    }
    else
      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                               factorsFoundIndex, degs, earlySuccess, info,
                               eval, smallFactorDeg);
    if (degs.getLength() > 1 && !earlySuccess &&
        smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
    {
      if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
      {
        bufUniFactors.insert (LC (A, x));
        henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
                            liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
        if (v!=alpha)
        {
          bufBufUniFactors= bufUniFactors;
          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
            iter.getItem()= replacevar (iter.getItem(), v, alpha);
        }
        if (!extension)
        {
          if (v==alpha)
          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                factorsFoundIndex, degs, earlySuccess,
                                liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
          else
          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
                                factorsFoundIndex, degs, earlySuccess,
                                liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
        }
        else
          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
                                   factorsFoundIndex, degs, earlySuccess, info,
                                   eval, liftPre[sizeOfLiftPre-1] + 1);
      }
    }
    else if (earlySuccess)
      liftBound= newLiftBound;
 
    int i= sizeOfLiftPre - 1;
    while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
    {
      if (newLiftBound >= liftPre[i] + 1)
      {
        bufUniFactors.insert (LC (A, x));
        henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
                            liftPre[i-1] + 1, Pi, diophant, M, b);
        if (v!=alpha)
        {
          bufBufUniFactors= bufUniFactors;
          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
            iter.getItem()= replacevar (iter.getItem(), v, alpha);
        }
        if (!extension)
        {
          if (v==alpha)
          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                factorsFoundIndex, degs, earlySuccess,
                                liftPre[i-1] + 1, eval, b, den);
          else
          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
                                factorsFoundIndex, degs, earlySuccess,
                                liftPre[i-1] + 1, eval, b, den);
        }
        else
          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
                                   factorsFoundIndex, degs, earlySuccess, info,
                                   eval, liftPre[i-1] + 1);
      }
      else
      {
        liftBound= newLiftBound;
        break;
      }
      i--;
    }
    if (earlySuccess)
      liftBound= newLiftBound;
    //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
  }
  else
  {
    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
    if (mipoHasDen)
    {
      for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
        if (hasFirstAlgVar (iter.getItem(), v))
          break;
      if (v != alpha)
      {
        bufBufUniFactors= bufUniFactors;
        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
          iter.getItem()= replacevar (iter.getItem(), v, alpha);
        A= replacevar (A, alpha, v);
      }
    }
    if (!extension)
    {
      if (v==alpha)
      earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                            factorsFoundIndex, degs, earlySuccess,
                            smallFactorDeg, eval, b, den);
      else
      earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
                            factorsFoundIndex, degs, earlySuccess,
                            smallFactorDeg, eval, b, den);
    }
    else
      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                               factorsFoundIndex, degs, earlySuccess, info,
                               eval, smallFactorDeg);
    int i= 1;
    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
      i++;
    dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
    if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
    {
      bufUniFactors.insert (LC (A, x));
      henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
                          dummy, Pi, diophant, M, b);
      if (v!=alpha)
      {
        bufBufUniFactors= bufUniFactors;
        for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
          iter.getItem()= replacevar (iter.getItem(), v, alpha);
      }
      if (!extension)
      {
        if (v==alpha)
        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                              factorsFoundIndex, degs, earlySuccess, dummy,eval,
                              b, den);
        else
        earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
                              factorsFoundIndex, degs, earlySuccess, dummy,eval,
                              b, den);
      }
      else
        extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
                                 factorsFoundIndex, degs, earlySuccess, info,
                                 eval, dummy);
    }
    while (degs.getLength() > 1 && !earlySuccess && i < 4)
    {
      if (newLiftBound >= dummy)
      {
        bufUniFactors.insert (LC (A, x));
        dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
        henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
                            dummy, Pi, diophant, M, b);
        if (v!=alpha)
        {
          bufBufUniFactors= bufUniFactors;
          for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
            iter.getItem()= replacevar (iter.getItem(), v, alpha);
        }
        if (!extension)
        {
          if (v==alpha)
          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                factorsFoundIndex, degs, earlySuccess, dummy,
                                eval, b, den);
          else
          earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
                                factorsFoundIndex, degs, earlySuccess, dummy,
                                eval, b, den);
        }
        else
          extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
                                   factorsFoundIndex, degs, earlySuccess, info,
                                   eval, dummy);
      }
      else
      {
        liftBound= newLiftBound;
        break;
      }
      i++;
    }
    if (earlySuccess)
      liftBound= newLiftBound;
  }
 
  A= bufA;
  if (earlyFactors.length() > 0 && degs.getLength() > 1)
  {
    liftBound= degree (A,y) + 1;
    earlySuccess= true;
    deleteFactors (bufUniFactors, factorsFoundIndex);
  }
 
  delete [] factorsFoundIndex;
  delete [] liftPre;
 
  return bufUniFactors;
}

prodMod0()

CanonicalForm prodMod0	(	const CFList &	L,
		const CanonicalForm &	M,
		const modpk &	b = modpk()
	)

via divide-and-conquer

Returns

prodMod0 computes the above defined product

See also

prodMod()

Parameters

[in]	L	a list of compressed, bivariate polynomials
[in]	M	a power of Variable (2)
[in]	b	coeff bound

TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT

(

fac_fq_bi_sqrf

)

const

uniFactorizer()

CFList uniFactorizer	(	const CanonicalForm &	A,
		const Variable &	alpha,
		const bool &	GF
	)

Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used.

Returns

uniFactorizer returns a list of monic factors

Parameters

[in]	A	squarefree univariate poly
[in]	alpha	algebraic variable
[in]	GF	GaloisFieldDomain?

Definition at line 160 of file facFqBivar.cc.

{
  Variable x= A.mvar();
  if (A.inCoeffDomain())
    return CFList();
  ASSERT (A.isUnivariate(),
          "univariate polynomial expected or constant expected");
  CFFList factorsA;
  if (GF)
  {
    int k= getGFDegree();
    char cGFName= gf_name;
    CanonicalForm mipo= gf_mipo;
    setCharacteristic (getCharacteristic());
    Variable beta= rootOf (mipo.mapinto());
    CanonicalForm buf= GF2FalphaRep (A, beta);
#ifdef HAVE_NTL    
    if (getCharacteristic() > 2)
#else
    if (getCharacteristic() > 0)
#endif
    {
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
      nmod_poly_t FLINTmipo, leadingCoeff;
      fq_nmod_ctx_t fq_con;
      fq_nmod_poly_t FLINTA;
      fq_nmod_poly_factor_t FLINTFactorsA;
 
      nmod_poly_init (FLINTmipo, getCharacteristic());
      convertFacCF2nmod_poly_t (FLINTmipo, mipo.mapinto());
 
      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
      convertFacCF2Fq_nmod_poly_t (FLINTA, buf, fq_con);
      fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
 
      fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
      nmod_poly_init (leadingCoeff, getCharacteristic());
 
      fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
 
      factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
                                                            beta, fq_con);
 
      fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
      fq_nmod_poly_clear (FLINTA, fq_con);
      nmod_poly_clear (FLINTmipo);
      nmod_poly_clear (leadingCoeff);
      fq_nmod_ctx_clear (fq_con);
#else
      if (fac_NTL_char != getCharacteristic())
      {
        fac_NTL_char= getCharacteristic();
        zz_p::init (getCharacteristic());
      }
      zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
      zz_pE::init (NTLMipo);
      zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
      MakeMonic (NTLA);
      vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
      zz_pE multi= to_zz_pE (1);
      factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
                                                         x, beta);
#endif
    }
#ifdef HAVE_NTL    
    else
    {
      GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
      GF2E::init (NTLMipo);
      GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
      MakeMonic (NTLA);
      vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
      GF2E multi= to_GF2E (1);
      factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
                                                           x, beta);
    }
#endif    
    setCharacteristic (getCharacteristic(), k, cGFName);
    for (CFFListIterator i= factorsA; i.hasItem(); i++)
    {
      buf= i.getItem().factor();
      buf= Falpha2GFRep (buf);
      i.getItem()= CFFactor (buf, i.getItem().exp());
    }
    prune (beta);
  }
  else if (alpha.level() != 1)
  {
#ifdef HAVE_NTL  
    if (getCharacteristic() > 2)
#else
    if (getCharacteristic() > 0)
#endif
    {
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
      nmod_poly_t FLINTmipo, leadingCoeff;
      fq_nmod_ctx_t fq_con;
      fq_nmod_poly_t FLINTA;
      fq_nmod_poly_factor_t FLINTFactorsA;
 
      nmod_poly_init (FLINTmipo, getCharacteristic());
      convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
      fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
 
      convertFacCF2Fq_nmod_poly_t (FLINTA, A, fq_con);
      fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
 
      fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
      nmod_poly_init (leadingCoeff, getCharacteristic());
 
      fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
 
      factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
                                                            alpha, fq_con);
 
      fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
      fq_nmod_poly_clear (FLINTA, fq_con);
      nmod_poly_clear (FLINTmipo);
      nmod_poly_clear (leadingCoeff);
      fq_nmod_ctx_clear (fq_con);
#else
      if (fac_NTL_char != getCharacteristic())
      {
        fac_NTL_char= getCharacteristic();
        zz_p::init (getCharacteristic());
      }
      zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
      zz_pE::init (NTLMipo);
      zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
      MakeMonic (NTLA);
      vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
      zz_pE multi= to_zz_pE (1);
      factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
                                                           x, alpha);
#endif
    }
#ifdef HAVE_NTL
    else
    {
      GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
      GF2E::init (NTLMipo);
      GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
      MakeMonic (NTLA);
      vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
      GF2E multi= to_GF2E (1);
      factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
                                                           x, alpha);
    }
#endif    
  }
  else
  {
#ifdef HAVE_FLINT
#ifdef HAVE_NTL
    if (degree (A) < 300)
#endif    
    {
      nmod_poly_t FLINTA;
      convertFacCF2nmod_poly_t (FLINTA, A);
      nmod_poly_factor_t result;
      nmod_poly_factor_init (result);
      mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
      factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
      if (factorsA.getFirst().factor().inCoeffDomain())
        factorsA.removeFirst();
      nmod_poly_factor_clear (result);
      nmod_poly_clear (FLINTA);
    }
#ifdef HAVE_NTL
    else
#endif
#endif /* HAVE_FLINT */
#ifdef HAVE_NTL
    if (getCharacteristic() > 2)
    {
      if (fac_NTL_char != getCharacteristic())
      {
        fac_NTL_char= getCharacteristic();
        zz_p::init (getCharacteristic());
      }
      zz_pX NTLA= convertFacCF2NTLzzpX (A);
      MakeMonic (NTLA);
      vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
      zz_p multi= to_zz_p (1);
      factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
                                                          x);
    }
    else
    {
      GF2X NTLA= convertFacCF2NTLGF2X (A);
      vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
      GF2 multi= to_GF2 (1);
      factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
                                                          x);
    }
#endif
  }
  CFList uniFactors;
  for (CFFListIterator i= factorsA; i.hasItem(); i++)
    uniFactors.append (i.getItem().factor());
  return uniFactors;
}