source: git/factory/facFqFactorize.h @ c1b9927

fieker-DuValspielwiese
Last change on this file since c1b9927 was c1b9927, checked in by Hans Schoenemann <hannes@…>, 13 years ago
- removed some unsed variables - never put static inline routine without a body in a .h file git-svn-id: file:///usr/local/Singular/svn/trunk@14265 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 18.9 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqFactorize.h
5 *
6 * This file provides functions for factorizing a multivariate polynomial over
7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
8 *
9 * ABSTRACT: So far factor recombination is done naive!
10 *
11 * @author Martin Lee
12 *
13 * @internal @version \$Id$
14 *
15 **/
16/*****************************************************************************/
17
18#ifndef FAC_FQ_FACTORIZE_H
19#define FAC_FQ_FACTORIZE_H
20
21#include <config.h>
22
23#include "facFqBivar.h"
24#include "DegreePattern.h"
25#include "ExtensionInfo.h"
26#include "cf_util.h"
27#include "facFqSquarefree.h"
28#include "facFqBivarUtil.h"
29
30/// Factorization over a finite field
31///
32/// @return @a multiFactorize returns a factorization of F
33/// @sa biFactorize(), extFactorize()
34CFList
35multiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
36                const ExtensionInfo& info  ///< [in] info about extension
37               );
38
39/// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
40///
41/// @return @a FpSqrfFactorize returns a list of monic factors, the first
42///         element is the leading coefficient.
43/// @sa FqSqrfFactorize(), GFSqrfFactorize()
44inline
45CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
46                       )
47{
48  if (getNumVars (F) == 2)
49    return FpBiSqrfFactorize (F);
50  ExtensionInfo info= ExtensionInfo (false);
51  CFList result= multiFactorize (F, info);
52  result.insert (Lc(F));
53  return result;
54}
55
56/// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
57///
58/// @return @a FqSqrfFactorize returns a list of monic factors, the first
59///         element is the leading coefficient.
60/// @sa FpSqrfFactorize(), GFSqrfFactorize()
61inline
62CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
63                        const Variable& alpha    ///< [in] algebraic variable
64                       )
65{
66  if (getNumVars (F) == 2)
67    return FqBiSqrfFactorize (F, alpha);
68  ExtensionInfo info= ExtensionInfo (alpha, false);
69  CFList result= multiFactorize (F, info);
70  result.insert (Lc(F));
71  return result;
72}
73
74/// factorize a squarefree multivariate polynomial over GF
75///
76/// @return @a GFSqrfFactorize returns a list of monic factors, the first
77///         element is the leading coefficient.
78/// @sa FpSqrfFactorize(), FqSqrfFactorize()
79inline
80CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
81                       )
82{
83  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
84          "GF as base field expected");
85  if (getNumVars (F) == 2)
86    return GFBiSqrfFactorize (F);
87  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
88  CFList result= multiFactorize (F, info);
89  result.insert (Lc(F));
90  return result;
91}
92
93/// factorize a multivariate polynomial over \f$ F_{p} \f$
94///
95/// @return @a FpFactorize returns a list of monic factors with
96///         multiplicity, the first element is the leading coefficient.
97/// @sa FqFactorize(), GFFactorize()
98inline
99CFFList FpFactorize (const CanonicalForm& F ///< [in] a multivariate poly
100                    )
101{
102  if (getNumVars (F) == 2)
103    return FpBiFactorize (F);
104  ExtensionInfo info= ExtensionInfo (false);
105  Variable a= Variable (1);
106  CanonicalForm LcF= Lc (F);
107  CanonicalForm pthRoot, A;
108  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, a);
109  CFList buf, bufRoot;
110  CFFList result, resultRoot;
111  int p= getCharacteristic();
112  int l;
113  if (degree (pthRoot) > 0)
114  {
115    pthRoot= maxpthRoot (pthRoot, p, l);
116    result= FpFactorize (pthRoot);
117    result.removeFirst();
118    for (CFFListIterator i= result; i.hasItem(); i++)
119      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
120    result.insert (CFFactor (LcF, 1));
121    return result;
122  }
123  else
124  {
125    buf= multiFactorize (sqrfP, info);
126    A= F/LcF;
127    result= multiplicity (A, buf);
128  }
129  if (degree (A) > 0)
130  {
131    resultRoot= FpFactorize (A);
132    resultRoot.removeFirst();
133    result= Union (result, resultRoot);
134  }
135  result.insert (CFFactor (LcF, 1));
136  return result;
137}
138
139/// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
140///
141/// @return @a FqFactorize returns a list of monic factors with
142///         multiplicity, the first element is the leading coefficient.
143/// @sa FpFactorize(), GFFactorize()
144inline
145CFFList FqFactorize (const CanonicalForm& F, ///< [in] a multivariate poly
146                     const Variable& alpha   ///< [in] algebraic variable
147                    )
148{
149  if (getNumVars (F) == 2)
150    return FqBiFactorize (F, alpha);
151  ExtensionInfo info= ExtensionInfo (alpha, false);
152  CanonicalForm LcF= Lc (F);
153  CanonicalForm pthRoot, A;
154  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
155  CFList buf, bufRoot;
156  CFFList result, resultRoot;
157  int p= getCharacteristic();
158  int q= ipower (p, degree (getMipo (alpha)));
159  int l;
160  if (degree (pthRoot) > 0)
161  {
162    pthRoot= maxpthRoot (pthRoot, q, l);
163    result= FqFactorize (pthRoot, alpha);
164    result.removeFirst();
165    for (CFFListIterator i= result; i.hasItem(); i++)
166      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
167    result.insert (CFFactor (LcF, 1));
168    return result;
169  }
170  else
171  {
172    buf= multiFactorize (sqrfP, info);
173    A= F/LcF;
174    result= multiplicity (A, buf);
175  }
176  if (degree (A) > 0)
177  {
178    resultRoot= FqFactorize (A, alpha);
179    resultRoot.removeFirst();
180    result= Union (result, resultRoot);
181  }
182  result.insert (CFFactor (LcF, 1));
183  return result;
184}
185
186/// factorize a multivariate polynomial over GF
187///
188/// @return @a GFFactorize returns a list of monic factors with
189///         multiplicity, the first element is the leading coefficient.
190/// @sa FpFactorize(), FqFactorize()
191inline
192CFFList GFFactorize (const CanonicalForm& F ///< [in] a multivariate poly
193                    )
194{
195  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
196          "GF as base field expected");
197  if (getNumVars (F) == 2)
198    return GFBiFactorize (F);
199  Variable a= Variable (1);
200  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
201  CanonicalForm LcF= Lc (F);
202  CanonicalForm pthRoot, A;
203  CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, a);
204  CFList buf;
205  CFFList result, resultRoot;
206  int p= getCharacteristic();
207  int q= ipower (p, getGFDegree());
208  int l;
209  if (degree (pthRoot) > 0)
210  {
211    pthRoot= maxpthRoot (pthRoot, q, l);
212    result= GFFactorize (pthRoot);
213    result.removeFirst();
214    for (CFFListIterator i= result; i.hasItem(); i++)
215      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
216    result.insert (CFFactor (LcF, 1));
217    return result;
218  }
219  else
220  {
221    buf= multiFactorize (sqrfP, info);
222    A= F/LcF;
223    result= multiplicity (A, buf);
224  }
225  if (degree (A) > 0)
226  {
227    resultRoot= GFFactorize (A);
228    resultRoot.removeFirst();
229    result= Union (result, resultRoot);
230  }
231  result.insert (CFFactor (LcF, 1));
232  return result;
233}
234
235/// naive factor recombination for bivariate factorization.
236/// Uses precomputed data to exclude combinations that are not possible.
237///
238/// @return @a monicFactorRecombi returns a list of factors of F, that are
239///         monic wrt Variable (1).
240/// @sa extFactorRecombination(), factorRecombination(), biFactorizer()
241CFList
242monicFactorRecombi (
243                  const CFList& factors,    ///< [in] list of lifted factors
244                                            ///< that are monic wrt Variable (1)
245                  const CanonicalForm& F,   ///< [in] bivariate poly
246                  const CanonicalForm& M,   ///< [in] Variable (2)^liftBound
247                  const DegreePattern& degs ///< [in] degree pattern
248                   );
249
250/// detects factors of @a F at stage @a deg of Hensel lifting.
251/// No combinations of more than one factor are tested. Lift bound and possible
252/// degree pattern are updated.
253///
254/// @return @a earlyMonicFactorDetect returns a list of factors of F (possibly
255///         incomplete) that are monic wrt Variable (1)
256/// @sa monicFactorRecombi(), earlyFactorDetection(), monicFactorDetect(),
257///     biFactorizer()
258CFList
259earlyMonicFactorDetect (
260           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
261                                   ///< poly divided by detected factors in case
262                                   ///< of success
263           CFList& factors,        ///< [in,out] list of factors lifted up to
264                                   ///< @a deg, returns a list of factors
265                                   ///< without detected factors
266           int& adaptedLiftBound,  ///< [in,out] adapted lift bound
267           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
268                                   ///< whenever we find a factor
269           bool& success,          ///< [in,out] indicating success
270           int deg,                ///< [in] stage of Hensel lifting
271           const int bound         ///< [in] degree (A, 2) + 1 +
272                                   ///< degree (LC (A, 1), 2), where A is the
273                                   ///< multivariate polynomial corresponding to
274                                   ///< F.
275                       );
276
277/// Bivariate factorization. In contrast to biFactorize() the factors returned
278/// are monic wrt Variable (1), if @a F is not irreducible. And no factorization
279/// wrt Variable (2) are performed. However,
280///
281/// @return @a biFactorizer returns a list of factors that are monic wrt
282///         Variable (1), if @a F is irreducible @a F is returned
283/// @sa multiFactorize(), biFactorize()
284CFList biFactorizer (const CanonicalForm& F,   ///< [in] a bivariate poly
285                     const Variable& alpha,    ///< [in] algebraic variable
286                     CanonicalForm& bivarEval, ///< [in,out] a valid evaluation
287                                               ///< point
288                     int& liftBound            ///< [in,out] lift bound, may be
289                                               ///< adapted during Hensel
290                                               ///< lifting
291                    );
292
293/// Naive factor recombination for multivariate factorization over an extension
294/// of the initial field. No precomputed is used to exclude combinations.
295///
296/// @return @a extFactorRecombination returns a list of factors of @a F, whose
297///         shift to zero is reversed.
298/// @sa factorRecombination()
299CFList
300extFactorRecombination (
301                 const CFList& factors,     ///< [in] list of lifted factors
302                                            ///< that are monic wrt Variable (1)
303                 const CanonicalForm& F,    ///< [in] poly to be factored
304                 const CFList& M,           ///< [in] a list of powers of
305                                            ///< Variables
306                 const ExtensionInfo& info, ///< [in] info about extension
307                 const CFList& evaluation   ///< [in] evaluation point
308                       );
309
310/// Naive factor recombination for multivariate factorization.
311/// No precomputed is used to exclude combinations.
312///
313/// @return @a factorRecombination returns a list of factors of @a F
314/// @sa extFactorRecombination()
315CFList
316factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
317                     const CFList& factors, ///< [in] list of lifted factors
318                                            ///< that are monic wrt Variable (1)
319                     const CFList& M        ///< [in] a list of powers of
320                                            ///< Variables
321                    );
322
323/// Lift bound adaption. Essentially an early factor detection but only the lift
324/// bound is adapted.
325///
326/// @return @a liftBoundAdaption returns an adapted lift bound.
327/// @sa earlyFactorDetect(), earlyFactorDetection()
328int
329liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
330                   const CFList& factors,  ///< [in] list of list of lifted
331                                           ///< factors that are monic wrt
332                                           ///< Variable (1)
333                   bool& success,          ///< [in,out] indicates that no
334                                           ///< further lifting is necessary
335                   const int deg,          ///< [in] stage of Hensel lifting
336                   const CFList& MOD,      ///< [in] a list of powers of
337                                           ///< Variables
338                   const int bound         ///< [in] initial lift bound
339                  );
340
341/// Lift bound adaption over an extension of the initial field. Essentially an
342///early factor detection but only the lift bound is adapted.
343///
344/// @return @a liftBoundAdaption returns an adapted lift bound.
345/// @sa earlyFactorDetect(), earlyFactorDetection()
346int
347extLiftBoundAdaption (
348            const CanonicalForm& F,    ///< [in] a poly
349            const CFList& factors,     ///< [in] list of list of lifted
350                                       ///< factors that are monic wrt
351            bool& success,             ///< [in,out] indicates that no further
352                                       ///< lifting is necessary
353            const ExtensionInfo& info, ///< [in] info about extension
354            const CFList& eval,        ///< [in] evaluation point
355            const int deg,             ///< [in] stage of Hensel lifting
356            const CFList& MOD,         ///< [in] a list of powers of
357                                       ///< Variables
358            const int bound            ///< [in] initial lift bound
359                     );
360
361/// detects factors of @a F at stage @a deg of Hensel lifting.
362/// No combinations of more than one factor are tested. Lift bound is adapted.
363///
364/// @return @a earlyFactorDetect returns a list of factors of F (possibly
365///         incomplete), in case of success. Otherwise an empty list.
366/// @sa factorRecombination(), extEarlyFactorDetect()
367CFList
368earlyFactorDetect (
369                CanonicalForm& F,      ///< [in,out] poly to be factored,
370                                       ///< returns poly divided by detected
371                                       ///< factors in case of success
372                CFList& factors,       ///< [in,out] list of factors lifted up
373                                       ///< to @a deg, returns a list of factors
374                                       ///< without detected factors
375                int& adaptedLiftBound, ///< [in,out] adapted lift bound
376                bool& success,         ///< [in,out] indicating success
377                const int deg,         ///< [in] stage of Hensel lifting
378                const CFList& MOD,     ///< [in] a list of powers of
379                                       ///< Variables
380                const int bound        ///< [in] initial lift bound
381                  );
382
383/// detects factors of @a F at stage @a deg of Hensel lifting.
384/// No combinations of more than one factor are tested. Lift bound is adapted.
385///
386/// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
387///         incomplete), whose shift to zero is reversed, in case of success.
388///         Otherwise an empty list.
389/// @sa factorRecombination(), earlyFactorDetection()
390CFList
391extEarlyFactorDetect (
392            CanonicalForm& F,          ///< [in,out] poly to be factored,
393                                       ///< returns poly divided by detected
394                                       ///< factors in case of success
395            CFList& factors,           ///< [in,out] list of factors lifted up
396                                       ///< to @a deg, returns a list of factors
397                                       ///< without detected factors
398            int& adaptedLiftBound,     ///< [in,out] adapted lift bound
399            bool& success,             ///< [in,out] indicating succes
400            const ExtensionInfo& info, ///< [in] info about extension
401            const CFList& eval,        ///< [in] evaluation point
402            const int deg,             ///< [in] stage of Hensel lifting
403            const CFList& MOD,         ///< [in] a list of powers of Variables
404            const int bound            ///< [in] initial lift bound
405                     );
406
407/// evaluation point search for multivariate factorization,
408/// looks for a (F.level() - 1)-tuple such that the resulting univariate
409/// polynomial has main variable F.mvar(), is squarefree and its degree
410/// coincides with degree(F) and the bivariate one is primitive wrt.
411/// Variable(1), fails if there are no valid evaluation points, eval contains
412/// the intermediate evaluated polynomials.
413///
414/// @return @a evalPoints returns an evaluation point, which is valid if and
415///         only if fail == false.
416CFList
417evalPoints (const CanonicalForm& F,  ///< [in] a compressed poly
418            CFList & eval,           ///< [in,out] an empty list, returns @a F
419                                     ///< successive evaluated
420            const Variable& alpha,   ///< [in] algebraic variable
421            CFList& list,            ///< [in,out] a list of points already
422                                     ///< considered, a point is encoded as a
423                                     ///< poly of degree F.level()-1 in
424                                     ///< Variable(1)
425            const bool& GF,          ///< [in] GF?
426            bool& fail               ///< [in,out] indicates failure
427           );
428
429/// hensel Lifting and early factor detection
430///
431/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
432///         factors without factors which have been detected at an early stage
433///         of Hensel lifting
434/// @sa earlyFactorDetectn(), extEarlyFactorDetect()
435CFList
436henselLiftAndEarly (
437            CanonicalForm& A,         ///< [in,out] poly to be factored,
438                                      ///< returns poly divided by detected
439                                      ///< factors, in case of success
440            CFList& MOD,              ///< [in,out] a list of powers of
441                                      ///< Variables
442            int*& liftBounds,         ///< [in,out] initial lift bounds, returns
443                                      ///< adapted lift bounds
444            bool& earlySuccess,       ///< [in,out] indicating success
445            CFList& earlyFactors,     ///< [in,out] early factors
446            const CFList& Aeval,      ///< [in] @a A successively evaluated at
447                                      ///< elements of @a evaluation
448            const CFList& biFactors,  ///< [in] bivariate factors
449            const CFList& evaluation, ///< [in] evaluation point
450            const ExtensionInfo& info ///< [in] info about extension
451                   );
452
453/// Factorization over an extension of initial field
454///
455/// @return @a extFactorize returns factorization of F over initial field
456/// @sa extBiFactorize(), multiFactorize()
457CFList
458extFactorize (const CanonicalForm& F,   ///< [in] poly to be factored
459              const ExtensionInfo& info ///< [in] info about extension
460             );
461
462#endif
463/* FAC_FQ_FACTORIZE_H */
464
Note: See TracBrowser for help on using the repository browser.