 |
My Project
debian-1:4.1.1-p2+ds-4build2
|
#include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cfEzgcd.h"
#include "cfModGcd.h"
#include "cf_util.h"
#include "cf_map_ext.h"
#include "cf_algorithm.h"
#include "cf_reval.h"
#include "cf_random.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "facHensel.h"
#include "NTLconvert.h"
Go to the source code of this file.
|
| 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 |
|
| for (int i=0;i<=n;i++) degsf[i] |
|
| if (both_non_zero==0) |
|
| while (k > 0) |
|
| DELETE_ARRAY (degsf) |
|
| DELETE_ARRAY (degsg) |
|
static CanonicalForm | myShift2Zero (const CanonicalForm &F, CFList &Feval, const CFList &evaluation) |
|
static CanonicalForm | myReverseShift (const CanonicalForm &F, const CFList &evaluation) |
|
static Evaluation | optimize4Lift (const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A) |
|
static int | Hensel (const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs) |
|
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) |
|
static CanonicalForm | ezgcd (const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal) |
| real implementation of EZGCD over Z More...
|
|
CanonicalForm | ezgcd (const CanonicalForm &FF, const CanonicalForm &GG) |
| Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm. More...
|
|
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 algorithm. More...
|
|
This file implements the GCD of two multivariate polynomials over Q or F_q using EZ-GCD as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahnn
- Author
- Martin Lee
Definition in file cfEzgcd.cc.
◆ DELETE_ARRAY() [1/2]
◆ DELETE_ARRAY() [2/2]
◆ ezgcd() [1/2]
Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.
Definition at line 796 of file cfEzgcd.cc.
◆ ezgcd() [2/2]
real implementation of EZGCD over Z
—> A2
—> A3
—> A4
—> A5
—> A6
—> A7
—> A8 (gcdfound)
—> A9
Definition at line 441 of file cfEzgcd.cc.
447 int sizeF=
size (FF);
451 if ((sizeF==1) || (sizeG==1))
473 CanonicalForm F,
G,
f,
g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0,
B, D0, lcF, lcG,
475 CFArray DD( 1, 2 ), lcDD( 1, 2 );
496 int best_level= compress4EZGCD (F,
G,
M,
N, smallestDegLev);
517 if ( F.isUnivariate() )
522 if(F.mvar()==
G.
mvar())
531 return N(d*
gcd(F,
g));
566 lcF =
LC( F,
x ); lcG =
LC(
G,
x );
567 lcD =
gcd( lcF, lcG );
576 DEBOUTLN( cerr,
"search for evaluation, delta = " <<
delta );
580 if (!
findeval( F,
G, Fb, Gb, Db,
b,
delta, degF, degG, maxeval,
count,
611 else if (
delta == degG)
636 if (!
findeval( F,
G, Fbt, Gbt, Dbt, bt,
delta, degF, degG, maxeval,
count,
659 else if ( dd <
delta )
663 Db = Dbt; Fb = Fbt; Gb = Gbt;
679 else if (
delta == degG)
707 xxx1 =
gcd( DD[1], Db );
743 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
744 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
748 DEBOUTLN( cerr,
"(hensel) DD = " << DD );
749 DEBOUTLN( cerr,
"(hensel) lcDD = " << lcDD );
751 gcdfound=
Hensel (
B*lcD, DD,
b, lcDD);
753 DEBOUTLN( cerr, "(hensel finished) DD = " << DD );
771 cand = DD[2] / contcand;
777 "time for termination test in EZ: ")
◆ EZGCD_P()
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.
Definition at line 815 of file cfEzgcd.cc.
823 if (FF ==
GG)
return FF/
Lc(FF);
827 int sizeF=
size (FF);
840 CanonicalForm F,
G,
f,
g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0,
B, D0, lcF, lcG,
842 CFArray DD( 1, 2 ), lcDD( 1, 2 );
859 int best_level= compress4EZGCD (F,
G,
M,
N, smallestDegLev);
861 if (best_level == 0)
return G.
genOne();
874 if( F.isUnivariate() &&
G.isUnivariate() )
876 if( F.mvar() ==
G.
mvar() )
882 if ( F.isUnivariate())
885 return N(d*
gcd(F,
g));
913 bool passToGF=
false;
914 bool extOfExt=
false;
926 else if (
p == 5 ||
p == 7)
959 bool primFail=
false;
962 ASSERT (!primFail,
"failure in integer factorizer");
966 BuildIrred (NTLIrredpoly, d*3);
973 BuildIrred (NTLIrredpoly, d*2);
980 else if ((
p == 3 && d < 4) || ((
p == 5 ||
p == 7) && d < 3))
987 bool primFail=
false;
990 ASSERT (!primFail,
"failure in integer factorizer");
992 BuildIrred (NTLIrredpoly, d*2);
1001 F=
mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1002 G=
mapUp (
G, a, v2, primElem, imPrimElem, source, dest);
1007 lcF =
LC( F,
x ); lcG =
LC(
G,
x );
1008 lcD =
gcd( lcF, lcG );
1028 int goodPointCount= 0;
1033 if( !
findeval( F,
G, Fb, Gb, Db,
b,
delta, degF, degG, maxeval,
count, o,
1080 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1088 else if (
delta == degG)
1107 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1127 if( !
findeval(F,
G,Fbt,Gbt,Dbt, bt,
delta, degF, degG, maxeval,
count, o,
1166 if (goodPointCount == 5)
1174 Db = Dbt; Fb = Fbt; Gb = Gbt;
1195 F=
mapDown (F, primElem, imPrimElem, oldA, dest, source);
1203 else if (
delta == degG)
1222 G=
mapDown (
G, primElem, imPrimElem, oldA, dest, source);
1246 xxx1 =
gcd( DD[1], Db );
1294 DD[2] = DD[2] * (
b( lcDD[2] ) /
lc( DD[2] ) );
1295 DD[1] = DD[1] * (
b( lcDD[1] ) /
lc( DD[1] ) );
1333 gcdfound=
Hensel (
B*lcD, DD,
b, lcDD);
1380 cand = DD[2] / contcand;
1386 "time for termination test EZ_P: ");
1388 if (passToGF && gcdfound)
1396 if (
k > 1 && gcdfound)
1401 if (extOfExt && gcdfound)
◆ findeval()
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 |
|
) |
| |
|
static |
◆ for()
for |
( |
int |
i = 0; i <= n; i++ | ) |
|
◆ Hensel()
Definition at line 293 of file cfEzgcd.cc.
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;
329 CFList shiftedLCsEval1, shiftedLCsEval2;
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);
◆ if()
◆ myReverseShift()
◆ myShift2Zero()
◆ optimize4Lift()
Definition at line 223 of file cfEzgcd.cc.
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++)
268 if (
k == 2 && n == 3)
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
ez_eval |
| ) |
const & |
◆ while()
◆ both_non_zero
◆ degsf
◆ degsg
◆ f_zero
◆ Flevel
◆ g_zero
◆ Glevel
◆ log2exp
const double log2exp = 1.442695041 |
|
static |
◆ max_min_deg
◆ maxNumEval
◆ sizePerVars1
static const int SW_RATIONAL
set to 1 for computations over Q
generate random elements in F_p
bool isZero(const CFArray &A)
checks if entries of A are zero
#define DEBOUTLN(stream, objects)
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)
class to evaluate a polynomial at points
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
const CanonicalForm int const CFList & evaluation
#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)
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.
#define ASSERT(expression, message)
int status int void * buf
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)
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
#define DEBINCLEVEL(stream, msg)
void prune(Variable &alpha)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
#define DEBDECLEVEL(stream, msg)
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)
const CanonicalForm CFMap CFMap int & both_non_zero
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)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
static CanonicalForm myReverseShift(const CanonicalForm &F, const CFList &evaluation)
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)
static CanonicalForm myShift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation)
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)
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)