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

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

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