My Project
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 861 of file cfEzgcd.cc.

862 {
863  REvaluation b;
864  return ezgcd( FF, GG, b, false );
865 }
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:498
const CanonicalForm & GG
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4105
class to generate random evaluation points
Definition: cf_reval.h:26

◆ 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 876 of file cfEzgcd.cc.

877 {
878  if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
879  else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
880  else if (FF.isZero() && GG.isZero()) return FF.genOne();
881  if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
882  if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
883  if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
884  if (FF == GG) return FF/Lc(FF);
885 
886  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
887  Variable a, oldA;
888  int sizeF= size (FF);
889  int sizeG= size (GG);
890 
891  if (sizeF==1)
892  {
893  return gcd_mon( FF, GG );
894  }
895  else if (sizeG==1)
896  {
897  return gcd_mon( GG, FF );
898  }
899 
900  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
901  {
902  if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
903  return modGCDFq (FF, GG, a);
905  return modGCDGF (FF, GG);
906  else
907  return modGCDFp (FF, GG);
908  }
909 
910  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
911  lcD;
912  CFArray DD( 1, 2 ), lcDD( 1, 2 );
913  int degF, degG, delta, count;
914  int maxeval;
915  int ch=getCharacteristic();
916  maxeval= tmin((ch/
917  (int)(ilog2(ch)*log2exp))*2, maxNumEval);
918  count= 0; // number of eval. used
919  REvaluation b, bt;
920  int gcdfound = 0;
921  Variable x = Variable(1);
922 
923  F= FF;
924  G= GG;
925 
926  CFMap M,N;
927  int smallestDegLev;
928  TIMING_DEFINE(ez_p_compress);
929  TIMING_START (ez_p_compress);
930  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
931 
932  if (best_level == 0) return G.genOne();
933 
934  F= M (F);
935  G= M (G);
936  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
937 
938  TIMING_DEFINE (ez_p_content)
939  TIMING_START (ez_p_content)
940  f = content( F, x ); g = content( G, x );
941  d = gcd( f, g );
942  F /= f; G /= g;
943  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
944 
945  if( F.isUnivariate() && G.isUnivariate() )
946  {
947  if( F.mvar() == G.mvar() )
948  d *= gcd( F, G );
949  else
950  return N (d);
951  return N (d);
952  }
953  if ( F.isUnivariate())
954  {
955  g= content (G,G.mvar());
956  return N(d*gcd(F,g));
957  }
958  if ( G.isUnivariate())
959  {
960  f= content (F,F.mvar());
961  return N(d*gcd(G,f));
962  }
963 
965  sizeF= size (F);
966  sizeG= size (G);
967 
968  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
969  {
970  if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
971  return N (d*modGCDFq (F, G, a));
973  return N (d*modGCDGF (F, G));
974  else
975  return N (d*modGCDFp (F, G));
976  }
977 
978  int dummy= 0;
979  if( gcd_test_one( F, G, false, dummy ) )
980  {
981  return N (d);
982  }
983 
984  bool passToGF= false;
985  bool extOfExt= false;
986  int p= getCharacteristic();
987  bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
988  int k= 1;
989  CanonicalForm primElem, imPrimElem;
990  CFList source, dest;
991  if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
992  {
993  if (p == 2)
994  setCharacteristic (2, 12, 'Z');
995  else if (p == 3)
996  setCharacteristic (3, 4, 'Z');
997  else if (p == 5 || p == 7)
998  setCharacteristic (p, 3, 'Z');
999  else
1000  setCharacteristic (p, 2, 'Z');
1001  passToGF= true;
1002  F= F.mapinto();
1003  G= G.mapinto();
1004  maxeval= 2*ipower (p, getGFDegree());
1005  }
1006  else if (CFFactory::gettype() == GaloisFieldDomain &&
1007  ipower (p , getGFDegree()) < 50)
1008  {
1009  k= getGFDegree();
1010  if (ipower (p, 2*k) > 50)
1011  setCharacteristic (p, 2*k, gf_name);
1012  else
1013  setCharacteristic (p, 3*k, gf_name);
1014  F= GFMapUp (F, k);
1015  G= GFMapUp (G, k);
1016  maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
1017  }
1018  else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
1019  {
1020  int d= degree (getMipo (a));
1021  oldA= a;
1022  Variable v2;
1023  if (p == 2 && d < 6)
1024  {
1025  bool primFail= false;
1026  Variable vBuf;
1027  primElem= primitiveElement (a, vBuf, primFail);
1028  ASSERT (!primFail, "failure in integer factorizer");
1029  if (d < 3)
1030  {
1031  #ifdef HAVE_FLINT
1032  nmod_poly_t Irredpoly;
1033  nmod_poly_init(Irredpoly,p);
1034  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
1035  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
1036  nmod_poly_clear(Irredpoly);
1037  #elif defined(HAVE_NTL)
1038  if (fac_NTL_char != p)
1039  {
1040  fac_NTL_char= p;
1041  zz_p::init (p);
1042  }
1043  zz_pX NTLIrredpoly;
1044  BuildIrred (NTLIrredpoly, d*3);
1045  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1046  #else
1047  factoryError("NTL/FLINT missing: EZGCD_P");
1048  #endif
1049  v2= rootOf (newMipo);
1050  }
1051  else
1052  {
1053  #ifdef HAVE_FLINT
1054  nmod_poly_t Irredpoly;
1055  nmod_poly_init(Irredpoly,p);
1056  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
1057  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
1058  nmod_poly_clear(Irredpoly);
1059  #elif defined(HAVE_NTL)
1060  if (fac_NTL_char != p)
1061  {
1062  fac_NTL_char= p;
1063  zz_p::init (p);
1064  }
1065  zz_pX NTLIrredpoly;
1066  BuildIrred (NTLIrredpoly, d*2);
1067  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1068  #else
1069  factoryError("NTL/FLINT missing: EZGCD_P");
1070  #endif
1071  v2= rootOf (newMipo);
1072  }
1073  imPrimElem= mapPrimElem (primElem, a, v2);
1074  extOfExt= true;
1075  }
1076  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
1077  {
1078  bool primFail= false;
1079  Variable vBuf;
1080  primElem= primitiveElement (a, vBuf, primFail);
1081  ASSERT (!primFail, "failure in integer factorizer");
1082  #ifdef HAVE_FLINT
1083  nmod_poly_t Irredpoly;
1084  nmod_poly_init(Irredpoly,p);
1085  nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
1086  CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
1087  nmod_poly_clear(Irredpoly);
1088  #elif defined(HAVE_NTL)
1089  if (fac_NTL_char != p)
1090  {
1091  fac_NTL_char= p;
1092  zz_p::init (p);
1093  }
1094  zz_pX NTLIrredpoly;
1095  BuildIrred (NTLIrredpoly, d*2);
1096  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1097  #else
1098  factoryError("NTL/FLINT missing: EZGCD_P");
1099  #endif
1100  v2= rootOf (newMipo);
1101  imPrimElem= mapPrimElem (primElem, a, v2);
1102  extOfExt= true;
1103  }
1104  if (extOfExt)
1105  {
1106  maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
1107  F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1108  G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
1109  a= v2;
1110  }
1111  }
1112 
1113  lcF = LC( F, x ); lcG = LC( G, x );
1114  lcD = gcd( lcF, lcG );
1115 
1116  delta = 0;
1117  degF = degree( F, x ); degG = degree( G, x );
1118 
1119  if (algExtension)
1120  b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
1121  else
1122  { // both not in extension given by algebraic variable
1124  b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
1125  else
1126  b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
1127  }
1128 
1129  CanonicalForm cand, contcand;
1131  int o, t;
1132  o= 0;
1133  t= 1;
1134  int goodPointCount= 0;
1135  TIMING_DEFINE(ez_p_eval);
1136  while( !gcdfound )
1137  {
1138  TIMING_START (ez_p_eval);
1139  if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
1140  maxeval/maxNumVars, t ))
1141  { // too many eval. used --> try another method
1142  Off (SW_USE_EZGCD_P);
1143  result= gcd (F,G);
1144  On (SW_USE_EZGCD_P);
1145  if (passToGF)
1146  {
1148  setCharacteristic (p);
1151  prune (alpha);
1152  }
1153  if (k > 1)
1154  {
1155  result= GFMapDown (result, k);
1157  }
1158  if (extOfExt)
1159  {
1160  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1161  prune1 (oldA);
1162  }
1163  return N (d*result);
1164  }
1165  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
1166  delta = degree( Db );
1167  if (delta == degF)
1168  {
1169  if (degF <= degG && fdivides (F, G))
1170  {
1171  if (passToGF)
1172  {
1174  setCharacteristic (p);
1176  F= GF2FalphaRep (F, alpha);
1177  prune (alpha);
1178  }
1179  if (k > 1)
1180  {
1181  F= GFMapDown (F, k);
1183  }
1184  if (extOfExt)
1185  {
1186  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1187  prune1 (oldA);
1188  }
1189  return N (d*F);
1190  }
1191  else
1192  delta--;
1193  }
1194  else if (delta == degG)
1195  {
1196  if (degG <= degF && fdivides (G, F))
1197  {
1198  if (passToGF)
1199  {
1201  setCharacteristic (p);
1203  G= GF2FalphaRep (G, alpha);
1204  prune (alpha);
1205  }
1206  if (k > 1)
1207  {
1208  G= GFMapDown (G, k);
1210  }
1211  if (extOfExt)
1212  {
1213  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1214  prune1 (oldA);
1215  }
1216  return N (d*G);
1217  }
1218  else
1219  delta--;
1220  }
1221  if( delta == 0 )
1222  {
1223  if (passToGF)
1224  setCharacteristic (p);
1225  if (k > 1)
1227  return N (d);
1228  }
1229  while( true )
1230  {
1231  bt = b;
1232  TIMING_START (ez_p_eval);
1233  if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1234  maxeval/maxNumVars, t ))
1235  { // too many eval. used --> try another method
1236  Off (SW_USE_EZGCD_P);
1237  result= gcd (F,G);
1238  On (SW_USE_EZGCD_P);
1239  if (passToGF)
1240  {
1242  setCharacteristic (p);
1245  prune (alpha);
1246  }
1247  if (k > 1)
1248  {
1249  result= GFMapDown (result, k);
1251  }
1252  if (extOfExt)
1253  {
1254  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1255  prune1 (oldA);
1256  }
1257  return N (d*result);
1258  }
1259  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
1260  int dd = degree( Dbt );
1261  if( dd == 0 )
1262  {
1263  if (passToGF)
1264  setCharacteristic (p);
1265  if (k > 1)
1267  return N (d);
1268  }
1269  if( dd == delta )
1270  {
1271  goodPointCount++;
1272  if (goodPointCount == 5)
1273  break;
1274  }
1275  if( dd < delta )
1276  {
1277  goodPointCount= 0;
1278  delta = dd;
1279  b = bt;
1280  Db = Dbt; Fb = Fbt; Gb = Gbt;
1281  }
1282  if (delta == degF)
1283  {
1284  if (degF <= degG && fdivides (F, G))
1285  {
1286  if (passToGF)
1287  {
1289  setCharacteristic (p);
1291  F= GF2FalphaRep (F, alpha);
1292  prune (alpha);
1293  }
1294  if (k > 1)
1295  {
1296  F= GFMapDown (F, k);
1298  }
1299  if (extOfExt)
1300  {
1301  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1302  prune1 (oldA);
1303  }
1304  return N (d*F);
1305  }
1306  else
1307  delta--;
1308  }
1309  else if (delta == degG)
1310  {
1311  if (degG <= degF && fdivides (G, F))
1312  {
1313  if (passToGF)
1314  {
1316  setCharacteristic (p);
1318  G= GF2FalphaRep (G, alpha);
1319  prune (alpha);
1320  }
1321  if (k > 1)
1322  {
1323  G= GFMapDown (G, k);
1325  }
1326  if (extOfExt)
1327  {
1328  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1329  prune1 (oldA);
1330  }
1331  return N (d*G);
1332  }
1333  else
1334  delta--;
1335  }
1336  if( delta == 0 )
1337  {
1338  if (passToGF)
1339  setCharacteristic (p);
1340  if (k > 1)
1342  return N (d);
1343  }
1344  }
1345  if( delta != degF && delta != degG )
1346  {
1347  bool B_is_F;
1348  CanonicalForm xxx1, xxx2;
1350  DD[1] = Fb / Db;
1351  buf= Gb/Db;
1352  xxx1 = gcd( DD[1], Db );
1353  xxx2 = gcd( buf, Db );
1354  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1355  (size (F) <= size (G)))
1356  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
1357  {
1358  B = F;
1359  DD[2] = Db;
1360  lcDD[1] = lcF;
1361  lcDD[2] = lcD;
1362  B_is_F = true;
1363  }
1364  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1365  (size (G) < size (F)))
1366  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
1367  {
1368  DD[1] = buf;
1369  B = G;
1370  DD[2] = Db;
1371  lcDD[1] = lcG;
1372  lcDD[2] = lcD;
1373  B_is_F = false;
1374  }
1375  else // special case handling
1376  {
1377  Off (SW_USE_EZGCD_P);
1378  result= gcd (F,G);
1379  On (SW_USE_EZGCD_P);
1380  if (passToGF)
1381  {
1383  setCharacteristic (p);
1386  prune (alpha);
1387  }
1388  if (k > 1)
1389  {
1390  result= GFMapDown (result, k);
1392  }
1393  if (extOfExt)
1394  {
1395  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1396  prune1 (oldA);
1397  }
1398  return N (d*result);
1399  }
1400  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
1401  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
1402 
1403  if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
1404  {
1405  if (algExtension)
1406  {
1407  result= modGCDFq (F, G, a);
1408  if (extOfExt)
1409  {
1410  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1411  prune1 (oldA);
1412  }
1413  return N (d*result);
1414  }
1416  {
1417  result= modGCDGF (F, G);
1418  if (passToGF)
1419  {
1421  setCharacteristic (p);
1424  prune (alpha);
1425  }
1426  if (k > 1)
1427  {
1428  result= GFMapDown (result, k);
1430  }
1431  return N (d*result);
1432  }
1433  else
1434  return N (d*modGCDFp (F,G));
1435  }
1436 
1437  TIMING_DEFINE(ez_p_hensel_lift);
1438  TIMING_START (ez_p_hensel_lift);
1439  gcdfound= Hensel (B*lcD, DD, b, lcDD);
1440  TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
1441 
1442  if (gcdfound == -1) //things became dense
1443  {
1444  if (algExtension)
1445  {
1446  result= modGCDFq (F, G, a);
1447  if (extOfExt)
1448  {
1449  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1450  prune1 (oldA);
1451  }
1452  return N (d*result);
1453  }
1455  {
1456  result= modGCDGF (F, G);
1457  if (passToGF)
1458  {
1460  setCharacteristic (p);
1463  prune (alpha);
1464  }
1465  if (k > 1)
1466  {
1467  result= GFMapDown (result, k);
1469  }
1470  return N (d*result);
1471  }
1472  else
1473  {
1474  if (p >= cf_getBigPrime(0))
1475  return N (d*sparseGCDFp (F,G));
1476  else
1477  return N (d*modGCDFp (F,G));
1478  }
1479  }
1480 
1481  if (gcdfound == 1)
1482  {
1483  TIMING_DEFINE(termination_test);
1484  TIMING_START (termination_test);
1485  contcand= content (DD[2], Variable (1));
1486  cand = DD[2] / contcand;
1487  if (B_is_F)
1488  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1489  else
1490  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
1491  TIMING_END_AND_PRINT (termination_test,
1492  "time for termination test EZ_P: ");
1493 
1494  if (passToGF && gcdfound)
1495  {
1497  setCharacteristic (p);
1500  prune (alpha);
1501  }
1502  if (k > 1 && gcdfound)
1503  {
1504  cand= GFMapDown (cand, k);
1506  }
1507  if (extOfExt && gcdfound)
1508  {
1509  cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
1510  prune1 (oldA);
1511  }
1512  }
1513  }
1514  delta--;
1515  goodPointCount= 0;
1516  }
1517  return N (d*cand);
1518 }
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
void On(int sw)
switches
void Off(int sw)
switches
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm lc(const CanonicalForm &f)
int ilog2(const CanonicalForm &a)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
if(both_non_zero==0)
Definition: cfEzgcd.cc:91
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
STATIC_VAR int maxNumEval
Definition: cfEzgcd.cc:871
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
Definition: cfEzgcd.cc:470
static const double log2exp
Definition: cfEzgcd.cc:45
const CanonicalForm & G
Definition: cfEzgcd.cc:55
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition: cfEzgcd.cc:302
const CanonicalForm CFMap & M
Definition: cfEzgcd.cc:55
STATIC_VAR int sizePerVars1
Definition: cfEzgcd.cc:872
int k
Definition: cfEzgcd.cc:99
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:386
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:25
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:480
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
Variable x
Definition: cfModGcd.cc:4084
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
int maxNumVars
Definition: cfModGcd.cc:4132
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1225
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3564
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:874
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:36
#define GaloisFieldDomain
Definition: cf_defs.h:24
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:450
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:276
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:342
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:123
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
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:240
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:195
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
FILE * f
Definition: checklibs.c:9
generate random elements in F_p(alpha)
Definition: cf_random.h:70
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CanonicalForm genOne() const
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
CanonicalForm mapinto() const
bool isUnivariate() const
generate random elements in F_p
Definition: cf_random.h:44
generate random elements in GF
Definition: cf_random.h:32
factory's class for variables
Definition: factory.h:134
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
b *CanonicalForm B
Definition: facBivar.cc:52
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void prune1(const Variable &alpha)
Definition: variable.cc:291
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
VAR char gf_name
Definition: gfops.cc:52
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void init()
Definition: lintree.cc:864
int status int void size_t count
Definition: si_signals.h:59
int status int void * buf
Definition: si_signals.h:59
#define TIMING_DEFINE(t)
Definition: timing.h:91
int gcd(int a, int b)
Definition: walkSupport.cc:836