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

operations mod p^k and some other useful functions for factorization More...

`#include "canonicalform.h"`
`#include "cf_eval.h"`

Go to the source code of this file.

## Data Structures

class | modpk
| class to do operations mod p^k for int's p and k More...

## Functions

CanonicalForm | replaceLc (const CanonicalForm &f, const CanonicalForm &c)
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 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.
void | extgcd (const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
CanonicalForm | remainder (const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
CanonicalForm | prod (const CFArray &a, int f, int l)
CanonicalForm | prod (const CFArray &a)

## Detailed Description

operations mod p^k and some other useful functions for factorization

Definition in file fac_util.h.

## Function Documentation

## extgcd()

void extgcd | ( | const CanonicalForm & | a,
|  | const CanonicalForm & | b,
|  | CanonicalForm & | S,
|  | CanonicalForm & | T,
|  | const modpk & | pk )

Definition at line 183 of file fac_util.cc.

{
int p = pk.getp(), k = pk.getk(), j;
CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
CanonicalForm modulus = p, sigmat, taut, q;
setCharacteristic( p );
{
amodp = mapinto( a ); bmodp = mapinto( b );
(void)extgcd( amodp, bmodp, smodp, tmodp );
}
setCharacteristic( 0 );
s = mapinto( smodp ); t = mapinto( tmodp );
for ( j = 1; j < k; j++ ) {
e = ( 1 - s * a - t * b ) / modulus;
setCharacteristic( p );
{
e = mapinto( e );
sigmat = smodp * e;
taut = tmodp * e;
divrem( sigmat, bmodp, q, sigma );
tau = taut + q * amodp;
}
setCharacteristic( 0 );
s += mapinto( sigma ) * modulus;
t += mapinto( tau ) * modulus;
modulus *= p;
}
S = s; T = t;
}
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
tau
void tau(int **points, int sizePoints, int k)
Definition cfNewtonPolygon.cc:461
CanonicalForm
factory's main class
Definition canonicalform.h:86
modpk::getk
int getk() const
Definition fac_util.h:36
modpk::getp
int getp() const
Definition fac_util.h:35
s
const CanonicalForm int s
Definition facAbsFact.cc:51
j
int j
Definition facHensel.cc:110
extgcd
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition fac_util.cc:183
T
STATIC_VAR jList * T
Definition janet.cc:30

## 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 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.

Definition at line 25 of file cfGcdUtil.cc.

{
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;
}
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
swap
#define swap(_i, _j)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
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
TEST_ONE_MAX
#define TEST_ONE_MAX
lcg
CanonicalForm lcg
Definition cfModGcd.cc:4105
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
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
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
AlgExtRandomF::clone
CFRandom * clone() const
Definition cf_random.cc:162
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFRandomFactory::generate
static CFRandom * generate()
Definition cf_random.cc:167
CFRandom
virtual class for random element generation
Definition cf_random.h:21
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::mapinto
CanonicalForm mapinto() const
Definition canonicalform.cc:210
REvaluation
class to generate random evaluation points
Definition cf_reval.h:26
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
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
gf_name
VAR char gf_name
Definition gfops.cc:52
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

## prod() [1/2]

CanonicalForm prod | ( | const CFArray & | a | ) |

Definition at line 177 of file fac_util.cc.

{
return prod( a, a.min(), a.max() );
}
Array::max
int max() const
Definition ftmpl_array.cc:104
Array::min
int min() const
Definition ftmpl_array.cc:98
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100

## prod() [2/2]

CanonicalForm prod | ( | const CFArray & | a,
|  | int | f,
|  | int | l )

Definition at line 166 of file fac_util.cc.

{
if ( f < a.min() ) f = a.min();
if ( l > a.max() ) l = a.max();
CanonicalForm p = 1;
for ( int i = f; i <= l; i++ )
p *= a[i];
return p;
}
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132

## remainder()

CanonicalForm remainder | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const modpk & | pk )

Definition at line 115 of file fac_util.cc.

{
ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
if ( f.inCoeffDomain() )
if ( g.inCoeffDomain() )
return pk( f % g );
else
return pk( f );
else {
Variable x = f.mvar();
CanonicalForm result = f;
int degg = g.degree();
CanonicalForm invlcg = pk.inverse( g.lc() );
CanonicalForm gg = pk( g*invlcg );
if((gg.lc().isOne()))
{
while ( result.degree() >= degg )
{
result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
result=pk(result);
}
}
else
// no inverse found
{
CanonicalForm ic=icontent(g);
if (!ic.isOne())
{
gg=g/ic;
return remainder(f,gg,pk);
}
while ( result.degree() >= degg )
{
if (gg.lc().isZero()) return result;
CanonicalForm lcgf = result.lc() / gg.lc();
if (lcgf.inZ())
gg = pk( g*lcgf );
else
{
//printf("!\n\n");
return result;
}
result -= gg * power( x, result.degree() - degg );
result=pk(result);
}
}
return result;
}
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
x
Variable x
Definition cfModGcd.cc:4090
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inZ
bool inZ() const
predicates
Definition canonicalform.cc:69
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition canonicalform.cc:337
modpk::inverse
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition fac_util.cc:59
degg
int degg
Definition facAlgExt.cc:64
remainder
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition fac_util.cc:115

## replaceLc()

CanonicalForm replaceLc | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | c )

Definition at line 90 of file fac_util.cc.

{
if ( f.inCoeffDomain() )
return c;
else
return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
}