Loading...
Searching...
No Matches
cfEzgcd.h File Reference

Extended Zassenhaus GCD over finite fields and Z. More...

Go to the source code of this file.

## Functions

CanonicalForm | EZGCD_P (const CanonicalForm &A, const CanonicalForm &B)
| Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.
CanonicalForm | ezgcd (const CanonicalForm &f, const CanonicalForm &g)
| Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.

## Detailed Description

Extended Zassenhaus GCD over finite fields and Z.

Definition in file cfEzgcd.h.

## Function Documentation

## ezgcd()

CanonicalForm ezgcd | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g )

Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.

Definition at line 861 of file cfEzgcd.cc.

{
REvaluation b;
return ezgcd( FF, GG, b, false );
}
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition cfEzgcd.cc:498
GG
const CanonicalForm & GG
Definition cfModGcd.cc:4084
b
CanonicalForm b
Definition cfModGcd.cc:4111
REvaluation
class to generate random evaluation points
Definition cf_reval.h:26

## EZGCD_P()

CanonicalForm EZGCD_P | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B )

Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.

Definition at line 876 of file cfEzgcd.cc.

{
if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
else if (FF.isZero() && GG.isZero()) return FF.genOne();
if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
if (FF == GG) return FF/Lc(FF);
int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
Variable a, oldA;
int sizeF= size (FF);
int sizeG= size (GG);
if (sizeF==1)
{
return gcd_mon( FF, GG );
}
else if (sizeG==1)
{
return gcd_mon( GG, FF );
}
if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
{
if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
return modGCDFq (FF, GG, a);
else if (CFFactory::gettype() == GaloisFieldDomain)
return modGCDGF (FF, GG);
else
return modGCDFp (FF, GG);
}
CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
lcD;
CFArray DD( 1, 2 ), lcDD( 1, 2 );
int degF, degG, delta, count;
int maxeval;
int ch=getCharacteristic();
maxeval= tmin((ch/
(int)(ilog2(ch)*log2exp))*2, maxNumEval);
count= 0; // number of eval. used
REvaluation b, bt;
int gcdfound = 0;
Variable x = Variable(1);
F= FF;
G= GG;
CFMap M,N;
int smallestDegLev;
TIMING_DEFINE(ez_p_compress);
TIMING_START (ez_p_compress);
int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
if (best_level == 0) return G.genOne();
F= M (F);
G= M (G);
TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
TIMING_DEFINE (ez_p_content)
TIMING_START (ez_p_content)
f = content( F, x ); g = content( G, x );
d = gcd( f, g );
F /= f; G /= g;
TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
if( F.isUnivariate() && G.isUnivariate() )
{
if( F.mvar() == G.mvar() )
d *= gcd( F, G );
else
return N (d);
return N (d);
}
if ( F.isUnivariate())
{
g= content (G,G.mvar());
return N(d*gcd(F,g));
}
if ( G.isUnivariate())
{
f= content (F,F.mvar());
return N(d*gcd(G,f));
}
maxNumVars= tmax (getNumVars (F), getNumVars (G));
sizeF= size (F);
sizeG= size (G);
if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
{
if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
return N (d*modGCDFq (F, G, a));
else if (CFFactory::gettype() == GaloisFieldDomain)
return N (d*modGCDGF (F, G));
else
return N (d*modGCDFp (F, G));
}
int dummy= 0;
if( gcd_test_one( F, G, false, dummy ) )
{
return N (d);
}
bool passToGF= false;
bool extOfExt= false;
int p= getCharacteristic();
bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
int k= 1;
CanonicalForm primElem, imPrimElem;
CFList source, dest;
if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
{
if (p == 2)
setCharacteristic (2, 12, 'Z');
else if (p == 3)
setCharacteristic (3, 4, 'Z');
else if (p == 5 || p == 7)
setCharacteristic (p, 3, 'Z');
else
setCharacteristic (p, 2, 'Z');
passToGF= true;
F= F.mapinto();
G= G.mapinto();
maxeval= 2*ipower (p, getGFDegree());
}
else if (CFFactory::gettype() == GaloisFieldDomain &&
ipower (p , getGFDegree()) < 50)
{
k= getGFDegree();
if (ipower (p, 2*k) > 50)
setCharacteristic (p, 2*k, gf_name);
else
setCharacteristic (p, 3*k, gf_name);
F= GFMapUp (F, k);
G= GFMapUp (G, k);
maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
}
else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
{
int d= degree (getMipo (a));
oldA= a;
Variable v2;
if (p == 2 && d < 6)
{
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (a, vBuf, primFail);
ASSERT (!primFail, "failure in integer factorizer");
if (d < 3)
{
#ifdef HAVE_FLINT
nmod_poly_t Irredpoly;
nmod_poly_init(Irredpoly,p);
nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 3*d+1);
CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
nmod_poly_clear(Irredpoly);
#elif defined(HAVE_NTL)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*3);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing: EZGCD_P");
#endif
v2= rootOf (newMipo);
}
else
{
#ifdef HAVE_FLINT
nmod_poly_t Irredpoly;
nmod_poly_init(Irredpoly,p);
nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
nmod_poly_clear(Irredpoly);
#elif defined(HAVE_NTL)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*2);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing: EZGCD_P");
#endif
v2= rootOf (newMipo);
}
imPrimElem= mapPrimElem (primElem, a, v2);
extOfExt= true;
}
else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
{
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (a, vBuf, primFail);
ASSERT (!primFail, "failure in integer factorizer");
#ifdef HAVE_FLINT
nmod_poly_t Irredpoly;
nmod_poly_init(Irredpoly,p);
nmod_poly_randtest_monic_irreducible(Irredpoly, FLINTrandom, 2*d+1);
CanonicalForm newMipo=convertnmod_poly_t2FacCF(Irredpoly,Variable(1));
nmod_poly_clear(Irredpoly);
#elif defined(HAVE_NTL)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*2);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing: EZGCD_P");
#endif
v2= rootOf (newMipo);
imPrimElem= mapPrimElem (primElem, a, v2);
extOfExt= true;
}
if (extOfExt)
{
maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
a= v2;
}
}
lcF = LC( F, x ); lcG = LC( G, x );
lcD = gcd( lcF, lcG );
delta = 0;
degF = degree( F, x ); degG = degree( G, x );
if (algExtension)
b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
else
{ // both not in extension given by algebraic variable
if (CFFactory::gettype() != GaloisFieldDomain)
b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
else
b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
}
CanonicalForm cand, contcand;
CanonicalForm result;
int o, t;
o= 0;
t= 1;
int goodPointCount= 0;
TIMING_DEFINE(ez_p_eval);
while( !gcdfound )
{
TIMING_START (ez_p_eval);
if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
maxeval/maxNumVars, t ))
{ // too many eval. used --> try another method
Off (SW_USE_EZGCD_P);
result= gcd (F,G);
On (SW_USE_EZGCD_P);
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
result= GF2FalphaRep (result, alpha);
prune (alpha);
}
if (k > 1)
{
result= GFMapDown (result, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*result);
}
TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
delta = degree( Db );
if (delta == degF)
{
if (degF <= degG && fdivides (F, G))
{
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
F= GF2FalphaRep (F, alpha);
prune (alpha);
}
if (k > 1)
{
F= GFMapDown (F, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*F);
}
else
delta--;
}
else if (delta == degG)
{
if (degG <= degF && fdivides (G, F))
{
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
G= GF2FalphaRep (G, alpha);
prune (alpha);
}
if (k > 1)
{
G= GFMapDown (G, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*G);
}
else
delta--;
}
if( delta == 0 )
{
if (passToGF)
setCharacteristic (p);
if (k > 1)
setCharacteristic (p, k, gf_name);
return N (d);
}
while( true )
{
bt = b;
TIMING_START (ez_p_eval);
if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
maxeval/maxNumVars, t ))
{ // too many eval. used --> try another method
Off (SW_USE_EZGCD_P);
result= gcd (F,G);
On (SW_USE_EZGCD_P);
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
result= GF2FalphaRep (result, alpha);
prune (alpha);
}
if (k > 1)
{
result= GFMapDown (result, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*result);
}
TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
int dd = degree( Dbt );
if( dd == 0 )
{
if (passToGF)
setCharacteristic (p);
if (k > 1)
setCharacteristic (p, k, gf_name);
return N (d);
}
if( dd == delta )
{
goodPointCount++;
if (goodPointCount == 5)
break;
}
if( dd < delta )
{
goodPointCount= 0;
delta = dd;
b = bt;
Db = Dbt; Fb = Fbt; Gb = Gbt;
}
if (delta == degF)
{
if (degF <= degG && fdivides (F, G))
{
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
F= GF2FalphaRep (F, alpha);
prune (alpha);
}
if (k > 1)
{
F= GFMapDown (F, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*F);
}
else
delta--;
}
else if (delta == degG)
{
if (degG <= degF && fdivides (G, F))
{
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
G= GF2FalphaRep (G, alpha);
prune (alpha);
}
if (k > 1)
{
G= GFMapDown (G, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*G);
}
else
delta--;
}
if( delta == 0 )
{
if (passToGF)
setCharacteristic (p);
if (k > 1)
setCharacteristic (p, k, gf_name);
return N (d);
}
}
if( delta != degF && delta != degG )
{
bool B_is_F;
CanonicalForm xxx1, xxx2;
CanonicalForm buf;
DD[1] = Fb / Db;
buf= Gb/Db;
xxx1 = gcd( DD[1], Db );
xxx2 = gcd( buf, Db );
if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
(size (F) <= size (G)))
|| (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
{
B = F;
DD[2] = Db;
lcDD[1] = lcF;
lcDD[2] = lcD;
B_is_F = true;
}
else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
(size (G) < size (F)))
|| (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
{
DD[1] = buf;
B = G;
DD[2] = Db;
lcDD[1] = lcG;
lcDD[2] = lcD;
B_is_F = false;
}
else // special case handling
{
Off (SW_USE_EZGCD_P);
result= gcd (F,G);
On (SW_USE_EZGCD_P);
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
result= GF2FalphaRep (result, alpha);
prune (alpha);
}
if (k > 1)
{
result= GFMapDown (result, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt)
{
result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*result);
}
DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
{
if (algExtension)
{
result= modGCDFq (F, G, a);
if (extOfExt)
{
result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*result);
}
if (CFFactory::gettype() == GaloisFieldDomain)
{
result= modGCDGF (F, G);
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
result= GF2FalphaRep (result, alpha);
prune (alpha);
}
if (k > 1)
{
result= GFMapDown (result, k);
setCharacteristic (p, k, gf_name);
}
return N (d*result);
}
else
return N (d*modGCDFp (F,G));
}
TIMING_DEFINE(ez_p_hensel_lift);
TIMING_START (ez_p_hensel_lift);
gcdfound= Hensel (B*lcD, DD, b, lcDD);
TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
if (gcdfound == -1) //things became dense
{
if (algExtension)
{
result= modGCDFq (F, G, a);
if (extOfExt)
{
result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
return N (d*result);
}
if (CFFactory::gettype() == GaloisFieldDomain)
{
result= modGCDGF (F, G);
if (passToGF)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
result= GF2FalphaRep (result, alpha);
prune (alpha);
}
if (k > 1)
{
result= GFMapDown (result, k);
setCharacteristic (p, k, gf_name);
}
return N (d*result);
}
else
{
if (p >= cf_getBigPrime(0))
return N (d*sparseGCDFp (F,G));
else
return N (d*modGCDFp (F,G));
}
}
if (gcdfound == 1)
{
TIMING_DEFINE(termination_test);
TIMING_START (termination_test);
contcand= content (DD[2], Variable (1));
cand = DD[2] / contcand;
if (B_is_F)
gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
else
gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
TIMING_END_AND_PRINT (termination_test,
"time for termination test EZ_P: ");
if (passToGF && gcdfound)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable alpha= rootOf (mipo.mapinto());
cand= GF2FalphaRep (cand, alpha);
prune (alpha);
}
if (k > 1 && gcdfound)
{
cand= GFMapDown (cand, k);
setCharacteristic (p, k, gf_name);
}
if (extOfExt && gcdfound)
{
cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
prune1 (oldA);
}
}
}
delta--;
goodPointCount= 0;
}
return N (d*cand);
}
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition FLINTconvert.cc:208
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
ilog2
int ilog2(const CanonicalForm &a)
Definition canonicalform.h:352
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
maxNumEval
STATIC_VAR int maxNumEval
Definition cfEzgcd.cc:871
gcd_mon
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
Definition cfEzgcd.cc:470
log2exp
static const double log2exp
Definition cfEzgcd.cc:45
Hensel
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition cfEzgcd.cc:302
M
const CanonicalForm CFMap & M
Definition cfEzgcd.cc:55
sizePerVars1
STATIC_VAR int sizePerVars1
Definition cfEzgcd.cc:872
k
int k
Definition cfEzgcd.cc:99
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)
Definition cfEzgcd.cc:386
gcd_test_one
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...
Definition cfGcdUtil.cc:25
modGCDFq
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....
Definition cfModGcd.cc:479
cand
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition cfModGcd.cc:70
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
maxNumVars
int maxNumVars
Definition cfModGcd.cc:4138
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition cfModGcd.cc:3570
modGCDGF
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 forComputer Algebra" by Geddes...
Definition cfModGcd.cc:873
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition cf_defs.h:37
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition cf_map_ext.cc:451
GFMapDown
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition cf_map_ext.cc:277
primitiveElement
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
Definition cf_map_ext.cc:343
mapDown
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 ,...
Definition cf_map_ext.cc:124
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
GFMapUp
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition cf_map_ext.cc:241
GF2FalphaRep
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition cf_map_ext.cc:196
cf_getBigPrime
int cf_getBigPrime(int i)
Definition cf_primes.cc:39
FLINTrandom
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:23
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
f
FILE * f
Definition checklibs.c:9
AlgExtRandomF
generate random elements in F_p(alpha)
Definition cf_random.h:70
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
FFRandom
generate random elements in F_p
Definition cf_random.h:44
GFRandom
generate random elements in GF
Definition cf_random.h:32
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
B
b *CanonicalForm B
Definition facBivar.cc:52
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
rootOf
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
prune1
void prune1(const Variable &alpha)
Definition variable.cc:291
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
if
if(!FE_OPT_NO_SHELL_FLAG)
Definition fehelp.cc:1000
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
gf_name
VAR char gf_name
Definition gfops.cc:52
gf_mipo
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56
G
STATIC_VAR TreeM * G
Definition janet.cc:31
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
count
int status int void size_t count
Definition si_signals.h:69
buf
int status int void * buf
Definition si_signals.h:69
M
#define M
Definition sirandom.c:25
TIMING_DEFINE
#define TIMING_DEFINE(t)
Definition timing.h:91
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836