/usr/share/doc/libntl-dev/NTL/GF2EXFactoring.cpp.html is in libntl-dev 9.9.1-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>/Volumes/unix-files/u/ntl-new/ntl-9.9.0dev/doc/GF2EXFactoring.cpp.html</title>
<meta name="Generator" content="Vim/7.1">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#ffffff" text="#000000"><font face="monospace">
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i>MODULE: GF2EXFactoring</i></font><br>
<br>
<font color="#0000ed"><i>SUMMARY:</i></font><br>
<br>
<font color="#0000ed"><i>Routines are provided for factorization of polynomials over GF2E, as</i></font><br>
<font color="#0000ed"><i>well as routines for related problems such as testing irreducibility</i></font><br>
<font color="#0000ed"><i>and constructing irreducible polynomials of given degree.</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/GF2EX.h></font><br>
<font color="#1773cc">#include </font><font color="#4a6f8b"><NTL/pair_GF2EX_long.h></font><br>
<br>
<font color="#008b00"><b>void</b></font> SquareFreeDecomp(vec_pair_GF2EX_long& u, <font color="#008b00"><b>const</b></font> GF2EX& f);<br>
vec_pair_GF2EX_long SquareFreeDecomp(<font color="#008b00"><b>const</b></font> GF2EX& f);<br>
<br>
<font color="#0000ed"><i>// Performs square-free decomposition. f must be monic. If f =</i></font><br>
<font color="#0000ed"><i>// prod_i g_i^i, then u is set to a list of pairs (g_i, i). The list</i></font><br>
<font color="#0000ed"><i>// is is increasing order of i, with trivial terms (i.e., g_i = 1)</i></font><br>
<font color="#0000ed"><i>// deleted.</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> FindRoots(vec_GF2E& x, <font color="#008b00"><b>const</b></font> GF2EX& f);<br>
vec_GF2E FindRoots(<font color="#008b00"><b>const</b></font> GF2EX& f);<br>
<br>
<font color="#0000ed"><i>// f is monic, and has deg(f) distinct roots. returns the list of</i></font><br>
<font color="#0000ed"><i>// roots</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> FindRoot(GF2E& root, <font color="#008b00"><b>const</b></font> GF2EX& f);<br>
GF2E FindRoot(<font color="#008b00"><b>const</b></font> GF2EX& f);<br>
<br>
<br>
<font color="#0000ed"><i>// finds a single root of f. assumes that f is monic and splits into</i></font><br>
<font color="#0000ed"><i>// distinct linear factors</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> SFBerlekamp(vec_GF2EX& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
vec_GF2EX SFBerlekamp(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<font color="#0000ed"><i>// Assumes f is square-free and monic. returns list of factors of f.</i></font><br>
<font color="#0000ed"><i>// Uses "Berlekamp" approach, as described in detail in [Shoup,</i></font><br>
<font color="#0000ed"><i>// J. Symbolic Comp. 20:363-397, 1995].</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> berlekamp(vec_pair_GF2EX_long& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <br>
<font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
vec_pair_GF2EX_long berlekamp(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<br>
<font color="#0000ed"><i>// returns a list of factors, with multiplicities. f must be monic.</i></font><br>
<font color="#0000ed"><i>// Calls SFBerlekamp.</i></font><br>
<br>
<br>
<br>
<font color="#008b00"><b>void</b></font> NewDDF(vec_pair_GF2EX_long& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>const</b></font> GF2EX& h,<br>
<font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
vec_pair_GF2EX_long NewDDF(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>const</b></font> GF2EX& h,<br>
<font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<br>
<font color="#0000ed"><i>// This computes a distinct-degree factorization. The input must be</i></font><br>
<font color="#0000ed"><i>// monic and square-free. factors is set to a list of pairs (g, d),</i></font><br>
<font color="#0000ed"><i>// where g is the product of all irreducible factors of f of degree d.</i></font><br>
<font color="#0000ed"><i>// Only nontrivial pairs (i.e., g != 1) are included. The polynomial</i></font><br>
<font color="#0000ed"><i>// h is assumed to be equal to X^{2^{GF2E::degree()}} mod f,</i></font><br>
<font color="#0000ed"><i>// which can be computed efficiently using the function FrobeniusMap </i></font><br>
<font color="#0000ed"><i>// (see below).</i></font><br>
<font color="#0000ed"><i>// This routine implements the baby step/giant step algorithm </i></font><br>
<font color="#0000ed"><i>// of [Kaltofen and Shoup, STOC 1995], </i></font><br>
<font color="#0000ed"><i>// further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995].</i></font><br>
<br>
<font color="#0000ed"><i>// NOTE: When factoring "large" polynomials,</i></font><br>
<font color="#0000ed"><i>// this routine uses external files to store some intermediate</i></font><br>
<font color="#0000ed"><i>// results, which are removed if the routine terminates normally.</i></font><br>
<font color="#0000ed"><i>// These files are stored in the current directory under names of the</i></font><br>
<font color="#0000ed"><i>// form tmp-*.</i></font><br>
<font color="#0000ed"><i>// The definition of "large" is controlled by the variable</i></font><br>
<br>
<font color="#008b00"><b>extern</b></font> <font color="#008b00"><b>double</b></font> GF2EXFileThresh<br>
<br>
<font color="#0000ed"><i>// which can be set by the user. If the sizes of the tables</i></font><br>
<font color="#0000ed"><i>// exceeds GF2EXFileThresh KB, external files are used.</i></font><br>
<font color="#0000ed"><i>// Initial value is NTL_FILE_THRESH (defined in tools.h).</i></font><br>
<br>
<br>
<br>
<font color="#008b00"><b>void</b></font> EDF(vec_GF2EX& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>const</b></font> GF2EX& h,<br>
<font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
vec_GF2EX EDF(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>const</b></font> GF2EX& h,<br>
<font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<font color="#0000ed"><i>// Performs equal-degree factorization. f is monic, square-free, and</i></font><br>
<font color="#0000ed"><i>// all irreducible factors have same degree. </i></font><br>
<font color="#0000ed"><i>// h = X^{2^{GF2E::degree()}} mod f,</i></font><br>
<font color="#0000ed"><i>// which can be computed efficiently using the function FrobeniusMap </i></font><br>
<font color="#0000ed"><i>// (see below).</i></font><br>
<font color="#0000ed"><i>// d = degree of irreducible factors of f. </i></font><br>
<font color="#0000ed"><i>// This routine implements the algorithm of [von zur Gathen and Shoup,</i></font><br>
<font color="#0000ed"><i>// Computational Complexity 2:187-224, 1992]</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> RootEDF(vec_GF2EX& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
vec_GF2EX RootEDF(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<font color="#0000ed"><i>// EDF for d==1</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> SFCanZass(vec_GF2EX& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
vec_GF2EX SFCanZass(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<font color="#0000ed"><i>// Assumes f is monic and square-free. returns list of factors of f.</i></font><br>
<font color="#0000ed"><i>// Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and</i></font><br>
<font color="#0000ed"><i>// EDF above.</i></font><br>
<br>
<br>
<font color="#008b00"><b>void</b></font> CanZass(vec_pair_GF2EX_long& factors, <font color="#008b00"><b>const</b></font> GF2EX& f, <br>
<font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
vec_pair_GF2EX_long CanZass(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> verbose=<font color="#ff8b00">0</font>);<br>
<br>
<br>
<font color="#0000ed"><i>// returns a list of factors, with multiplicities. f must be monic.</i></font><br>
<font color="#0000ed"><i>// Calls SquareFreeDecomp and SFCanZass.</i></font><br>
<br>
<font color="#0000ed"><i>// NOTE: these routines use modular composition. The space</i></font><br>
<font color="#0000ed"><i>// used for the required tables can be controlled by the variable</i></font><br>
<font color="#0000ed"><i>// GF2EXArgBound (see GF2EX.txt).</i></font><br>
<br>
<br>
<br>
<font color="#008b00"><b>void</b></font> mul(GF2EX& f, <font color="#008b00"><b>const</b></font> vec_pair_GF2EX_long& v);<br>
GF2EX mul(<font color="#008b00"><b>const</b></font> vec_pair_GF2EX_long& v);<br>
<br>
<font color="#0000ed"><i>// multiplies polynomials, with multiplicities</i></font><br>
<br>
<br>
<font color="#0000ed"><i>/*</i></font><font color="#0000ed"><i>*************************************************************************\</i></font><br>
<br>
<font color="#0000ed"><i> Irreducible Polynomials</i></font><br>
<br>
<font color="#0000ed"><i>\*************************************************************************</i></font><font color="#0000ed"><i>*/</i></font><br>
<br>
<font color="#008b00"><b>long</b></font> ProbIrredTest(<font color="#008b00"><b>const</b></font> GF2EX& f, <font color="#008b00"><b>long</b></font> iter=<font color="#ff8b00">1</font>);<br>
<br>
<font color="#0000ed"><i>// performs a fast, probabilistic irreduciblity test. The test can</i></font><br>
<font color="#0000ed"><i>// err only if f is reducible, and the error probability is bounded by</i></font><br>
<font color="#0000ed"><i>// 2^{-iter*GF2E::degree()}. This implements an algorithm from [Shoup,</i></font><br>
<font color="#0000ed"><i>// J. Symbolic Comp. 17:371-391, 1994].</i></font><br>
<br>
<font color="#008b00"><b>long</b></font> DetIrredTest(<font color="#008b00"><b>const</b></font> GF2EX& f);<br>
<br>
<font color="#0000ed"><i>// performs a recursive deterministic irreducibility test. Fast in</i></font><br>
<font color="#0000ed"><i>// the worst-case (when input is irreducible). This implements an</i></font><br>
<font color="#0000ed"><i>// algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994].</i></font><br>
<br>
<font color="#008b00"><b>long</b></font> IterIrredTest(<font color="#008b00"><b>const</b></font> GF2EX& f);<br>
<br>
<font color="#0000ed"><i>// performs an iterative deterministic irreducibility test, based on</i></font><br>
<font color="#0000ed"><i>// DDF. Fast on average (when f has a small factor).</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> BuildIrred(GF2EX& f, <font color="#008b00"><b>long</b></font> n);<br>
GF2EX BuildIrred_GF2EX(<font color="#008b00"><b>long</b></font> n);<br>
<br>
<font color="#0000ed"><i>// Build a monic irreducible poly of degree n. </i></font><br>
<br>
<font color="#008b00"><b>void</b></font> BuildRandomIrred(GF2EX& f, <font color="#008b00"><b>const</b></font> GF2EX& g);<br>
GF2EX BuildRandomIrred(<font color="#008b00"><b>const</b></font> GF2EX& g);<br>
<br>
<font color="#0000ed"><i>// g is a monic irreducible polynomial. Constructs a random monic</i></font><br>
<font color="#0000ed"><i>// irreducible polynomial f of the same degree.</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> FrobeniusMap(GF2EX& h, <font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
GF2EX FrobeniusMap(<font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
<br>
<font color="#0000ed"><i>// Computes h = X^{2^{GF2E::degree()}} mod F, </i></font><br>
<font color="#0000ed"><i>// by either iterated squaring or modular</i></font><br>
<font color="#0000ed"><i>// composition. The latter method is based on a technique developed</i></font><br>
<font color="#0000ed"><i>// in Kaltofen & Shoup (Faster polynomial factorization over high</i></font><br>
<font color="#0000ed"><i>// algebraic extensions of finite fields, ISSAC 1997). This method is</i></font><br>
<font color="#0000ed"><i>// faster than iterated squaring when deg(F) is large relative to</i></font><br>
<font color="#0000ed"><i>// GF2E::degree().</i></font><br>
<br>
<br>
<font color="#008b00"><b>long</b></font> IterComputeDegree(<font color="#008b00"><b>const</b></font> GF2EX& h, <font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
<br>
<font color="#0000ed"><i>// f is assumed to be an "equal degree" polynomial, and h =</i></font><br>
<font color="#0000ed"><i>// X^{2^{GF2E::degree()}} mod f (see function FrobeniusMap above) </i></font><br>
<font color="#0000ed"><i>// The common degree of the irreducible factors</i></font><br>
<font color="#0000ed"><i>// of f is computed. Uses a "baby step/giant step" algorithm, similar</i></font><br>
<font color="#0000ed"><i>// to NewDDF. Although asymptotocally slower than RecComputeDegree</i></font><br>
<font color="#0000ed"><i>// (below), it is faster for reasonably sized inputs.</i></font><br>
<br>
<font color="#008b00"><b>long</b></font> RecComputeDegree(<font color="#008b00"><b>const</b></font> GF2EX& h, <font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
<br>
<font color="#0000ed"><i>// f is assumed to be an "equal degree" polynomial, h = X^{2^{GF2E::degree()}}</i></font><br>
<font color="#0000ed"><i>// mod f (see function FrobeniusMap above). </i></font><br>
<font color="#0000ed"><i>// The common degree of the irreducible factors of f is</i></font><br>
<font color="#0000ed"><i>// computed. Uses a recursive algorithm similar to DetIrredTest.</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> TraceMap(GF2EX& w, <font color="#008b00"><b>const</b></font> GF2EX& a, <font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>const</b></font> GF2EXModulus& F,<br>
<font color="#008b00"><b>const</b></font> GF2EX& h);<br>
<br>
GF2EX TraceMap(<font color="#008b00"><b>const</b></font> GF2EX& a, <font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>const</b></font> GF2EXModulus& F,<br>
<font color="#008b00"><b>const</b></font> GF2EX& h);<br>
<br>
<font color="#0000ed"><i>// Computes w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0,</i></font><br>
<font color="#0000ed"><i>// and h = X^q mod f, q a power of 2^{GF2E::degree()}. This routine</i></font><br>
<font color="#0000ed"><i>// implements an algorithm from [von zur Gathen and Shoup,</i></font><br>
<font color="#0000ed"><i>// Computational Complexity 2:187-224, 1992].</i></font><br>
<font color="#0000ed"><i>// If q = 2^{GF2E::degree()}, then h can be computed most efficiently</i></font><br>
<font color="#0000ed"><i>// by using the function FrobeniusMap above.</i></font><br>
<br>
<font color="#008b00"><b>void</b></font> PowerCompose(GF2EX& w, <font color="#008b00"><b>const</b></font> GF2EX& h, <font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
<br>
GF2EX PowerCompose(<font color="#008b00"><b>const</b></font> GF2EX& h, <font color="#008b00"><b>long</b></font> d, <font color="#008b00"><b>const</b></font> GF2EXModulus& F);<br>
<br>
<font color="#0000ed"><i>// Computes w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q</i></font><br>
<font color="#0000ed"><i>// mod f, q a power of 2^{GF2E::degree()}. This routine implements an</i></font><br>
<font color="#0000ed"><i>// algorithm from [von zur Gathen and Shoup, Computational Complexity</i></font><br>
<font color="#0000ed"><i>// 2:187-224, 1992].</i></font><br>
<font color="#0000ed"><i>// If q = 2^{GF2E::degree()}, then h can be computed most efficiently</i></font><br>
<font color="#0000ed"><i>// by using the function FrobeniusMap above.</i></font><br>
<br>
</font></body>
</html>
|