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

MODULE: ZZ_pXFactoring

SUMMARY:

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

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

#include <NTL/ZZ_pX.h>
#include <NTL/pair_ZZ_pX_long.h>

void SquareFreeDecomp(vec_pair_ZZ_pX_long& u, const ZZ_pX& f);
vec_pair_ZZ_pX_long SquareFreeDecomp(const ZZ_pX& f);

// Performs square-free decomposition.  f must be monic.  If f =
// prod_i g_i^i, then u is set to a lest 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_p& x, const ZZ_pX& f);
vec_ZZ_p FindRoots(const ZZ_pX& f);

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

void FindRoot(ZZ_p& root, const ZZ_pX& f);
ZZ_p FindRoot(const ZZ_pX& f);

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


void SFBerlekamp(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX  SFBerlekamp(const ZZ_pX& f, long verbose=0);

// Assumes f is square-free and monic.  returns list of factors of f.
// Uses "Berlekamp" approach, as described in detail in [Shoup,
// J. Symbolic Comp. 20:363-397, 1995].


void berlekamp(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f,
               long verbose=0);

vec_pair_ZZ_pX_long berlekamp(const ZZ_pX& f, long verbose=0);

// returns a list of factors, with multiplicities.  f must be monic.
// Calls SFBerlekamp.



void NewDDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h,
         long verbose=0);

vec_pair_ZZ_pX_long NewDDF(const ZZ_pX& f, const ZZ_pX& 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^p 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 tmp-*.
// The definition of "large" is controlled by the variable

      extern thread_local double ZZ_pXFileThresh

// which can be set by the user.  If the sizes of the tables
// exceeds ZZ_pXFileThresh KB, external files are used.
// Initial value is NTL_FILE_THRESH (defined in tools.h).




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

vec_ZZ_pX EDF(const ZZ_pX& f, const ZZ_pX& h,
         long d, long verbose=0);

// Performs equal-degree factorization.  f is monic, square-free, and
// all irreducible factors have same degree.  h = X^p 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_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX RootEDF(const ZZ_pX& f, long verbose=0);

// EDF for d==1

void SFCanZass(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);