My Project
Loading...
Searching...
No Matches
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
30void 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
35void decompress (CFList& factors, ///< [in,out] a list of polys
36 const CFMap& N ///< [in] a map
37 );
38
39/// as above
40void decompress (CFFList& factors, ///< [in,out] a list of factors
41 const CFMap& N ///< [in] a map
42 );
43
44/// as above
45void 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
51void 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
62void 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()
73bool 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()
92mapDown (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()
108void 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()
120void
121appendMapDown (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
129void normalize (CFList& factors ///< [in,out] a list of polys
130 );
131
132/// as above
133void 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.
144CFList 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
156CFArray copy (const CFList& list ///< [in] a list of polys
157 );
158
159/// update @a index
160void 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
173int 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
179CFFList 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
188CFArray 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
200logarithmicDerivative (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
215int *
216computeBounds (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
224int *
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&)}
239getCoeffs (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&)}
251getCoeffs (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)}
265getCoeffs (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)}
283getCoeffs (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
294void
295writeInMatrix (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
305int substituteCheck (const CFList& L ///< [in] a list of univariate polys
306 );
307
308/// substitute x^d by x in F
309void
310subst (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
321reverseSubst (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
327void
328reverseSubst (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
338int
339substituteCheck (const CanonicalForm& F, ///<[in] a polynomial
340 const Variable& x ///<[in] some variable
341 );
342
343#endif
344/* FAC_FQ_BIVAR_UTIL_H */
345
This file provides a class to store information about finite fields and extensions thereof.
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Conversion to and from NTL.
#define swap(_i, _j)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
map polynomials
FILE * f
Definition: checklibs.c:9
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
factory's class for variables
Definition: variable.h:33
Variable alpha
Definition: facAbsBiFact.cc:51
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CFList & factors2
void append(CFList &factors1, const CFList &factors2)
append factors2 on factors1
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
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
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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 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...
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 normalize(CFList &factors)
normalize factors, i.e. make factors monic
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
CFArray copy(const CFList &list)
write elements of list into an array
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
int substituteCheck(const CFList &L)
checks if a substitution x^n->x is possible
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...
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 writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
STATIC_VAR int * multiplicity
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define info
Definition: libparse.cc:1256
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
#define Q
Definition: sirandom.c:26