/usr/share/doc/libntl-dev/NTL/lzz_pEXFactoring.txt 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 | /**************************************************************************\
MODULE: zz_pEXFactoring
SUMMARY:
Routines are provided for factorization of polynomials over zz_pE, as
well as routines for related problems such as testing irreducibility
and constructing irreducible polynomials of given degree.
\**************************************************************************/
#include <NTL/lzz_pEX.h>
#include <NTL/pair_lzz_pEX_long.h>
void SquareFreeDecomp(vec_pair_zz_pEX_long& u, const zz_pEX& f);
vec_pair_zz_pEX_long SquareFreeDecomp(const zz_pEX& f);
// Performs square-free decomposition. f must be monic. If f =
// prod_i g_i^i, then u is set to a list of pairs (g_i, i). The list
// is is increasing order of i, with trivial terms (i.e., g_i = 1)
// deleted.
void FindRoots(vec_zz_pE& x, const zz_pEX& f);
vec_zz_pE FindRoots(const zz_pEX& f);
// f is monic, and has deg(f) distinct roots. returns the list of
// roots
void FindRoot(zz_pE& root, const zz_pEX& f);
zz_pE FindRoot(const zz_pEX& f);
// finds a single root of f. assumes that f is monic and splits into
// distinct linear factors
void NewDDF(vec_pair_zz_pEX_long& factors, const zz_pEX& f,
const zz_pEX& h, long verbose=0);
vec_pair_zz_pEX_long NewDDF(const zz_pEX& f, const zz_pEX& h,
long verbose=0);
// This computes a distinct-degree factorization. The input must be
// monic and square-free. factors is set to a list of pairs (g, d),
// where g is the product of all irreducible factors of f of degree d.
// Only nontrivial pairs (i.e., g != 1) are included. The polynomial
// h is assumed to be equal to X^{zz_pE::cardinality()} mod f.
// This routine implements the baby step/giant step algorithm
// of [Kaltofen and Shoup, STOC 1995].
// further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995].
// NOTE: When factoring "large" polynomials,
// this routine uses external files to store some intermediate
// results, which are removed if the routine terminates normally.
// These files are stored in the current directory under names of the
// form tmp-*.
// The definition of "large" is controlled by the variable
extern double zz_pEXFileThresh
// which can be set by the user. If the sizes of the tables
// exceeds zz_pEXFileThresh KB, external files are used.
// Initial value is NTL_FILE_THRESH (defined in tools.h).
void EDF(vec_zz_pEX& factors, const zz_pEX& f, const zz_pEX& h,
long d, long verbose=0);
vec_zz_pEX EDF(const zz_pEX& f, const zz_pEX& h,
long d, long verbose=0);
// Performs equal-degree factorization. f is monic, square-free, and
// all irreducible factors have same degree. h = X^{zz_pE::cardinality()} mod
// f. d = degree of irreducible factors of f. This routine
// implements the algorithm of [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]
void RootEDF(vec_zz_pEX& factors, const zz_pEX& f, long verbose=0);
vec_zz_pEX RootEDF(const zz_pEX& f, long verbose=0);
// EDF for d==1
void SFCanZass(vec_zz_pEX& factors, const zz_pEX& f, long verbose=0);
vec_zz_pEX SFCanZass(const zz_pEX& f, long verbose=0);
// Assumes f is monic and square-free. returns list of factors of f.
// Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and
// EDF above.
void CanZass(vec_pair_zz_pEX_long& factors, const zz_pEX& f,
long verbose=0);
vec_pair_zz_pEX_long CanZass(const zz_pEX& f, long verbose=0);
// returns a list of factors, with multiplicities. f must be monic.
// Calls SquareFreeDecomp and SFCanZass.
// NOTE: these routines use modular composition. The space
// used for the required tables can be controlled by the variable
// zz_pEXArgBound (see zz_pEX.txt).
void mul(zz_pEX& f, const vec_pair_zz_pEX_long& v);
zz_pEX mul(const vec_pair_zz_pEX_long& v);
// multiplies polynomials, with multiplicities
/**************************************************************************\
Irreducible Polynomials
\**************************************************************************/
long ProbIrredTest(const zz_pEX& f, long iter=1);
// performs a fast, probabilistic irreduciblity test. The test can
// err only if f is reducible, and the error probability is bounded by
// zz_pE::cardinality()^{-iter}. This implements an algorithm from [Shoup,
// J. Symbolic Comp. 17:371-391, 1994].
long DetIrredTest(const zz_pEX& f);
// performs a recursive deterministic irreducibility test. Fast in
// the worst-case (when input is irreducible). This implements an
// algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994].
long IterIrredTest(const zz_pEX& f);
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
void BuildIrred(zz_pEX& f, long n);
zz_pEX BuildIrred_zz_pEX(long n);
// Build a monic irreducible poly of degree n.
void BuildRandomIrred(zz_pEX& f, const zz_pEX& g);
zz_pEX BuildRandomIrred(const zz_pEX& g);
// g is a monic irreducible polynomial. Constructs a random monic
// irreducible polynomial f of the same degree.
long IterComputeDegree(const zz_pEX& h, const zz_pEXModulus& F);
// f is assumed to be an "equal degree" polynomial, and h =
// X^{zz_pE::cardinality()} mod f. The common degree of the irreducible
// factors of f is computed. Uses a "baby step/giant step" algorithm, similar
// to NewDDF. Although asymptotocally slower than RecComputeDegree
// (below), it is faster for reasonably sized inputs.
long RecComputeDegree(const zz_pEX& h, const zz_pEXModulus& F);
// f is assumed to be an "equal degree" polynomial,
// h = X^{zz_pE::cardinality()} mod f.
// The common degree of the irreducible factors of f is
// computed Uses a recursive algorithm similar to DetIrredTest.
void TraceMap(zz_pEX& w, const zz_pEX& a, long d, const zz_pEXModulus& F,
const zz_pEX& h);
zz_pEX TraceMap(const zz_pEX& a, long d, const zz_pEXModulus& F,
const zz_pEX& h);
// Computes w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0,
// and h = X^q mod f, q a power of zz_pE::cardinality(). This routine
// implements an algorithm from [von zur Gathen and Shoup,
// Computational Complexity 2:187-224, 1992]
void PowerCompose(zz_pEX& w, const zz_pEX& h, long d, const zz_pEXModulus& F);
zz_pEX PowerCompose(const zz_pEX& h, long d, const zz_pEXModulus& F);
// Computes w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q
// mod f, q a power of zz_pE::cardinality(). This routine implements an
// algorithm from [von zur Gathen and Shoup, Computational Complexity
// 2:187-224, 1992]
|