# source:git/factory/facFqBivar.h@19bf86

spielwiese
Last change on this file since 19bf86 was e558c41, checked in by Hans Schoenemann <hannes@…>, 13 years ago
• Property mode set to 100644
File size: 14.8 KB
Line
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqBivar.h
5 *
6 * This file provides functions for factorizing a bivariate polynomial over
7 * \f$F_{p} \f$ , \f$F_{p}(\alpha ) \f$ or GF.
8 *
9 * ABSTRACT: In contrast to biFactorizer() in facFqFactorice.cc we evaluate and
10 * factorize the polynomial in both variables. So far factor recombination is
11 * done naive!
12 *
13 * @author Martin Lee
14 *
15 * @internal @version \$Id$
16 *
17 **/
18/*****************************************************************************/
19
20#ifndef FAC_FQ_BIVAR_H
21#define FAC_FQ_BIVAR_H
22
23#include <config.h>
24
25#include "assert.h"
26
27#include "facFqBivarUtil.h"
28#include "DegreePattern.h"
29#include "ExtensionInfo.h"
30#include "ExtensionInfo.cc"
31#include "cf_util.h"
32#include "facFqSquarefree.h"
33
34/// Factorization of a squarefree bivariate polynomials over an arbitrary finite
35/// field, information on the current field we work over is in @a info. @a info
36/// may also contain information about the initial field if initial and current
37/// field do not coincide. In this case the current field is an extension of the
38/// initial field and the factors returned are factors of F over the initial
39/// field.
40///
41/// @return @a biFactorize returns a list of factors of F. If F is not monic
42///         its leading coefficient is not outputted.
43/// @sa extBifactorize()
44CFList
45biFactorize (const CanonicalForm& F,       ///< [in] a bivariate poly
46             const ExtensionInfo& info     ///< [in] information about extension
47            );
48
49/// factorize a squarefree bivariate polynomial over \f$F_{p} \f$.
50///
51/// @return @a FpBiSqrfFactorize returns a list of monic factors, the first
52///         element is the leading coefficient.
53/// @sa FqBiSqrfFactorize(), GFBiSqrfFactorize()
54inline
55CFList FpBiSqrfFactorize (const CanonicalForm & F ///< [in] a bivariate poly
56                         )
57{
58  ExtensionInfo info= ExtensionInfo (false);
59  CFList result= biFactorize (F, info);
60  result.insert (Lc(F));
61  return result;
62}
63
64/// factorize a squarefree bivariate polynomial over \f$F_{p}(\alpha ) \f$.
65///
66/// @return @a FqBiSqrfFactorize returns a list of monic factors, the first
67///         element is the leading coefficient.
68/// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize()
69inline
70CFList FqBiSqrfFactorize (const CanonicalForm & F, ///< [in] a bivariate poly
71                          const Variable& alpha    ///< [in] algebraic variable
72                         )
73{
74  ExtensionInfo info= ExtensionInfo (alpha, false);
75  CFList result= biFactorize (F, info);
76  result.insert (Lc(F));
77  return result;
78}
79
80/// factorize a squarefree bivariate polynomial over GF
81///
82/// @return @a GFBiSqrfFactorize returns a list of monic factors, the first
83///         element is the leading coefficient.
84/// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize()
85inline
86CFList GFBiSqrfFactorize (const CanonicalForm & F ///< [in] a bivariate poly
87                         )
88{
89  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
90          "GF as base field expected");
91  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
92  CFList result= biFactorize (F, info);
93  result.insert (Lc(F));
94  return result;
95}
96
97/// factorize a bivariate polynomial over \f$F_{p} \f$
98///
99/// @return @a FpBiFactorize returns a list of monic factors with
100///         multiplicity, the first element is the leading coefficient.
101/// @sa FqBiFactorize(), GFBiFactorize()
102inline
103CFFList FpBiFactorize (const CanonicalForm & F ///< [in] a bivariate poly
104                      )
105{
106  ExtensionInfo info= ExtensionInfo (false);
107  bool GF= false;
108  CanonicalForm LcF= Lc (F);
109  CanonicalForm pthRoot, A;
110  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, info.getAlpha());
111  CFList buf, bufRoot;
112  CFFList result, resultRoot;
113  int p= getCharacteristic();
114  int l;
115  if (degree (pthRoot) > 0)
116  {
117    pthRoot= maxpthRoot (pthRoot, p, l);
118    result= FpBiFactorize (pthRoot);
119    result.removeFirst();
120    for (CFFListIterator i= result; i.hasItem(); i++)
121      i.getItem()= CFFactor (i.getItem().factor(), i.getItem().exp()*l*p);
122    result.insert (CFFactor (LcF, 1));
123    return result;
124  }
125  else
126  {
127    buf= biFactorize (sqrfP, info);
128    A= F/LcF;
129    result= multiplicity (A, buf);
130  }
131  if (degree (A) > 0)
132  {
133    resultRoot= FpBiFactorize (A);
134    resultRoot.removeFirst();
135    result= Union (result, resultRoot);
136  }
137  result.insert (CFFactor (LcF, 1));
138  return result;
139}
140
141/// factorize a bivariate polynomial over \f$F_{p}(\alpha ) \f$
142///
143/// @return @a FqBiFactorize returns a list of monic factors with
144///         multiplicity, the first element is the leading coefficient.
145/// @sa FpBiFactorize(), FqBiFactorize()
146inline
147CFFList FqBiFactorize (const CanonicalForm & F, ///< [in] a bivariate poly
148                       const Variable & alpha   ///< [in] algebraic variable
149                      )
150{
151  ExtensionInfo info= ExtensionInfo (alpha, false);
152  bool GF= false;
153  CanonicalForm LcF= Lc (F);
154  CanonicalForm pthRoot, A;
155  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
156  CFList buf, bufRoot;
157  CFFList result, resultRoot;
158  int p= getCharacteristic();
159  int q= ipower (p, degree (getMipo (alpha)));
160  int l;
161  if (degree (pthRoot) > 0)
162  {
163    pthRoot= maxpthRoot (pthRoot, q, l);
164    result= FqBiFactorize (pthRoot, alpha);
165    result.removeFirst();
166    for (CFFListIterator i= result; i.hasItem(); i++)
167      i.getItem()= CFFactor (i.getItem().factor(), i.getItem().exp()*l*p);
168    result.insert (CFFactor (LcF, 1));
169    return result;
170  }
171  else
172  {
173    buf= biFactorize (sqrfP, info);
174    A= F/LcF;
175    result= multiplicity (A, buf);
176  }
177  if (degree (A) > 0)
178  {
179    resultRoot= FqBiFactorize (A, alpha);
180    resultRoot.removeFirst();
181    result= Union (result, resultRoot);
182  }
183  result.insert (CFFactor (LcF, 1));
184  return result;
185}
186
187/// factorize a bivariate polynomial over GF
188///
189/// @return @a GFBiFactorize returns a list of monic factors with
190///         multiplicity, the first element is the leading coefficient.
191/// @sa FpBiFactorize(), FqBiFactorize()
192inline
193CFFList GFBiFactorize (const CanonicalForm & F ///< [in] a bivariate poly
194                      )
195{
196  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
197          "GF as base field expected");
198  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
199  bool GF= true;
200  CanonicalForm LcF= Lc (F);
201  CanonicalForm pthRoot, A;
202  CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, info.getAlpha());
203  CFList buf;
204  CFFList result, resultRoot;
205  int p= getCharacteristic();
206  int q= ipower (p, getGFDegree());
207  int l;
208  if (degree (pthRoot) > 0)
209  {
210    pthRoot= maxpthRoot (pthRoot, q, l);
211    result= GFBiFactorize (pthRoot);
212    result.removeFirst();
213    for (CFFListIterator i= result; i.hasItem(); i++)
214      i.getItem()= CFFactor (i.getItem().factor(), i.getItem().exp()*l*p);
215    result.insert (CFFactor (LcF, 1));
216    return result;
217  }
218  else
219  {
220    buf= biFactorize (sqrfP, info);
221    A= F/LcF;
222    result= multiplicity (A, buf);
223  }
224  if (degree (A) > 0)
225  {
226    resultRoot= GFBiFactorize (A);
227    resultRoot.removeFirst();
228    result= Union (result, resultRoot);
229  }
230  result.insert (CFFactor (LcF, 1));
231  return result;
232}
233
234/// \f$\prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer
235///
236/// @return @a prodMod0 computes the above defined product
237/// @sa prodMod()
238CanonicalForm prodMod0 (const CFList& L,       ///< [in] a list of compressed,
239                                               ///< bivariate polynomials
240                        const CanonicalForm& M ///< [in] a power of Variable (2)
241                       );
242
243/// find an evaluation point p, s.t. F(p,y) is squarefree and
244/// \f$deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$.
245///
246/// @return @a evalPoint returns an evaluation point, which is valid if and only
247///         if fail == false.
248CanonicalForm
249evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly
250           CanonicalForm & eval,   ///< [in,out] F (p, y)
251           const Variable& alpha,  ///< [in] algebraic variable
252           CFList& list,           ///< [in] list of points already considered
253           const bool& GF,         ///< [in] GaloisFieldDomain?
254           bool& fail              ///< [in,out] equals true, if there is no
255                                   ///< valid evaluation point
256          );
257
258/// Univariate factorization of squarefree monic polys over finite fields via
259/// NTL. If the characteristic is even special GF2 routines of NTL are used.
260///
261/// @return @a uniFactorizer returns a list of monic factors
262inline CFList
263uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly
264               const Variable& alpha,  ///< [in] algebraic variable
265               const bool& GF          ///< [in] GaloisFieldDomain?
266              );
267
268/// naive factor recombination over an extension of the initial field.
269/// Uses precomputed data to exclude combinations that are not possible.
270///
271/// @return @a extFactorRecombination returns a list of factors over the initial
272///         field, whose shift to zero is reversed.
273/// @sa factorRecombination(), extEarlyFactorDetection()
274inline CFList
275extFactorRecombination (
276         const CFList& factors,     ///< [in] list of lifted factors that are
277                                    ///< monic wrt Variable (1)
278         const CanonicalForm& F,    ///< [in] poly to be factored
279         const CanonicalForm& M,    ///< [in] Variable (2)^liftBound
280         const ExtensionInfo& info, ///< [in] contains information about
281                                    ///< extension
282         const CanonicalForm& eval  ///< [in] evaluation point
283                       );
284
285/// naive factor recombination.
286/// Uses precomputed data to exclude combinations that are not possible.
287///
288/// @return @a factorRecombination returns a list of factors of F.
289/// @sa extFactorRecombination(), earlyFactorDetectection()
290inline CFList
291factorRecombination (
292                const CFList& factors,      ///< [in] list of lifted factors
293                                            ///< that are monic wrt Variable (1)
294                const CanonicalForm& F,     ///< [in] poly to be factored
295                const CanonicalForm& M,     ///< [in] Variable (2)^liftBound
296                const DegreePattern& degs   ///< [in] degree pattern
297                    );
298
299/// chooses a field extension.
300///
301/// @return @a chooseExtension returns an extension specified by @a beta of
302///         appropiate size
303Variable chooseExtension (
304                      const CanonicalForm & A, ///< [in] some bivariate poly
305                      const Variable & beta    ///< [in] some algebraic
306                                               ///< variable
307                         );
308
309/// detects factors of @a F at stage @a deg of Hensel lifting.
310/// No combinations of more than one factor are tested. Lift bound and possible
311/// degree pattern are updated.
312///
313/// @return @a earlyFactorDetection returns a list of factors of F (possibly in-
314///         complete), in case of success. Otherwise an empty list.
315/// @sa factorRecombination(), extEarlyFactorDetection()
316inline CFList
317earlyFactorDetection (
318           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
319                                   ///< poly divided by detected factors in case
320                                   ///< of success
321           CFList& factors,        ///< [in,out] list of factors lifted up to
322                                   ///< @a deg, returns a list of factors
323                                   ///< without detected factors
325           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
326                                   ///< whenever we find a factor
327           bool& success,          ///< [in,out] indicating success
328           int deg                 ///< [in] stage of Hensel lifting
329                     );
330
331/// detects factors of @a F at stage @a deg of Hensel lifting.
332/// No combinations of more than one factor are tested. Lift bound and possible
333/// degree pattern are updated.
334///
335/// @return @a extEarlyFactorDetection returns a list of factors of F (possibly
336///         incomplete), whose shift to zero is reversed, in case of success.
337///         Otherwise an empty list.
338/// @sa factorRecombination(), earlyFactorDetection()
339inline CFList
340extEarlyFactorDetection (
341        CanonicalForm& F,          ///< [in,out] poly to be factored, returns
342                                   ///< poly divided by detected factors in case
343                                   ///< of success
344        CFList& factors,           ///< [in,out] list of factors lifted up to
345                                   ///< @a deg, returns a list of factors
346                                   ///< without detected factors
348        DegreePattern& degs,       ///< [in,out] degree pattern, is updated
349                                   ///< whenever we find a factor
350        bool& success,             ///< [in,out] indicating success
351        const ExtensionInfo& info,  ///< [in] information about extension
352        const CanonicalForm& eval, ///< [in] evaluation point
353        int deg                    ///< [in] stage of Hensel lifting
354                      );
355
356/// hensel Lifting and early factor detection
357///
358/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
359///         factors without factors which have been detected at an early stage
360///         of Hensel lifting
361/// @sa earlyFactorDetection(), extEarlyFactorDetection()
362
363inline CFList
364henselLiftAndEarly (
365        CanonicalForm& A,          ///< [in,out] poly to be factored,
366                                   ///< returns poly divided by detected factors
367                                   ///< in case of success
368        bool& earlySuccess,        ///< [in,out] indicating success
369        CFList& earlyFactors,      ///< [in,out] list of factors detected
370                                   ///< at early stage of Hensel lifting
371        DegreePattern& degs,       ///< [in,out] degree pattern
372        int& liftBound,            ///< [in,out] (adapted) lift bound
373        const CFList& uniFactors,  ///< [in] univariate factors
374        const ExtensionInfo& info, ///< [in] information about extension
375        const CanonicalForm& eval  ///< [in] evaluation point
376                  );
377
378/// Factorization over an extension of initial field
379///
380/// @return @a extBiFactorize returns factorization of F over initial field
381/// @sa biFactorize()
382inline CFList
383extBiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
384                const ExtensionInfo& info  ///< [in] info about extension
385               );
386
387
388#endif
389/* FAC_FQ_BIVAR_H */
390
Note: See TracBrowser for help on using the repository browser.