Function AlgExtSqrfFactorize

factory/facAlgExt.cc:148–284

#endif

CFList AlgExtSqrfFactorize (const CanonicalForm& F, const Variable& alpha)
{
  ASSERT (F.isUnivariate(), "univariate input expected");
  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");

  bool save_rat=!isOn (SW_RATIONAL);
  On (SW_RATIONAL);
  CanonicalForm f= F*bCommonDen (F);
  Variable y= f.mvar();
  int shift= 0, k= 0, count= 0;
  CanonicalForm norm, buf, factor, oldF;
  CFFList normFactors;
  bool save_sort= !isOn (SW_USE_NTL_SORT);
  CFList factors, tmp, tmp2;
  CFFListIterator i;
  CFListIterator iter;
  bool shiftBuf= false;

  tmp.append (f);
  do
  {
    tmp2= CFList();
    for (iter= tmp; iter.hasItem(); iter++)
    {
      oldF= iter.getItem()*bCommonDen (iter.getItem());
      if (shift == 0)
        f= oldF;
      else
      {
        f= oldF (y - shift*alpha, y);
        f *= bCommonDen (f);
      }
      TIMING_START (fac_alg_norm);
      norm= Norm (f, alpha);
      TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
      ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");

      TIMING_START (fac_alg_factor_norm);
      On (SW_USE_NTL_SORT);
      normFactors= factorize (norm);
      if (save_sort)
        Off (SW_USE_NTL_SORT);
      TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");

      if (normFactors.getFirst().factor().inCoeffDomain())
        normFactors.removeFirst();
      if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
      {
        factors.append (oldF);
        continue;
      }

      i= normFactors;
      shiftBuf= false;
      if (!(normFactors.length() == 2 &&
            degree (i.getItem().factor()) <= degree (f)))
      {
        TIMING_START (fac_alg_time_shift);