<!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-10.5.0test/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 : -->
