1
2
3 #ifndef NTL_ZZ_pXFactoring__H
4 #define NTL_ZZ_pXFactoring__H
5
6 #include <NTL/ZZ.h>
7 #include <NTL/ZZ_p.h>
8 #include <NTL/ZZ_pX.h>
9 #include <NTL/pair_ZZ_pX_long.h>
10
11 NTL_OPEN_NNS
12
13
14
15
16 /************************************************************
17
18 factorization routines
19
20 ************************************************************/
21
22
23
24
25
26 void SquareFreeDecomp(vec_pair_ZZ_pX_long& u, const ZZ_pX& f);
SquareFreeDecomp(const ZZ_pX & f)27 inline vec_pair_ZZ_pX_long SquareFreeDecomp(const ZZ_pX& f)
28 { vec_pair_ZZ_pX_long x; SquareFreeDecomp(x, f); return x; }
29
30 // Performs square-free decomposition.
31 // f must be monic.
32 // If f = prod_i g_i^i, then u is set to a lest of pairs (g_i, i).
33 // The list is is increasing order of i, with trivial terms
34 // (i.e., g_i = 1) deleted.
35
36
37 void FindRoots(vec_ZZ_p& x, const ZZ_pX& f);
FindRoots(const ZZ_pX & f)38 inline vec_ZZ_p FindRoots(const ZZ_pX& f)
39 { vec_ZZ_p x; FindRoots(x, f); return x; }
40
41 // f is monic, and has deg(f) distinct roots.
42 // returns the list of roots
43
44 void FindRoot(ZZ_p& root, const ZZ_pX& f);
FindRoot(const ZZ_pX & f)45 inline ZZ_p FindRoot(const ZZ_pX& f)
46 { ZZ_p x; FindRoot(x, f); return x; }
47
48 // finds a single root of f.
49 // assumes that f is monic and splits into distinct linear factors
50
51
52 void SFBerlekamp(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
53 inline vec_ZZ_pX SFBerlekamp(const ZZ_pX& f, long verbose=0)
54 { vec_ZZ_pX x; SFBerlekamp(x, f, verbose); return x; }
55
56 // Assumes f is square-free and monic.
57 // returns list of factors of f.
58 // Uses "Berlekamp" appraoch.
59
60
61 void berlekamp(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, long verbose=0);
62 inline vec_pair_ZZ_pX_long
63 berlekamp(const ZZ_pX& f, long verbose=0)
64 { vec_pair_ZZ_pX_long x; berlekamp(x, f, verbose); return x; }
65
66 // returns a list of factors, with multiplicities.
67 // f must be monic.
68 // Uses "Berlekamp" appraoch.
69
70
71 extern NTL_CHEAP_THREAD_LOCAL long ZZ_pX_BlockingFactor;
72 // Controls GCD blocking for DDF.
73
74 void DDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h,
75 long verbose=0);
76
77 inline vec_pair_ZZ_pX_long DDF(const ZZ_pX& f, const ZZ_pX& h,
78 long verbose=0)
79 { vec_pair_ZZ_pX_long x; DDF(x, f, h, verbose); return x; }
80
81 // Performs distinct-degree factorization.
82 // Assumes f is monic and square-free, and h = X^p mod f
83 // Obsolete: see NewDDF, below.
84
85 extern NTL_CHEAP_THREAD_LOCAL long ZZ_pX_GCDTableSize; /* = 4 */
86 // Controls GCD blocking for NewDDF
87
88
89 extern NTL_CHEAP_THREAD_LOCAL double ZZ_pXFileThresh;
90 // external files are used for baby/giant steps if size
91 // of these tables exceeds ZZ_pXFileThresh KB.
92
93 void NewDDF(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f, const ZZ_pX& h,
94 long verbose=0);
95
96 inline vec_pair_ZZ_pX_long NewDDF(const ZZ_pX& f, const ZZ_pX& h,
97 long verbose=0)
98 { vec_pair_ZZ_pX_long x; NewDDF(x, f, h, verbose); return x; }
99
100 // same as above, but uses baby-step/giant-step method
101
102
103 void EDF(vec_ZZ_pX& factors, const ZZ_pX& f, const ZZ_pX& b,
104 long d, long verbose=0);
105
106 inline vec_ZZ_pX EDF(const ZZ_pX& f, const ZZ_pX& b,
107 long d, long verbose=0)
108 { vec_ZZ_pX x; EDF(x, f, b, d, verbose); return x; }
109
110 // Performs equal-degree factorization.
111 // f is monic, square-free, and all irreducible factors have same degree.
112 // b = X^p mod f.
113 // d = degree of irreducible factors of f
114 // Space for the trace-map computation can be controlled via ComposeBound.
115
116
117
118 void RootEDF(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
119 inline vec_ZZ_pX RootEDF(const ZZ_pX& f, long verbose=0)
120 { vec_ZZ_pX x; RootEDF(x, f, verbose); return x; }
121
122 // EDF for d==1
123
124 void SFCanZass(vec_ZZ_pX& factors, const ZZ_pX& f, long verbose=0);
125 inline vec_ZZ_pX SFCanZass(const ZZ_pX& f, long verbose=0)
126 { vec_ZZ_pX x; SFCanZass(x, f, verbose); return x; }
127
128 // Assumes f is monic and square-free.
129 // returns list of factors of f.
130 // Uses "Cantor/Zassenhaus" approach.
131
132
133
134 void CanZass(vec_pair_ZZ_pX_long& factors, const ZZ_pX& f,
135 long verbose=0);
136
137 inline vec_pair_ZZ_pX_long CanZass(const ZZ_pX& f, long verbose=0)
138 { vec_pair_ZZ_pX_long x; CanZass(x, f, verbose); return x; }
139
140 // returns a list of factors, with multiplicities.
141 // f must be monic.
142 // Uses "Cantor/Zassenhaus" approach.
143
144
145 void mul(ZZ_pX& f, const vec_pair_ZZ_pX_long& v);
mul(const vec_pair_ZZ_pX_long & v)146 inline ZZ_pX mul(const vec_pair_ZZ_pX_long& v)
147 { ZZ_pX x; mul(x, v); return x; }
148
149 // multiplies polynomials, with multiplicities
150
151
152 /*************************************************************
153
154 irreducible poly's: tests and constructions
155
156 **************************************************************/
157
158 long ProbIrredTest(const ZZ_pX& f, long iter=1);
159
160 // performs a fast, probabilistic irreduciblity test
161 // the test can err only if f is reducible, and the
162 // error probability is bounded by p^{-iter}.
163
164 long DetIrredTest(const ZZ_pX& f);
165
166 // performs a recursive deterministic irreducibility test
167 // fast in the worst-case (when input is irreducible).
168
169 long IterIrredTest(const ZZ_pX& f);
170
171 // performs an iterative deterministic irreducibility test,
172 // based on DDF. Fast on average (when f has a small factor).
173
174 void BuildIrred(ZZ_pX& f, long n);
BuildIrred_ZZ_pX(long n)175 inline ZZ_pX BuildIrred_ZZ_pX(long n)
176 { ZZ_pX x; BuildIrred(x, n); NTL_OPT_RETURN(ZZ_pX, x); }
177
178 // Build a monic irreducible poly of degree n.
179
180 void BuildRandomIrred(ZZ_pX& f, const ZZ_pX& g);
BuildRandomIrred(const ZZ_pX & g)181 inline ZZ_pX BuildRandomIrred(const ZZ_pX& g)
182 { ZZ_pX x; BuildRandomIrred(x, g); NTL_OPT_RETURN(ZZ_pX, x); }
183
184 // g is a monic irreducible polynomial.
185 // constructs a random monic irreducible polynomial f of the same degree.
186
187
188 long ComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
189
190 // f = F.f is assumed to be an "equal degree" polynomial
191 // h = X^p mod f
192 // the common degree of the irreducible factors of f is computed
193 // This routine is useful in counting points on elliptic curves
194
195 long ProbComputeDegree(const ZZ_pX& h, const ZZ_pXModulus& F);
196
197 // same as above, but uses a slightly faster probabilistic algorithm
198 // the return value may be 0 or may be too big, but for large p
199 // (relative to n), this happens with very low probability.
200
201
202
203 void TraceMap(ZZ_pX& w, const ZZ_pX& a, long d, const ZZ_pXModulus& F,
204 const ZZ_pX& b);
205
TraceMap(const ZZ_pX & a,long d,const ZZ_pXModulus & F,const ZZ_pX & b)206 inline ZZ_pX TraceMap(const ZZ_pX& a, long d, const ZZ_pXModulus& F,
207 const ZZ_pX& b)
208 { ZZ_pX x; TraceMap(x, a, d, F, b); return x; }
209
210 // w = a+a^q+...+^{q^{d-1}} mod f;
211 // it is assumed that d >= 0, and b = X^q mod f, q a power of p
212 // Space allocation can be controlled via ComposeBound (see <NTL/ZZ_pX.h>)
213
214
215
216 void PowerCompose(ZZ_pX& w, const ZZ_pX& a, long d, const ZZ_pXModulus& F);
PowerCompose(const ZZ_pX & a,long d,const ZZ_pXModulus & F)217 inline ZZ_pX PowerCompose(const ZZ_pX& a, long d, const ZZ_pXModulus& F)
218 { ZZ_pX x; PowerCompose(x, a, d, F); return x; }
219
220 // w = X^{q^d} mod f;
221 // it is assumed that d >= 0, and b = X^q mod f, q a power of p
222 // Space allocation can be controlled via ComposeBound (see <NTL/ZZ_pX.h>)
223
224
225 NTL_CLOSE_NNS
226
227 #endif
228