Functions
cfEzgcd.h File Reference

Extended Zassenhaus GCD over finite fields and Z. More...

Go to the source code of this file.

Functions

CanonicalForm EZGCD_P (const CanonicalForm &A, const CanonicalForm &B)
 Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm. More...
 
CanonicalForm ezgcd (const CanonicalForm &f, const CanonicalForm &g)
 Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm. More...
 

Detailed Description

Extended Zassenhaus GCD over finite fields and Z.

Definition in file cfEzgcd.h.

Function Documentation

§ ezgcd()

Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.

Definition at line 783 of file cfEzgcd.cc.

784 {
785 #ifdef HAVE_NTL
786  REvaluation b;
787  return ezgcd( FF, GG, b, false );
788 #else
789  Off (SW_USE_EZGCD);
790  return gcd (FF, GG);
791  On (SW_USE_EZGCD);
792 #endif
793 }
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:438
void Off(int sw)
switches
class to generate random evaluation points
Definition: cf_reval.h:25
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
void On(int sw)
switches
int gcd(int a, int b)
Definition: walkSupport.cc:839
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
const poly b
Definition: syzextra.cc:213

§ EZGCD_P()

CanonicalForm EZGCD_P ( const CanonicalForm A,
const CanonicalForm B 
)

Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.

Definition at line 802 of file cfEzgcd.cc.

803 {
804  if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
805  else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
806  else if (FF.isZero() && GG.isZero()) return FF.genOne();
807  if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
808  if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
809  if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
810  if (FF == GG) return FF/Lc(FF);
811 
812  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
813  Variable a, oldA;
814  int sizeF= size (FF);
815  int sizeG= size (GG);
816 
817  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
818  {
819  if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
820  return modGCDFq (FF, GG, a);
822  return modGCDGF (FF, GG);
823  else
824  return modGCDFp (FF, GG);
825  }
826 
827  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
828  lcD;
829  CFArray DD( 1, 2 ), lcDD( 1, 2 );
830  int degF, degG, delta, count;
831  int maxeval;
832  maxeval= tmin((getCharacteristic()/
833  (int)(ilog2(getCharacteristic())*log2exp))*2, maxNumEval);
834  count= 0; // number of eval. used
835  REvaluation b, bt;
836  int gcdfound = 0;
837  Variable x = Variable(1);
838 
839  F= FF;
840  G= GG;
841 
842  CFMap M,N;
843  int smallestDegLev;
844  TIMING_START (ez_p_compress)
845  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
846 
847  if (best_level == 0) return G.genOne();
848 
849  F= M (F);
850  G= M (G);
851  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
852 
853  TIMING_START (ez_p_content)
854  f = content( F, x ); g = content( G, x );
855  d = gcd( f, g );
856  F /= f; G /= g;
857  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
858 
859  if( F.isUnivariate() && G.isUnivariate() )
860  {
861  if( F.mvar() == G.mvar() )
862  d *= gcd( F, G );
863  else
864  return N (d);
865  return N (d);
866  }
867  if ( F.isUnivariate())
868  {
869  g= content (G,G.mvar());
870  return N(d*gcd(F,g));
871  }
872  if ( G.isUnivariate())
873  {
874  f= content (F,F.mvar());
875  return N(d*gcd(G,f));
876  }
877 
878  maxNumVars= tmax (getNumVars (F), getNumVars (G));
879  sizeF= size (F);
880  sizeG= size (G);
881 
882  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
883  {
884  if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
885  return N (d*modGCDFq (F, G, a));
887  return N (d*modGCDGF (F, G));
888  else
889  return N (d*modGCDFp (F, G));
890  }
891 
892  int dummy= 0;
893  if( gcd_test_one( F, G, false, dummy ) )
894  {
895  return N (d);
896  }
897 
898  bool passToGF= false;
899  bool extOfExt= false;
900  int p= getCharacteristic();
901  bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
902  int k= 1;
903  CanonicalForm primElem, imPrimElem;
904  CFList source, dest;
905  if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
906  {
907  if (p == 2)
908  setCharacteristic (2, 12, 'Z');
909  else if (p == 3)
910  setCharacteristic (3, 4, 'Z');
911  else if (p == 5 || p == 7)
912  setCharacteristic (p, 3, 'Z');
913  else
914  setCharacteristic (p, 2, 'Z');
915  passToGF= true;
916  F= F.mapinto();
917  G= G.mapinto();
918  maxeval= 2*ipower (p, getGFDegree());
919  }
920  else if (CFFactory::gettype() == GaloisFieldDomain &&
921  ipower (p , getGFDegree()) < 50)
922  {
923  k= getGFDegree();
924  if (ipower (p, 2*k) > 50)
925  setCharacteristic (p, 2*k, gf_name);
926  else
927  setCharacteristic (p, 3*k, gf_name);
928  F= GFMapUp (F, k);
929  G= GFMapUp (G, k);
930  maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
931  }
932  else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
933  {
934  int d= degree (getMipo (a));
935  oldA= a;
936  Variable v2;
937  if (p == 2 && d < 6)
938  {
939  if (fac_NTL_char != p)
940  {
941  fac_NTL_char= p;
942  zz_p::init (p);
943  }
944  bool primFail= false;
945  Variable vBuf;
946  primElem= primitiveElement (a, vBuf, primFail);
947  ASSERT (!primFail, "failure in integer factorizer");
948  if (d < 3)
949  {
950  zz_pX NTLIrredpoly;
951  BuildIrred (NTLIrredpoly, d*3);
952  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
953  v2= rootOf (newMipo);
954  }
955  else
956  {
957  zz_pX NTLIrredpoly;
958  BuildIrred (NTLIrredpoly, d*2);
959  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
960  v2= rootOf (newMipo);
961  }
962  imPrimElem= mapPrimElem (primElem, a, v2);
963  extOfExt= true;
964  }
965  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
966  {
967  if (fac_NTL_char != p)
968  {
969  fac_NTL_char= p;
970  zz_p::init (p);
971  }
972  bool primFail= false;
973  Variable vBuf;
974  primElem= primitiveElement (a, vBuf, primFail);
975  ASSERT (!primFail, "failure in integer factorizer");
976  zz_pX NTLIrredpoly;
977  BuildIrred (NTLIrredpoly, d*2);
978  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
979  v2= rootOf (newMipo);
980  imPrimElem= mapPrimElem (primElem, a, v2);
981  extOfExt= true;
982  }
983  if (extOfExt)
984  {
985  maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
986  F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
987  G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
988  a= v2;
989  }
990  }
991 
992  lcF = LC( F, x ); lcG = LC( G, x );
993  lcD = gcd( lcF, lcG );
994 
995  delta = 0;
996  degF = degree( F, x ); degG = degree( G, x );
997 
998  if (algExtension)
999  b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
1000  else
1001  { // both not in extension given by algebraic variable
1003  b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
1004  else
1005  b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
1006  }
1007 
1008  CanonicalForm cand, contcand;
1010  int o, t;
1011  o= 0;
1012  t= 1;
1013  int goodPointCount= 0;
1014  while( !gcdfound )
1015  {
1016  TIMING_START (ez_p_eval);
1017  if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
1018  maxeval/maxNumVars, t ))
1019  { // too many eval. used --> try another method
1020  Off (SW_USE_EZGCD_P);
1021  result= gcd (F,G);
1022  On (SW_USE_EZGCD_P);
1023  if (passToGF)
1024  {
1025  CanonicalForm mipo= gf_mipo;
1026  setCharacteristic (p);
1027  Variable alpha= rootOf (mipo.mapinto());
1028  result= GF2FalphaRep (result, alpha);
1029  prune (alpha);
1030  }
1031  if (k > 1)
1032  {
1033  result= GFMapDown (result, k);
1034  setCharacteristic (p, k, gf_name);
1035  }
1036  if (extOfExt)
1037  {
1038  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1039  prune1 (oldA);
1040  }
1041  return N (d*result);
1042  }
1043  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
1044  delta = degree( Db );
1045  if (delta == degF)
1046  {
1047  if (degF <= degG && fdivides (F, G))
1048  {
1049  if (passToGF)
1050  {
1051  CanonicalForm mipo= gf_mipo;
1052  setCharacteristic (p);
1053  Variable alpha= rootOf (mipo.mapinto());
1054  F= GF2FalphaRep (F, alpha);
1055  prune (alpha);
1056  }
1057  if (k > 1)
1058  {
1059  F= GFMapDown (F, k);
1060  setCharacteristic (p, k, gf_name);
1061  }
1062  if (extOfExt)
1063  {
1064  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1065  prune1 (oldA);
1066  }
1067  return N (d*F);
1068  }
1069  else
1070  delta--;
1071  }
1072  else if (delta == degG)
1073  {
1074  if (degG <= degF && fdivides (G, F))
1075  {
1076  if (passToGF)
1077  {
1078  CanonicalForm mipo= gf_mipo;
1079  setCharacteristic (p);
1080  Variable alpha= rootOf (mipo.mapinto());
1081  G= GF2FalphaRep (G, alpha);
1082  prune (alpha);
1083  }
1084  if (k > 1)
1085  {
1086  G= GFMapDown (G, k);
1087  setCharacteristic (p, k, gf_name);
1088  }
1089  if (extOfExt)
1090  {
1091  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1092  prune1 (oldA);
1093  }
1094  return N (d*G);
1095  }
1096  else
1097  delta--;
1098  }
1099  if( delta == 0 )
1100  {
1101  if (passToGF)
1102  setCharacteristic (p);
1103  if (k > 1)
1104  setCharacteristic (p, k, gf_name);
1105  return N (d);
1106  }
1107  while( true )
1108  {
1109  bt = b;
1110  TIMING_START (ez_p_eval);
1111  if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1112  maxeval/maxNumVars, t ))
1113  { // too many eval. used --> try another method
1114  Off (SW_USE_EZGCD_P);
1115  result= gcd (F,G);
1116  On (SW_USE_EZGCD_P);
1117  if (passToGF)
1118  {
1119  CanonicalForm mipo= gf_mipo;
1120  setCharacteristic (p);
1121  Variable alpha= rootOf (mipo.mapinto());
1122  result= GF2FalphaRep (result, alpha);
1123  prune (alpha);
1124  }
1125  if (k > 1)
1126  {
1127  result= GFMapDown (result, k);
1128  setCharacteristic (p, k, gf_name);
1129  }
1130  if (extOfExt)
1131  {
1132  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1133  prune1 (oldA);
1134  }
1135  return N (d*result);
1136  }
1137  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
1138  int dd = degree( Dbt );
1139  if( dd == 0 )
1140  {
1141  if (passToGF)
1142  setCharacteristic (p);
1143  if (k > 1)
1144  setCharacteristic (p, k, gf_name);
1145  return N (d);
1146  }
1147  if( dd == delta )
1148  {
1149  goodPointCount++;
1150  if (goodPointCount == 5)
1151  break;
1152  }
1153  if( dd < delta )
1154  {
1155  goodPointCount= 0;
1156  delta = dd;
1157  b = bt;
1158  Db = Dbt; Fb = Fbt; Gb = Gbt;
1159  }
1160  if (delta == degF)
1161  {
1162  if (degF <= degG && fdivides (F, G))
1163  {
1164  if (passToGF)
1165  {
1166  CanonicalForm mipo= gf_mipo;
1167  setCharacteristic (p);
1168  Variable alpha= rootOf (mipo.mapinto());
1169  F= GF2FalphaRep (F, alpha);
1170  prune (alpha);
1171  }
1172  if (k > 1)
1173  {
1174  F= GFMapDown (F, k);
1175  setCharacteristic (p, k, gf_name);
1176  }
1177  if (extOfExt)
1178  {
1179  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1180  prune1 (oldA);
1181  }
1182  return N (d*F);
1183  }
1184  else
1185  delta--;
1186  }
1187  else if (delta == degG)
1188  {
1189  if (degG <= degF && fdivides (G, F))
1190  {
1191  if (passToGF)
1192  {
1193  CanonicalForm mipo= gf_mipo;
1194  setCharacteristic (p);
1195  Variable alpha= rootOf (mipo.mapinto());
1196  G= GF2FalphaRep (G, alpha);
1197  prune (alpha);
1198  }
1199  if (k > 1)
1200  {
1201  G= GFMapDown (G, k);
1202  setCharacteristic (p, k, gf_name);
1203  }
1204  if (extOfExt)
1205  {
1206  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1207  prune1 (oldA);
1208  }
1209  return N (d*G);
1210  }
1211  else
1212  delta--;
1213  }
1214  if( delta == 0 )
1215  {
1216  if (passToGF)
1217  setCharacteristic (p);
1218  if (k > 1)
1219  setCharacteristic (p, k, gf_name);
1220  return N (d);
1221  }
1222  }
1223  if( delta != degF && delta != degG )
1224  {
1225  bool B_is_F;
1226  CanonicalForm xxx1, xxx2;
1228  DD[1] = Fb / Db;
1229  buf= Gb/Db;
1230  xxx1 = gcd( DD[1], Db );
1231  xxx2 = gcd( buf, Db );
1232  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1233  (size (F) <= size (G)))
1234  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
1235  {
1236  B = F;
1237  DD[2] = Db;
1238  lcDD[1] = lcF;
1239  lcDD[2] = lcD;
1240  B_is_F = true;
1241  }
1242  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1243  (size (G) < size (F)))
1244  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
1245  {
1246  DD[1] = buf;
1247  B = G;
1248  DD[2] = Db;
1249  lcDD[1] = lcG;
1250  lcDD[2] = lcD;
1251  B_is_F = false;
1252  }
1253  else // special case handling
1254  {
1255  Off (SW_USE_EZGCD_P);
1256  result= gcd (F,G);
1257  On (SW_USE_EZGCD_P);
1258  if (passToGF)
1259  {
1260  CanonicalForm mipo= gf_mipo;
1261  setCharacteristic (p);
1262  Variable alpha= rootOf (mipo.mapinto());
1263  result= GF2FalphaRep (result, alpha);
1264  prune (alpha);
1265  }
1266  if (k > 1)
1267  {
1268  result= GFMapDown (result, k);
1269  setCharacteristic (p, k, gf_name);
1270  }
1271  if (extOfExt)
1272  {
1273  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1274  prune1 (oldA);
1275  }
1276  return N (d*result);
1277  }
1278  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
1279  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
1280 
1281  if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
1282  {
1283  if (algExtension)
1284  {
1285  result= modGCDFq (F, G, a);
1286  if (extOfExt)
1287  {
1288  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1289  prune1 (oldA);
1290  }
1291  return N (d*result);
1292  }
1294  {
1295  result= modGCDGF (F, G);
1296  if (passToGF)
1297  {
1298  CanonicalForm mipo= gf_mipo;
1299  setCharacteristic (p);
1300  Variable alpha= rootOf (mipo.mapinto());
1301  result= GF2FalphaRep (result, alpha);
1302  prune (alpha);
1303  }
1304  if (k > 1)
1305  {
1306  result= GFMapDown (result, k);
1307  setCharacteristic (p, k, gf_name);
1308  }
1309  return N (d*result);
1310  }
1311  else
1312  return N (d*modGCDFp (F,G));
1313  }
1314 
1315  TIMING_START (ez_p_hensel_lift);
1316  gcdfound= Hensel (B*lcD, DD, b, lcDD);
1317  TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
1318 
1319  if (gcdfound == -1) //things became dense
1320  {
1321  if (algExtension)
1322  {
1323  result= modGCDFq (F, G, a);
1324  if (extOfExt)
1325  {
1326  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1327  prune1 (oldA);
1328  }
1329  return N (d*result);
1330  }
1332  {
1333  result= modGCDGF (F, G);
1334  if (passToGF)
1335  {
1336  CanonicalForm mipo= gf_mipo;
1337  setCharacteristic (p);
1338  Variable alpha= rootOf (mipo.mapinto());
1339  result= GF2FalphaRep (result, alpha);
1340  prune (alpha);
1341  }
1342  if (k > 1)
1343  {
1344  result= GFMapDown (result, k);
1345  setCharacteristic (p, k, gf_name);
1346  }
1347  return N (d*result);
1348  }
1349  else
1350  {
1351  if (p >= cf_getBigPrime(0))
1352  return N (d*sparseGCDFp (F,G));
1353  else
1354  return N (d*modGCDFp (F,G));
1355  }
1356  }
1357 
1358  if (gcdfound == 1)
1359  {
1360  TIMING_START (termination_test);
1361  contcand= content (DD[2], Variable (1));
1362  cand = DD[2] / contcand;
1363  if (B_is_F)
1364  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1365  else
1366  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
1367  TIMING_END_AND_PRINT (termination_test,
1368  "time for termination test EZ_P: ");
1369 
1370  if (passToGF && gcdfound)
1371  {
1372  CanonicalForm mipo= gf_mipo;
1373  setCharacteristic (p);
1374  Variable alpha= rootOf (mipo.mapinto());
1375  cand= GF2FalphaRep (cand, alpha);
1376  prune (alpha);
1377  }
1378  if (k > 1 && gcdfound)
1379  {
1380  cand= GFMapDown (cand, k);
1381  setCharacteristic (p, k, gf_name);
1382  }
1383  if (extOfExt && gcdfound)
1384  {
1385  cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
1386  prune1 (oldA);
1387  }
1388  }
1389  }
1390  delta--;
1391  goodPointCount= 0;
1392  }
1393  return N (d*cand);
1394 }
int status int void size_t count
Definition: si_signals.h:59
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ...
Definition: cf_map_ext.cc:90
generate random elements in GF
Definition: cf_random.h:31
const poly a
Definition: syzextra.cc:212
void prune1(const Variable &alpha)
Definition: variable.cc:288
return
Definition: syzextra.cc:280
void Off(int sw)
switches
const CanonicalForm CFMap & M
Definition: cfEzgcd.cc:49
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to ...
Definition: cf_map_ext.cc:310
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
static bool findeval(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Fb, CanonicalForm &Gb, CanonicalForm &Db, REvaluation &b, int delta, int degF, int degG, int maxeval, int &count, int &k, int bound, int &l)
Definition: cfEzgcd.cc:371
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503
CanonicalForm gf_mipo(0)
factory&#39;s main class
Definition: canonicalform.h:75
char gf_name
Definition: gfops.cc:52
class to generate random evaluation points
Definition: cf_reval.h:25
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:251
g
Definition: cfModGcd.cc:4031
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:860
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
static const double log2exp
Definition: cfEzgcd.cc:40
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm mapinto() const
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
CanonicalForm lc(const CanonicalForm &f)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition: cfGcdUtil.cc:21
clock_t to
Definition: walk.cc:99
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
bool inBaseDomain() const
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int status int void * buf
Definition: si_signals.h:59
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:66
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:243
bool isUnivariate() const
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
void On(int sw)
switches
FILE * f
Definition: checklibs.c:7
generate random elements in F_p
Definition: cf_random.h:43
int ilog2(const CanonicalForm &a)
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg...
Definition: cfModGcd.cc:467
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
generate random elements in F_p(alpha)
Definition: cf_random.h:70
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
static int maxNumEval
Definition: cfEzgcd.cc:797
static int gettype()
Definition: cf_factory.h:27
const CanonicalForm & G
Definition: cfEzgcd.cc:49
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
b *CanonicalForm B
Definition: facBivar.cc:51
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define TIMING_START(t)
Definition: timing.h:87
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition: cfEzgcd.cc:290
int maxNumVars
Definition: cfModGcd.cc:4071
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm genOne() const
long fac_NTL_char
Definition: NTLconvert.cc:44
int degree(const CanonicalForm &f)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
if(both_non_zero==0)
Definition: cfEzgcd.cc:85
CanonicalForm LC(const CanonicalForm &f)
const poly b
Definition: syzextra.cc:213
static int sizePerVars1
Definition: cfEzgcd.cc:798
return result
Definition: facAbsBiFact.cc:76
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const