My Project
Loading...
Searching...
No Matches
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{
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:4076
CanonicalForm b
Definition: cfModGcd.cc:4103
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)
1012 else
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
1143 result= gcd (F,G);
1145 if (passToGF)
1146 {
1151 prune (alpha);
1152 }
1153 if (k > 1)
1154 {
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 {
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 {
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)
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
1237 result= gcd (F,G);
1239 if (passToGF)
1240 {
1245 prune (alpha);
1246 }
1247 if (k > 1)
1248 {
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)
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 {
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 {
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)
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 {
1378 result= gcd (F,G);
1380 if (passToGF)
1381 {
1386 prune (alpha);
1387 }
1388 if (k > 1)
1389 {
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 {
1424 prune (alpha);
1425 }
1426 if (k > 1)
1427 {
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 {
1463 prune (alpha);
1464 }
1465 if (k > 1)
1466 {
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 {
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
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
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 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:478
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
int maxNumVars
Definition: cfModGcd.cc:4130
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1223
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3562
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:872
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:37
#define GaloisFieldDomain
Definition: cf_defs.h:18
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: variable.h:33
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:52
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
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
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94
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
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
int gcd(int a, int b)
Definition: walkSupport.cc:836