1 | |
---|
2 | /*****************************************************************************\ |
---|
3 | |
---|
4 | MODULE: ZZXFactoring |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | Routines are provided for factoring in ZZX. |
---|
9 | |
---|
10 | See IMPLEMENTATION DETAILS below for a discussion of the algorithms used, |
---|
11 | and of the flags available for selecting among these algorithms. |
---|
12 | |
---|
13 | \*****************************************************************************/ |
---|
14 | |
---|
15 | #include <NTL/ZZX.h> |
---|
16 | #include <NTL/pair_ZZX_long.h> |
---|
17 | |
---|
18 | void SquareFreeDecomp(vec_pair_ZZX_long& u, const ZZX& f); |
---|
19 | const vector(pair_ZZX_long SquareFreeDecomp(const ZZX& f); |
---|
20 | |
---|
21 | // input is primitive, with positive leading coefficient. Performs |
---|
22 | // square-free decomposition. If f = prod_i g_i^i, then u is set to a |
---|
23 | // lest of pairs (g_i, i). The list is is increasing order of i, with |
---|
24 | // trivial terms (i.e., g_i = 1) deleted. |
---|
25 | |
---|
26 | |
---|
27 | void MultiLift(vec_ZZX& A, const vec_zz_pX& a, const ZZX& f, long e, |
---|
28 | long verbose=0); |
---|
29 | |
---|
30 | // Using current value p of zz_p::modulus(), this lifts the |
---|
31 | // square-free factorization a mod p of f to a factorization A mod p^e |
---|
32 | // of f. It is required that f and all the polynomials in a are |
---|
33 | // monic. |
---|
34 | |
---|
35 | |
---|
36 | |
---|
37 | void SFFactor(vec_ZZX& factors, const ZZX& f, long verbose=0, long bnd=0); |
---|
38 | vec_ZZX SFFactor(const ZZX& f, long verbose=0, long bnd=0); |
---|
39 | |
---|
40 | // input f is primitive and square-free, with positive leading |
---|
41 | // coefficient. bnd, if not zero, indicates that f divides a |
---|
42 | // polynomial h whose Euclidean norm is bounded by 2^{bnd} in absolute |
---|
43 | // value. This uses the routine SFCanZass in zz_pXFactoring and then |
---|
44 | // performs a MultiLift, followed by a brute-force search for the |
---|
45 | // factors. |
---|
46 | |
---|
47 | // A number of heuristics are used to speed up the factor-search step. |
---|
48 | // See "implementation details" below. |
---|
49 | |
---|
50 | |
---|
51 | void factor(ZZ& c, |
---|
52 | vec_pair_ZZX_long& factors, |
---|
53 | const ZZX& f, |
---|
54 | long verbose=0, |
---|
55 | long bnd=0); |
---|
56 | |
---|
57 | // input f is is an arbitrary polynomial. c is the content of f, and |
---|
58 | // factors is the facrorization of its primitive part. bnd is as in |
---|
59 | // SFFactor. The routine calls SquareFreeDecomp and SFFactor. |
---|
60 | |
---|
61 | void mul(ZZX& x, const vec_pair_ZZX_long& a); |
---|
62 | ZZX mul(const vec_pair_ZZX_long& a); |
---|
63 | // multiplies polynomials, with multiplcities. |
---|
64 | |
---|
65 | |
---|
66 | |
---|
67 | |
---|
68 | /*****************************************************************************\ |
---|
69 | |
---|
70 | IMPLEMENTATION DETAILS |
---|
71 | |
---|
72 | To factor a polynomial, first its content is extracted, and it is |
---|
73 | made squarefree. This is typically very fast. |
---|
74 | |
---|
75 | Second, a simple hack is performed: if the polynomial is of the |
---|
76 | form g(x^l), then an attempt is made to factor g(k^m), |
---|
77 | for divisors m of l, which can in some cases greatly simplify |
---|
78 | the factorization task. |
---|
79 | You can turn this "power hack" on/off by setting the following variable |
---|
80 | to 1/0: |
---|
81 | |
---|
82 | extern long ZZXFac_PowerHack; // initial value = 1 |
---|
83 | |
---|
84 | |
---|
85 | Third, the polynomial is factored modulo several |
---|
86 | small primes, and one small prime p is selected as the "best". |
---|
87 | You can choose the number of small primes that you want to use |
---|
88 | by setting the following variable: |
---|
89 | |
---|
90 | extern long ZZXFac_InitNumPrimes; // initial value = 7 |
---|
91 | |
---|
92 | Fourth, The factorization mod p is "lifted" to a factorization mod p^k |
---|
93 | for a sufficiently large k. This is done via quadratic Hensel |
---|
94 | lifting. Despite "folk wisdom" to the contrary, this is much |
---|
95 | more efficient than linear Hensel lifting, especially since NTL |
---|
96 | has very fast polynomial arithmetic. |
---|
97 | |
---|
98 | After the "lifting phase" comes the "factor recombination phase". |
---|
99 | The factorization mod p^k may be "finer" than the true factorization |
---|
100 | over the integers, hence we have to "combine" subsets of modular factors |
---|
101 | and test if these are factors over the integers. |
---|
102 | |
---|
103 | There are two basic strategies: the "Zassenhaus" method |
---|
104 | and the "van Hoeij" method. |
---|
105 | |
---|
106 | The van Hoeij method: |
---|
107 | |
---|
108 | The van Hoeij method is fairly new, but it is so much better than |
---|
109 | the older, Zassenhaus method, that it is now the default. |
---|
110 | For a description of the method, go to Mark van Hoeij's home page: |
---|
111 | |
---|
112 | http://www.openmath.org/~hoeij/ |
---|
113 | |
---|
114 | The van Hoeij method is not really a specific algorithm, but a general |
---|
115 | algorithmic approach: many parameters and strategies have to be selected |
---|
116 | to obtain a specific algorithm, and it is a challenge to |
---|
117 | make all of these choices so that the resulting algorithm works |
---|
118 | fairly well on all input polynomials. |
---|
119 | |
---|
120 | Set the following variable to 1 to enable the van Hoeij method, |
---|
121 | and to 0 to revert to the Zassenhaus method: |
---|
122 | |
---|
123 | extern long ZZXFac_van_Hoeij; // initial value = 1 |
---|
124 | |
---|
125 | Note that the "power hack" is still on by default when using van Hoeij's |
---|
126 | method, but we have arranged things so that the "power hack" strategy |
---|
127 | is abandoned if it appears to be too much a waste of time. |
---|
128 | Unlike with the Zassenhaus method, using the "power hack" method with |
---|
129 | van Hoeij can sometimes be a huge waste of time if one is not careful. |
---|
130 | |
---|
131 | |
---|
132 | |
---|
133 | The Zassenhaus method: |
---|
134 | |
---|
135 | The Zassenhaus method is essentially a brute-force search, but with |
---|
136 | a lot of fancy "pruning" techniques, as described in the paper |
---|
137 | [J. Abbott, V. Shoup, P. Zimmermann, "Factoring in Z[x]: the searching phase", |
---|
138 | ISSAC 2000]. |
---|
139 | |
---|
140 | These heuristics are fairly effective, and allow one to easily deal |
---|
141 | with up to around 30-40 modular factors, which is *much* more |
---|
142 | than other Zassenhaus-based factorizers can deal with; however, after this, |
---|
143 | the exponential behavior of the algorithm really starts to dominate. |
---|
144 | |
---|
145 | The behaviour of these heuristics can be fine tuned by |
---|
146 | setting the following global variables: |
---|
147 | |
---|
148 | extern long ZZXFac_MaxNumPrimes; // initial value = 50 |
---|
149 | // During the factor recombination phase, if not much progress |
---|
150 | // is being made, occasionally more "local" information is |
---|
151 | // collected by factoring f modulo another prime. |
---|
152 | // This "local" information is used to rule out degrees |
---|
153 | // of potential factors during recombination. |
---|
154 | // This value bounds the total number of primes modulo which f |
---|
155 | // is factored. |
---|
156 | |
---|
157 | extern long ZZXFac_MaxPrune; // initial value = 10 |
---|
158 | // A kind of "meet in the middle" strategy is used |
---|
159 | // to prune the search space during recombination. |
---|
160 | // For many (but not all) polynomials, this can greatly |
---|
161 | // reduce the running time. |
---|
162 | // When it does work, there is a time-space tradeoff: |
---|
163 | // If t = ZZXFac_MaxPrune, the running time will be reduced by a factor near |
---|
164 | // 2^t, but the table will take (at most) t*2^(t-1) bytes of storage. |
---|
165 | // Note that ZZXFac_MaxPrune is treated as an upper bound on t---the |
---|
166 | // factoring algorithm may decide to use a smaller value of t for |
---|
167 | // a number of reasons. |
---|
168 | |
---|
169 | |
---|
170 | |
---|
171 | \*****************************************************************************/ |
---|