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();
885
890
892 {
894 }
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,
922
925
931
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
980 {
982 }
983
992 {
997 else if (
p == 5 ||
p == 7)
999 else
1002 F= F.mapinto();
1005 }
1008 {
1012 else
1017 }
1019 {
1023 if (
p == 2 && d < 6)
1024 {
1029 if (d < 3)
1030 {
1031 #ifdef HAVE_FLINT
1037 #elif defined(HAVE_NTL)
1039 {
1042 }
1046 #else
1048 #endif
1050 }
1051 else
1052 {
1053 #ifdef HAVE_FLINT
1059 #elif defined(HAVE_NTL)
1061 {
1064 }
1068 #else
1070 #endif
1072 }
1075 }
1076 else if ((
p == 3 && d < 4) || ((
p == 5 ||
p == 7) && d < 3))
1077 {
1082 #ifdef HAVE_FLINT
1088 #elif defined(HAVE_NTL)
1090 {
1093 }
1097 #else
1099 #endif
1103 }
1105 {
1110 }
1111 }
1112
1115
1118
1121 else
1122 {
1125 else
1127 }
1128
1131 int o, t;
1132 o= 0;
1133 t= 1;
1137 {
1139 if( !
findeval( F,
G,
Fb,
Gb,
Db,
b, delta,
degF,
degG,
maxeval,
count, o,
1141 {
1146 {
1152 }
1154 {
1157 }
1159 {
1162 }
1164 }
1168 {
1170 {
1172 {
1178 }
1180 {
1183 }
1185 {
1188 }
1190 }
1191 else
1193 }
1194 else if (delta ==
degG)
1195 {
1197 {
1199 {
1205 }
1207 {
1210 }
1212 {
1215 }
1217 }
1218 else
1220 }
1221 if( delta == 0 )
1222 {
1228 }
1229 while( true )
1230 {
1233 if( !
findeval(F,
G,
Fbt,
Gbt,
Dbt,
bt, delta,
degF,
degG,
maxeval,
count, o,
1235 {
1240 {
1246 }
1248 {
1251 }
1253 {
1256 }
1258 }
1262 {
1268 }
1270 {
1273 break;
1274 }
1276 {
1281 }
1283 {
1285 {
1287 {
1293 }
1295 {
1298 }
1300 {
1303 }
1305 }
1306 else
1308 }
1309 else if (delta ==
degG)
1310 {
1312 {
1314 {
1320 }
1322 {
1325 }
1327 {
1330 }
1332 }
1333 else
1335 }
1336 if( delta == 0 )
1337 {
1343 }
1344 }
1345 if( delta !=
degF && delta !=
degG )
1346 {
1354 if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
1356 || (
xxx1.inCoeffDomain() && !
xxx2.inCoeffDomain()))
1357 {
1363 }
1364 else if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
1366 || (!
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()))
1367 {
1374 }
1375 else
1376 {
1381 {
1387 }
1389 {
1392 }
1394 {
1397 }
1399 }
1402
1404 {
1406 {
1409 {
1412 }
1414 }
1416 {
1419 {
1425 }
1427 {
1430 }
1432 }
1433 else
1435 }
1436
1441
1443 {
1445 {
1448 {
1451 }
1453 }
1455 {
1458 {
1464 }
1466 {
1469 }
1471 }
1472 else
1473 {
1476 else
1478 }
1479 }
1480
1482 {
1489 else
1492 "time for termination test EZ_P: ");
1493
1495 {
1501 }
1503 {
1506 }
1508 {
1511 }
1512 }
1513 }
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)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
void prune1(const Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
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)