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

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
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
return
Definition: syzextra.cc:280
void Off(int sw)
switches
bool inCoeffDomain() const
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: variable.h:32
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)
void prune1(const Variable &alpha)
Definition: variable.cc:288
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
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm Lc(const CanonicalForm &f)
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
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
CanonicalForm lc(const CanonicalForm &f)
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:100
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
CanonicalForm genOne() 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 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
CanonicalForm mapinto() const
FILE * f
Definition: checklibs.c:7
generate random elements in F_p
Definition: cf_random.h:43
void prune(Variable &alpha)
Definition: variable.cc:261
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
bool isUnivariate() const
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
bool inBaseDomain() const
int maxNumVars
Definition: cfModGcd.cc:4071
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
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
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)