doc/ZZ_pXFactoring.cpp.html

<!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>/Volumes/Unix/unix-files.noindex/ntl-new/ntl-9.6.0/doc/ZZ_pXFactoring.cpp.html</title>
<meta name="Generator" content="Vim/7.3">
<meta name="plugin-version" content="vim7.3_v6">
<meta name="syntax" content="cpp">
<meta name="settings" content="use_css">
<style type="text/css">
<!--
pre { font-family: monospace; color: #000000; background-color: #ffffff; }
body { font-family: monospace; color: #000000; background-color: #ffffff; }
.Constant { color: #ff8c00; }
.Type { color: #008b00; font-weight: bold; }
.String { color: #4a708b; }
.PreProc { color: #1874cd; }
.Comment { color: #0000ee; font-style: italic; }
-->
</style>
</head>
<body>
<pre>

<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">&lt;NTL/ZZ_pX.h&gt;</span>
<span class="PreProc">#include </span><span class="String">&lt;NTL/pair_ZZ_pX_long.h&gt;</span>

<span class="Type">void</span> SquareFreeDecomp(vec_pair_ZZ_pX_long&amp; u, <span class="Type">const</span> ZZ_pX&amp; f);
vec_pair_ZZ_pX_long SquareFreeDecomp(<span class="Type">const</span> ZZ_pX&amp; 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&amp; x, <span class="Type">const</span> ZZ_pX&amp; f);
vec_ZZ_p FindRoots(<span class="Type">const</span> ZZ_pX&amp; 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&amp; root, <span class="Type">const</span> ZZ_pX&amp; f);
ZZ_p FindRoot(<span class="Type">const</span> ZZ_pX&amp; 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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX  SFBerlekamp(<span class="Type">const</span> ZZ_pX&amp; 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 &quot;Berlekamp&quot; 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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; 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&amp; 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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; f, <span class="Type">const</span> ZZ_pX&amp; 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&amp; f, <span class="Type">const</span> ZZ_pX&amp; 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 &quot;large&quot; 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 &quot;large&quot; is controlled by the variable</span>

      <span class="Type">extern</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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; f, <span class="Type">const</span> ZZ_pX&amp; 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&amp; f, <span class="Type">const</span> ZZ_pX&amp; 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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX RootEDF(<span class="Type">const</span> ZZ_pX&amp; 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&amp; factors, <span class="Type">const</span> ZZ_pX&amp; f, <span class="Type">long</span> verbose=<span class="Constant">0</span>);
vec_ZZ_pX SFCanZass(<span class="Type">const</span> ZZ_pX&amp; 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 &quot;Cantor/Zassenhaus&quot; approach, using the routines NewDDF and</span>
<span class="Comment">// EDF above.</span>


<span class="Type">void</span> CanZass(vec_pair_ZZ_pX_long&amp; factors, <span class="Type">const</span> ZZ_pX&amp; 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&amp; 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: these routines use modular composition.  The space</span>
<span class="Comment">// used for the required tables can be controlled by the variable</span>
<span class="Comment">// ZZ_pXArgBound (see ZZ_pX.txt).</span>


<span class="Type">void</span> mul(ZZ_pX&amp; f, <span class="Type">const</span> vec_pair_ZZ_pX_long&amp; v);
ZZ_pX mul(<span class="Type">const</span> vec_pair_ZZ_pX_long&amp; 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&amp; 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&amp; 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&amp; 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&amp; 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&amp; f, <span class="Type">const</span> ZZ_pX&amp; g);
ZZ_pX BuildRandomIrred(<span class="Type">const</span> ZZ_pX&amp; 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&amp; h, <span class="Type">const</span> ZZ_pXModulus&amp; F);

<span class="Comment">// f is assumed to be an &quot;equal degree&quot; 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&amp; h, <span class="Type">const</span> ZZ_pXModulus&amp; 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&amp; w, <span class="Type">const</span> ZZ_pX&amp; a, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus&amp; F,
              <span class="Type">const</span> ZZ_pX&amp; h);

ZZ_pX TraceMap(<span class="Type">const</span> ZZ_pX&amp; a, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus&amp; F,
              <span class="Type">const</span> ZZ_pX&amp; h);

<span class="Comment">// w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d &gt;= 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&amp; w, <span class="Type">const</span> ZZ_pX&amp; h, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus&amp; F);

ZZ_pX PowerCompose(<span class="Type">const</span> ZZ_pX&amp; h, <span class="Type">long</span> d, <span class="Type">const</span> ZZ_pXModulus&amp; F);

<span class="Comment">// w = X^{q^d} mod f; it is assumed that d &gt;= 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>