lzz_pexfactoring.txt

数值算法库for Unix

/**************************************************************************\

MODULE: zz_pEXFactoring

SUMMARY:

Routines are provided for factorization of polynomials over zz_pE, as
well as routines for related problems such as testing irreducibility
and constructing irreducible polynomials of given degree.

\**************************************************************************/

#include <NTL/lzz_pEX.h>
#include <NTL/pair_lzz_pEX_long.h>

void SquareFreeDecomp(vec_pair_zz_pEX_long& u, const zz_pEX& f);
vec_pair_zz_pEX_long SquareFreeDecomp(const zz_pEX& f);

// Performs square-free decomposition.  f must be monic.  If f =
// prod_i g_i^i, then u is set to a list of pairs (g_i, i).  The list
// is is increasing order of i, with trivial terms (i.e., g_i = 1)
// deleted.


void FindRoots(vec_zz_pE& x, const zz_pEX& f);
vec_zz_pE FindRoots(const zz_pEX& f);

// f is monic, and has deg(f) distinct roots.  returns the list of
// roots

void FindRoot(zz_pE& root, const zz_pEX& f);
zz_pE FindRoot(const zz_pEX& f);

// finds a single root of f.  assumes that f is monic and splits into
// distinct linear factors


void NewDDF(vec_pair_zz_pEX_long& factors, const zz_pEX& f, 
            const zz_pEX& h, long verbose=0);

vec_pair_zz_pEX_long NewDDF(const zz_pEX& f, const zz_pEX& h,
         long verbose=0);


// This computes a distinct-degree factorization.  The input must be
// monic and square-free.  factors is set to a list of pairs (g, d),
// where g is the product of all irreducible factors of f of degree d.
// Only nontrivial pairs (i.e., g != 1) are included.  The polynomial
// h is assumed to be equal to X^{zz_pE::cardinality()} mod f.

// This routine implements the baby step/giant step algorithm
// of [Kaltofen and Shoup, STOC 1995].
// further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995].

// NOTE: When factoring "large" polynomials,
// this routine uses external files to store some intermediate
// results, which are removed if the routine terminates normally.
// These files are stored in the current directory under names of the
// form ddf-*-baby-* and ddf-*-giant-*.
// The definition of "large" is controlled by the variable

      extern double zz_pEXFileThresh

// which can be set by the user.  If the sizes of the tables
// exceeds zz_pEXFileThresh KB, external files are used.
// Initial value is 256.



void EDF(vec_zz_pEX& factors, const zz_pEX& f, const zz_pEX& h,
         long d, long verbose=0);

vec_zz_pEX EDF(const zz_pEX& f, const zz_pEX& h,
         long d, long verbose=0);

// Performs equal-degree factorization.  f is monic, square-free, and
// all irreducible factors have same degree.  h = X^{zz_pE::cardinality()} mod
// f.  d = degree of irreducible factors of f.  This routine
// implements the algorithm of [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]

void RootEDF(vec_zz_pEX& factors, const zz_pEX& f, long verbose=0);
vec_zz_pEX RootEDF(const zz_pEX& f, long verbose=0);

// EDF for d==1


void SFCanZass(vec_zz_pEX& factors, const zz_pEX& f, long verbose=0);
vec_zz_pEX SFCanZass(const zz_pEX& f, long verbose=0);

// Assumes f is monic and square-free.  returns list of factors of f.
// Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and
// EDF above.


void CanZass(vec_pair_zz_pEX_long& factors, const zz_pEX& f, 
             long verbose=0);

vec_pair_zz_pEX_long CanZass(const zz_pEX& f, long verbose=0);


// returns a list of factors, with multiplicities.  f must be monic.
// Calls SquareFreeDecomp and SFCanZass.

// NOTE: these routines use modular composition.  The space
// used for the required tables can be controlled by the variable
// zz_pEXArgBound (see zz_pEX.txt).



void mul(zz_pEX& f, const vec_pair_zz_pEX_long& v);
zz_pEX mul(const vec_pair_zz_pEX_long& v);

// multiplies polynomials, with multiplicities


/**************************************************************************\

                            Irreducible Polynomials

\**************************************************************************/

long ProbIrredTest(const zz_pEX& f, long iter=1);

// performs a fast, probabilistic irreduciblity test.  The test can
// err only if f is reducible, and the error probability is bounded by
// zz_pE::cardinality()^{-iter}.  This implements an algorithm from [Shoup,
// J. Symbolic Comp. 17:371-391, 1994].

long DetIrredTest(const zz_pEX& f);

// performs a recursive deterministic irreducibility test.  Fast in
// the worst-case (when input is irreducible).  This implements an
// algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994].

long IterIrredTest(const zz_pEX& f);

// performs an iterative deterministic irreducibility test, based on
// DDF.  Fast on average (when f has a small factor).

void BuildIrred(zz_pEX& f, long n);
zz_pEX BuildIrred_zz_pEX(long n);

// Build a monic irreducible poly of degree n. 

void BuildRandomIrred(zz_pEX& f, const zz_pEX& g);
zz_pEX BuildRandomIrred(const zz_pEX& g);

// g is a monic irreducible polynomial.  Constructs a random monic
// irreducible polynomial f of the same degree.


long IterComputeDegree(const zz_pEX& h, const zz_pEXModulus& F);

// f is assumed to be an "equal degree" polynomial, and h =
// X^{zz_pE::cardinality()} mod f.  The common degree of the irreducible 
// factors of f is computed.  Uses a "baby step/giant step" algorithm, similar
// to NewDDF.  Although asymptotocally slower than RecComputeDegree
// (below), it is faster for reasonably sized inputs.

long RecComputeDegree(const zz_pEX& h, const zz_pEXModulus& F);

// f is assumed to be an "equal degree" polynomial, 
// h = X^{zz_pE::cardinality()} mod f.  
// The common degree of the irreducible factors of f is
// computed Uses a recursive algorithm similar to DetIrredTest.

void TraceMap(zz_pEX& w, const zz_pEX& a, long d, const zz_pEXModulus& F,
              const zz_pEX& h);

zz_pEX TraceMap(const zz_pEX& a, long d, const zz_pEXModulus& F,
              const zz_pEX& h);

// Computes w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0,
// and h = X^q mod f, q a power of zz_pE::cardinality().  This routine
// implements an algorithm from [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]

void PowerCompose(zz_pEX& w, const zz_pEX& h, long d, const zz_pEXModulus& F);

zz_pEX PowerCompose(const zz_pEX& h, long d, const zz_pEXModulus& F);

// Computes w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q
// mod f, q a power of zz_pE::cardinality().  This routine implements an
// algorithm from [von zur Gathen and Shoup, Computational Complexity
// 2:187-224, 1992]