/usr/share/doc/libntl-dev/NTL/ZZ_pXFactoring.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 187 188 189 190 191 192 193 194 195 196 | /**************************************************************************\
MODULE: ZZ_pXFactoring
SUMMARY:
Routines are provided for factorization of polynomials over ZZ_p, as
well as routines for related problems such as testing irreducibility
and constructing irreducible polynomials of given degree.
\**************************************************************************/
#include <NTL/ZZ_pX.h>
#include <NTL/pair_ZZ_pX_long.h>
void SquareFreeDecomp(vec_pair_ZZ_pX_long& u, const ZZ_pX& f);
vec_pair_ZZ_pX_long SquareFreeDecomp(const ZZ_pX& f);
// Performs square-free decomposition. f must be monic. If f =
// prod_i g_i^i, then u is set to a lest 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_p& x, const ZZ_pX& f);
vec_ZZ_p FindRoots(const ZZ_pX& f);
// f is monic, and has deg(f) distinct roots. returns the list of
// roots
void FindRoot(ZZ_p& root, const ZZ_pX& f);
ZZ_p FindRoot(const ZZ_pX& f);
// finds a single root of f. assumes that f is monic and splits into
// distinct linear factors
void SFBerlekamp(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX SFBerlekamp(const ZZ_pX& f, long verbose=0);
// Assumes f is square-free and monic. returns list of factors of f.
// Uses "Berlekamp" approach, as described in detail in [Shoup,
// J. Symbolic Comp. 20:363-397, 1995].
void berlekamp(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f,
long verbose=0);
vec_pair_ZZ_pX_long berlekamp(const ZZ_pX& f, long verbose=0);
// returns a list of factors, with multiplicities. f must be monic.
// Calls SFBerlekamp.
void NewDDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h,
long verbose=0);
vec_pair_ZZ_pX_long NewDDF(const ZZ_pX& f, const ZZ_pX& 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^p 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_pXFileThresh
// which can be set by the user. If the sizes of the tables
// exceeds ZZ_pXFileThresh KB, external files are used.
// Initial value is NTL_FILE_THRESH (defined in tools.h).
void EDF(vec_ZZ_pX& factors, const ZZ_pX& f, const ZZ_pX& h,
long d, long verbose=0);
vec_ZZ_pX EDF(const ZZ_pX& f, const ZZ_pX& h,
long d, long verbose=0);
// Performs equal-degree factorization. f is monic, square-free, and
// all irreducible factors have same degree. h = X^p 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_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX RootEDF(const ZZ_pX& f, long verbose=0);
// EDF for d==1
void SFCanZass(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
vec_ZZ_pX SFCanZass(const ZZ_pX& 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_pX_long& factors, const ZZ_pX& f,
long verbose=0);
vec_pair_ZZ_pX_long CanZass(const ZZ_pX& 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_pXArgBound (see ZZ_pX.txt).
void mul(ZZ_pX& f, const vec_pair_ZZ_pX_long& v);
ZZ_pX mul(const vec_pair_ZZ_pX_long& v);
// multiplies polynomials, with multiplicities
/**************************************************************************\
Irreducible Polynomials
\**************************************************************************/
long ProbIrredTest(const ZZ_pX& 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
// p^{-iter}. This implements an algorithm from [Shoup, J. Symbolic
// Comp. 17:371-391, 1994].
long DetIrredTest(const ZZ_pX& 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_pX& f);
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
void BuildIrred(ZZ_pX& f, long n);
ZZ_pX BuildIrred_ZZ_pX(long n);
// Build a monic irreducible poly of degree n.
void BuildRandomIrred(ZZ_pX& f, const ZZ_pX& g);
ZZ_pX BuildRandomIrred(const ZZ_pX& g);
// g is a monic irreducible polynomial. Constructs a random monic
// irreducible polynomial f of the same degree.
long ComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
// f is assumed to be an "equal degree" polynomial; h = X^p mod f.
// The common degree of the irreducible factors of f is computed This
// routine is useful in counting points on elliptic curves
long ProbComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
// Same as above, but uses a slightly faster probabilistic algorithm.
// The return value may be 0 or may be too big, but for large p
// (relative to n), this happens with very low probability.
void TraceMap(ZZ_pX& w, const ZZ_pX& a, long d, const ZZ_pXModulus& F,
const ZZ_pX& h);
ZZ_pX TraceMap(const ZZ_pX& a, long d, const ZZ_pXModulus& F,
const ZZ_pX& h);
// 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 p. This routine implements an algorithm
// from [von zur Gathen and Shoup, Computational Complexity 2:187-224,
// 1992].
void PowerCompose(ZZ_pX& w, const ZZ_pX& h, long d, const ZZ_pXModulus& F);
ZZ_pX PowerCompose(const ZZ_pX& h, long d, const ZZ_pXModulus& F);
// w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q mod f, q
// a power of p. This routine implements an algorithm from [von zur
// Gathen and Shoup, Computational Complexity 2:187-224, 1992]
|