My Project  debian-1:4.1.1-p2+ds-4
Functions
cfEzgcd.h File Reference

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

797 {
798 #ifdef HAVE_NTL
799  REvaluation b;
800  return ezgcd( FF, GG, b, false );
801 #else
802  Off (SW_USE_EZGCD);
803  return gcd (FF, GG);
804  On (SW_USE_EZGCD);
805 #endif
806 }

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

816 {
817  if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
818  else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
819  else if (FF.isZero() && GG.isZero()) return FF.genOne();
820  if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
821  if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
822  if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
823  if (FF == GG) return FF/Lc(FF);
824 
825  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
826  Variable a, oldA;
827  int sizeF= size (FF);
828  int sizeG= size (GG);
829 
830  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
831  {
832  if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
833  return modGCDFq (FF, GG, a);
835  return modGCDGF (FF, GG);
836  else
837  return modGCDFp (FF, GG);
838  }
839 
840  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
841  lcD;
842  CFArray DD( 1, 2 ), lcDD( 1, 2 );
843  int degF, degG, delta, count;
844  int maxeval;
845  maxeval= tmin((getCharacteristic()/
846  (int)(ilog2(getCharacteristic())*log2exp))*2, maxNumEval);
847  count= 0; // number of eval. used
848  REvaluation b, bt;
849  int gcdfound = 0;
850  Variable x = Variable(1);
851 
852  F= FF;
853  G= GG;
854 
855  CFMap M,N;
856  int smallestDegLev;
857  TIMING_DEFINE(ez_p_compress);
858  TIMING_START (ez_p_compress);
859  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
860 
861  if (best_level == 0) return G.genOne();
862 
863  F= M (F);
864  G= M (G);
865  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
866 
867  TIMING_DEFINE (ez_p_content)
868  TIMING_START (ez_p_content)
869  f = content( F, x ); g = content( G, x );
870  d = gcd( f, g );
871  F /= f; G /= g;
872  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
873 
874  if( F.isUnivariate() && G.isUnivariate() )
875  {
876  if( F.mvar() == G.mvar() )
877  d *= gcd( F, G );
878  else
879  return N (d);
880  return N (d);
881  }
882  if ( F.isUnivariate())
883  {
884  g= content (G,G.mvar());
885  return N(d*gcd(F,g));
886  }
887  if ( G.isUnivariate())
888  {
889  f= content (F,F.mvar());
890  return N(d*gcd(G,f));
891  }
892 
894  sizeF= size (F);
895  sizeG= size (G);
896 
897  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
898  {
899  if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
900  return N (d*modGCDFq (F, G, a));
902  return N (d*modGCDGF (F, G));
903  else
904  return N (d*modGCDFp (F, G));
905  }
906 
907  int dummy= 0;
908  if( gcd_test_one( F, G, false, dummy ) )
909  {
910  return N (d);
911  }
912 
913  bool passToGF= false;
914  bool extOfExt= false;
915  int p= getCharacteristic();
916  bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
917  int k= 1;
918  CanonicalForm primElem, imPrimElem;
919  CFList source, dest;
920  if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
921  {
922  if (p == 2)
923  setCharacteristic (2, 12, 'Z');
924  else if (p == 3)
925  setCharacteristic (3, 4, 'Z');
926  else if (p == 5 || p == 7)
927  setCharacteristic (p, 3, 'Z');
928  else
929  setCharacteristic (p, 2, 'Z');
930  passToGF= true;
931  F= F.mapinto();
932  G= G.mapinto();
933  maxeval= 2*ipower (p, getGFDegree());
934  }
935  else if (CFFactory::gettype() == GaloisFieldDomain &&
936  ipower (p , getGFDegree()) < 50)
937  {
938  k= getGFDegree();
939  if (ipower (p, 2*k) > 50)
941  else
943  F= GFMapUp (F, k);
944  G= GFMapUp (G, k);
945  maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
946  }
947  else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
948  {
949  int d= degree (getMipo (a));
950  oldA= a;
951  Variable v2;
952  if (p == 2 && d < 6)
953  {
954  if (fac_NTL_char != p)
955  {
956  fac_NTL_char= p;
957  zz_p::init (p);
958  }
959  bool primFail= false;
960  Variable vBuf;
961  primElem= primitiveElement (a, vBuf, primFail);
962  ASSERT (!primFail, "failure in integer factorizer");
963  if (d < 3)
964  {
965  zz_pX NTLIrredpoly;
966  BuildIrred (NTLIrredpoly, d*3);
967  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
968  v2= rootOf (newMipo);
969  }
970  else
971  {
972  zz_pX NTLIrredpoly;
973  BuildIrred (NTLIrredpoly, d*2);
974  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
975  v2= rootOf (newMipo);
976  }
977  imPrimElem= mapPrimElem (primElem, a, v2);
978  extOfExt= true;
979  }
980  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
981  {
982  if (fac_NTL_char != p)
983  {
984  fac_NTL_char= p;
985  zz_p::init (p);
986  }
987  bool primFail= false;
988  Variable vBuf;
989  primElem= primitiveElement (a, vBuf, primFail);
990  ASSERT (!primFail, "failure in integer factorizer");
991  zz_pX NTLIrredpoly;
992  BuildIrred (NTLIrredpoly, d*2);
993  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
994  v2= rootOf (newMipo);
995  imPrimElem= mapPrimElem (primElem, a, v2);
996  extOfExt= true;
997  }
998  if (extOfExt)
999  {
1000  maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
1001  F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1002  G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
1003  a= v2;
1004  }
1005  }
1006 
1007  lcF = LC( F, x ); lcG = LC( G, x );
1008  lcD = gcd( lcF, lcG );
1009 
1010  delta = 0;
1011  degF = degree( F, x ); degG = degree( G, x );
1012 
1013  if (algExtension)
1014  b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
1015  else
1016  { // both not in extension given by algebraic variable
1018  b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
1019  else
1020  b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
1021  }
1022 
1023  CanonicalForm cand, contcand;
1025  int o, t;
1026  o= 0;
1027  t= 1;
1028  int goodPointCount= 0;
1029  TIMING_DEFINE(ez_p_eval);
1030  while( !gcdfound )
1031  {
1032  TIMING_START (ez_p_eval);
1033  if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
1034  maxeval/maxNumVars, t ))
1035  { // too many eval. used --> try another method
1036  Off (SW_USE_EZGCD_P);
1037  result= gcd (F,G);
1038  On (SW_USE_EZGCD_P);
1039  if (passToGF)
1040  {
1042  setCharacteristic (p);
1045  prune (alpha);
1046  }
1047  if (k > 1)
1048  {
1049  result= GFMapDown (result, k);
1051  }
1052  if (extOfExt)
1053  {
1054  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1055  prune1 (oldA);
1056  }
1057  return N (d*result);
1058  }
1059  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
1060  delta = degree( Db );
1061  if (delta == degF)
1062  {
1063  if (degF <= degG && fdivides (F, G))
1064  {
1065  if (passToGF)
1066  {
1068  setCharacteristic (p);
1070  F= GF2FalphaRep (F, alpha);
1071  prune (alpha);
1072  }
1073  if (k > 1)
1074  {
1075  F= GFMapDown (F, k);
1077  }
1078  if (extOfExt)
1079  {
1080  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1081  prune1 (oldA);
1082  }
1083  return N (d*F);
1084  }
1085  else
1086  delta--;
1087  }
1088  else if (delta == degG)
1089  {
1090  if (degG <= degF && fdivides (G, F))
1091  {
1092  if (passToGF)
1093  {
1095  setCharacteristic (p);
1097  G= GF2FalphaRep (G, alpha);
1098  prune (alpha);
1099  }
1100  if (k > 1)
1101  {
1102  G= GFMapDown (G, k);
1104  }
1105  if (extOfExt)
1106  {
1107  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1108  prune1 (oldA);
1109  }
1110  return N (d*G);
1111  }
1112  else
1113  delta--;
1114  }
1115  if( delta == 0 )
1116  {
1117  if (passToGF)
1118  setCharacteristic (p);
1119  if (k > 1)
1121  return N (d);
1122  }
1123  while( true )
1124  {
1125  bt = b;
1126  TIMING_START (ez_p_eval);
1127  if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1128  maxeval/maxNumVars, t ))
1129  { // too many eval. used --> try another method
1130  Off (SW_USE_EZGCD_P);
1131  result= gcd (F,G);
1132  On (SW_USE_EZGCD_P);
1133  if (passToGF)
1134  {
1136  setCharacteristic (p);
1139  prune (alpha);
1140  }
1141  if (k > 1)
1142  {
1143  result= GFMapDown (result, k);
1145  }
1146  if (extOfExt)
1147  {
1148  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1149  prune1 (oldA);
1150  }
1151  return N (d*result);
1152  }
1153  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
1154  int dd = degree( Dbt );
1155  if( dd == 0 )
1156  {
1157  if (passToGF)
1158  setCharacteristic (p);
1159  if (k > 1)
1161  return N (d);
1162  }
1163  if( dd == delta )
1164  {
1165  goodPointCount++;
1166  if (goodPointCount == 5)
1167  break;
1168  }
1169  if( dd < delta )
1170  {
1171  goodPointCount= 0;
1172  delta = dd;
1173  b = bt;
1174  Db = Dbt; Fb = Fbt; Gb = Gbt;
1175  }
1176  if (delta == degF)
1177  {
1178  if (degF <= degG && fdivides (F, G))
1179  {
1180  if (passToGF)
1181  {
1183  setCharacteristic (p);
1185  F= GF2FalphaRep (F, alpha);
1186  prune (alpha);
1187  }
1188  if (k > 1)
1189  {
1190  F= GFMapDown (F, k);
1192  }
1193  if (extOfExt)
1194  {
1195  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1196  prune1 (oldA);
1197  }
1198  return N (d*F);
1199  }
1200  else
1201  delta--;
1202  }
1203  else if (delta == degG)
1204  {
1205  if (degG <= degF && fdivides (G, F))
1206  {
1207  if (passToGF)
1208  {
1210  setCharacteristic (p);
1212  G= GF2FalphaRep (G, alpha);
1213  prune (alpha);
1214  }
1215  if (k > 1)
1216  {
1217  G= GFMapDown (G, k);
1219  }
1220  if (extOfExt)
1221  {
1222  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1223  prune1 (oldA);
1224  }
1225  return N (d*G);
1226  }
1227  else
1228  delta--;
1229  }
1230  if( delta == 0 )
1231  {
1232  if (passToGF)
1233  setCharacteristic (p);
1234  if (k > 1)
1236  return N (d);
1237  }
1238  }
1239  if( delta != degF && delta != degG )
1240  {
1241  bool B_is_F;
1242  CanonicalForm xxx1, xxx2;
1244  DD[1] = Fb / Db;
1245  buf= Gb/Db;
1246  xxx1 = gcd( DD[1], Db );
1247  xxx2 = gcd( buf, Db );
1248  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1249  (size (F) <= size (G)))
1250  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
1251  {
1252  B = F;
1253  DD[2] = Db;
1254  lcDD[1] = lcF;
1255  lcDD[2] = lcD;
1256  B_is_F = true;
1257  }
1258  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1259  (size (G) < size (F)))
1260  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
1261  {
1262  DD[1] = buf;
1263  B = G;
1264  DD[2] = Db;
1265  lcDD[1] = lcG;
1266  lcDD[2] = lcD;
1267  B_is_F = false;
1268  }
1269  else // special case handling
1270  {
1271  Off (SW_USE_EZGCD_P);
1272  result= gcd (F,G);
1273  On (SW_USE_EZGCD_P);
1274  if (passToGF)
1275  {
1277  setCharacteristic (p);
1280  prune (alpha);
1281  }
1282  if (k > 1)
1283  {
1284  result= GFMapDown (result, k);
1286  }
1287  if (extOfExt)
1288  {
1289  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1290  prune1 (oldA);
1291  }
1292  return N (d*result);
1293  }
1294  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
1295  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
1296 
1297  if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
1298  {
1299  if (algExtension)
1300  {
1301  result= modGCDFq (F, G, a);
1302  if (extOfExt)
1303  {
1304  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1305  prune1 (oldA);
1306  }
1307  return N (d*result);
1308  }
1310  {
1311  result= modGCDGF (F, G);
1312  if (passToGF)
1313  {
1315  setCharacteristic (p);
1318  prune (alpha);
1319  }
1320  if (k > 1)
1321  {
1322  result= GFMapDown (result, k);
1324  }
1325  return N (d*result);
1326  }
1327  else
1328  return N (d*modGCDFp (F,G));
1329  }
1330 
1331  TIMING_DEFINE(ez_p_hensel_lift);
1332  TIMING_START (ez_p_hensel_lift);
1333  gcdfound= Hensel (B*lcD, DD, b, lcDD);
1334  TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
1335 
1336  if (gcdfound == -1) //things became dense
1337  {
1338  if (algExtension)
1339  {
1340  result= modGCDFq (F, G, a);
1341  if (extOfExt)
1342  {
1343  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1344  prune1 (oldA);
1345  }
1346  return N (d*result);
1347  }
1349  {
1350  result= modGCDGF (F, G);
1351  if (passToGF)
1352  {
1354  setCharacteristic (p);
1357  prune (alpha);
1358  }
1359  if (k > 1)
1360  {
1361  result= GFMapDown (result, k);
1363  }
1364  return N (d*result);
1365  }
1366  else
1367  {
1368  if (p >= cf_getBigPrime(0))
1369  return N (d*sparseGCDFp (F,G));
1370  else
1371  return N (d*modGCDFp (F,G));
1372  }
1373  }
1374 
1375  if (gcdfound == 1)
1376  {
1377  TIMING_DEFINE(termination_test);
1378  TIMING_START (termination_test);
1379  contcand= content (DD[2], Variable (1));
1380  cand = DD[2] / contcand;
1381  if (B_is_F)
1382  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1383  else
1384  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
1385  TIMING_END_AND_PRINT (termination_test,
1386  "time for termination test EZ_P: ");
1387 
1388  if (passToGF && gcdfound)
1389  {
1391  setCharacteristic (p);
1394  prune (alpha);
1395  }
1396  if (k > 1 && gcdfound)
1397  {
1398  cand= GFMapDown (cand, k);
1400  }
1401  if (extOfExt && gcdfound)
1402  {
1403  cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
1404  prune1 (oldA);
1405  }
1406  }
1407  }
1408  delta--;
1409  goodPointCount= 0;
1410  }
1411  return N (d*cand);
1412 }
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
FFRandom
generate random elements in F_p
Definition: cf_random.h:43
if
if(both_non_zero==0)
Definition: cfEzgcd.cc:84
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
sizePerVars1
static int sizePerVars1
Definition: cfEzgcd.cc:811
x
Variable x
Definition: cfModGcd.cc:4023
result
return result
Definition: facAbsBiFact.cc:76
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:441
CFMap
class CFMap
Definition: cf_map.h:84
AlgExtRandomF
generate random elements in F_p(alpha)
Definition: cf_random.h:70
g
g
Definition: cfModGcd.cc:4031
gcd_test_one
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
rootOf
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
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
gf_name
char gf_name
Definition: gfops.cc:52
primitiveElement
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
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
M
const CanonicalForm CFMap & M
Definition: cfEzgcd.cc:48
CanonicalForm
factory's main class
Definition: canonicalform.h:77
GFMapDown
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
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
CanonicalForm::genOne
CanonicalForm genOne() const
Definition: canonicalform.cc:1822
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
Array
Definition: ftmpl_array.h:17
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
buf
int status int void * buf
Definition: si_signals.h:58
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
findeval
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:374
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
ilog2
int ilog2(const CanonicalForm &a)
Definition: canonicalform.h:345
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
modGCDFq
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
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
log2exp
static const double log2exp
Definition: cfEzgcd.cc:39
prune
void prune(Variable &alpha)
Definition: variable.cc:261
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
GG
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
TIMING_DEFINE
#define TIMING_DEFINE(t)
Definition: timing.h:91
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
GFRandom
generate random elements in GF
Definition: cf_random.h:31
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
Hensel
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition: cfEzgcd.cc:293
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
cand
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
Variable
factory's class for variables
Definition: factory.h:117
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
B
b *CanonicalForm B
Definition: facBivar.cc:52
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
mapPrimElem
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
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
maxNumVars
int maxNumVars
Definition: cfModGcd.cc:4071
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
count
int status int void size_t count
Definition: si_signals.h:58
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
GF2FalphaRep
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
G
const CanonicalForm & G
Definition: cfEzgcd.cc:48
GFMapUp
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
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
maxNumEval
static int maxNumEval
Definition: cfEzgcd.cc:810
prune1
void prune1(const Variable &alpha)
Definition: variable.cc:289
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
modGCDGF
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
mapDown
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
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503