My Project  debian-1:4.1.2-p1+ds-2
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 843 of file cfEzgcd.cc.

844 {
845 #ifdef HAVE_NTL
846  REvaluation b;
847  return ezgcd( FF, GG, b, false );
848 #else
849  Off (SW_USE_EZGCD);
850  return gcd (FF, GG);
851  On (SW_USE_EZGCD);
852 #endif
853 }
void On(int sw)
switches
void Off(int sw)
switches
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:481
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
CanonicalForm b
Definition: cfModGcd.cc:4044
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:33
class to generate random evaluation points
Definition: cf_reval.h:26
int gcd(int a, int b)
Definition: walkSupport.cc:836

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

863 {
864  if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
865  else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
866  else if (FF.isZero() && GG.isZero()) return FF.genOne();
867  if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
868  if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
869  if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
870  if (FF == GG) return FF/Lc(FF);
871 
872  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
873  Variable a, oldA;
874  int sizeF= size (FF);
875  int sizeG= size (GG);
876 
877  if (sizeF==1)
878  {
879  return gcd_mon( FF, GG );
880  }
881  else if (sizeG==1)
882  {
883  return gcd_mon( GG, FF );
884  }
885 
886  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
887  {
888  if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
889  return modGCDFq (FF, GG, a);
891  return modGCDGF (FF, GG);
892  else
893  return modGCDFp (FF, GG);
894  }
895 
896  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
897  lcD;
898  CFArray DD( 1, 2 ), lcDD( 1, 2 );
899  int degF, degG, delta, count;
900  int maxeval;
901  maxeval= tmin((getCharacteristic()/
902  (int)(ilog2(getCharacteristic())*log2exp))*2, maxNumEval);
903  count= 0; // number of eval. used
904  REvaluation b, bt;
905  int gcdfound = 0;
906  Variable x = Variable(1);
907 
908  F= FF;
909  G= GG;
910 
911  CFMap M,N;
912  int smallestDegLev;
913  TIMING_DEFINE(ez_p_compress);
914  TIMING_START (ez_p_compress);
915  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
916 
917  if (best_level == 0) return G.genOne();
918 
919  F= M (F);
920  G= M (G);
921  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
922 
923  TIMING_DEFINE (ez_p_content)
924  TIMING_START (ez_p_content)
925  f = content( F, x ); g = content( G, x );
926  d = gcd( f, g );
927  F /= f; G /= g;
928  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
929 
930  if( F.isUnivariate() && G.isUnivariate() )
931  {
932  if( F.mvar() == G.mvar() )
933  d *= gcd( F, G );
934  else
935  return N (d);
936  return N (d);
937  }
938  if ( F.isUnivariate())
939  {
940  g= content (G,G.mvar());
941  return N(d*gcd(F,g));
942  }
943  if ( G.isUnivariate())
944  {
945  f= content (F,F.mvar());
946  return N(d*gcd(G,f));
947  }
948 
950  sizeF= size (F);
951  sizeG= size (G);
952 
953  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
954  {
955  if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
956  return N (d*modGCDFq (F, G, a));
958  return N (d*modGCDGF (F, G));
959  else
960  return N (d*modGCDFp (F, G));
961  }
962 
963  int dummy= 0;
964  if( gcd_test_one( F, G, false, dummy ) )
965  {
966  return N (d);
967  }
968 
969  bool passToGF= false;
970  bool extOfExt= false;
971  int p= getCharacteristic();
972  bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
973  int k= 1;
974  CanonicalForm primElem, imPrimElem;
975  CFList source, dest;
976  if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
977  {
978  if (p == 2)
979  setCharacteristic (2, 12, 'Z');
980  else if (p == 3)
981  setCharacteristic (3, 4, 'Z');
982  else if (p == 5 || p == 7)
983  setCharacteristic (p, 3, 'Z');
984  else
985  setCharacteristic (p, 2, 'Z');
986  passToGF= true;
987  F= F.mapinto();
988  G= G.mapinto();
989  maxeval= 2*ipower (p, getGFDegree());
990  }
991  else if (CFFactory::gettype() == GaloisFieldDomain &&
992  ipower (p , getGFDegree()) < 50)
993  {
994  k= getGFDegree();
995  if (ipower (p, 2*k) > 50)
997  else
999  F= GFMapUp (F, k);
1000  G= GFMapUp (G, k);
1001  maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
1002  }
1003  else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
1004  {
1005  int d= degree (getMipo (a));
1006  oldA= a;
1007  Variable v2;
1008  if (p == 2 && d < 6)
1009  {
1010  if (fac_NTL_char != p)
1011  {
1012  fac_NTL_char= p;
1013  zz_p::init (p);
1014  }
1015  bool primFail= false;
1016  Variable vBuf;
1017  primElem= primitiveElement (a, vBuf, primFail);
1018  ASSERT (!primFail, "failure in integer factorizer");
1019  if (d < 3)
1020  {
1021  zz_pX NTLIrredpoly;
1022  BuildIrred (NTLIrredpoly, d*3);
1023  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1024  v2= rootOf (newMipo);
1025  }
1026  else
1027  {
1028  zz_pX NTLIrredpoly;
1029  BuildIrred (NTLIrredpoly, d*2);
1030  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1031  v2= rootOf (newMipo);
1032  }
1033  imPrimElem= mapPrimElem (primElem, a, v2);
1034  extOfExt= true;
1035  }
1036  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
1037  {
1038  if (fac_NTL_char != p)
1039  {
1040  fac_NTL_char= p;
1041  zz_p::init (p);
1042  }
1043  bool primFail= false;
1044  Variable vBuf;
1045  primElem= primitiveElement (a, vBuf, primFail);
1046  ASSERT (!primFail, "failure in integer factorizer");
1047  zz_pX NTLIrredpoly;
1048  BuildIrred (NTLIrredpoly, d*2);
1049  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
1050  v2= rootOf (newMipo);
1051  imPrimElem= mapPrimElem (primElem, a, v2);
1052  extOfExt= true;
1053  }
1054  if (extOfExt)
1055  {
1056  maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
1057  F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1058  G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
1059  a= v2;
1060  }
1061  }
1062 
1063  lcF = LC( F, x ); lcG = LC( G, x );
1064  lcD = gcd( lcF, lcG );
1065 
1066  delta = 0;
1067  degF = degree( F, x ); degG = degree( G, x );
1068 
1069  if (algExtension)
1070  b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
1071  else
1072  { // both not in extension given by algebraic variable
1074  b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
1075  else
1076  b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
1077  }
1078 
1079  CanonicalForm cand, contcand;
1081  int o, t;
1082  o= 0;
1083  t= 1;
1084  int goodPointCount= 0;
1085  TIMING_DEFINE(ez_p_eval);
1086  while( !gcdfound )
1087  {
1088  TIMING_START (ez_p_eval);
1089  if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
1090  maxeval/maxNumVars, t ))
1091  { // too many eval. used --> try another method
1092  Off (SW_USE_EZGCD_P);
1093  result= gcd (F,G);
1094  On (SW_USE_EZGCD_P);
1095  if (passToGF)
1096  {
1098  setCharacteristic (p);
1101  prune (alpha);
1102  }
1103  if (k > 1)
1104  {
1105  result= GFMapDown (result, k);
1107  }
1108  if (extOfExt)
1109  {
1110  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1111  prune1 (oldA);
1112  }
1113  return N (d*result);
1114  }
1115  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
1116  delta = degree( Db );
1117  if (delta == degF)
1118  {
1119  if (degF <= degG && fdivides (F, G))
1120  {
1121  if (passToGF)
1122  {
1124  setCharacteristic (p);
1126  F= GF2FalphaRep (F, alpha);
1127  prune (alpha);
1128  }
1129  if (k > 1)
1130  {
1131  F= GFMapDown (F, k);
1133  }
1134  if (extOfExt)
1135  {
1136  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1137  prune1 (oldA);
1138  }
1139  return N (d*F);
1140  }
1141  else
1142  delta--;
1143  }
1144  else if (delta == degG)
1145  {
1146  if (degG <= degF && fdivides (G, F))
1147  {
1148  if (passToGF)
1149  {
1151  setCharacteristic (p);
1153  G= GF2FalphaRep (G, alpha);
1154  prune (alpha);
1155  }
1156  if (k > 1)
1157  {
1158  G= GFMapDown (G, k);
1160  }
1161  if (extOfExt)
1162  {
1163  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1164  prune1 (oldA);
1165  }
1166  return N (d*G);
1167  }
1168  else
1169  delta--;
1170  }
1171  if( delta == 0 )
1172  {
1173  if (passToGF)
1174  setCharacteristic (p);
1175  if (k > 1)
1177  return N (d);
1178  }
1179  while( true )
1180  {
1181  bt = b;
1182  TIMING_START (ez_p_eval);
1183  if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1184  maxeval/maxNumVars, t ))
1185  { // too many eval. used --> try another method
1186  Off (SW_USE_EZGCD_P);
1187  result= gcd (F,G);
1188  On (SW_USE_EZGCD_P);
1189  if (passToGF)
1190  {
1192  setCharacteristic (p);
1195  prune (alpha);
1196  }
1197  if (k > 1)
1198  {
1199  result= GFMapDown (result, k);
1201  }
1202  if (extOfExt)
1203  {
1204  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1205  prune1 (oldA);
1206  }
1207  return N (d*result);
1208  }
1209  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
1210  int dd = degree( Dbt );
1211  if( dd == 0 )
1212  {
1213  if (passToGF)
1214  setCharacteristic (p);
1215  if (k > 1)
1217  return N (d);
1218  }
1219  if( dd == delta )
1220  {
1221  goodPointCount++;
1222  if (goodPointCount == 5)
1223  break;
1224  }
1225  if( dd < delta )
1226  {
1227  goodPointCount= 0;
1228  delta = dd;
1229  b = bt;
1230  Db = Dbt; Fb = Fbt; Gb = Gbt;
1231  }
1232  if (delta == degF)
1233  {
1234  if (degF <= degG && fdivides (F, G))
1235  {
1236  if (passToGF)
1237  {
1239  setCharacteristic (p);
1241  F= GF2FalphaRep (F, alpha);
1242  prune (alpha);
1243  }
1244  if (k > 1)
1245  {
1246  F= GFMapDown (F, k);
1248  }
1249  if (extOfExt)
1250  {
1251  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1252  prune1 (oldA);
1253  }
1254  return N (d*F);
1255  }
1256  else
1257  delta--;
1258  }
1259  else if (delta == degG)
1260  {
1261  if (degG <= degF && fdivides (G, F))
1262  {
1263  if (passToGF)
1264  {
1266  setCharacteristic (p);
1268  G= GF2FalphaRep (G, alpha);
1269  prune (alpha);
1270  }
1271  if (k > 1)
1272  {
1273  G= GFMapDown (G, k);
1275  }
1276  if (extOfExt)
1277  {
1278  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1279  prune1 (oldA);
1280  }
1281  return N (d*G);
1282  }
1283  else
1284  delta--;
1285  }
1286  if( delta == 0 )
1287  {
1288  if (passToGF)
1289  setCharacteristic (p);
1290  if (k > 1)
1292  return N (d);
1293  }
1294  }
1295  if( delta != degF && delta != degG )
1296  {
1297  bool B_is_F;
1298  CanonicalForm xxx1, xxx2;
1300  DD[1] = Fb / Db;
1301  buf= Gb/Db;
1302  xxx1 = gcd( DD[1], Db );
1303  xxx2 = gcd( buf, Db );
1304  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1305  (size (F) <= size (G)))
1306  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
1307  {
1308  B = F;
1309  DD[2] = Db;
1310  lcDD[1] = lcF;
1311  lcDD[2] = lcD;
1312  B_is_F = true;
1313  }
1314  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1315  (size (G) < size (F)))
1316  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
1317  {
1318  DD[1] = buf;
1319  B = G;
1320  DD[2] = Db;
1321  lcDD[1] = lcG;
1322  lcDD[2] = lcD;
1323  B_is_F = false;
1324  }
1325  else // special case handling
1326  {
1327  Off (SW_USE_EZGCD_P);
1328  result= gcd (F,G);
1329  On (SW_USE_EZGCD_P);
1330  if (passToGF)
1331  {
1333  setCharacteristic (p);
1336  prune (alpha);
1337  }
1338  if (k > 1)
1339  {
1340  result= GFMapDown (result, k);
1342  }
1343  if (extOfExt)
1344  {
1345  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1346  prune1 (oldA);
1347  }
1348  return N (d*result);
1349  }
1350  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
1351  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
1352 
1353  if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
1354  {
1355  if (algExtension)
1356  {
1357  result= modGCDFq (F, G, a);
1358  if (extOfExt)
1359  {
1360  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1361  prune1 (oldA);
1362  }
1363  return N (d*result);
1364  }
1366  {
1367  result= modGCDGF (F, G);
1368  if (passToGF)
1369  {
1371  setCharacteristic (p);
1374  prune (alpha);
1375  }
1376  if (k > 1)
1377  {
1378  result= GFMapDown (result, k);
1380  }
1381  return N (d*result);
1382  }
1383  else
1384  return N (d*modGCDFp (F,G));
1385  }
1386 
1387  TIMING_DEFINE(ez_p_hensel_lift);
1388  TIMING_START (ez_p_hensel_lift);
1389  gcdfound= Hensel (B*lcD, DD, b, lcDD);
1390  TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
1391 
1392  if (gcdfound == -1) //things became dense
1393  {
1394  if (algExtension)
1395  {
1396  result= modGCDFq (F, G, a);
1397  if (extOfExt)
1398  {
1399  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1400  prune1 (oldA);
1401  }
1402  return N (d*result);
1403  }
1405  {
1406  result= modGCDGF (F, G);
1407  if (passToGF)
1408  {
1410  setCharacteristic (p);
1413  prune (alpha);
1414  }
1415  if (k > 1)
1416  {
1417  result= GFMapDown (result, k);
1419  }
1420  return N (d*result);
1421  }
1422  else
1423  {
1424  if (p >= cf_getBigPrime(0))
1425  return N (d*sparseGCDFp (F,G));
1426  else
1427  return N (d*modGCDFp (F,G));
1428  }
1429  }
1430 
1431  if (gcdfound == 1)
1432  {
1433  TIMING_DEFINE(termination_test);
1434  TIMING_START (termination_test);
1435  contcand= content (DD[2], Variable (1));
1436  cand = DD[2] / contcand;
1437  if (B_is_F)
1438  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1439  else
1440  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
1441  TIMING_END_AND_PRINT (termination_test,
1442  "time for termination test EZ_P: ");
1443 
1444  if (passToGF && gcdfound)
1445  {
1447  setCharacteristic (p);
1450  prune (alpha);
1451  }
1452  if (k > 1 && gcdfound)
1453  {
1454  cand= GFMapDown (cand, k);
1456  }
1457  if (extOfExt && gcdfound)
1458  {
1459  cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
1460  prune1 (oldA);
1461  }
1462  }
1463  }
1464  delta--;
1465  goodPointCount= 0;
1466  }
1467  return N (d*cand);
1468 }
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
VAR long fac_NTL_char
Definition: NTLconvert.cc:41
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getCharacteristic()
Definition: cf_char.cc:51
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:56
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
void setCharacteristic(int c)
Definition: cf_char.cc:23
CanonicalForm LC(const CanonicalForm &f)
if(both_non_zero==0)
Definition: cfEzgcd.cc:84
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
STATIC_VAR int maxNumEval
Definition: cfEzgcd.cc:857
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
Definition: cfEzgcd.cc:455
static const double log2exp
Definition: cfEzgcd.cc:39
const CanonicalForm & G
Definition: cfEzgcd.cc:48
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition: cfEzgcd.cc:293
const CanonicalForm CFMap & M
Definition: cfEzgcd.cc:48
STATIC_VAR int sizePerVars1
Definition: cfEzgcd.cc:858
int k
Definition: cfEzgcd.cc:92
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
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
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
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
Variable x
Definition: cfModGcd.cc:4023
int p
Definition: cfModGcd.cc:4019
g
Definition: cfModGcd.cc:4031
int maxNumVars
Definition: cfModGcd.cc:4071
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503
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
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:35
#define GaloisFieldDomain
Definition: cf_defs.h:23
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
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
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
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
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 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 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
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:26
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:83
CanonicalForm genOne() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
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:118
Variable alpha
Definition: facAbsBiFact.cc:52
return result
Definition: facAbsBiFact.cc:76
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
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
void prune1(const Variable &alpha)
Definition: variable.cc:291
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
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
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