Function earlyFactorDetect

factory/facFqFactorize.cc:611–660

#if defined(HAVE_NTL) || defined(HAVE_FLINT)
CFList
earlyFactorDetect (CanonicalForm& F, CFList& factors, int& adaptedLiftBound,
                   bool& success, const int deg, const CFList& MOD,
                   const int bound)
{
  CFList result;
  CFList T= factors;
  CanonicalForm buf= F;
  Variable y= F.mvar();
  Variable x= Variable (1);
  CanonicalForm LCBuf= LC (buf, x);
  CanonicalForm g, quot;
  CFList M= MOD;
  M.append (power (y, deg));
  adaptedLiftBound= 0;
  int d= bound;
  int e= 0;
  int nBuf;
  for (CFListIterator i= factors; i.hasItem(); i++)
  {
    g= mulMod (i.getItem(), LCBuf, M);
    g /= myContent (g);
    if (fdivides (g, buf, quot))
    {
      result.append (g);
      nBuf= degree (g, y) + degree (LC (g, x), y);
      d -= nBuf;
      e= tmax (e, nBuf);
      buf= quot;
      LCBuf= LC (buf, x);
      T= Difference (T, CFList (i.getItem()));
    }
  }
  adaptedLiftBound= d;

  if (adaptedLiftBound < deg)
  {
    if (adaptedLiftBound < degree (F) + 1)
    {
      if (d == 1)
        adaptedLiftBound= tmin (e + 1, deg);
      else
        adaptedLiftBound= deg;
    }
    factors= T;
    F= buf;
    success= true;
  }
  return result;
}
#endif

#if defined(HAVE_NTL) || defined(HAVE_FLINT)