fac_util.cc File Reference

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

Go to the source code of this file.

Functions
static CanonicalForm	mappk (const CanonicalForm &)
static CanonicalForm	mappksymmetric (const CanonicalForm &)
CanonicalForm	replaceLc (const CanonicalForm &f, const CanonicalForm &c)
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)
void	extgcd (const CanonicalForm &a, const CanonicalForm &b, CanonicalForm &S, CanonicalForm &T, const modpk &pk)

Variables
STATIC_INST_VAR CanonicalForm	PK
STATIC_INST_VAR CanonicalForm	PKHALF

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;
}

mappk()

CanonicalForm mappk ( const CanonicalForm &  f )

static

Definition at line 109 of file fac_util.cc.

{
    return mod( f, PK );
}

mappksymmetric()

CanonicalForm mappksymmetric ( const CanonicalForm &  f )

static

Definition at line 99 of file fac_util.cc.

{
    CanonicalForm result = mod( f, PK );
    if ( result > PKHALF )
        return result - PK;
    else
        return result;
}

prod() [1/2]

CanonicalForm prod

(

const CFArray &

a

)

Definition at line 177 of file fac_util.cc.

{
    return prod( a, a.min(), a.max() );
}   

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;
}

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;
    }
}

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 ) );
}

Variable Documentation

PK

STATIC_INST_VAR CanonicalForm PK

Definition at line 15 of file fac_util.cc.

PKHALF

STATIC_INST_VAR CanonicalForm PKHALF

Definition at line 15 of file fac_util.cc.