Loading...
Searching...
No Matches
cfGcdUtil.cc
Go to the documentation of this file.
#include "config.h"
#include "canonicalform.h"
#include "cf_factory.h"
#include "cf_reval.h"
#include "cf_util.h"
#include "cf_iter.h"
#include "gfops.h"
#include "cf_map_ext.h"
#include "templates/ftmpl_functions.h"
#ifdef HAVE_NTL
#include "NTLconvert.h"
#endif
#ifdef HAVE_FLINT
#include "FLINTconvert.h"
#endif
/// Coprimality Check. f and g are assumed to have the same level. If swap is
/// true, the main variables of f and g are swapped with Variable(1). If the
/// result is false, d is set to the degree of the gcd of f and g evaluated at a
/// random point in K^n-1. This gcd is a gcd of univariate polynomials.
bool
gcd_test_one ( const CanonicalForm & f, const CanonicalForm & g, bool swap, int & d )
{
d= 0;
int count = 0;
// assume polys have same level;
Variable v= Variable (1);
bool algExtension= (hasFirstAlgVar (f, v) || hasFirstAlgVar (g, v));
CanonicalForm lcf, lcg;
if ( swap )
{
lcf = swapvar( LC( f ), Variable(1), f.mvar() );
lcg = swapvar( LC( g ), Variable(1), f.mvar() );
}
else
{
lcf = LC( f, Variable(1) );
lcg = LC( g, Variable(1) );
}
CanonicalForm F, G;
if ( swap )
{
F=swapvar( f, Variable(1), f.mvar() );
G=swapvar( g, Variable(1), g.mvar() );
}
else
{
F = f;
G = g;
}
#define TEST_ONE_MAX 50
int p= getCharacteristic();
bool passToGF= false;
int k= 1;
bool extOfExt= false;
Variable v3;
if (p > 0 && p < TEST_ONE_MAX && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
{
if (p == 2)
setCharacteristic (2, 6, '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;
}
else if (p > 0 && CFFactory::gettype() == GaloisFieldDomain && ipower (p , getGFDegree()) < TEST_ONE_MAX)
{
k= getGFDegree();
if (ipower (p, 2*k) > TEST_ONE_MAX)
setCharacteristic (p, 2*k, gf_name);
else
setCharacteristic (p, 3*k, gf_name);
F= GFMapUp (F, k);
G= GFMapUp (G, k);
lcf= GFMapUp (lcf, k);
lcg= GFMapUp (lcg, k);
}
else if (p > 0 && p < TEST_ONE_MAX && algExtension)
{
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
int d= degree (getMipo (v));
CFList source, dest;
Variable v2;
CanonicalForm primElem, imPrimElem;
#if defined(HAVE_NTL) && !defined(HAVE_FLINT)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
#endif
if (p == 2 && d < 6)
{
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (v, 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)
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*3);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing:gcd_test_one");
#endif
v2= rootOf (newMipo);
}
else
{
#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)
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*2);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing:gcd_test_one");
#endif
v2= rootOf (newMipo);
}
imPrimElem= mapPrimElem (primElem, v, v2);
extOfExt= true;
}
else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
{
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (v, 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)
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, d*2);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing:gcd_test_one");
#endif
v2= rootOf (newMipo);
imPrimElem= mapPrimElem (primElem, v, v2);
extOfExt= true;
}
if (extOfExt)
{
v3= v;
F= mapUp (F, v, v2, primElem, imPrimElem, source, dest);
G= mapUp (G, v, v2, primElem, imPrimElem, source, dest);
lcf= mapUp (lcf, v, v2, primElem, imPrimElem, source, dest);
lcg= mapUp (lcg, v, v2, primElem, imPrimElem, source, dest);
v= v2;
}
#endif
}
CFRandom * sample;
if ((!algExtension && p > 0) || p == 0)
sample = CFRandomFactory::generate();
else
sample = AlgExtRandomF (v).clone();
REvaluation e( 2, tmax( f.level(), g.level() ), *sample );
delete sample;
if (passToGF)
{
lcf= lcf.mapinto();
lcg= lcg.mapinto();
}
CanonicalForm eval1, eval2;
if (passToGF)
{
eval1= e (lcf);
eval2= e (lcg);
}
else
{
eval1= e (lcf);
eval2= e (lcg);
}
while ( ( eval1.isZero() || eval2.isZero() ) && count < TEST_ONE_MAX )
{
e.nextpoint();
count++;
eval1= e (lcf);
eval2= e (lcg);
}
if ( count >= TEST_ONE_MAX )
{
if (passToGF)
setCharacteristic (p);
if (k > 1)
setCharacteristic (p, k, gf_name);
if (extOfExt)
prune1 (v3);
return false;
}
if (passToGF)
{
F= F.mapinto();
G= G.mapinto();
eval1= e (F);
eval2= e (G);
}
else
{
eval1= e (F);
eval2= e (G);
}
CanonicalForm c= gcd (eval1, eval2);
d= c.degree();
bool result= d < 1;
if (d < 0)
d= 0;
if (passToGF)
setCharacteristic (p);
if (k > 1)
setCharacteristic (p, k, gf_name);
if (extOfExt)
prune1 (v3);
return result;
}
/**
* same as balance_p ( const CanonicalForm & f, const CanonicalForm & q )
* but qh= q/2 is provided, too.
**/
CanonicalForm
balance_p ( const CanonicalForm & f, const CanonicalForm & q, const CanonicalForm & qh )
{
Variable x = f.mvar();
CanonicalForm result = 0;
CanonicalForm c;
CFIterator i;
for ( i = f; i.hasTerms(); i++ )
{
c = i.coeff();
if ( c.inCoeffDomain())
{
if ( c > qh )
result += power( x, i.exp() ) * (c - q);
else
result += power( x, i.exp() ) * c;
}
else
result += power( x, i.exp() ) * balance_p(c,q,qh);
}
return result;
}
/** static CanonicalForm balance_p ( const CanonicalForm & f, const CanonicalForm & q )
*
* balance_p() - map f from positive to symmetric representation
* mod q.
*
* This makes sense for polynomials over Z only.
* q should be an integer.
*
**/
CanonicalForm
balance_p ( const CanonicalForm & f, const CanonicalForm & q )
{
CanonicalForm qh = q / 2;
return balance_p (f, q, qh);
}
/*static CanonicalForm
balance ( const CanonicalForm & f, const CanonicalForm & q )
{
Variable x = f.mvar();
CanonicalForm result = 0, qh = q / 2;
CanonicalForm c;
CFIterator i;
for ( i = f; i.hasTerms(); i++ ) {
c = mod( i.coeff(), q );
if ( c > qh )
result += power( x, i.exp() ) * (c - q);
else
result += power( x, i.exp() ) * c;
}
return result;
}*/
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
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
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
NTLconvert.h
Conversion to and from NTL.
swap
#define swap(_i, _j)
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
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
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
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
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
TEST_ONE_MAX
#define TEST_ONE_MAX
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
balance_p
CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
same as balance_p ( const CanonicalForm & f, const CanonicalForm & q ) but qh= q/2 is provided,...
Definition cfGcdUtil.cc:258
x
Variable x
Definition cfModGcd.cc:4090
lcg
CanonicalForm lcg
Definition cfModGcd.cc:4105
p
int p
Definition cfModGcd.cc:4086
lcf
CanonicalForm lcf
Definition cfModGcd.cc:4105
g
g
Definition cfModGcd.cc:4098
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
cf_factory.h
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
cf_iter.h
Iterators for CanonicalForm's.
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
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
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
cf_map_ext.h
This file implements functions to map between extensions of finite fields.
FLINTrandom
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:23
cf_reval.h
generate random evaluation points
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
cf_util.h
f
FILE * f
Definition checklibs.c:9
AlgExtRandomF
generate random elements in F_p(alpha)
Definition cf_random.h:70
AlgExtRandomF::clone
CFRandom * clone() const
Definition cf_random.cc:162
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFRandomFactory::generate
static CFRandom * generate()
Definition cf_random.cc:167
CFRandom
virtual class for random element generation
Definition cf_random.h:21
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition canonicalform.cc:210
REvaluation
class to generate random evaluation points
Definition cf_reval.h:26
REvaluation::nextpoint
void nextpoint()
Definition cf_reval.cc:46
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
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
ftmpl_functions.h
some useful template functions.
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
gf_name
VAR char gf_name
Definition gfops.cc:52
gfops.h
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
G
STATIC_VAR TreeM * G
Definition janet.cc:31
count
int status int void size_t count
Definition si_signals.h:69
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836