Changeset 2a2e43 in git


Ignore:
Timestamp:
Jul 17, 2014, 3:09:51 PM (9 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
Children:
e243f1d19971923717babbc0dc13cd49ed4840cf
Parents:
3169ca78b60cbcbd96901fbd89cf164a5ed0b62d88355ebe9326d86d566d6c175b82b315be5b63ed
Message:
Merge pull request #618 from mmklee/alg_prune

Alg prune
Files:
17 edited

Legend:

Unmodified
Added
Removed

  • factory/canonicalform.h

    r3169ca r2a2e43  
    271271
    272272bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
     273
     274CanonicalForm leftShift (const CanonicalForm& F, int n);
    273275//}}}
    274276

  • factory/cfEzgcd.cc

    r3169ca r2a2e43  
    11351135  degF = degree( F, x ); degG = degree( G, x );
    11361136
    1137   if(hasFirstAlgVar(G,a))
     1137  if (algExtension)
    11381138    b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
    11391139  else
    … …  
    11661166        Variable alpha= rootOf (mipo.mapinto());
    11671167        result= GF2FalphaRep (result, alpha);
     1168        prune (alpha);
    11681169      }
    11691170      if (k > 1)
    … …  
    11731174      }
    11741175      if (extOfExt)
     1176      {
    11751177        result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     1178        prune1 (oldA);
     1179      }
    11761180      return N (d*result);
    11771181    }
    … …  
    11881192          Variable alpha= rootOf (mipo.mapinto());
    11891193          F= GF2FalphaRep (F, alpha);
     1194          prune (alpha);
    11901195        }
    11911196        if (k > 1)
    … …  
    11951200        }
    11961201        if (extOfExt)
     1202        {
    11971203          F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
     1204          prune1 (oldA);
     1205        }
    11981206        return N (d*F);
    11991207      }
    … …  
    12111219          Variable alpha= rootOf (mipo.mapinto());
    12121220          G= GF2FalphaRep (G, alpha);
     1221          prune (alpha);
    12131222        }
    12141223        if (k > 1)
    … …  
    12181227        }
    12191228        if (extOfExt)
     1229        {
    12201230          G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
     1231          prune1 (oldA);
     1232        }
    12211233        return N (d*G);
    12221234      }
    … …  
    12481260          Variable alpha= rootOf (mipo.mapinto());
    12491261          result= GF2FalphaRep (result, alpha);
     1262          prune (alpha);
    12501263        }
    12511264        if (k > 1)
    … …  
    12551268        }
    12561269        if (extOfExt)
     1270        {
    12571271          result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     1272          prune1 (oldA);
     1273        }
    12581274        return N (d*result);
    12591275      }
    … …  
    12911307            Variable alpha= rootOf (mipo.mapinto());
    12921308            F= GF2FalphaRep (F, alpha);
     1309            prune (alpha);
    12931310          }
    12941311          if (k > 1)
    … …  
    12981315          }
    12991316          if (extOfExt)
     1317          {
    13001318            F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
     1319            prune1 (oldA);
     1320          }
    13011321          return N (d*F);
    13021322        }
    … …  
    13141334            Variable alpha= rootOf (mipo.mapinto());
    13151335            G= GF2FalphaRep (G, alpha);
     1336            prune (alpha);
    13161337          }
    13171338          if (k > 1)
    … …  
    13211342          }
    13221343          if (extOfExt)
     1344          {
    13231345            G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
     1346            prune1 (oldA);
     1347          }
    13241348          return N (d*G);
    13251349        }
    … …  
    13771401          Variable alpha= rootOf (mipo.mapinto());
    13781402          result= GF2FalphaRep (result, alpha);
     1403          prune (alpha);
    13791404        }
    13801405        if (k > 1)
    … …  
    13841409        }
    13851410        if (extOfExt)
     1411        {
    13861412          result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     1413          prune1 (oldA);
     1414        }
    13871415        return N (d*result);
    13881416      }
    … …  
    13961424          result= modGCDFq (F, G, a);
    13971425          if (extOfExt)
     1426          {
    13981427            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     1428            prune1 (oldA);
     1429          }
    13991430          return N (d*result);
    14001431        }
    … …  
    14081439            Variable alpha= rootOf (mipo.mapinto());
    14091440            result= GF2FalphaRep (result, alpha);
     1441            prune (alpha);
    14101442          }
    14111443          if (k > 1)
    … …  
    14301462          result= modGCDFq (F, G, a);
    14311463          if (extOfExt)
     1464          {
    14321465            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
     1466            prune1 (oldA);
     1467          }
    14331468          return N (d*result);
    14341469        }
    … …  
    14421477            Variable alpha= rootOf (mipo.mapinto());
    14431478            result= GF2FalphaRep (result, alpha);
     1479            prune (alpha);
    14441480          }
    14451481          if (k > 1)
    … …  
    14771513          Variable alpha= rootOf (mipo.mapinto());
    14781514          cand= GF2FalphaRep (cand, alpha);
     1515          prune (alpha);
    14791516        }
    14801517        if (k > 1 && gcdfound)
    … …  
    14841521        }
    14851522        if (extOfExt && gcdfound)
     1523        {
    14861524          cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
     1525          prune1 (oldA);
     1526        }
    14871527      }
    14881528    }

  • factory/cfGcdAlgExt.cc

    r3169ca r2a2e43  
    859859          && f.level() == tmp.level() && tmp.level() == g.level())
    860860      {
    861         CanonicalForm Q, R, sf, sg, stmp;
    862         Variable x= Variable (1);
    863         sf= swapvar (f, f.mvar(), x);
    864         sg= swapvar (g, f.mvar(), x);
    865         stmp= swapvar (tmp, f.mvar(), x);
    866         newtonDivrem (sf, stmp, Q, R);
     861        CanonicalForm Q, R;
     862        newtonDivrem (f, tmp, Q, R);
    867863        if (R.isZero())
    868864        {
    869           newtonDivrem (sg, stmp, Q, R);
     865          newtonDivrem (g, tmp, Q, R);
    870866          if (R.isZero())
    871867          {

  • factory/cfGcdUtil.cc

    r3169ca r2a2e43  
    5252    bool passToGF= false;
    5353    int k= 1;
     54    bool extOfExt= false;
     55    Variable v3;
    5456    if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
    5557    {
    … …  
    7880    else if (p > 0 && p < TEST_ONE_MAX && algExtension)
    7981    {
    80       bool extOfExt= false;
    8182#ifdef HAVE_NTL
    8283      int d= degree (getMipo (v));
    … …  
    132133      if (extOfExt)
    133134      {
     135        v3= v;
    134136        F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
    135137        G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
    … …  
    181183        if (k > 1)
    182184          setCharacteristic (p, k, gf_name);
     185        if (extOfExt)
     186          prune1 (v3);
    183187        return false;
    184188    }
    … …  
    208212    if (k > 1)
    209213      setCharacteristic (p, k, gf_name);
     214    if (extOfExt)
     215      prune1 (v3);
    210216    return result;
    211217}

  • factory/cfModGcd.cc

    r3169ca r2a2e43  
    695695        ppA= mapDown (ppA, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
    696696        ppB= mapDown (ppB, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
     697        prune1 (alpha);
    697698      }
    698699      coF= N (ppA*(cA/gcdcAcB));
    … …  
    770771          TIMING_END_AND_PRINT (termination_test,
    771772                                "time for successful termination test Fq: ");
     773          prune1 (alpha);
    772774          return N(gcdcAcB*ppH);
    773775        }
    … …  
    13191321  coG= 0;
    13201322  G_m= 0;
    1321   Variable alpha, V_buf;
     1323  Variable alpha, V_buf, cleanUp;
    13221324  bool fail= false;
    13231325  bool inextension= false;
    … …  
    13641366      CanonicalForm mipo;
    13651367      int deg= 2;
    1366       do {
     1368      bool initialized= false;
     1369      do
     1370      {
    13671371        mipo= randomIrredpoly (deg, x);
    1368         alpha= rootOf (mipo);
     1372        if (initialized)
     1373          setMipo (alpha, mipo);
     1374        else
     1375          alpha= rootOf (mipo);
    13691376        inextension= true;
     1377        initialized= true;
    13701378        fail= false;
    13711379        random_element= randomElement (m*lcA*lcB, alpha, l, fail);
    … …  
    13741382      list= CFList();
    13751383      V_buf= alpha;
     1384      cleanUp= alpha;
    13761385      TIMING_START (gcd_recursion);
    13771386      G_random_element=
    … …  
    14611470    if (d0 == 0)
    14621471    {
     1472      if (inextension)
     1473        prune (cleanUp);
    14631474      coF= N (ppA*(cA/gcdcAcB));
    14641475      coG= N (ppB*(cB/gcdcAcB));
    … …  
    15251536           (fdivides (ppH, ppA, ppCoF) && fdivides (ppH, ppB, ppCoG)))
    15261537      {
     1538        if (inextension)
     1539          prune (cleanUp);
    15271540        coF= N ((cA/gcdcAcB)*ppCoF);
    15281541        coG= N ((cB/gcdcAcB)*ppCoG);
    … …  
    22772290        CanonicalForm mipo;
    22782291        int deg= 2;
    2279         do {
     2292        bool initialized= false;
     2293        do
     2294        {
    22802295          mipo= randomIrredpoly (deg, x);
    2281           V_buf= rootOf (mipo);
     2296          if (initialized)
     2297            setMipo (V_buf, mipo);
     2298          else
     2299            V_buf= rootOf (mipo);
    22822300          evalFail= false;
     2301          initialized= true;
    22832302          evalPoints= evaluationPoints (A, B, Aeval, Beval, LCA, GF, V_buf,
    22842303                                        evalFail, list);
    … …  
    22962315      delete[] pEvalPoints;
    22972316      fail= true;
     2317      if (alpha.level() != 1 && V_buf != alpha)
     2318        prune1 (alpha);
    22982319      return 0;
    22992320    }
    … …  
    23052326        delete[] pEvalPoints;
    23062327        fail= true;
     2328        if (alpha.level() != 1 && V_buf != alpha)
     2329          prune1 (alpha);
    23072330        return 0;
    23082331      }
    … …  
    23672390      delete[] coeffMonoms;
    23682391      fail= true;
     2392      if (alpha.level() != 1 && V_buf != alpha)
     2393        prune1 (alpha);
    23692394      return 0;
    23702395    }
    … …  
    23832408    CFList u, v;
    23842409    result= mapDown (result, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
     2410    prune1 (alpha);
    23852411  }
    23862412
    … …  
    25512577          CanonicalForm mipo;
    25522578          int deg= 2;
    2553           do {
     2579          bool initialized= false;
     2580          do
     2581          {
    25542582            mipo= randomIrredpoly (deg, x);
    2555             V_buf= rootOf (mipo);
     2583            if (initialized)
     2584              setMipo (V_buf, mipo);
     2585            else
     2586              V_buf= rootOf (mipo);
    25562587            evalFail= false;
     2588            initialized= true;
    25572589            evalPoints= evaluationPoints (A, B, Aeval, Beval, LCA, GF, V_buf,
    25582590                                          evalFail, list);
    … …  
    25762608      delete[] pEvalPoints;
    25772609      fail= true;
     2610      if (alpha.level() != 1 && V_buf != alpha)
     2611        prune1 (alpha);
    25782612      return 0;
    25792613    }
    … …  
    25852619        delete[] pEvalPoints;
    25862620        fail= true;
     2621        if (alpha.level() != 1 && V_buf != alpha)
     2622          prune1 (alpha);
    25872623        return 0;
    25882624      }
    … …  
    27452781            delete [] bufpEvalPoints;
    27462782          fail= true;
     2783          if (alpha.level() != 1 && V_buf != alpha)
     2784            prune1 (alpha);
    27472785          return 0;
    27482786        }
    … …  
    27602798              delete [] bufpEvalPoints;
    27612799            fail= true;
     2800            if (alpha.level() != 1 && V_buf != alpha)
     2801              prune1 (alpha);
    27622802            return 0;
    27632803          }
    … …  
    28482888          delete [] bufpEvalPoints;
    28492889        fail= true;
     2890        if (alpha.level() != 1 && V_buf != alpha)
     2891          prune1 (alpha);
    28502892        return 0;
    28512893      }
    … …  
    28702912          delete [] bufpEvalPoints;
    28712913        fail= true;
     2914        if (alpha.level() != 1 && V_buf != alpha)
     2915          prune1 (alpha);
    28722916        return 0;
    28732917      }
    … …  
    29062950        delete [] bufpEvalPoints;
    29072951      fail= true;
     2952      if (alpha.level() != 1 && V_buf != alpha)
     2953        prune1 (alpha);
    29082954      return 0;
    29092955    }
    … …  
    29222968      CFList u, v;
    29232969      result= mapDown (result,prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
     2970      prune1 (alpha);
    29242971    }
    29252972    result= N(result);
    … …  
    29873034      delete[] pM;
    29883035      fail= true;
     3036      if (alpha.level() != 1 && V_buf != alpha)
     3037        prune1 (alpha);
    29893038      return 0;
    29903039    }
    … …  
    30073056    CFList u, v;
    30083057    result= mapDown (result, prim_elem, im_prim_elem, alpha, u, v);
     3058    prune1 (alpha);
    30093059  }
    30103060  result= N(result);
    … …  
    31953245
    31963246    if (d0 == 0)
     3247    {
     3248      if (inextension)
     3249        prune1 (alpha);
    31973250      return N(gcdcAcB);
     3251    }
    31983252    if (d0 >  d)
    31993253    {
    … …  
    32383292          ppH /= Lc(ppH);
    32393293          DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
     3294          prune1 (alpha);
    32403295          return N(gcdcAcB*ppH);
    32413296        }
    … …  
    33743429
    33753430        if (d0 == 0)
     3431        {
     3432          if (inextension)
     3433            prune1 (alpha);
    33763434          return N(gcdcAcB);
     3435        }
    33773436        if (d0 >  d)
    33783437        {
    … …  
    34213480              ppH /= Lc(ppH);
    34223481              DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
     3482              prune1 (alpha);
    34233483              return N(gcdcAcB*ppH);
    34243484            }
    … …  
    35183578  topLevel= false;
    35193579  bool inextension= false;
    3520   Variable V_buf, alpha;
     3580  Variable V_buf, alpha, cleanUp;
    35213581  CanonicalForm prim_elem, im_prim_elem;
    35223582  CFList source, dest;
    … …  
    35633623      CanonicalForm mipo;
    35643624      int deg= 2;
     3625      bool initialized= false;
    35653626      do
    35663627      {
    35673628        mipo= randomIrredpoly (deg, x);
    3568         alpha= rootOf (mipo);
     3629        if (initialized)
     3630          setMipo (alpha, mipo);
     3631        else
     3632          alpha= rootOf (mipo);
    35693633        inextension= true;
    35703634        fail= false;
     3635        initialized= true;
    35713636        random_element= randomElement (m, alpha, l, fail);
    35723637        deg++;
    35733638      } while (fail);
     3639      cleanUp= alpha;
    35743640      V_buf= alpha;
    35753641      list= CFList();
    … …  
    36503716
    36513717    if (d0 == 0)
     3718    {
     3719      if (inextension)
     3720        prune (cleanUp);
    36523721      return N(gcdcAcB);
     3722    }
    36533723    if (d0 >  d)
    36543724    {
    … …  
    36883758
    36893759      if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
     3760      {
     3761        if (inextension)
     3762          prune (cleanUp);
    36903763        return N(gcdcAcB*ppH);
     3764      }
    36913765    }
    36923766    G_m= H;
    … …  
    37583832          CanonicalForm mipo;
    37593833          int deg= 2;
     3834          bool initialized= false;
    37603835          do
    37613836          {
    37623837            mipo= randomIrredpoly (deg, x);
    3763             alpha= rootOf (mipo);
     3838            if (initialized)
     3839              setMipo (alpha, mipo);
     3840            else
     3841              alpha= rootOf (mipo);
    37643842            inextension= true;
    37653843            fail= false;
     3844            initialized= true;
    37663845            random_element= randomElement (m, alpha, l, fail);
    37673846            deg++;
    37683847          } while (fail);
     3848          cleanUp= alpha;
    37693849          V_buf= alpha;
    37703850          list= CFList();
    … …  
    38623942
    38633943        if (d0 == 0)
     3944        {
     3945          if (inextension)
     3946            prune (cleanUp);
    38643947          return N(gcdcAcB);
     3948        }
    38653949        if (d0 >  d)
    38663950        {
    … …  
    39013985          DEBOUTLN (cerr, "ppH= " << ppH);
    39023986          if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
     3987          {
     3988            if (inextension)
     3989              prune (cleanUp);
    39033990            return N(gcdcAcB*ppH);
     3991          }
    39043992        }
    39053993
    … …  
    39134001    }
    39144002    else
     4003    {
     4004      if (inextension)
     4005        prune (cleanUp);
    39154006      return N(gcdcAcB*modGCDFp (ppA, ppB));
     4007    }
    39164008  } while (1); //end of first do
    39174009}

  • factory/cfModResultant.cc

    r3169ca r2a2e43  
    2424#include "cf_algorithm.h"
    2525#include "cf_iter.h"
     26#include "cf_irred.h"
     27#include "cf_generator.h"
     28#include "cf_random.h"
     29#include "cf_map_ext.h"
     30#include "facFqBivarUtil.h"
    2631
    2732#ifdef HAVE_NTL
    … …  
    253258  if (F.isZero() || G.isZero())
    254259    return 0;
     260  Variable alpha;
    255261
    256262#ifdef HAVE_FLINT
    257   nmod_poly_t FLINTF, FLINTG;
    258   convertFacCF2nmod_poly_t (FLINTF, F);
    259   convertFacCF2nmod_poly_t (FLINTG, G);
    260   mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
    261   nmod_poly_clear (FLINTF);
    262   nmod_poly_clear (FLINTG);
    263   return CanonicalForm ((long) FLINTresult);
     263  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
     264  {
     265    nmod_poly_t FLINTF, FLINTG;
     266    convertFacCF2nmod_poly_t (FLINTF, F);
     267    convertFacCF2nmod_poly_t (FLINTG, G);
     268    mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
     269    nmod_poly_clear (FLINTF);
     270    nmod_poly_clear (FLINTG);
     271    return CanonicalForm ((long) FLINTresult);
     272  }
    264273#else
     274  if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
     275  {
     276    if (fac_NTL_char != getCharacteristic())
     277    {
     278      fac_NTL_char= getCharacteristic();
     279      zz_p::init (getCharacteristic());
     280    }
     281    zz_pX NTLF= convertFacCF2NTLzzpX (F);
     282    zz_pX NTLG= convertFacCF2NTLzzpX (G);
     283
     284    zz_p NTLResult= resultant (NTLF, NTLG);
     285
     286    return CanonicalForm (to_long (rep (NTLResult)));
     287  }
     288#endif
     289  //at this point F or G has an algebraic var.
    265290  if (fac_NTL_char != getCharacteristic())
    266291  {
    … …  
    268293    zz_p::init (getCharacteristic());
    269294  }
    270   zz_pX NTLF= convertFacCF2NTLzzpX (F);
    271   zz_pX NTLG= convertFacCF2NTLzzpX (G);
    272 
    273   zz_p NTLResult= resultant (NTLF, NTLG);
    274 
    275   return CanonicalForm (to_long (rep (NTLResult)));
    276 #endif
     295  zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
     296  zz_pE::init (NTLMipo);
     297  zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
     298  zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
     299  zz_pE NTLResult= resultant (NTLF, NTLG);
     300
     301  return convertNTLzzpE2CF (NTLResult, alpha);
    277302#else
    278303  return resultant (F, G, F.mvar());
    … …  
    282307static inline
    283308void evalPoint (const CanonicalForm& F, const CanonicalForm& G,
    284                 CanonicalForm& FEval, CanonicalForm& GEval, int& evalPoint)
     309                CanonicalForm& FEval, CanonicalForm& GEval,
     310                CFGenerator& evalPoint)
    285311{
    286312  int degF, degG;
    … …  
    290316  do
    291317  {
    292     evalPoint++;
    293     if (evalPoint >= getCharacteristic())
     318    if (!evalPoint.hasItems())
    294319      break;
    295     FEval= F (evalPoint, 2);
    296     GEval= G (evalPoint, 2);
     320    FEval= F (evalPoint.item(), 2);
     321    GEval= G (evalPoint.item(), 2);
    297322    if (degree (FEval, 1) < degF || degree (GEval, 1) < degG)
     323    {
     324      evalPoint.next();
    298325      continue;
     326    }
    299327    else
    300328      return;
    301329  }
    302   while (evalPoint < getCharacteristic());
     330  while (evalPoint.hasItems());
    303331}
    304332
    … …  
    350378  Variable y= Variable (2);
    351379
    352   int i= -1;
    353380  CanonicalForm GEval, FEval, recResult, H;
    354381  CanonicalForm newtonPoly= 1;
    … …  
    358385  int bound= degAx*degree (G, 2) + degree (F, 2)*degBx;
    359386
     387  int p= getCharacteristic();
     388  CanonicalForm minpoly;
     389  Variable alpha= Variable (tmax (F.level(), G.level()) + 1);
     390  bool algExt= hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha);
     391  CFGenerator * gen;
     392  bool extOfExt= false;
     393  Variable v= alpha;
     394  CanonicalForm primElemAlpha, imPrimElemAlpha;
     395  CFList source,dest;
     396  if (!algExt && (p < (1 << 28)))
     397  {
     398    // pass to an extension of size at least 2^29
     399    // for very very large input that is maybe too small though
     400    int deg= ceil (29.0*((double) log (2)/log (p)))+1;
     401    minpoly= randomIrredpoly (deg, z);
     402    alpha= rootOf (minpoly);
     403    AlgExtGenerator AlgExtGen (alpha);
     404    gen= AlgExtGen.clone();
     405    for (int i= 0; i < p; i++) // skip values from the prime field
     406      (*gen).next();
     407  }
     408  else if (!algExt)
     409  {
     410    FFGenerator FFGen;
     411    gen= FFGen.clone();
     412  }
     413  else
     414  {
     415    int deg= ceil (29.0*((double) log (2)/log (p)));
     416    if (degree (getMipo (alpha)) < deg)
     417    {
     418      mpz_t field_size;
     419      mpz_init (field_size);
     420      mpz_ui_pow_ui (field_size, p,
     421                 deg + degree (getMipo (alpha)) - deg%degree (getMipo (alpha)));
     422
     423      // field_size needs to fit in an int because of mapUp, mapDown, length of lists etc.
     424      if (mpz_fits_sint_p (field_size))
     425      {
     426        minpoly= randomIrredpoly (deg + degree (getMipo (alpha))
     427                                  - deg%degree (getMipo (alpha)), z);
     428        v= rootOf (minpoly);
     429        Variable V_buf2;
     430        bool primFail= false;
     431        extOfExt= true;
     432        primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
     433        ASSERT (!primFail, "failure in integer factorizer");
     434        if (primFail)
     435          ; //ERROR
     436        else
     437          imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
     438        F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
     439        G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
     440      }
     441      else
     442      {
     443        deg= deg - deg % degree (getMipo (alpha));
     444        mpz_ui_pow_ui (field_size, p, deg);
     445        while (deg / degree (getMipo (alpha)) >= 2 && !mpz_fits_sint_p (field_size))
     446        {
     447          deg -= degree (getMipo (alpha));
     448          mpz_ui_pow_ui (field_size, p, deg);
     449        }
     450        if (deg != degree (getMipo (alpha)))
     451        {
     452           minpoly= randomIrredpoly (deg, z);
     453           v= rootOf (minpoly);
     454           Variable V_buf2;
     455           bool primFail= false;
     456           extOfExt= true;
     457           primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
     458           ASSERT (!primFail, "failure in integer factorizer");
     459           if (primFail)
     460             ; //ERROR
     461           else
     462             imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
     463           F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
     464           G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
     465        }
     466      }
     467      mpz_clear (field_size);
     468    }
     469    AlgExtGenerator AlgExtGen (v);
     470    gen= AlgExtGen.clone();
     471    for (int i= 0; i < p; i++)
     472      (*gen).next();
     473  }
    360474  int count= 0;
    361475  int equalCount= 0;
     476  CanonicalForm point;
    362477  do
    363478  {
    364     evalPoint (F, G, FEval, GEval, i);
    365 
    366     ASSERT (i < getCharacteristic(), "ran out of points");
    367 
    368     recResult= resultantFp (FEval, GEval, z);
    369 
    370     H= newtonInterp (i, recResult, newtonPoly, modResult, y);
     479    evalPoint (F, G, FEval, GEval, *gen);
     480
     481    recResult= resultantFp (FEval, GEval, z, prob);
     482
     483    H= newtonInterp ((*gen).item(), recResult, newtonPoly, modResult, y);
    371484
    372485    if (H == modResult)
    … …  
    377490    count++;
    378491    if (count > bound || (prob && equalCount == 2))
    379       break;
     492    {
     493      if (!algExt && degree (H, alpha) <= 0)
     494        break;
     495      else if (algExt)
     496      {
     497        if (extOfExt && !isInExtension (H, imPrimElemAlpha, 1, primElemAlpha,
     498                                        dest, source))
     499        {
     500          H= mapDown (H, primElemAlpha, imPrimElemAlpha, alpha, dest, source);
     501          prune (v);
     502          break;
     503        }
     504        else if (!extOfExt)
     505          break;
     506      }
     507    }
    380508
    381509    modResult= H;
    382     newtonPoly *= (y - i);
     510    newtonPoly *= (y - (*gen).item());
     511    if ((*gen).hasItems())
     512        (*gen).next();
     513    else
     514      STICKYASSERT (0, "out of evaluation points");
    383515  } while (1);
     516
     517  delete gen;
    384518
    385519  return N (H);

  • factory/cf_cyclo.cc

    r3169ca r2a2e43  
    131131  for (int i= 0; i < distinct_factors_length; i++)
    132132  {
    133     result= result (power (x, distinct_factors[i]), x)/result;
     133    result= leftShift (result, distinct_factors[i])/result;
    134134    prod *= distinct_factors[i];
    135135  }
    136   return result (power (x, n/prod), x);
     136  return leftShift (result, n/prod);
    137137}
    138138

  • factory/cf_map_ext.cc

    r3169ca r2a2e43  
    165165{
    166166  Variable beta= rootOf (gf_mipo);
    167   return GF2FalphaHelper (F, beta) (alpha, beta);
     167  CanonicalForm result= GF2FalphaHelper (F, beta) (alpha, beta);
     168  prune (beta);
     169  return result;
    168170}
    169171
    … …  
    339341  primitive= false;
    340342  fail= false;
     343  bool initialized= false;
    341344  do
    342345  {
    343346    BuildIrred (NTL_mipo, d);
    344347    mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
    345     beta= rootOf (mipo2);
     348    if (!initialized)
     349      beta= rootOf (mipo2);
     350    else
     351      setMipo (beta, mipo2);
    346352    primitive= isPrimitive (beta, fail);
    347353    if (primitive)

  • factory/cf_ops.cc

    r3169ca r2a2e43  
    677677  return false;
    678678}
     679
     680/** left shift the main variable of F by n
     681 *  @return if x is the main variable of F the result is F(x^n)
     682 **/
     683CanonicalForm leftShift (const CanonicalForm& F, int n)
     684{
     685  ASSERT (n >= 0, "cannot left shift by negative number");
     686  if (F.inBaseDomain())
     687    return F;
     688  if (n == 0)
     689    return F;
     690  Variable x=F.mvar();
     691  CanonicalForm result= 0;
     692  for (CFIterator i= F; i.hasTerms(); i++)
     693    result += i.coeff()*power (x, i.exp()*n);
     694  return result;
     695}

  • factory/facAlgFunc.cc

    r3169ca r2a2e43  
    367367          j.getItem()= j.getItem() (rb, i.getItem().mvar());
    368368        }
     369        prune (alpha);
    369370      }
    370371      else
    … …  
    463464    if (!isRat && getCharacteristic() == 0)
    464465      Off (SW_RATIONAL);
     466    prune (alpha);
    465467    return L;
    466468  }
    … …  
    10001002      }
    10011003      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
     1004      if (extdeg > 1)
     1005        prune (vminpoly);
    10021006      return Factorlist;
    10031007    }
    … …  
    10151019      }
    10161020      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
     1021      if (extdeg > 1)
     1022        prune (vminpoly);
    10171023      return Factorlist;
    10181024    }

  • factory/facBivar.cc

    r3169ca r2a2e43  
    578578    for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
    579579      iter.getItem()= replacevar (iter.getItem(), vv, v);
     580    prune (vv);
    580581  }
    581582

  • factory/facFqBivar.cc

    r3169ca r2a2e43  
    233233      i.getItem()= CFFactor (buf, i.getItem().exp());
    234234    }
     235    prune (beta);
    235236  }
    236237  else if (alpha.level() != 1)
    … …  
    88508851      for (CFListIterator j= factors; j.hasItem(); j++)
    88518852        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
     8853      prune (vBuf);
    88528854    }
    88538855    else // not able to pass to GF, pass to F_p(\alpha)
    … …  
    88578859      ExtensionInfo info2= ExtensionInfo (v);
    88588860      factors= biFactorize (A, info2);
     8861      prune (v);
    88598862    }
    88608863    return factors;
    … …  
    88708873      ExtensionInfo info2= ExtensionInfo (v);
    88718874      factors= biFactorize (A, info2);
     8875      prune (v);
    88728876    }
    88738877    else
    … …  
    88918895        ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
    88928896        factors= biFactorize (bufA, info2);
     8897        prune (v);
    88938898      }
    88948899      else
    … …  
    89118916        ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
    89128917        factors= biFactorize (bufA, info2);
     8918        prune (v);
    89138919      }
    89148920    }
    … …  
    89338939        ExtensionInfo info2= ExtensionInfo (extension);
    89348940        factors= biFactorize (A.mapinto(), info2);
     8941        prune (vBuf);
    89358942      }
    89368943      else // not able to pass to another GF, pass to F_p(\alpha)
    … …  
    89438950        ExtensionInfo info2= ExtensionInfo (v, extension);
    89448951        factors= biFactorize (A, info2);
     8952        prune (vBuf);
    89458953      }
    89468954    }
    … …  
    89808988        for (CFListIterator i= factors; i.hasItem(); i++)
    89818989          i.getItem()= Falpha2GFRep (i.getItem());
     8990        prune (v1);
    89828991      }
    89838992    }

  • factory/facFqFactorize.cc

    r3169ca r2a2e43  
    20442044    tmp= iter.getItem() (evalPoint, x);
    20452045    tmp /= Lc (tmp);
    2046     if (pos= findItem (factors2, tmp))
     2046    if ((pos= findItem (factors2, tmp)))
    20472047    {
    20482048      result2.append (getItem (factors3, pos));
    … …  
    36473647      for (CFListIterator j= factors; j.hasItem(); j++)
    36483648        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
     3649      prune (vBuf);
    36493650    }
    36503651    else if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
    … …  
    36603661      for (CFListIterator j= factors; j.hasItem(); j++)
    36613662        j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
     3663      prune (vBuf);
    36623664    }
    36633665    else  // not able to pass to GF, pass to F_p(\alpha)
    … …  
    36673669      ExtensionInfo info= ExtensionInfo (v);
    36683670      factors= multiFactorize (A, info);
     3671      prune (v);
    36693672    }
    36703673    return factors;
    … …  
    36803683      ExtensionInfo info= ExtensionInfo (v);
    36813684      factors= multiFactorize (A, info);
     3685      prune (v);
    36823686    }
    36833687    else
    … …  
    37013705        ExtensionInfo info= ExtensionInfo (v, alpha, imPrimElem, primElem);
    37023706        factors= multiFactorize (bufA, info);
     3707        prune (v);
    37033708      }
    37043709      else
    … …  
    37213726        ExtensionInfo info= ExtensionInfo (v, beta, imPrimElem, delta);
    37223727        factors= multiFactorize (bufA, info);
     3728        prune (v);
    37233729      }
    37243730    }
    … …  
    37433749        ExtensionInfo info= ExtensionInfo (extension);
    37443750        factors= multiFactorize (A.mapinto(), info);
     3751        prune (vBuf);
    37453752      }
    37463753      else // not able to pass to another GF, pass to F_p(\alpha)
    … …  
    37533760        ExtensionInfo info= ExtensionInfo (v, extension);
    37543761        factors= multiFactorize (A, info);
     3762        prune (vBuf);
    37553763      }
    37563764    }
    … …  
    37883796        for (CFListIterator i= factors; i.hasItem(); i++)
    37893797          i.getItem()= Falpha2GFRep (i.getItem());
     3798        prune (v1);
    37903799      }
    37913800    }

  • factory/facMul.cc

    r3169ca r2a2e43  
    230230mulFLINTQTrunc (const CanonicalForm& F, const CanonicalForm& G, int m)
    231231{
    232   if (F.inCoeffDomain() || G.inCoeffDomain())
    233     return mod (F*G, power (Variable (1), m));
     232  if (F.inCoeffDomain() && G.inCoeffDomain())
     233    return F*G;
     234  if (F.inCoeffDomain())
     235    return mod (F*G, power (G.mvar(), m));
     236  if (G.inCoeffDomain())
     237    return mod (F*G, power (F.mvar(), m));
    234238  Variable alpha;
    235239  if (hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha))
    … …  
    257261}
    258262
    259 CanonicalForm uniReverse (const CanonicalForm& F, int d)
     263CanonicalForm uniReverse (const CanonicalForm& F, int d, const Variable& x)
    260264{
    261265  if (d == 0)
    262266    return F;
    263267  if (F.inCoeffDomain())
    264     return F*power (Variable (1),d);
    265   Variable x= Variable (1);
     268    return F*power (x,d);
    266269  CanonicalForm result= 0;
    267270  CFIterator i= F;
    … …  
    275278
    276279CanonicalForm
    277 newtonInverse (const CanonicalForm& F, const int n)
     280newtonInverse (const CanonicalForm& F, const int n, const Variable& x)
    278281{
    279282  int l= ilog2(n);
    280283
    281   CanonicalForm g= F [0];
    282 
     284  CanonicalForm g;
     285  if (F.inCoeffDomain())
     286    g= F;
     287  else
     288    g= F [0];
     289
     290  if (!F.inCoeffDomain())
     291    ASSERT (F.mvar() == x, "main variable of F and x differ");
    283292  ASSERT (!g.isZero(), "expected a unit");
    284293
    285294  if (!g.isOne())
    286295    g = 1/g;
    287   Variable x= Variable (1);
    288296  CanonicalForm result;
    289297  int exp= 0;
    … …  
    328336              CanonicalForm& R)
    329337{
     338  ASSERT (F.level() == G.level(), "F and G have different level");
    330339  CanonicalForm A= F;
    331340  CanonicalForm B= G;
    332   Variable x= Variable (1);
    333   int degA= degree (A, x);
    334   int degB= degree (B, x);
     341  Variable x= A.mvar();
     342  int degA= degree (A);
     343  int degB= degree (B);
    335344  int m= degA - degB;
    336345
    … …  
    346355  else
    347356  {
    348     R= uniReverse (A, degA);
    349 
    350     CanonicalForm revB= uniReverse (B, degB);
    351     CanonicalForm buf= revB;
    352     revB= newtonInverse (revB, m + 1);
     357    R= uniReverse (A, degA, x);
     358
     359    CanonicalForm revB= uniReverse (B, degB, x);
     360    revB= newtonInverse (revB, m + 1, x);
    353361    Q= mulFLINTQTrunc (R, revB, m + 1);
    354     Q= uniReverse (Q, m);
     362    Q= uniReverse (Q, m, x);
    355363
    356364    R= A - mulNTL (Q, B);
    … …  
    361369newtonDiv (const CanonicalForm& F, const CanonicalForm& G, CanonicalForm& Q)
    362370{
     371  ASSERT (F.level() == G.level(), "F and G have different level");
    363372  CanonicalForm A= F;
    364373  CanonicalForm B= G;
    365   Variable x= Variable (1);
    366   int degA= degree (A, x);
    367   int degB= degree (B, x);
     374  Variable x= A.mvar();
     375  int degA= degree (A);
     376  int degB= degree (B);
    368377  int m= degA - degB;
    369378
    … …  
    378387  else
    379388  {
    380     CanonicalForm R= uniReverse (A, degA);
    381 
    382     CanonicalForm revB= uniReverse (B, degB);
    383     revB= newtonInverse (revB, m + 1);
     389    CanonicalForm R= uniReverse (A, degA, x);
     390    CanonicalForm revB= uniReverse (B, degB, x);
     391    revB= newtonInverse (revB, m + 1, x);
    384392    Q= mulFLINTQTrunc (R, revB, m + 1);
    385     Q= uniReverse (Q, m);
     393    Q= uniReverse (Q, m, x);
    386394  }
    387395}
    … …  
    36953703  }
    36963704  CanonicalForm Q, R;
    3697   Variable x= Variable (1);
    3698   Variable y= Variable (2);
    3699   newtonDivrem (swapvar (B, y, x), swapvar (A, y, x), Q, R);
     3705  newtonDivrem (B, A, Q, R);
    37003706  if (!isRat)
    37013707    Off (SW_RATIONAL);

  • factory/variable.cc

    r3169ca r2a2e43  
    220220{
    221221    ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
     222    algextensions[-alpha.level()]= ext_entry( 0, false );
    222223    algextensions[-alpha.level()]= ext_entry((InternalPoly*)(conv2mipo( mipo, alpha ).getval()), true );
    223224}
    … …  
    256257    return 0;
    257258  return strlen( var_names_ext )-1;
     259}
     260
     261void prune (Variable& alpha)
     262{
     263  int i, n = strlen( var_names_ext );
     264  ASSERT (n+1 >= -alpha.level(), "wrong variable");
     265  if (-alpha.level() == 1)
     266  {
     267    delete [] var_names_ext;
     268    delete [] algextensions;
     269    var_names_ext= 0;
     270    algextensions= 0;
     271    alpha= Variable();
     272    return;
     273  }
     274  char * newvarnames = new char [-alpha.level() + 1];
     275  for ( i = 0; i < -alpha.level(); i++ )
     276    newvarnames[i] = var_names_ext[i];
     277  newvarnames[-alpha.level()] = 0;
     278  delete [] var_names_ext;
     279  var_names_ext = newvarnames;
     280  ext_entry * newalgext = new ext_entry [-alpha.level()];
     281  for ( i = 0; i < -alpha.level(); i++ )
     282    newalgext[i] = algextensions[i];
     283  delete [] algextensions;
     284  algextensions = newalgext;
     285  alpha= Variable();
     286}
     287
     288void prune1 (const Variable& alpha)
     289{
     290  int i, n = strlen( var_names_ext );
     291  ASSERT (n+1 >= -alpha.level(), "wrong variable");
     292
     293  char * newvarnames = new char [-alpha.level() + 2];
     294  for ( i = 0; i <= -alpha.level(); i++ )
     295    newvarnames[i] = var_names_ext[i];
     296  newvarnames[-alpha.level()+1] = 0;
     297  delete [] var_names_ext;
     298  var_names_ext = newvarnames;
     299  ext_entry * newalgext = new ext_entry [-alpha.level()+1];
     300  for ( i = 0; i <= -alpha.level(); i++ )
     301    newalgext[i] = algextensions[i];
     302  delete [] algextensions;
     303  algextensions = newalgext;
    258304}
    259305

  • factory/variable.h

    r3169ca r2a2e43  
    103103char getDefaultExtName();
    104104
     105void prune (Variable& alpha);
     106void prune1 (const Variable& alpha);
    105107int ExtensionLevel();
    106108

  • libpolys/polys/clapsing.cc

    r3169ca r2a2e43  
    124124                    G( convSingAPFactoryAP( g,a,r ) );
    125125      res= convFactoryAPSingAP( gcd( F, G ),r );
     126      prune (a);
    126127      if (!b1) Off(SW_USE_QGCD);
    127128    }
    … …  
    235236      }
    236237      res= convFactoryAPSingAP( GCD,r );
     238      prune (a);
    237239      if (!b1) Off(SW_USE_QGCD);
    238240    }
    … …  
    343345                    G( convSingAPFactoryAP( g,a,r ) );
    344346      res= convFactoryAPSingAP( resultant( F, G, X ),r );
     347      prune (a);
    345348    }
    346349    else
    … …  
    497500      pa=convFactoryAPSingAP(Fa,r);
    498501      pb=convFactoryAPSingAP(Gb,r);
     502      prune (a);
    499503    }
    500504    else
    … …  
    556560                    G( convSingAPFactoryAP( g,a,r ) );
    557561      res= convFactoryAPSingAP(  F / G, r  );
     562      prune (a);
    558563    }
    559564    else
    … …  
    745750      }
    746751    }
     752    if (r->cf->extRing!=NULL)
     753      if (r->cf->extRing->qideal!=NULL)
     754        prune (a);
    747755    if (e==0)
    748756    {
    … …  
    841849  number old_lead_coeff=n_Copy(pGetCoeff(f), r->cf);
    842850
     851  Variable a;
    843852  if (!rField_is_Zp(r) && !rField_is_Zp_a(r)) /* Q, Q(a) */
    844853  {
    … …  
    894903      CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->qideal->m[0],
    895904                                           r->cf->extRing);
    896       Variable a=rootOf(mipo);
     905      a=rootOf(mipo);
    897906      CanonicalForm F( convSingAPFactoryAP( f, a, r ) );
    898907      if (rField_is_Zp_a(r))
    … …  
    982991      }
    983992    }
     993    if (r->cf->extRing!=NULL)
     994      if (r->cf->extRing->qideal!=NULL)
     995        prune (a);
    984996#ifndef SING_NDEBUG
    985997    if ((r->cf->extRing!=NULL) && (!p_IsConstantPoly(ff,r)))
    … …  
    12101222  number NN=NULL;
    12111223  number old_lead_coeff=n_Copy(pGetCoeff(f), r->cf);
     1224  Variable a;
    12121225
    12131226  if (!rField_is_Zp(r) && !rField_is_Zp_a(r)) /* Q, Q(a) */
    … …  
    12611274      CanonicalForm mipo=convSingPFactoryP(r->cf->extRing->qideal->m[0],
    12621275                                           r->cf->extRing);
    1263       Variable a=rootOf(mipo);
     1276      a=rootOf(mipo);
    12641277      CanonicalForm F( convSingAPFactoryAP( f, a, r ) );
    12651278      L= sqrFree (F);
    … …  
    13361349    }
    13371350  }
     1351  if (r->cf->extRing!=NULL)
     1352    if (r->cf->extRing->qideal!=NULL)
     1353      prune (a);
    13381354  if (rField_is_Q_a(r) && (r->cf->extRing->qideal!=NULL))
    13391355  {
    … …  
    17941810      mipos->m[i]= convFactoryPSingTrP (replacevar (iter.getItem().minpoly(), alpha, x), r);
    17951811    }
     1812    if (!iter.getItem().minpoly().isOne())
     1813      prune (alpha);
    17961814    numFactors += count;
    17971815  }
Note: See TracChangeset for help on using the changeset viewer.