facFqBivarUtil.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqBivarUtil.h
5  *
6  * This file provides utility functions for bivariate factorization
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 #ifndef FAC_FQ_BIVAR_UTIL_H
14 #define FAC_FQ_BIVAR_UTIL_H
15 
16 // #include "config.h"
17 
18 #include "cf_map.h"
19 #include "ExtensionInfo.h"
20 
21 #ifdef HAVE_NTL
22 #include "NTLconvert.h"
23 #endif
24 
25 #ifdef HAVE_FLINT
26 #include "FLINTconvert.h"
27 #endif
28 
29 /// append @a factors2 on @a factors1
30 void append (CFList& factors1, ///< [in,out] a list of polys
31  const CFList& factors2 ///< [in] a list of polys
32  );
33 
34 /// decompress a list of polys @a factors using the map @a N
35 void decompress (CFList& factors, ///< [in,out] a list of polys
36  const CFMap& N ///< [in] a map
37  );
38 
39 /// as above
40 void decompress (CFFList& factors, ///< [in,out] a list of factors
41  const CFMap& N ///< [in] a map
42  );
43 
44 /// as above
45 void decompress (CFAFList& factors, ///< [in,out] a list of factors
46  const CFMap& N ///< [in] a map
47  );
48 
49 /// first swap Variables in @a factors1 if necessary, then append @a factors2
50 /// and @a factors3 on @a factors1 and finally decompress @a factors1
51 void appendSwapDecompress (CFList& factors1, ///< [in,out] a list of polys
52  const CFList& factors2, ///< [in] a list of polys
53  const CFList& factors3, ///< [in] a list of polys
54  const bool swap1, ///< [in] indicates the need
55  ///< to swap
56  const bool swap2, ///< [in] indicates the need
57  ///< to swap
58  const CFMap& N ///< [in] a map
59  );
60 
61 /// swap Variables in @a factors, then decompress @a factors
62 void swapDecompress (CFList& factors, ///< [in,out] a list of polys
63  const bool swap, ///< [in] indicates the need to swap
64  const CFMap& N ///< [in] a map
65  );
66 
67 /// tests if F is not contained in a subfield defined by @a gamma (Fq case) or
68 /// @a k (GF case)
69 ///
70 /// @return @a isInExtension returns true if @a F is not contained in a subfield
71 /// defined by @a gamma (Fq case) or @a k (GF case), false else
72 /// @sa appendTestMapDown()
73 bool isInExtension (const CanonicalForm& F, ///< [in] a poly over
74  ///< F_p (alpha)=Fq or GF(p^l)
75  const CanonicalForm& gamma, ///< [in] a primitive element
76  ///< defining a subfield of
77  ///< Fq if we are not over some
78  ///< GF
79  const int k, ///< some int k such that k
80  ///< divides l if we are not
81  ///< over some Fq
82  const CanonicalForm& delta, ///< [in] image of gamma
83  CFList& source, ///< [in,out] list of preimages
84  CFList& dest ///< [in,out] list of images
85  );
86 
87 /// map a poly into a subfield of the current field, no testing is performed!
88 ///
89 /// @return @a mapDown returns @a F mapped into a subfield of the current field
90 /// @sa appendTestMapDown(), appendMapDown()
92 mapDown (const CanonicalForm& F, ///< [in] a poly
93  const ExtensionInfo& info, ///< [in] information about the sub- and
94  ///< current field
95  CFList& source, ///< [in,out] in case we are over some
96  ///< F_p (alpha) and want to map down into
97  ///< F_p (beta) source contains powers of
98  ///< the primitive element of F_p (alpha)
99  CFList& dest ///< [in,out] as source but contains
100  ///< the corresponding powers of the
101  ///< primitive element of F_p (beta)
102  );
103 
104 /// test if @a g is in a subfield of the current field, if so map it down and
105 /// append it to @a factors
106 ///
107 /// @sa mapDown(), isInExtension()
108 void appendTestMapDown (CFList& factors, ///< [in,out] a list of polys
109  const CanonicalForm& f, ///< [in] a poly
110  const ExtensionInfo& info,///< [in] information about
111  ///< extension
112  CFList& source, ///< [in,out] @sa mapDown()
113  CFList& dest ///< [in,out] @sa mapDown()
114  );
115 
116 /// map @a g down into a subfield of the current field and append it to @a
117 /// factors
118 ///
119 /// @sa mapDown(), appendTestMapDown()
120 void
121 appendMapDown (CFList& factors, ///< [in,out] a list of polys
122  const CanonicalForm& g, ///< [in] a poly
123  const ExtensionInfo& info,///< [in] information about extension
124  CFList& source, ///< [in,out] @sa mapDown()
125  CFList& dest ///< [in,out] @sa mapDown()
126  );
127 
128 /// normalize factors, i.e. make factors monic
129 void normalize (CFList& factors ///< [in,out] a list of polys
130  );
131 
132 /// as above
133 void normalize (CFFList& factors ///< [in,out] a list of factors
134  );
135 
136 /// extract a subset given by @a index of size @a s from @a elements, if there
137 /// is no subset we have not yet considered noSubset is set to true. @a index
138 /// encodes the next subset, e.g. if s= 3, elements= {a,b,c,d},
139 /// index= {1, 2, 4, 0}, then subset= {a,c,d}. @a index is of size
140 /// @a elements.size().
141 ///
142 /// @return @a subset returns a list of polys of length @a s if there is a
143 /// subset we have not yet considered.
144 CFList subset (int index [], ///< [in,out] an array encoding the next
145  ///< subset
146  const int& s, ///< [in] size of the subset
147  const CFArray& elements, ///< [in] an array of polys
148  bool& noSubset ///< [in,out] if there is no subset we
149  ///< have not yet considered @a noSubset
150  ///< is true
151  );
152 
153 /// write elements of @a list into an array
154 ///
155 /// @return an array of polys
156 CFArray copy (const CFList& list ///< [in] a list of polys
157  );
158 
159 /// update @a index
160 void indexUpdate (int index [], ///< [in,out] an array encoding a
161  ///< subset of size subsetSize
162  const int& subsetSize, ///< [in] size of the subset
163  const int& setSize, ///< [in] size of the given set
164  bool& noSubset ///< [in,out] if there is no subset we
165  ///< have not yet considered @a
166  ///< noSubset is true
167  );
168 
169 /// compute the sum of degrees in Variable(1) of elements in S
170 ///
171 /// @return @a subsetDegree returns the sum of degrees in Variable(1) of
172 /// elements in S
173 int subsetDegree (const CFList& S ///< [in] a list of polys
174  );
175 
176 /// determine multiplicity of the factors
177 ///
178 /// @return a list of factors of F with their multiplicity
179 CFFList multiplicity (CanonicalForm& F, ///< [in] a poly
180  const CFList& factors ///< [in] a list of factors of F
181  );
182 
183 /// compute the coefficients of the logarithmic derivative of G mod
184 /// Variable (2)^l over Fq
185 ///
186 /// @return an array of coefficients of the logarithmic derivative of G mod
187 /// Variable (2)^l
188 CFArray logarithmicDerivative (const CanonicalForm& F,///<[in] a bivariate poly
189  const CanonicalForm& G, ///<[in] a factor of F
190  int l, ///<[in] lifting precision
191  CanonicalForm& Q ///<[in,out] F/G
192  );
193 
194 /// compute the coefficients of the logarithmic derivative of G mod
195 /// Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL
196 ///
197 /// @return an array of coefficients of the logarithmic derivative of G mod
198 /// Variable (2)^l
199 CFArray
200 logarithmicDerivative (const CanonicalForm& F, ///< [in] bivariate poly
201  ///< truncated at Variable(2)^l
202  const CanonicalForm& G, ///< [in] a factor of F
203  int l, ///< [in] lifting precision
204  int oldL, ///< [in] old precision
205  const CanonicalForm& oldQ,///< [in] F/G mod
206  ///< Variable(2)^oldL
207  CanonicalForm& Q ///< [in, out] F/G
208  );
209 
210 /// compute bounds for logarithmic derivative as described in K. Belabas,
211 /// M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global
212 /// fields
213 ///
214 /// @return @a computeBounds returns bounds as described above
215 int *
216 computeBounds (const CanonicalForm& F,///< [in] compressed bivariate polynomial
217  int& n, ///< [in,out] length of output
218  bool& isIrreducible ///< [in,out] check if poly is irreducible
219  );
220 
221 /// as above just wrt to the other variable
222 ///
223 /// @return @a computeBounds returns bounds as described above
224 int *
226  (const CanonicalForm& F,///< [in] compressed bivariate polynomial
227  int& n, ///< [in,out] length of output
228  bool& isIrreducible ///< [in,out] check if poly is irreducible
229  );
230 
231 /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
232 /// a variable of level 1
233 ///
234 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
235 /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&),
236 /// getCoeffs (const CanonicalForm&, const int, const int, const int,
237 /// const Variable&, const CanonicalForm&, const mat_zz_p&)}
238 CFArray
239 getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over F_p
240  const int k ///< [in] some int
241  );
242 
243 /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
244 /// a variable of level 1
245 ///
246 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
247 /// @sa {getCoeffs (const CanonicalForm&, const int),
248 /// getCoeffs (const CanonicalForm&, const int, const int, const int,
249 /// const Variable&, const CanonicalForm&, const mat_zz_p&)}
250 CFArray
251 getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over
252  ///< F_p(alpha)
253  const int k, ///< [in] some int
254  const Variable& alpha ///< [in] algebraic variable
255  );
256 
257 #ifdef HAVE_NTL
258 /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
259 /// a variable of level 1
260 ///
261 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
262 /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
263 /// getCoeffs (const CanonicalForm&, const int)}
264 CFArray
265 getCoeffs (const CanonicalForm& F, ///< [in] compressed bivariate poly
266  const int k, ///< [in] some int
267  const int l, ///< [in] precision
268  const int degMipo, ///< [in] degree of minimal poly
269  const Variable& alpha, ///< [in] algebraic variable
270  const CanonicalForm& evaluation,///< [in] evaluation point
271  const mat_zz_p& M ///< [in] bases change matrix
272  );
273 #endif
274 
275 #ifdef HAVE_FLINT
276 /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
277 /// a variable of level 1
278 ///
279 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
280 /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
281 /// getCoeffs (const CanonicalForm&, const int)}
282 CFArray
283 getCoeffs (const CanonicalForm& F, ///< [in] compressed bivariate poly
284  const int k, ///< [in] some int
285  const int l, ///< [in] precision
286  const int degMipo, ///< [in] degree of minimal poly
287  const Variable& alpha, ///< [in] algebraic variable
288  const CanonicalForm& evaluation,///< [in] evaluation point
289  const nmod_mat_t M ///< [in] bases change matrix
290  );
291 #endif
292 
293 /// write A into M starting at row startIndex
294 void
295 writeInMatrix (CFMatrix& M, ///< [in,out] some matrix
296  const CFArray& A, ///< [in] array of polys
297  const int column, ///< [in] column in which A is written
298  const int startIndex///< [in] row in which to start
299  );
300 
301 /// checks if a substitution x^n->x is possible
302 ///
303 /// @return an integer n > 1, if a substitution described as above is possible
304 /// else n <= 1
305 int substituteCheck (const CFList& L ///< [in] a list of univariate polys
306  );
307 
308 /// substitute x^d by x in F
309 void
310 subst (const CanonicalForm& F, ///< [in] a polynomial
311  CanonicalForm& A, ///< [in,out] returns F with x^d replaced by x
312  const int d, ///< d > 1 such that a substitution x^d -> x
313  ///< [in] is possible
314  const Variable& x ///< [in] a Variable
315  );
316 
317 /// reverse a substitution x^d->x
318 ///
319 /// @return a poly with x replaced by x^d
321 reverseSubst (const CanonicalForm& F, ///< [in] a poly
322  const int d, ///< [in] an integer > 0
323  const Variable& x ///< [in] a Variable
324  );
325 
326 /// reverse a substitution x^d->x
327 void
328 reverseSubst (CFList& L, ///< [in,out] a list of polys, returns the
329  ///< given list with x replaced by x^d
330  const int d, ///< [in] an integer > 0
331  const Variable& x ///< [in] a Variable
332  );
333 
334 /// check if a substitution x^n->x is possible
335 ///
336 /// @return an integer n > 1, if a substitution described as above is possible
337 /// else n <= 1
338 int
339 substituteCheck (const CanonicalForm& F, ///<[in] a polynomial
340  const Variable& x ///<[in] some variable
341  );
342 
343 #endif
344 /* FAC_FQ_BIVAR_UTIL_H */
345 
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
const CanonicalForm int s
Definition: facAbsFact.cc:55
Conversion to and from NTL.
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int substituteCheck(const CFList &L)
checks if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
factory's class for variables
Definition: variable.h:32
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
factory's main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
Variable alpha
Definition: facAbsBiFact.cc:52
#define Q
Definition: sirandom.c:25
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
const CFList & factors2
static TreeM * G
Definition: janet.cc:38
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
map polynomials
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
#define M
Definition: sirandom.c:24
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
#define A
Definition: sirandom.c:23
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
#define info
Definition: libparse.cc:1254
FILE * f
Definition: checklibs.c:7
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors ...
void append(CFList &factors1, const CFList &factors2)
append factors2 on factors1
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:597
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq ...
class CFMap
Definition: cf_map.h:84
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
CFFList multiplicity(CanonicalForm &F, const CFList &factors)
determine multiplicity of the factors
#define swap(_i, _j)
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
CFArray copy(const CFList &list)
write elements of list into an array
Variable x
Definition: cfModGcd.cc:4023
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
CanonicalForm mapDown(const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
map a poly into a subfield of the current field, no testing is performed!
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
int l
Definition: cfEzgcd.cc:94
This file provides a class to store information about finite fields and extensions thereof...