1 | |
---|
2 | /**************************************************************************\ |
---|
3 | |
---|
4 | MODULE: ZZ_pXFactoring |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | Routines are provided for factorization of polynomials over ZZ_p, as |
---|
9 | well as routines for related problems such as testing irreducibility |
---|
10 | and constructing irreducible polynomials of given degree. |
---|
11 | |
---|
12 | \**************************************************************************/ |
---|
13 | |
---|
14 | #include <NTL/ZZ_pX.h> |
---|
15 | #include <NTL/pair_ZZ_pX_long.h> |
---|
16 | |
---|
17 | void SquareFreeDecomp(vec_pair_ZZ_pX_long& u, const ZZ_pX& f); |
---|
18 | vec_pair_ZZ_pX_long SquareFreeDecomp(const ZZ_pX& f); |
---|
19 | |
---|
20 | // Performs square-free decomposition. f must be monic. If f = |
---|
21 | // prod_i g_i^i, then u is set to a lest of pairs (g_i, i). The list |
---|
22 | // is is increasing order of i, with trivial terms (i.e., g_i = 1) |
---|
23 | // deleted. |
---|
24 | |
---|
25 | |
---|
26 | void FindRoots(vec_ZZ_p& x, const ZZ_pX& f); |
---|
27 | vec_ZZ_p FindRoots(const ZZ_pX& f); |
---|
28 | |
---|
29 | // f is monic, and has deg(f) distinct roots. returns the list of |
---|
30 | // roots |
---|
31 | |
---|
32 | void FindRoot(ZZ_p& root, const ZZ_pX& f); |
---|
33 | ZZ_p FindRoot(const ZZ_pX& f); |
---|
34 | |
---|
35 | // finds a single root of f. assumes that f is monic and splits into |
---|
36 | // distinct linear factors |
---|
37 | |
---|
38 | |
---|
39 | void SFBerlekamp(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0); |
---|
40 | vec_ZZ_pX SFBerlekamp(const ZZ_pX& f, long verbose=0); |
---|
41 | |
---|
42 | // Assumes f is square-free and monic. returns list of factors of f. |
---|
43 | // Uses "Berlekamp" approach, as described in detail in [Shoup, |
---|
44 | // J. Symbolic Comp. 20:363-397, 1995]. |
---|
45 | |
---|
46 | |
---|
47 | void berlekamp(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, |
---|
48 | long verbose=0); |
---|
49 | |
---|
50 | vec_pair_ZZ_pX_long berlekamp(const ZZ_pX& f, long verbose=0); |
---|
51 | |
---|
52 | // returns a list of factors, with multiplicities. f must be monic. |
---|
53 | // Calls SFBerlekamp. |
---|
54 | |
---|
55 | |
---|
56 | |
---|
57 | void NewDDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h, |
---|
58 | long verbose=0); |
---|
59 | |
---|
60 | vec_pair_ZZ_pX_long NewDDF(const ZZ_pX& f, const ZZ_pX& h, |
---|
61 | long verbose=0); |
---|
62 | |
---|
63 | // This computes a distinct-degree factorization. The input must be |
---|
64 | // monic and square-free. factors is set to a list of pairs (g, d), |
---|
65 | // where g is the product of all irreducible factors of f of degree d. |
---|
66 | // Only nontrivial pairs (i.e., g != 1) are included. The polynomial |
---|
67 | // h is assumed to be equal to X^p mod f. |
---|
68 | |
---|
69 | // This routine implements the baby step/giant step algorithm |
---|
70 | // of [Kaltofen and Shoup, STOC 1995]. |
---|
71 | // further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995]. |
---|
72 | |
---|
73 | // NOTE: When factoring "large" polynomials, |
---|
74 | // this routine uses external files to store some intermediate |
---|
75 | // results, which are removed if the routine terminates normally. |
---|
76 | // These files are stored in the current directory under names of the |
---|
77 | // form ddf-*-baby-* and ddf-*-giant-*. |
---|
78 | // The definition of "large" is controlled by the variable |
---|
79 | |
---|
80 | extern double ZZ_pXFileThresh |
---|
81 | |
---|
82 | // which can be set by the user. If the sizes of the tables |
---|
83 | // exceeds ZZ_pXFileThresh KB, external files are used. |
---|
84 | // Initial value is 256. |
---|
85 | |
---|
86 | |
---|
87 | |
---|
88 | |
---|
89 | void EDF(vec_ZZ_pX& factors, const ZZ_pX& f, const ZZ_pX& h, |
---|
90 | long d, long verbose=0); |
---|
91 | |
---|
92 | vec_ZZ_pX EDF(const ZZ_pX& f, const ZZ_pX& h, |
---|
93 | long d, long verbose=0); |
---|
94 | |
---|
95 | // Performs equal-degree factorization. f is monic, square-free, and |
---|
96 | // all irreducible factors have same degree. h = X^p mod f. d = |
---|
97 | // degree of irreducible factors of f. This routine implements the |
---|
98 | // algorithm of [von zur Gathen and Shoup, Computational Complexity |
---|
99 | // 2:187-224, 1992]. |
---|
100 | |
---|
101 | void RootEDF(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0); |
---|
102 | vec_ZZ_pX RootEDF(const ZZ_pX& f, long verbose=0); |
---|
103 | |
---|
104 | // EDF for d==1 |
---|
105 | |
---|
106 | void SFCanZass(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0); |
---|
107 | vec_ZZ_pX SFCanZass(const ZZ_pX& f, long verbose=0); |
---|
108 | |
---|
109 | // Assumes f is monic and square-free. returns list of factors of f. |
---|
110 | // Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and |
---|
111 | // EDF above. |
---|
112 | |
---|
113 | |
---|
114 | void CanZass(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, |
---|
115 | long verbose=0); |
---|
116 | |
---|
117 | vec_pair_ZZ_pX_long CanZass(const ZZ_pX& f, long verbose=0); |
---|
118 | |
---|
119 | // returns a list of factors, with multiplicities. f must be monic. |
---|
120 | // Calls SquareFreeDecomp and SFCanZass. |
---|
121 | |
---|
122 | // NOTE: these routines use modular composition. The space |
---|
123 | // used for the required tables can be controlled by the variable |
---|
124 | // ZZ_pXArgBound (see ZZ_pX.txt). |
---|
125 | |
---|
126 | |
---|
127 | void mul(ZZ_pX& f, const vec_pair_ZZ_pX_long& v); |
---|
128 | ZZ_pX mul(const vec_pair_ZZ_pX_long& v); |
---|
129 | |
---|
130 | // multiplies polynomials, with multiplicities |
---|
131 | |
---|
132 | |
---|
133 | /**************************************************************************\ |
---|
134 | |
---|
135 | Irreducible Polynomials |
---|
136 | |
---|
137 | \**************************************************************************/ |
---|
138 | |
---|
139 | long ProbIrredTest(const ZZ_pX& f, long iter=1); |
---|
140 | |
---|
141 | // performs a fast, probabilistic irreduciblity test. The test can |
---|
142 | // err only if f is reducible, and the error probability is bounded by |
---|
143 | // p^{-iter}. This implements an algorithm from [Shoup, J. Symbolic |
---|
144 | // Comp. 17:371-391, 1994]. |
---|
145 | |
---|
146 | long DetIrredTest(const ZZ_pX& f); |
---|
147 | |
---|
148 | // performs a recursive deterministic irreducibility test. Fast in |
---|
149 | // the worst-case (when input is irreducible). This implements an |
---|
150 | // algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994]. |
---|
151 | |
---|
152 | long IterIrredTest(const ZZ_pX& f); |
---|
153 | |
---|
154 | // performs an iterative deterministic irreducibility test, based on |
---|
155 | // DDF. Fast on average (when f has a small factor). |
---|
156 | |
---|
157 | void BuildIrred(ZZ_pX& f, long n); |
---|
158 | ZZ_pX BuildIrred_ZZ_pX(long n); |
---|
159 | |
---|
160 | // Build a monic irreducible poly of degree n. |
---|
161 | |
---|
162 | void BuildRandomIrred(ZZ_pX& f, const ZZ_pX& g); |
---|
163 | ZZ_pX BuildRandomIrred(const ZZ_pX& g); |
---|
164 | |
---|
165 | // g is a monic irreducible polynomial. Constructs a random monic |
---|
166 | // irreducible polynomial f of the same degree. |
---|
167 | |
---|
168 | long ComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F); |
---|
169 | |
---|
170 | // f is assumed to be an "equal degree" polynomial; h = X^p mod f. |
---|
171 | // The common degree of the irreducible factors of f is computed This |
---|
172 | // routine is useful in counting points on elliptic curves |
---|
173 | |
---|
174 | long ProbComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F); |
---|
175 | |
---|
176 | // Same as above, but uses a slightly faster probabilistic algorithm. |
---|
177 | // The return value may be 0 or may be too big, but for large p |
---|
178 | // (relative to n), this happens with very low probability. |
---|
179 | |
---|
180 | void TraceMap(ZZ_pX& w, const ZZ_pX& a, long d, const ZZ_pXModulus& F, |
---|
181 | const ZZ_pX& h); |
---|
182 | |
---|
183 | ZZ_pX TraceMap(const ZZ_pX& a, long d, const ZZ_pXModulus& F, |
---|
184 | const ZZ_pX& h); |
---|
185 | |
---|
186 | // w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0, and h = |
---|
187 | // X^q mod f, q a power of p. This routine implements an algorithm |
---|
188 | // from [von zur Gathen and Shoup, Computational Complexity 2:187-224, |
---|
189 | // 1992]. |
---|
190 | |
---|
191 | void PowerCompose(ZZ_pX& w, const ZZ_pX& h, long d, const ZZ_pXModulus& F); |
---|
192 | |
---|
193 | ZZ_pX PowerCompose(const ZZ_pX& h, long d, const ZZ_pXModulus& F); |
---|
194 | |
---|
195 | // w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q mod f, q |
---|
196 | // a power of p. This routine implements an algorithm from [von zur |
---|
197 | // Gathen and Shoup, Computational Complexity 2:187-224, 1992] |
---|
198 | |
---|