 |
My Project
debian-1:4.1.2-p1+ds-2
|
Go to the source code of this file.
Extended Zassenhaus GCD over finite fields and Z
Definition in file cfEzgcd.h.
◆ 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.
◆ EZGCD_P()
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.
868 if (FF.isUnivariate() &&
fdivides(FF,
GG))
return FF/
Lc(FF);
870 if (FF ==
GG)
return FF/
Lc(FF);
874 int sizeF=
size (FF);
896 CanonicalForm F,
G,
f,
g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0,
B, D0, lcF, lcG,
898 CFArray DD( 1, 2 ), lcDD( 1, 2 );
915 int best_level= compress4EZGCD (F,
G,
M,
N, smallestDegLev);
917 if (best_level == 0)
return G.
genOne();
930 if( F.isUnivariate() &&
G.isUnivariate() )
932 if( F.mvar() ==
G.
mvar() )
938 if ( F.isUnivariate())
941 return N(d*
gcd(F,
g));
969 bool passToGF=
false;
970 bool extOfExt=
false;
982 else if (
p == 5 ||
p == 7)
1008 if (
p == 2 && d < 6)
1015 bool primFail=
false;
1018 ASSERT (!primFail,
"failure in integer factorizer");
1022 BuildIrred (NTLIrredpoly, d*3);
1029 BuildIrred (NTLIrredpoly, d*2);
1036 else if ((
p == 3 && d < 4) || ((
p == 5 ||
p == 7) && d < 3))
1043 bool primFail=
false;
1046 ASSERT (!primFail,
"failure in integer factorizer");
1048 BuildIrred (NTLIrredpoly, d*2);
1057 F=
mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1058 G=
mapUp (
G, a, v2, primElem, imPrimElem, source, dest);
1063 lcF =
LC( F,
x ); lcG =
LC(
G,
x );
1064 lcD =
gcd( lcF, lcG );
1084 int goodPointCount= 0;
1089 if( !
findeval( F,
G, Fb, Gb, Db,
b,
delta, degF, degG, maxeval,
count, o,
1136 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1144 else if (
delta == degG)
1163 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1183 if( !
findeval(F,
G,Fbt,Gbt,Dbt, bt,
delta, degF, degG, maxeval,
count, o,
1222 if (goodPointCount == 5)
1230 Db = Dbt; Fb = Fbt; Gb = Gbt;
1251 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1259 else if (
delta == degG)
1278 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1302 xxx1 =
gcd( DD[1], Db );
1350 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
1351 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
1389 gcdfound=
Hensel (
B*lcD, DD,
b, lcDD);
1436 cand = DD[2] / contcand;
1442 "time for termination test EZ_P: ");
1444 if (passToGF && gcdfound)
1452 if (
k > 1 && gcdfound)
1457 if (extOfExt && gcdfound)
generate random elements in F_p
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
generate random elements in F_p(alpha)
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...
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
const CanonicalForm CFMap CFMap & N
int cf_getBigPrime(int i)
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
bool delta(X x, Y y, D d)
const CanonicalForm CFMap & M
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
#define GaloisFieldDomain
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
#define ASSERT(expression, message)
int status int void * buf
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)
TIMING_START(fac_alg_resultant)
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....
static const double log2exp
void prune(Variable &alpha)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
class to generate random evaluation points
generate random elements in GF
int ipower(int b, int m)
int ipower ( int b, int m )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
factory's class for variables
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
STATIC_VAR int sizePerVars1
STATIC_VAR int maxNumEval
int status int void size_t count
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
void prune1(const Variable &alpha)
INST_VAR CanonicalForm gf_mipo
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
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...
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 ,...
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)