<!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/ZZ_pXFactoring.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: ZZ_pXFactoring</span>
<span class="Comment">SUMMARY:</span>
<span class="Comment">Routines are provided for factorization of polynomials over ZZ_p, as</span>
<span class="Comment">well as routines for related problems such as testing irreducibility</span>
<span class="Comment">and constructing irreducible polynomials of given degree.</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="PreProc">#include </span><span class="String"><NTL/ZZ_pX.h></span>
<span class="PreProc">#include </span><span class="String"><NTL/pair_ZZ_pX_long.h></span>
<span class="Type">void</span> SquareFreeDecomp(vec_pair_ZZ_pX_long& u, <span class="Type">const</span> ZZ_pX& f);
vec_pair_ZZ_pX_long SquareFreeDecomp(<span class="Type">const</span> ZZ_pX& f);
<span class="Comment">// Performs square-free decomposition. f must be monic. If f =</span>
<span class="Comment">// prod_i g_i^i, then u is set to a lest of pairs (g_i, i). The list</span>
<span class="Comment">// is is increasing order of i, with trivial terms (i.e., g_i = 1)</span>
<span class="Comment">// deleted.</span>
<span class="Type">void</span> FindRoots(vec_ZZ_p& x, <span class="Type">const</span> ZZ_pX& f);
vec_ZZ_p FindRoots(<span class="Type">const</span> ZZ_pX& f);
<span class="Comment">// f is monic, and has deg(f) distinct roots. returns the list of</span>
<span class="Comment">// roots</span>
<span class="Type">void</span> FindRoot(ZZ_p& root, <span class="Type">const</span> ZZ_pX& f);
ZZ_p FindRoot(<span class="Type">const</span> ZZ_pX& f);
<span class="Comment">// finds a single root of f. assumes that f is monic and splits into</span>
<span class="Comment">// distinct linear factors</span>
<span class="Type">void</span> SFBerlekamp(vec_ZZ_pX& factors, <span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX SFBerlekamp(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// Assumes f is square-free and monic. returns list of factors of f.</span>
<span class="Comment">// Uses "Berlekamp" approach, as described in detail in [Shoup,</span>
<span class="Comment">// J. Symbolic Comp. 20:363-397, 1995].</span>
<span class="Type">void</span> berlekamp(vec_pair_ZZ_pX_long& factors, <span class="Type">const</span> ZZ_pX& f,
<span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_pair_ZZ_pX_long berlekamp(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// returns a list of factors, with multiplicities. f must be monic.</span>
<span class="Comment">// Calls SFBerlekamp.</span>
<span class="Type">void</span> NewDDF(vec_pair_ZZ_pX_long& factors, <span class="Type">const</span> ZZ_pX& f, <span class="Type">const</span> ZZ_pX& h,
<span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_pair_ZZ_pX_long NewDDF(<span class="Type">const</span> ZZ_pX& f, <span class="Type">const</span> ZZ_pX& h,
<span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// This computes a distinct-degree factorization. The input must be</span>
<span class="Comment">// monic and square-free. factors is set to a list of pairs (g, d),</span>
<span class="Comment">// where g is the product of all irreducible factors of f of degree d.</span>
<span class="Comment">// Only nontrivial pairs (i.e., g != 1) are included. The polynomial</span>
<span class="Comment">// h is assumed to be equal to X^p mod f. </span>
<span class="Comment">// This routine implements the baby step/giant step algorithm </span>
<span class="Comment">// of [Kaltofen and Shoup, STOC 1995].</span>
<span class="Comment">// further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995].</span>
<span class="Comment">// NOTE: When factoring "large" polynomials,</span>
<span class="Comment">// this routine uses external files to store some intermediate</span>
<span class="Comment">// results, which are removed if the routine terminates normally.</span>
<span class="Comment">// These files are stored in the current directory under names of the</span>
<span class="Comment">// form tmp-*.</span>
<span class="Comment">// The definition of "large" is controlled by the variable</span>
<span class="Type">extern</span> <span class="Type">thread_local</span> <span class="Type">double</span> ZZ_pXFileThresh
<span class="Comment">// which can be set by the user. If the sizes of the tables</span>
<span class="Comment">// exceeds ZZ_pXFileThresh KB, external files are used.</span>
<span class="Comment">// Initial value is NTL_FILE_THRESH (defined in tools.h).</span>
<span class="Type">void</span> EDF(vec_ZZ_pX& factors, <span class="Type">const</span> ZZ_pX& f, <span class="Type">const</span> ZZ_pX& h,
<span class="Type">long</span> d, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX EDF(<span class="Type">const</span> ZZ_pX& f, <span class="Type">const</span> ZZ_pX& h,
<span class="Type">long</span> d, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// Performs equal-degree factorization. f is monic, square-free, and</span>
<span class="Comment">// all irreducible factors have same degree. h = X^p mod f. d =</span>
<span class="Comment">// degree of irreducible factors of f. This routine implements the</span>
<span class="Comment">// algorithm of [von zur Gathen and Shoup, Computational Complexity</span>
<span class="Comment">// 2:187-224, 1992].</span>
<span class="Type">void</span> RootEDF(vec_ZZ_pX& factors, <span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX RootEDF(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// EDF for d==1</span>
<span class="Type">void</span> SFCanZass(vec_ZZ_pX& factors, <span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX SFCanZass(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// Assumes f is monic and square-free. returns list of factors of f.</span>
<span class="Comment">// Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and</span>
<span class="Comment">// EDF above.</span>
<span class="Type">void</span> CanZass(vec_pair_ZZ_pX_long& factors, <span class="Type">const</span> ZZ_pX& f,
<span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_pair_ZZ_pX_long CanZass(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
<span class="Comment">// returns a list of factors, with multiplicities. f must be monic.</span>
<span class="Comment">// Calls SquareFreeDecomp and SFCanZass.</span>
<span class="Comment">// NOTE: In most situations, you should use the CanZass factoring</span>
<span class="Comment">// routine, rather than Berlekamp: it is faster and uses less space.</span>
<span class="Type">void</span> mul(ZZ_pX& f, <span class="Type">const</span> vec_pair_ZZ_pX_long& v);
ZZ_pX mul(<span class="Type">const</span> vec_pair_ZZ_pX_long& v);
<span class="Comment">// multiplies polynomials, with multiplicities</span>
<span class="Comment">/*</span><span class="Comment">*************************************************************************\</span>
<span class="Comment"> Irreducible Polynomials</span>
<span class="Comment">\*************************************************************************</span><span class="Comment">*/</span>
<span class="Type">long</span> ProbIrredTest(<span class="Type">const</span> ZZ_pX& f, <span class="Type">long</span> iter=<span class="Constant">1</span>);
<span class="Comment">// performs a fast, probabilistic irreduciblity test. The test can</span>
<span class="Comment">// err only if f is reducible, and the error probability is bounded by</span>
<span class="Comment">// p^{-iter}. This implements an algorithm from [Shoup, J. Symbolic</span>
<span class="Comment">// Comp. 17:371-391, 1994].</span>
<span class="Type">long</span> DetIrredTest(<span class="Type">const</span> ZZ_pX& f);
<span class="Comment">// performs a recursive deterministic irreducibility test. Fast in</span>
<span class="Comment">// the worst-case (when input is irreducible). This implements an</span>
<span class="Comment">// algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994].</span>
<span class="Type">long</span> IterIrredTest(<span class="Type">const</span> ZZ_pX& f);
<span class="Comment">// performs an iterative deterministic irreducibility test, based on</span>
<span class="Comment">// DDF. Fast on average (when f has a small factor).</span>
<span class="Type">void</span> BuildIrred(ZZ_pX& f, <span class="Type">long</span> n);
ZZ_pX BuildIrred_ZZ_pX(<span class="Type">long</span> n);
<span class="Comment">// Build a monic irreducible poly of degree n.</span>
<span class="Type">void</span> BuildRandomIrred(ZZ_pX& f, <span class="Type">const</span> ZZ_pX& g);
ZZ_pX BuildRandomIrred(<span class="Type">const</span> ZZ_pX& g);
<span class="Comment">// g is a monic irreducible polynomial. Constructs a random monic</span>
<span class="Comment">// irreducible polynomial f of the same degree.</span>
<span class="Type">long</span> ComputeDegree(<span class="Type">const</span> ZZ_pX& h, <span class="Type">const</span> ZZ_pXModulus& F);
<span class="Comment">// f is assumed to be an "equal degree" polynomial; h = X^p mod f.</span>
<span class="Comment">// The common degree of the irreducible factors of f is computed This</span>
<span class="Comment">// routine is useful in counting points on elliptic curves</span>
<span class="Type">long</span> ProbComputeDegree(<span class="Type">const</span> ZZ_pX& h, <span class="Type">const</span> ZZ_pXModulus& F);
<span class="Comment">// Same as above, but uses a slightly faster probabilistic algorithm.</span>
<span class="Comment">// The return value may be 0 or may be too big, but for large p</span>
<span class="Comment">// (relative to n), this happens with very low probability.</span>
<span class="Type">void</span> TraceMap(ZZ_pX& w, <span class="Type">const</span> ZZ_pX& a, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus& F,
<span class="Type">const</span> ZZ_pX& h);
ZZ_pX TraceMap(<span class="Type">const</span> ZZ_pX& a, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus& F,
<span class="Type">const</span> ZZ_pX& h);
<span class="Comment">// w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0, and h =</span>
<span class="Comment">// X^q mod f, q a power of p. This routine implements an algorithm</span>
<span class="Comment">// from [von zur Gathen and Shoup, Computational Complexity 2:187-224,</span>
<span class="Comment">// 1992].</span>
<span class="Type">void</span> PowerCompose(ZZ_pX& w, <span class="Type">const</span> ZZ_pX& h, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus& F);
ZZ_pX PowerCompose(<span class="Type">const</span> ZZ_pX& h, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus& F);
<span class="Comment">// w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q mod f, q</span>
<span class="Comment">// a power of p. This routine implements an algorithm from [von zur</span>
<span class="Comment">// Gathen and Shoup, Computational Complexity 2:187-224, 1992]</span>
</pre>
</body>
</html>
<!-- vim: set foldmethod=manual : -->
