source: git/factory/facHensel.h @ c9b1d66

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