1 | |
---|
2 | /**************************************************************************\ |
---|
3 | |
---|
4 | MODULE: GF2EXFactoring |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | Routines are provided for factorization of polynomials over GF2E, 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/GF2EX.h> |
---|
15 | #include <NTL/pair_GF2EX_long.h> |
---|
16 | |
---|
17 | void SquareFreeDecomp(vec_pair_GF2EX_long& u, const GF2EX& f); |
---|
18 | vec_pair_GF2EX_long SquareFreeDecomp(const GF2EX& 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 list 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_GF2E& x, const GF2EX& f); |
---|
27 | vec_GF2E FindRoots(const GF2EX& f); |
---|
28 | |
---|
29 | // f is monic, and has deg(f) distinct roots. returns the list of |
---|
30 | // roots |
---|
31 | |
---|
32 | void FindRoot(GF2E& root, const GF2EX& f); |
---|
33 | GF2E FindRoot(const GF2EX& f); |
---|
34 | |
---|
35 | |
---|
36 | // finds a single root of f. assumes that f is monic and splits into |
---|
37 | // distinct linear factors |
---|
38 | |
---|
39 | |
---|
40 | void SFBerlekamp(vec_GF2EX& factors, const GF2EX& f, long verbose=0); |
---|
41 | vec_GF2EX SFBerlekamp(const GF2EX& f, long verbose=0); |
---|
42 | |
---|
43 | // Assumes f is square-free and monic. returns list of factors of f. |
---|
44 | // Uses "Berlekamp" approach, as described in detail in [Shoup, |
---|
45 | // J. Symbolic Comp. 20:363-397, 1995]. |
---|
46 | |
---|
47 | |
---|
48 | void berlekamp(vec_pair_GF2EX_long& factors, const GF2EX& f, |
---|
49 | long verbose=0); |
---|
50 | |
---|
51 | vec_pair_GF2EX_long berlekamp(const GF2EX& f, long verbose=0); |
---|
52 | |
---|
53 | |
---|
54 | // returns a list of factors, with multiplicities. f must be monic. |
---|
55 | // Calls SFBerlekamp. |
---|
56 | |
---|
57 | |
---|
58 | |
---|
59 | void NewDDF(vec_pair_GF2EX_long& factors, const GF2EX& f, const GF2EX& h, |
---|
60 | long verbose=0); |
---|
61 | |
---|
62 | vec_pair_GF2EX_long NewDDF(const GF2EX& f, const GF2EX& h, |
---|
63 | long verbose=0); |
---|
64 | |
---|
65 | |
---|
66 | // This computes a distinct-degree factorization. The input must be |
---|
67 | // monic and square-free. factors is set to a list of pairs (g, d), |
---|
68 | // where g is the product of all irreducible factors of f of degree d. |
---|
69 | // Only nontrivial pairs (i.e., g != 1) are included. The polynomial |
---|
70 | // h is assumed to be equal to X^{2^{GF2E::degree()}} mod f, |
---|
71 | // which can be computed efficiently using the function FrobeniusMap |
---|
72 | // (see below). |
---|
73 | // This routine implements the baby step/giant step algorithm |
---|
74 | // of [Kaltofen and Shoup, STOC 1995], |
---|
75 | // further described in [Shoup, J. Symbolic Comp. 20:363-397, 1995]. |
---|
76 | |
---|
77 | // NOTE: When factoring "large" polynomials, |
---|
78 | // this routine uses external files to store some intermediate |
---|
79 | // results, which are removed if the routine terminates normally. |
---|
80 | // These files are stored in the current directory under names of the |
---|
81 | // form ddf-*-baby-* and ddf-*-giant-*. |
---|
82 | // The definition of "large" is controlled by the variable |
---|
83 | |
---|
84 | extern double GF2EXFileThresh |
---|
85 | |
---|
86 | // which can be set by the user. If the sizes of the tables |
---|
87 | // exceeds GF2EXFileThresh KB, external files are used. |
---|
88 | // Initial value is 256. |
---|
89 | |
---|
90 | |
---|
91 | |
---|
92 | void EDF(vec_GF2EX& factors, const GF2EX& f, const GF2EX& h, |
---|
93 | long d, long verbose=0); |
---|
94 | |
---|
95 | vec_GF2EX EDF(const GF2EX& f, const GF2EX& h, |
---|
96 | long d, long verbose=0); |
---|
97 | |
---|
98 | // Performs equal-degree factorization. f is monic, square-free, and |
---|
99 | // all irreducible factors have same degree. |
---|
100 | // h = X^{2^{GF2E::degree()}} mod f, |
---|
101 | // which can be computed efficiently using the function FrobeniusMap |
---|
102 | // (see below). |
---|
103 | // d = degree of irreducible factors of f. |
---|
104 | // This routine implements the algorithm of [von zur Gathen and Shoup, |
---|
105 | // Computational Complexity 2:187-224, 1992] |
---|
106 | |
---|
107 | void RootEDF(vec_GF2EX& factors, const GF2EX& f, long verbose=0); |
---|
108 | vec_GF2EX RootEDF(const GF2EX& f, long verbose=0); |
---|
109 | |
---|
110 | // EDF for d==1 |
---|
111 | |
---|
112 | |
---|
113 | void SFCanZass(vec_GF2EX& factors, const GF2EX& f, long verbose=0); |
---|
114 | vec_GF2EX SFCanZass(const GF2EX& f, long verbose=0); |
---|
115 | |
---|
116 | // Assumes f is monic and square-free. returns list of factors of f. |
---|
117 | // Uses "Cantor/Zassenhaus" approach, using the routines NewDDF and |
---|
118 | // EDF above. |
---|
119 | |
---|
120 | |
---|
121 | void CanZass(vec_pair_GF2EX_long& factors, const GF2EX& f, |
---|
122 | long verbose=0); |
---|
123 | |
---|
124 | vec_pair_GF2EX_long CanZass(const GF2EX& f, long verbose=0); |
---|
125 | |
---|
126 | |
---|
127 | // returns a list of factors, with multiplicities. f must be monic. |
---|
128 | // Calls SquareFreeDecomp and SFCanZass. |
---|
129 | |
---|
130 | // NOTE: these routines use modular composition. The space |
---|
131 | // used for the required tables can be controlled by the variable |
---|
132 | // GF2EXArgBound (see GF2EX.txt). |
---|
133 | |
---|
134 | |
---|
135 | |
---|
136 | void mul(GF2EX& f, const vec_pair_GF2EX_long& v); |
---|
137 | GF2EX mul(const vec_pair_GF2EX_long& v); |
---|
138 | |
---|
139 | // multiplies polynomials, with multiplicities |
---|
140 | |
---|
141 | |
---|
142 | /**************************************************************************\ |
---|
143 | |
---|
144 | Irreducible Polynomials |
---|
145 | |
---|
146 | \**************************************************************************/ |
---|
147 | |
---|
148 | long ProbIrredTest(const GF2EX& f, long iter=1); |
---|
149 | |
---|
150 | // performs a fast, probabilistic irreduciblity test. The test can |
---|
151 | // err only if f is reducible, and the error probability is bounded by |
---|
152 | // 2^{-iter*GF2E::degree()}. This implements an algorithm from [Shoup, |
---|
153 | // J. Symbolic Comp. 17:371-391, 1994]. |
---|
154 | |
---|
155 | long DetIrredTest(const GF2EX& f); |
---|
156 | |
---|
157 | // performs a recursive deterministic irreducibility test. Fast in |
---|
158 | // the worst-case (when input is irreducible). This implements an |
---|
159 | // algorithm from [Shoup, J. Symbolic Comp. 17:371-391, 1994]. |
---|
160 | |
---|
161 | long IterIrredTest(const GF2EX& f); |
---|
162 | |
---|
163 | // performs an iterative deterministic irreducibility test, based on |
---|
164 | // DDF. Fast on average (when f has a small factor). |
---|
165 | |
---|
166 | void BuildIrred(GF2EX& f, long n); |
---|
167 | GF2EX BuildIrred_GF2EX(long n); |
---|
168 | |
---|
169 | // Build a monic irreducible poly of degree n. |
---|
170 | |
---|
171 | void BuildRandomIrred(GF2EX& f, const GF2EX& g); |
---|
172 | GF2EX BuildRandomIrred(const GF2EX& g); |
---|
173 | |
---|
174 | // g is a monic irreducible polynomial. Constructs a random monic |
---|
175 | // irreducible polynomial f of the same degree. |
---|
176 | |
---|
177 | void FrobeniusMap(GF2EX& h, const GF2EXModulus& F); |
---|
178 | GF2EX FrobeniusMap(const GF2EXModulus& F); |
---|
179 | |
---|
180 | // Computes h = X^{2^{GF2E::degree()}} mod F, |
---|
181 | // by either iterated squaring or modular |
---|
182 | // composition. The latter method is based on a technique developed |
---|
183 | // in Kaltofen & Shoup (Faster polynomial factorization over high |
---|
184 | // algebraic extensions of finite fields, ISSAC 1997). This method is |
---|
185 | // faster than iterated squaring when deg(F) is large relative to |
---|
186 | // GF2E::degree(). |
---|
187 | |
---|
188 | |
---|
189 | long IterComputeDegree(const GF2EX& h, const GF2EXModulus& F); |
---|
190 | |
---|
191 | // f is assumed to be an "equal degree" polynomial, and h = |
---|
192 | // X^{2^{GF2E::degree()}} mod f (see function FrobeniusMap above) |
---|
193 | // The common degree of the irreducible factors |
---|
194 | // of f is computed. Uses a "baby step/giant step" algorithm, similar |
---|
195 | // to NewDDF. Although asymptotocally slower than RecComputeDegree |
---|
196 | // (below), it is faster for reasonably sized inputs. |
---|
197 | |
---|
198 | long RecComputeDegree(const GF2EX& h, const GF2EXModulus& F); |
---|
199 | |
---|
200 | // f is assumed to be an "equal degree" polynomial, h = X^{2^{GF2E::degree()}} |
---|
201 | // mod f (see function FrobeniusMap above). |
---|
202 | // The common degree of the irreducible factors of f is |
---|
203 | // computed. Uses a recursive algorithm similar to DetIrredTest. |
---|
204 | |
---|
205 | void TraceMap(GF2EX& w, const GF2EX& a, long d, const GF2EXModulus& F, |
---|
206 | const GF2EX& h); |
---|
207 | |
---|
208 | GF2EX TraceMap(const GF2EX& a, long d, const GF2EXModulus& F, |
---|
209 | const GF2EX& h); |
---|
210 | |
---|
211 | // Computes w = a+a^q+...+^{q^{d-1}} mod f; it is assumed that d >= 0, |
---|
212 | // and h = X^q mod f, q a power of 2^{GF2E::degree()}. This routine |
---|
213 | // implements an algorithm from [von zur Gathen and Shoup, |
---|
214 | // Computational Complexity 2:187-224, 1992]. |
---|
215 | // If q = 2^{GF2E::degree()}, then h can be computed most efficiently |
---|
216 | // by using the function FrobeniusMap above. |
---|
217 | |
---|
218 | void PowerCompose(GF2EX& w, const GF2EX& h, long d, const GF2EXModulus& F); |
---|
219 | |
---|
220 | GF2EX PowerCompose(const GF2EX& h, long d, const GF2EXModulus& F); |
---|
221 | |
---|
222 | // Computes w = X^{q^d} mod f; it is assumed that d >= 0, and h = X^q |
---|
223 | // mod f, q a power of 2^{GF2E::degree()}. This routine implements an |
---|
224 | // algorithm from [von zur Gathen and Shoup, Computational Complexity |
---|
225 | // 2:187-224, 1992]. |
---|
226 | // If q = 2^{GF2E::degree()}, then h can be computed most efficiently |
---|
227 | // by using the function FrobeniusMap above. |
---|
228 | |
---|