source: git/factory/facHensel.h @ 6db552

spielwiese
Last change on this file since 6db552 was 6db552, checked in by Hans Schoenemann <hannes@…>, 13 years ago
removed include-wrapppers git-svn-id: file:///usr/local/Singular/svn/trunk@13772 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 18.7 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facHensel.h
5 *
6 * This file defines functions for Hensel lifting and modular multiplication.
7 *
8 * ABSTRACT: function are used for bi- and multivariate factorization over
9 * finite fields
10 *
11 * @author Martin Lee
12 *
13 * @internal @version \$Id$
14 *
15 **/
16/*****************************************************************************/
17
18#ifndef FAC_HENSEL_H
19#define FAC_HENSEL_H
20
21#include <config.h>
22#include "assert.h"
23#include "debug.h"
24#include "timing.h"
25
26#include "canonicalform.h"
27#include "cf_iter.h"
28#include "templates/ftmpl_functions.h"
29#include "algext.h"
30
31CanonicalForm mul (const CanonicalForm& F, const CanonicalForm& G);
32CanonicalForm mulMod3 (const CanonicalForm& F, const CanonicalForm& G, const CFList& MOD);
33/// multiplication of univariate polys over a finite field using NTL, if we are
34/// in GF factory's default multiplication is used.
35///
36/// @return @a mulNTL returns F*G
37static inline
38CanonicalForm
39mulNTL (const CanonicalForm& F, ///< [in] a univariate poly
40        const CanonicalForm& G  ///< [in] a univariate poly
41       );
42
43/// mod of univariate polys over a finite field using NTL, if we are
44/// in GF factory's default mod is used.
45///
46/// @return @a modNTL returns F mod G
47static inline
48CanonicalForm
49modNTL (const CanonicalForm& F, ///< [in] a univariate poly
50        const CanonicalForm& G  ///< [in] a univariate poly
51       );
52
53/// division of univariate polys over a finite field using NTL, if we are
54/// in GF factory's default division is used.
55///
56/// @return @a divNTL returns F/G
57static inline
58CanonicalForm
59divNTL (const CanonicalForm& F, ///< [in] a univariate poly
60        const CanonicalForm& G  ///< [in] a univariate poly
61       );
62
63/*/// division with remainder of univariate polys over a finite field using NTL,
64/// if we are in GF factory's default division with remainder is used.
65static inline
66void
67divremNTL (const CanonicalForm& F, ///< [in] a univariate poly
68           const CanonicalForm& G, ///< [in] a univariate poly
69           CanonicalForm& Q,       ///< [in,out] dividend
70           CanonicalForm& R        ///< [in,out] remainder
71          );*/
72
73/// splits @a F into degree (F, x)/m polynomials each of degree less than @a m
74/// in @a x.
75///
76/// @return @a split returns a list of polynomials of degree less than @a m in
77///         @a x. If degree (F, x) <= 0, F is returned.
78/// @sa divrem32(), divrem21()
79static inline
80CFList split (const CanonicalForm& F, ///< [in] some poly
81              const int m,            ///< [in] some int
82              const Variable& x       ///< [in] some Variable
83             );
84
85/// division with remainder of @a F by
86/// @a G wrt Variable (1) modulo @a M.
87///
88/// @sa divrem(), divrem21(), divrem2()
89static inline
90void divrem32 (const CanonicalForm& F, ///< [in] poly, s.t. 3*(degree (G, 1)/2)>
91                                       ///< degree (F, 1)
92               const CanonicalForm& G, ///< [in] some poly
93               CanonicalForm& Q,       ///< [in,out] dividend
94               CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
95                                       ///< degree (G, 1)
96               const CFList& M         ///< [in] only contains powers of
97                                       ///< Variables of level higher than 1
98              );
99
100/// division with remainder of @a F by
101/// @a G wrt Variable (1) modulo @a M.
102///
103/// @sa divrem(), divrem32(), divrem2()
104static inline
105void divrem21 (const CanonicalForm& F, ///< [in] poly, s.t. 2*degree (G, 1) >
106                                       ///< degree (F, 1)
107               const CanonicalForm& G, ///< [in] some poly
108               CanonicalForm& Q,       ///< [in,out] dividend
109               CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
110                                       ///< degree (G, 1)
111               const CFList& M         ///< [in] only contains powers of
112                                       ///< Variables of level higher than 1
113              );
114
115/// division with remainder of @a F by
116/// @a G wrt Variable (1) modulo @a M.
117///
118/// @return @a Q returns the dividend, @a R returns the remainder.
119/// @sa divrem()
120void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
121              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
122              CanonicalForm& Q,       ///< [in,out] dividend
123              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
124                                      ///< degree (G, 1)
125              const CanonicalForm& M  ///< [in] power of Variable (2)
126             );
127
128/// division with remainder of @a F by
129/// @a G wrt Variable (1) modulo @a MOD.
130///
131/// @sa divrem2()
132void divrem (
133           const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
134           const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
135           CanonicalForm& Q,       ///< [in,out] dividend
136           CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
137                                   ///< degree (G, 1)
138           const CFList& MOD       ///< [in] only contains powers of
139                                   ///< Variables of level higher than 1
140            );
141
142/// reduce @a F modulo elements in @a M.
143///
144/// @return @a mod returns @a F modulo @a M
145CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
146                   const CFList& M         ///< [in] list containing only
147                                           ///< univariate polynomials
148                  );
149
150/// Karatsuba style modular multiplication for bivariate polynomials.
151///
152/// @return @a mulMod2 returns @a A * @a B mod @a M.
153CanonicalForm
154mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
155         const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
156         const CanonicalForm& M  ///< [in] power of Variable (2)
157        );
158
159/// Karatsuba style modular multiplication for multivariate polynomials.
160///
161/// @return @a mulMod2 returns @a A * @a B mod @a MOD.
162CanonicalForm
163mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
164        const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
165        const CFList& MOD       ///< [in] only contains powers of
166                                ///< Variables of level higher than 1
167       );
168
169/// product of all elements in @a L modulo @a M via divide-and-conquer.
170///
171/// @return @a prodMod returns product of all elements in @a L modulo @a M.
172CanonicalForm
173prodMod (const CFList& L,       ///< [in] contains only bivariate, compressed
174                                ///< polynomials
175         const CanonicalForm& M ///< [in] power of Variable (2)
176        );
177
178/// product of all elements in @a L modulo @a M via divide-and-conquer.
179///
180/// @return @a prodMod returns product of all elements in @a L modulo @a M.
181CanonicalForm
182prodMod (const CFList& L, ///< [in] contains multivariate, compressed
183                          ///< polynomials
184         const CFList& M  ///< [in] contains only powers of Variables
185        );
186
187/// sort a list of polynomials by their degree in @a x.
188///
189void sortList (CFList& list,     ///< [in, out] list of polys, sorted list
190               const Variable& x ///< [in] some Variable
191              );
192
193/// solve the univariate diophantine equation
194/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \f$.
195/// Where \f$ F= \prod_{i= 1}^{r} {g_{i}} \f$ and \f$ F \f$ is squarefree
196/// the \f$ \delta_{i} \f$ have degree less than the degree of \f$ g_{i} \f$.
197///
198/// @return @a diophantine returns a list of polynomials \f$ \delta_{i} \f$ as
199/// specified above
200/// @sa biDiophantine(), multiRecDiophantine()
201static inline
202CFList diophantine (const CanonicalForm& F, ///< [in] compressed, bivariate
203                                            ///< polynomial
204                    const CFList& factors   ///< [in] a list of factors, as
205                                            ///< specified above, including
206                                            ///< LC (F, Variable (1)) as first
207                                            ///< element
208                   );
209
210/// Hensel lift from univariate to bivariate.
211///
212/// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
213void
214henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
215              CFList& factors,        ///< [in, out] monic univariate factors of
216                                      ///< F, including leading coefficient as
217                                      ///< first element. Returns monic lifted
218                                      ///< factors without the leading
219                                      ///< coefficient
220              int l,                  ///< [in] lifting precision
221              CFArray& Pi,            ///< [in,out] stores intermediate results
222              CFList& diophant,       ///< [in,out] result of diophantine()
223              CFMatrix& M             ///< [in,out] stores intermediate results
224             );
225
226/// resume Hensel lift from univariate to bivariate. Assumes factors are lifted
227/// to precision Variable (2)^start and lifts them to precision Variable (2)^end
228///
229/// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift()
230void
231henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
232                    CFList& factors,        ///< [in,out] monic factors of F,
233                                            ///< lifted to precision start,
234                                            ///< including leading coefficient
235                                            ///< as first element. Returns monic
236                                            ///< lifted factors without the
237                                            ///< leading coefficient
238                    int start,              ///< [in] starting precision
239                    int end,                ///< [in] end precision
240                    CFArray& Pi,            ///< [in,out] stores intermediate
241                                            ///< results
242                    const CFList& diophant, ///< [in] result of diophantine
243                    CFMatrix& M             ///< [in,out] stores intermediate
244                                            ///< results
245                   );
246
247/// solves the bivariate polynomial diophantine equation
248/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ y^{d} \f$,
249/// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ y^{d}\f$ and
250/// \f$ F \in K[x][y]\f$ is squarefree, the \f$ \delta_{i} \f$ have degree less
251/// than the degree of \f$ g_{i} \f$ in x.
252///
253/// @return @a biDiophantine returns a list of polynomials \f$ \delta_{i} \f$ as
254///         specified above
255/// @sa diophantine(), multiRecDiophantine()
256static inline
257CFList
258biDiophantine (const CanonicalForm& F, ///< [in] compressed, bivariate poly
259               const CFList& factors,  ///< [in] list of monic bivariate factors
260                                       ///< including LC (F, Variable (1)) as
261                                       ///< first element
262               const int d             ///< [in] precision
263              );
264
265/// solve the multivariate polynomial diophantine equation
266/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ <M,F.mvar()^{d}>\f$,
267/// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ <M,F.mvar()^{d}>\f$ and
268/// \f$ F \in K[x][x_1,\ldots , x_n]\f$ is squarefree, the \f$ \delta_{i} \f$
269/// have degree less than the degree of \f$ g_{i} \f$ in x.
270///
271/// @return @a multiDiophantine returns a list of polynomials \f$ \delta_{i} \f$
272///         as specified above
273/// @sa diophantine(), biDiophantine()
274static inline
275CFList
276multiRecDiophantine (
277               const CanonicalForm& F,   ///< [in] compressed,
278                                         ///< multivariate polynomial
279               const CFList& factors,    ///< [in] list of monic factors
280                                         ///< including LC (F, Variable (1)) as
281                                         ///< first element
282               const CFList& recResult, ///< [in] result of above equation
283                                         ///< modulo M
284               const CFList& M,          ///< [in] a list of powers of Variables
285                                         ///< of level higher than 1
286               const int d               ///< [in] precision
287                    );
288
289/// Hensel lifting from bivariate to trivariate.
290///
291/// @return @a henselLift23 returns a list of polynomials lifted to precision
292///          Variable (3)^l[1]
293/// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
294CFList
295henselLift23 (const CFList& eval,    ///< [in] contains compressed, bivariate
296                                     ///< as first element and trivariate one as
297                                     ///< second element
298              const CFList& factors, ///< [in] monic bivariate factors,
299                                     ///< including leading coefficient
300                                     ///< as first element.
301              const int* l,          ///< [in] l[0]: precision of bivariate
302                                     ///< lifting, l[1] as above
303              CFList& diophant,      ///< [in,out] returns the result of
304                                     ///< biDiophantine()
305              CFArray& Pi,           ///< [in,out] stores intermediate results
306              CFMatrix& M            ///< [in,out] stores intermediate results
307             );
308
309/// resume Hensel lifting.
310///
311/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
312void
313henselLiftResume (
314              const CanonicalForm& F, ///< [in] compressed, multivariate poly
315              CFList& factors,        ///< [in,out] monic multivariate factors
316                                      ///< lifted to precision F.mvar()^start,
317                                      ///< including leading coefficient
318                                      ///< as first element. Returns factors
319                                      ///< lifted to precision F.mvar()^end
320              int start,              ///< [in] starting precision
321              int end,                ///< [in] end precision
322              CFArray& Pi,            ///< [in,out] stores intermediate results
323              const CFList& diophant, ///< [in] result of multiRecDiophantine()
324              CFMatrix& M,            ///< [in, out] stores intermediate results
325              const CFList& MOD       ///< [in] a list of powers of Variables
326                                      ///< of level higher than 1
327                 );
328
329/// Hensel lifting
330///
331/// @return @a henselLift returns a list of polynomials lifted to
332///          precision F.getLast().mvar()^l_new
333/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
334CFList
335henselLift (const CFList& F,       ///< [in] two compressed, multivariate
336                                   ///< polys F and G
337            const CFList& factors, ///< [in] monic multivariate factors
338                                   ///< including leading coefficient
339                                   ///< as first element.
340            const CFList& MOD,     ///< [in] a list of powers of Variables
341                                   ///< of level higher than 1
342            CFList& diophant,      ///< [in,out] result of multiRecDiophantine()
343            CFArray& Pi,           ///< [in,out] stores intermediate results
344            CFMatrix& M,           ///< [in,out] stores intermediate results
345            const int lOld,       ///< [in] lifting precision of F.mvar()
346            const int lNew        ///< [in] lifting precision of G.mvar()
347           );
348
349/// Hensel lifting from bivariate to multivariate
350///
351/// @return @a henselLift returns a list of lifted factors
352/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
353CFList
354henselLift (const CFList& eval,    ///< [in] a list of polynomials the last
355                                   ///< element is a compressed multivariate
356                                   ///< poly, last but one element equals the
357                                   ///< last elements modulo its main variable
358                                   ///< and so on. The first element is a
359                                   ///< compressed bivariate poly.
360            const CFList& factors, ///< [in] bivariate factors, including
361                                   ///< leading coefficient
362            const int* l,          ///< [in] lifting bounds
363            const int lLength     ///< [in] length of l
364           );
365
366/// two factor Hensel lifting from univariate to bivariate, factors need not to
367/// be monic
368void
369henselLift122 (const CanonicalForm& F,///< [in] a bivariate poly
370               CFList& factors,       ///< [in, out] a list of univariate polys
371                                      ///< lifted factors
372               int l,                 ///< [in] lift bound
373               CFArray& Pi,           ///< [in, out] stores intermediate results
374               CFList& diophant,      ///< [in, out] result of diophantine
375               CFMatrix& M,           ///< [in, out] stores intermediate results
376               const CFArray& LCs,    ///< [in] leading coefficients
377               bool sort              ///< [in] if true factors are sorted by
378                                      ///< their degree
379              );
380
381/// two factor Hensel lifting from bivariate to multivariate, factors need not
382/// to be monic
383///
384/// @return @a henselLift122 returns a list of lifted factors
385CFList
386henselLift2 (const CFList& eval,   ///< [in] a list of polynomials the last
387                                   ///< element is a compressed multivariate
388                                   ///< poly, last but one element equals the
389                                   ///< last elements modulo its main variable
390                                   ///< and so on. The first element is a
391                                   ///< compressed bivariate poly.
392             const CFList& factors,///< [in] bivariate factors
393             int* l,               ///< [in] lift bounds
394             const int lLength,    ///< [in] length of l
395             bool sort,            ///< [in] if true factors are sorted by
396                                   ///< their degree in Variable(1)
397             const CFList& LCs1,   ///< [in] a list of evaluated LC of first
398                                   ///< factor
399             const CFList& LCs2,   ///< [in] a list of evaluated LC of second
400                                   ///< factor
401             const CFArray& Pi,    ///< [in] intermediate result
402             const CFList& diophant///< [in] result of diophantine
403            );
404
405#endif
406/* FAC_HENSEL_H */
407
Note: See TracBrowser for help on using the repository browser.