Loading...
Searching...
No Matches
fac_util.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
#include "config.h"
#include "cf_assert.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "fac_util.h"
#include "cfUnivarGcd.h"
STATIC_INST_VAR CanonicalForm PK, PKHALF;
static CanonicalForm mappk ( const CanonicalForm& );
static CanonicalForm mappksymmetric ( const CanonicalForm& );
modpk::modpk()
{
p = 0;
k = 0;
pk = 1;
pkhalf = 0;
}
modpk::modpk( int q, int l )
{
p = q;
k = l;
pk = power( CanonicalForm( p ), k );
pkhalf = pk / 2;
}
modpk::modpk( const modpk & m )
{
p = m.p;
k = m.k;
pk = m.pk;
pkhalf = m.pkhalf;
}
modpk&
modpk::operator= ( const modpk & m )
{
if ( this != &m ) {
p = m.p;
k = m.k;
pk = m.pk;
pkhalf = m.pkhalf;
}
return *this;
}
CanonicalForm
modpk::inverse( const CanonicalForm & f, bool symmetric ) const
{
CanonicalForm u, r0 = this->operator()( f, false ), r1 = pk, q0 = 1, q1 = 0;
while ( ( r0 > 0 ) && ( r1 > 0 ) ) {
u = r0 / r1;
r0 = r0 % r1;
q0 = u*q1 + q0;
if ( r0 > 0 ) {
u = r1 / r0;
r1 = r1 % r0;
q1 = u*q0 + q1;
}
}
if ( r0 == 0 )
return this->operator()( pk-q1, symmetric );
else
return this->operator()( q0, symmetric );
}
CanonicalForm
modpk::operator() ( const CanonicalForm & f, bool symmetric ) const
{
PKHALF = pkhalf;
PK = pk;
if ( symmetric )
return mapdomain( f, mappksymmetric );
else
return mapdomain( f, mappk );
}
CanonicalForm
replaceLc( const CanonicalForm & f, const CanonicalForm & c )
{
if ( f.inCoeffDomain() )
return c;
else
return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
}
CanonicalForm
mappksymmetric ( const CanonicalForm & f )
{
CanonicalForm result = mod( f, PK );
if ( result > PKHALF )
return result - PK;
else
return result;
}
CanonicalForm
mappk ( const CanonicalForm & f )
{
return mod( f, PK );
}
CanonicalForm
remainder( const CanonicalForm & f, const CanonicalForm & g, const modpk & pk )
{
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;
}
}
CanonicalForm
prod ( const CFArray & a, int f, int l )
{
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;
}
CanonicalForm
prod ( const CFArray & a )
{
return prod( a, a.min(), a.max() );
}
void
extgcd ( const CanonicalForm & a, const CanonicalForm & b, CanonicalForm & S, CanonicalForm & T, const modpk & pk )
{
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
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
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
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
b
CanonicalForm b
Definition cfModGcd.cc:4111
tau
void tau(int **points, int sizePoints, int k)
Definition cfNewtonPolygon.cc:461
cfUnivarGcd.h
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
cf_defs.h
factory switches.
cf_iter.h
Iterators for CanonicalForm's.
f
FILE * f
Definition checklibs.c:9
Array::max
int max() const
Definition ftmpl_array.cc:104
Array::min
int min() const
Definition ftmpl_array.cc:98
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
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
Variable
factory's class for variables
Definition factory.h:127
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk::operator()
CanonicalForm operator()(const CanonicalForm &f, bool symmetric=true) const
Definition fac_util.cc:79
modpk::operator=
modpk & operator=(const modpk &m)
Definition fac_util.cc:47
modpk::inverse
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition fac_util.cc:59
modpk::getk
int getk() const
Definition fac_util.h:36
modpk::modpk
modpk()
Definition fac_util.cc:22
modpk::getp
int getp() const
Definition fac_util.h:35
modpk::p
int p
Definition fac_util.h:27
modpk::pkhalf
CanonicalForm pkhalf
Definition fac_util.h:26
modpk::pk
CanonicalForm pk
Definition fac_util.h:25
modpk::k
int k
Definition fac_util.h:28
result
return result
Definition facAbsBiFact.cc:76
s
const CanonicalForm int s
Definition facAbsFact.cc:51
degg
int degg
Definition facAlgExt.cc:64
j
int j
Definition facHensel.cc:110
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
mappksymmetric
static CanonicalForm mappksymmetric(const CanonicalForm &)
Definition fac_util.cc:99
extgcd
void extgcd(const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)
Definition fac_util.cc:183
PKHALF
STATIC_INST_VAR CanonicalForm PKHALF
Definition fac_util.cc:15
remainder
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition fac_util.cc:115
PK
STATIC_INST_VAR CanonicalForm PK
Definition fac_util.cc:15
mappk
static CanonicalForm mappk(const CanonicalForm &)
Definition fac_util.cc:109
replaceLc
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition fac_util.cc:90
fac_util.h
operations mod p^k and some other useful functions for factorization
STATIC_INST_VAR
#define STATIC_INST_VAR
Definition globaldefs.h:10
mapdomain
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ).
Definition cf_ops.cc:440
power
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
T
STATIC_VAR jList * T
Definition janet.cc:30