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