Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.
877{
880 else if (FF.isZero() &&
GG.
isZero())
return FF.genOne();
882 if (FF.isUnivariate() &&
fdivides(FF,
GG))
return FF/
Lc(FF);
884 if (FF ==
GG)
return FF/
Lc(FF);
885
888 int sizeF=
size (FF);
890
891 if (sizeF==1)
892 {
894 }
895 else if (sizeG==1)
896 {
898 }
899
901 {
906 else
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 );
914 int maxeval;
920 int gcdfound = 0;
922
923 F= FF;
925
927 int smallestDegLev;
930 int best_level= compress4EZGCD (F,
G,
M,
N, smallestDegLev);
931
932 if (best_level == 0)
return G.
genOne();
933
937
944
945 if( F.isUnivariate() &&
G.isUnivariate() )
946 {
947 if( F.mvar() ==
G.
mvar() )
949 else
952 }
953 if ( F.isUnivariate())
954 {
956 return N(d*
gcd(F,
g));
957 }
959 {
962 }
963
967
969 {
974 else
976 }
977
978 int dummy= 0;
980 {
982 }
983
984 bool passToGF= false;
985 bool extOfExt= false;
992 {
997 else if (
p == 5 ||
p == 7)
999 else
1001 passToGF= true;
1002 F= F.mapinto();
1005 }
1008 {
1012 else
1017 }
1019 {
1021 oldA= a;
1023 if (
p == 2 && d < 6)
1024 {
1025 bool primFail= false;
1028 ASSERT (!primFail,
"failure in integer factorizer");
1029 if (d < 3)
1030 {
1031 #ifdef HAVE_FLINT
1032 nmod_poly_t Irredpoly;
1034 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom, 3*d+1);
1037 #elif defined(HAVE_NTL)
1039 {
1042 }
1043 zz_pX NTLIrredpoly;
1044 BuildIrred (NTLIrredpoly, d*3);
1046 #else
1048 #endif
1050 }
1051 else
1052 {
1053 #ifdef HAVE_FLINT
1054 nmod_poly_t Irredpoly;
1056 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom, 2*d+1);
1059 #elif defined(HAVE_NTL)
1061 {
1064 }
1065 zz_pX NTLIrredpoly;
1066 BuildIrred (NTLIrredpoly, d*2);
1068 #else
1070 #endif
1072 }
1074 extOfExt= true;
1075 }
1076 else if ((
p == 3 && d < 4) || ((
p == 5 ||
p == 7) && d < 3))
1077 {
1078 bool primFail= false;
1081 ASSERT (!primFail,
"failure in integer factorizer");
1082 #ifdef HAVE_FLINT
1083 nmod_poly_t Irredpoly;
1085 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom, 2*d+1);
1088 #elif defined(HAVE_NTL)
1090 {
1093 }
1094 zz_pX NTLIrredpoly;
1095 BuildIrred (NTLIrredpoly, d*2);
1097 #else
1099 #endif
1102 extOfExt= true;
1103 }
1104 if (extOfExt)
1105 {
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
1118
1119 if (algExtension)
1121 else
1122 {
1125 else
1127 }
1128
1131 int o, t;
1132 o= 0;
1133 t= 1;
1134 int goodPointCount= 0;
1136 while( !gcdfound )
1137 {
1139 if( !
findeval( F,
G, Fb, Gb, Db,
b, delta, degF, degG, maxeval,
count, o,
1141 {
1145 if (passToGF)
1146 {
1152 }
1154 {
1157 }
1158 if (extOfExt)
1159 {
1162 }
1164 }
1167 if (delta == degF)
1168 {
1170 {
1171 if (passToGF)
1172 {
1178 }
1180 {
1183 }
1184 if (extOfExt)
1185 {
1186 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1188 }
1190 }
1191 else
1193 }
1194 else if (delta == degG)
1195 {
1197 {
1198 if (passToGF)
1199 {
1205 }
1207 {
1210 }
1211 if (extOfExt)
1212 {
1213 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1215 }
1217 }
1218 else
1220 }
1221 if( delta == 0 )
1222 {
1223 if (passToGF)
1228 }
1229 while( true )
1230 {
1233 if( !
findeval(F,
G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval,
count, o,
1235 {
1239 if (passToGF)
1240 {
1246 }
1248 {
1251 }
1252 if (extOfExt)
1253 {
1256 }
1258 }
1261 if( dd == 0 )
1262 {
1263 if (passToGF)
1268 }
1269 if( dd == delta )
1270 {
1271 goodPointCount++;
1272 if (goodPointCount == 5)
1273 break;
1274 }
1275 if( dd < delta )
1276 {
1277 goodPointCount= 0;
1280 Db = Dbt; Fb = Fbt; Gb = Gbt;
1281 }
1282 if (delta == degF)
1283 {
1285 {
1286 if (passToGF)
1287 {
1293 }
1295 {
1298 }
1299 if (extOfExt)
1300 {
1301 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1303 }
1305 }
1306 else
1308 }
1309 else if (delta == degG)
1310 {
1312 {
1313 if (passToGF)
1314 {
1320 }
1322 {
1325 }
1326 if (extOfExt)
1327 {
1328 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1330 }
1332 }
1333 else
1335 }
1336 if( delta == 0 )
1337 {
1338 if (passToGF)
1343 }
1344 }
1345 if( delta != degF && delta != degG )
1346 {
1347 bool B_is_F;
1350 DD[1] = Fb / Db;
1352 xxx1 =
gcd( DD[1], Db );
1357 {
1359 DD[2] = Db;
1360 lcDD[1] = lcF;
1361 lcDD[2] = lcD;
1362 B_is_F = true;
1363 }
1367 {
1370 DD[2] = Db;
1371 lcDD[1] = lcG;
1372 lcDD[2] = lcD;
1373 B_is_F = false;
1374 }
1375 else
1376 {
1380 if (passToGF)
1381 {
1387 }
1389 {
1392 }
1393 if (extOfExt)
1394 {
1397 }
1399 }
1400 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
1401 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
1402
1404 {
1405 if (algExtension)
1406 {
1408 if (extOfExt)
1409 {
1412 }
1414 }
1416 {
1418 if (passToGF)
1419 {
1425 }
1427 {
1430 }
1432 }
1433 else
1435 }
1436
1439 gcdfound=
Hensel (
B*lcD, DD,
b, lcDD);
1441
1442 if (gcdfound == -1)
1443 {
1444 if (algExtension)
1445 {
1447 if (extOfExt)
1448 {
1451 }
1453 }
1455 {
1457 if (passToGF)
1458 {
1464 }
1466 {
1469 }
1471 }
1472 else
1473 {
1476 else
1478 }
1479 }
1480
1481 if (gcdfound == 1)
1482 {
1486 cand = DD[2] / contcand;
1487 if (B_is_F)
1489 else
1492 "time for termination test EZ_P: ");
1493
1494 if (passToGF && gcdfound)
1495 {
1501 }
1502 if (
k > 1 && gcdfound)
1503 {
1506 }
1507 if (extOfExt && gcdfound)
1508 {
1511 }
1512 }
1513 }
1515 goodPointCount= 0;
1516 }
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)
const CanonicalForm CFMap CFMap & N
STATIC_VAR int maxNumEval
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
static const double log2exp
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
const CanonicalForm CFMap & M
STATIC_VAR int sizePerVars1
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)
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...
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....
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
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...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
#define ASSERT(expression, message)
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
#define GaloisFieldDomain
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
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
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 ,...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
int cf_getBigPrime(int i)
GLOBAL_VAR flint_rand_t FLINTrandom
VAR void(* factoryError)(const char *s)
int ipower(int b, int m)
int ipower ( int b, int m )
generate random elements in F_p(alpha)
generate random elements in F_p
generate random elements in GF
factory's class for variables
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear(FLINTmipo)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
INST_VAR CanonicalForm gf_mipo
bool delta(X x, Y y, D d)
int status int void size_t count
int status int void * buf
#define TIMING_END_AND_PRINT(t, msg)
void prune1(const Variable &alpha)
void prune(Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables