zzxfactoring.txt

密码大家Shoup写的数论算法c语言实现,windows版本

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

MODULE: ZZXFactoring

SUMMARY:

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 DETAILS

To factor a polynomial, first its content is extracted, and it is
made squarefree.  

Next, a simple hack is performed: if the polynomial is of the
form g(x^l), then an attempt is made to factor g(k^m),
for divisors m of l, which can in some cases greatly simplify
the factorization task.

Next, the polynomial is factored modulo several
small primes, and one small prime p is selected as the "best".

The factorization mod p is "lifted" to a factorization mod p^k
for a sufficiently large k.  This is done via quadratic Hensel
lifting.  Despite "folk wisdom" to the contrary, this is much
more efficient than linear Hensel lifting, especially since NTL
has very fast polynomial arithmetic.

After the "lifting phase" comes the "factor recombination phase".
The factorization mod p^k may be "finer" than the true factorization
over the integers, hence we have to "combine" subsets of factors
mod 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 so
every 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 of
the search space to be "pruned" altogether.
Many of these heuristics were developed together with
John 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 combined
to rule out degrees of candidate factors.
To make this as useful as possible, if the search is taking
a long time, a the polynomial is occasionally factored modulo
a new small prime.
In some cases, entire cardinalities can be skipped based
on this local degree information.

We also use the fact that the sizes of the coefficients of
a true factor must be small.
If n is the degree of a candidate polynomial, we test
the size of X^(n-1) and X^(n-2).
These tests can be carried out using single precision integer
arithmetic, and so are extremely fast.
Moreover, in some cases we can "prune" huge portions of the
search 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 greatly
reduces the workload.

The behaviour of these heuristics can be fine tuned by
setting 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.


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