55 for (
int i = 0;
i <= n;
i++)
56 degsf[
i]= degsg[
i]= 0;
65 for (
int i= 1;
i <= n;
i++)
67 if (degsf[
i] != 0 && degsg[
i] != 0)
72 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= G.
level())
77 if (degsg[
i] == 0 && degsf[
i] &&
i <= F.
level())
84 if (both_non_zero == 0)
96 for (
int i= 1;
i <= n;
i++)
98 if (degsf[
i] != 0 && degsg[
i] == 0 &&
i <= Flevel)
100 if (k + both_non_zero !=
i)
107 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= Glevel)
109 if (l + g_zero + both_non_zero !=
i)
128 max_min_deg=
tmin (degsf[i], degsg[i]);
129 while (max_min_deg == 0)
132 max_min_deg=
tmin (degsf[i], degsg[i]);
134 for (
int j= i + 1;
j <=
m;
j++)
136 if ((
tmin (degsf[
j],degsg[j]) < max_min_deg) &&
137 (
tmin (degsf[j], degsg[j]) != 0))
139 max_min_deg=
tmin (degsf[j], degsg[j]);
198 for (k= evaluation.
length() + 1; k > 2; k--)
209 int l= evaluation.
length() + 1;
212 int Flevel=F.
level();
213 for (
int i= 2; i < l + 1; i++, j++)
229 for (
int i = n; i >= 0; i--)
235 ASSERT (A.
min() == 2,
"expected A.min() == 2");
244 while ((i<n) &&(max_deg == 0))
250 for (
int j= i + 1;
j <= n;
j++)
252 if (degsf[
j] > max_deg)
268 if (k == 2 && n == 3)
305 LCs [1]= MM (LeadCoeffs [1]);
306 LCs [2]= MM (LeadCoeffs [2]);
309 long termEstimate=
size (U);
310 for (
int i= A.
min(); i <= A.
max(); i++)
315 termEstimate *=
degree (U,i)*2;
318 evaluation.
append (A [i]);
329 CFList shiftedLCsEval1, shiftedLCsEval2;
330 shiftedLCs[0]=
myShift2Zero (LCs[1], shiftedLCsEval1, evaluation);
331 shiftedLCs[1]=
myShift2Zero (LCs[2], shiftedLCsEval2, evaluation);
338 lcs [0]= shiftedLCsEval1.
getFirst();
339 lcs [1]= shiftedLCsEval2.
getFirst();
350 bool noOneToOne=
false;
354 liftBounds[0]= liftBound;
355 for (
int i= 1; i < U.
level() - 1; i++)
358 false, shiftedLCsEval1, shiftedLCsEval2, Pi,
359 diophant, noOneToOne);
379 if( count == 0 && delta != 0)
381 if( count++ > maxeval )
398 if (count++ > maxeval)
404 if(
degree( Fb, 1 ) == degF )
407 if(
degree( Gb, 1 ) == degG )
412 if(
degree( Db, 1 ) <= delta )
434 if( count++ > maxeval )
442 for(
int i=pl-1;i>0;i--) exp[i]=0;
447 for(
int i=pl-1;i>
l;i--) exp[i]=0;
450 if (i.exp()<exp[
l]) exp[l]=i.exp();
461 for(
int i=ll;i>=0;i--) exp[i]=0;
471 for(
int i=0;i<=ll;i++)
487 int sizeF=
size (FF);
488 int sizeG=
size (GG);
507 if (sizeF/maxNumVars > 500 && sizeG/maxNumVars > 500)
520 CanonicalForm F,
G,
f,
g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0,
B, D0, lcF, lcG,
522 CFArray DD( 1, 2 ), lcDD( 1, 2 );
543 int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
578 return N(d*
gcd(F,g));
584 return N(d*
gcd(G,f));
593 if (sizeF/maxNumVars > 500 && sizeG/maxNumVars > 500)
613 lcF =
LC( F, x ); lcG =
LC( G, x );
614 lcD =
gcd( lcF, lcG );
623 DEBOUTLN( cerr,
"search for evaluation, delta = " << delta );
627 if (!
findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count,
640 DEBOUTLN( cerr,
"found evaluation b = " << b );
648 if (degF <= degG &&
fdivides (F, G))
658 else if (delta == degG)
660 if (degG <= degF &&
fdivides( G, F ))
683 if (!
findeval( F, G, Fbt, Gbt, Dbt, bt, delta, degF, degG, maxeval, count,
706 else if ( dd < delta )
710 Db = Dbt; Fb = Fbt; Gb = Gbt;
712 DEBOUTLN( cerr,
"now after A4, delta = " << delta );
716 if (degF <= degG &&
fdivides (F, G))
726 else if (delta == degG)
728 if (degG <= degF &&
fdivides( G, F ))
746 if ( delta != degF && delta != degG )
754 xxx1 =
gcd( DD[1], Db );
755 xxx2 =
gcd( buf, Db );
790 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
791 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
792 DEBOUTLN( cerr,
"(hensel) B = " << B );
794 DEBOUTLN( cerr,
"(hensel) b(B) = " <<
b(B) );
795 DEBOUTLN( cerr,
"(hensel) DD = " << DD );
796 DEBOUTLN( cerr,
"(hensel) lcDD = " << lcDD );
798 gcdfound=
Hensel (B*lcD, DD, b, lcDD);
800 DEBOUTLN( cerr,
"(hensel finished) DD = " << DD );
818 cand = DD[2] / contcand;
820 gcdfound =
fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
822 gcdfound =
fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) ==
G;
824 "time for termination test in EZ: ")
847 return ezgcd( FF, GG, b,
false );
870 if (FF == GG)
return FF/
Lc(FF);
874 int sizeF=
size (FF);
875 int sizeG=
size (GG);
886 if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
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();
941 return N(d*
gcd(F,g));
946 return N(d*
gcd(G,f));
953 if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
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,
1090 maxeval/maxNumVars, t ))
1110 result=
mapDown (result, primElem, imPrimElem, oldA, dest, source);
1113 return N (d*result);
1119 if (degF <= degG &&
fdivides (F, G))
1136 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1144 else if (delta == degG)
1146 if (degG <= degF &&
fdivides (G, F))
1163 G=
mapDown (G, primElem, imPrimElem, oldA, dest, source);
1183 if( !
findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1184 maxeval/maxNumVars, t ))
1204 result=
mapDown (result, primElem, imPrimElem, oldA, dest, source);
1207 return N (d*result);
1222 if (goodPointCount == 5)
1230 Db = Dbt; Fb = Fbt; Gb = Gbt;
1234 if (degF <= degG &&
fdivides (F, G))
1251 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1259 else if (delta == degG)
1261 if (degG <= degF &&
fdivides (G, F))
1278 G=
mapDown (G, primElem, imPrimElem, oldA, dest, source);
1295 if( delta != degF && delta != degG )
1302 xxx1 =
gcd( DD[1], Db );
1303 xxx2 =
gcd( buf, Db );
1345 result=
mapDown (result, primElem, imPrimElem, oldA, dest, source);
1348 return N (d*result);
1350 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
1351 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
1360 result=
mapDown (result, primElem, imPrimElem, oldA, dest, source);
1363 return N (d*result);
1381 return N (d*result);
1389 gcdfound=
Hensel (B*lcD, DD, b, lcDD);
1399 result=
mapDown (result, primElem, imPrimElem, oldA, dest, source);
1402 return N (d*result);
1420 return N (d*result);
1436 cand = DD[2] / contcand;
1438 gcdfound =
fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1440 gcdfound =
fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) ==
G;
1442 "time for termination test EZ_P: ");
1444 if (passToGF && gcdfound)
1452 if (k > 1 && gcdfound)
1457 if (extOfExt && gcdfound)
1459 cand=
mapDown (cand, primElem, imPrimElem, oldA, dest, source);
static CanonicalForm myReverseShift(const CanonicalForm &F, const CFList &evaluation)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void size_t count
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 ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
generate random elements in GF
Conversion to and from NTL.
This file defines functions for Hensel lifting.
static CanonicalForm bound(const CFMatrix &M)
void prune1(const Variable &alpha)
const CanonicalForm CFMap & M
gmp_float exp(const gmp_float &a)
some useful template functions.
functions to print debug output
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
TIMING_START(fac_alg_resultant)
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 ...
#define DEBINCLEVEL(stream, msg)
factory's class for variables
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
generate random evaluation points
static Evaluation optimize4Lift(const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A)
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)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
class to generate random evaluation points
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...
const CanonicalForm int const CFList & evaluation
#define DEBDECLEVEL(stream, msg)
static const double log2exp
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Extended Zassenhaus GCD over finite fields and Z.
bool delta(X x, Y y, D d)
void prune(Variable &alpha)
This file implements functions to map between extensions of finite fields.
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
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...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
const CanonicalForm CFMap CFMap & N
int status int void * buf
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
void setValue(int i, const CanonicalForm &f)
static const int SW_RATIONAL
set to 1 for computations over Q
generate random elements in F_p
generate random integers, random elements of finite fields
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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...
class to iterate through CanonicalForm's
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
generate random elements in F_p(alpha)
int ipower(int b, int m)
int ipower ( int b, int m )
class to evaluate a polynomial at points
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
int cf_getBigPrime(int i)
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
#define GaloisFieldDomain
bool isZero(const CFArray &A)
checks if entries of A are zero
modular and sparse modular GCD algorithms over finite fields and Z.
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
const CanonicalForm CFMap CFMap int & both_non_zero
TIMING_DEFINE_PRINT(ez_eval) TIMING_DEFINE_PRINT(ez_compress) TIMING_DEFINE_PRINT(ez_hensel_lift) TIMING_DEFINE_PRINT(ez_content) TIMING_DEFINE_PRINT(ez_termination) static int compress4EZGCD(const CanonicalForm &F
#define ASSERT(expression, message)
#define DEBOUTLN(stream, objects)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
static void gcd_mon_rec(CanonicalForm G, CanonicalForm &cf, int *exp, int pl)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
static CanonicalForm myShift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation)