/*****************************************************************************\MODULE: ZZXFactoringSUMMARY:Routines are provided for factoring in ZZX.\*****************************************************************************/#include <NTL/ZZX.h>#include <NTL/pair_ZZX_long.h>void SquareFreeDecomp(vec_pair_ZZX_long& u, const ZZX& f);const vector(pair_ZZX_long SquareFreeDecomp(const ZZX& f);// input is primitive, with positive leading coefficient.  Performs// square-free decomposition.  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 MultiLift(vec_ZZX& A, const vec_zz_pX& a, const ZZX& f, long e,               long verbose=0);// Using current value p of zz_p::modulus(), this lifts the// square-free factorization a mod p of f to a factorization A mod p^e// of f.  It is required that f and all the polynomials in a are// monic.void SFFactor(vec_ZZX& factors, const ZZX& f, long verbose=0, long bnd=0);vec_ZZX SFFactor(const ZZX& f, long verbose=0, long bnd=0);// input f is primitive and square-free, with positive leading// coefficient.  bnd, if not zero, indicates that f divides a// polynomial h whose Euclidean norm is bounded by 2^{bnd} in absolute// value.  This uses the routine SFCanZass in zz_pXFactoring and then// performs a MultiLift, followed by a brute-force search for the// factors.  // A number of heuristics are used to speed up the factor-search step.// See "implementation details" below.void factor(ZZ& c,            vec_pair_ZZX_long& factors,            const ZZX& f,            long verbose=0,            long bnd=0);// input f is is an arbitrary polynomial.  c is the content of f, and// factors is the facrorization of its primitive part.  bnd is as in// SFFactor.  The routine calls SquareFreeDecomp and SFFactor.void mul(ZZX& x, const vec_pair_ZZX_long& a);ZZX mul(const vec_pair_ZZX_long& a);// multiplies polynomials, with multiplcities./*****************************************************************************\IMPLEMENTATION DETAILSTo factor a polynomial, first its content is extracted, and it ismade squarefree.  Next, a simple hack is performed: if the polynomial is of theform g(x^l), then an attempt is made to factor g(k^m),for divisors m of l, which can in some cases greatly simplifythe factorization task.Next, the polynomial is factored modulo severalsmall primes, and one small prime p is selected as the "best".The factorization mod p is "lifted" to a factorization mod p^kfor a sufficiently large k.  This is done via quadratic Hensellifting.  Despite "folk wisdom" to the contrary, this is muchmore efficient than linear Hensel lifting, especially since NTLhas very fast polynomial arithmetic.After the "lifting phase" comes the "factor recombination phase".The factorization mod p^k may be "finer" than the true factorizationover the integers, hence we have to "combine" subsets of factorsmod p^k and test if these are factors over the integers.Subsets are considered in order of increasing cardinality.This phase can take exponential time in some cases, and soevery effort has been made to make it as fast as possible.Several heuristics are used to avoid expensive operations,and one heuristic is employed that allows huge portions ofthe search space to be "pruned" altogether.Many of these heuristics were developed together withJohn Abbott and Paul Zimmermann.They are described in the paper "Factoring in Z[x]: the searching phase",in Proc. ISSAC 2000.The factorization pattern modulo small primes can be combinedto rule out degrees of candidate factors.To make this as useful as possible, if the search is takinga long time, a the polynomial is occasionally factored moduloa new small prime.In some cases, entire cardinalities can be skipped basedon this local degree information.We also use the fact that the sizes of the coefficients ofa true factor must be small.If n is the degree of a candidate polynomial, we testthe size of X^(n-1) and X^(n-2).These tests can be carried out using single precision integerarithmetic, and so are extremely fast.Moreover, in some cases we can "prune" huge portions of thesearch space based on the X^(n-1) test.If these tests pass, then we employ both an f(1) test and an f(0)test.  By an "f(r) test", we mean that if g is a candidate factor,then g(r) must divide f(r).For both of these tests, as well as the X^(n-2) test above,we use a "lazy stack evaluation" strategy, which greatlyreduces the workload.The behaviour of these heuristics can be fine tuned bysetting the following global variables:extern long ZZXFac_InitNumPrimes;  // initial value 7// f is factored modulo this many primes// before choosing one that is "best" to work with, where// currently, "best" means that f mod p has the minimal number// of irreducible factors.extern long ZZXFac_MaxNumPrimes;  // initial value 50// During the factor recombination phase, if not much progress// is being made, occasionally more "local" information is // collected by factoring f modulo another prime.// This "local" information is used to rule out degrees // of potential factors during recombination.// This value bounds the total number of primes modulo which f // is factored.extern long ZZXFac_MaxPrune;  // initial value = 10// A kind of "meet in the middle" strategy is used// to prune the search space during recombination,// based on the X^(n-1) test.// For many (but not all) polynomials, this can greatly// reduce the running time.// When it does work, there is a time-space tradeoff:// If t = ZZXFac_MaxPrune, the running time will be reduced by a factor near// 2^t, but the table will take (at most) t*2^(t-1) bytes of storage.// Note that ZZXFac_MaxPrune is treated as an upper bound on t---the// factoring algorithm may decide to use a smaller value of t for// a number of reasons.extern long ZZXFac_PowerHack;  // initial value = 1// If this is nonzero, then the g(x^l) hack is performed;// otherwise, if it is zero, this hack is not performed.// NOTE: if you have a very hard-to-factor polynomial, run the// factoring algorithm with verbose=1 to see what is going on,// and then you can adjust these variables accordingly.\*****************************************************************************/