source: git/factory/facFqBivar.h @ 7bf145

spielwiese
Last change on this file since 7bf145 was 7bf145, checked in by Martin Lee <martinlee84@…>, 14 years ago
new factorization over finite fields git-svn-id: file:///usr/local/Singular/svn/trunk@12873 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • 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
303inline
304Variable chooseExtension (
305                      const CanonicalForm & A, ///< [in] some bivariate poly
306                      const Variable & beta    ///< [in] some algebraic
307                                               ///< variable
308                         );
309
310/// detects factors of @a F at stage @a deg of Hensel lifting.
311/// No combinations of more than one factor are tested. Lift bound and possible
312/// degree pattern are updated.
313///
314/// @return @a earlyFactorDetection returns a list of factors of F (possibly in-
315///         complete), in case of success. Otherwise an empty list.
316/// @sa factorRecombination(), extEarlyFactorDetection()
317inline CFList
318earlyFactorDetection (
319           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
320                                   ///< poly divided by detected factors in case
321                                   ///< of success
322           CFList& factors,        ///< [in,out] list of factors lifted up to
323                                   ///< @a deg, returns a list of factors
324                                   ///< without detected factors
325           int& adaptedLiftBound,  ///< [in,out] adapted lift bound
326           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
327                                   ///< whenever we find a factor
328           bool& success,          ///< [in,out] indicating success
329           int deg                 ///< [in] stage of Hensel lifting
330                     );
331
332/// detects factors of @a F at stage @a deg of Hensel lifting.
333/// No combinations of more than one factor are tested. Lift bound and possible
334/// degree pattern are updated.
335///
336/// @return @a extEarlyFactorDetection returns a list of factors of F (possibly
337///         incomplete), whose shift to zero is reversed, in case of success.
338///         Otherwise an empty list.
339/// @sa factorRecombination(), earlyFactorDetection()
340inline CFList
341extEarlyFactorDetection (
342        CanonicalForm& F,          ///< [in,out] poly to be factored, returns 
343                                   ///< poly divided by detected factors in case
344                                   ///< of success
345        CFList& factors,           ///< [in,out] list of factors lifted up to
346                                   ///< @a deg, returns a list of factors
347                                   ///< without detected factors
348        int& adaptedLiftBound,     ///< [in,out] adapted lift bound
349        DegreePattern& degs,       ///< [in,out] degree pattern, is updated
350                                   ///< whenever we find a factor
351        bool& success,             ///< [in,out] indicating success
352        const ExtensionInfo& info,  ///< [in] information about extension
353        const CanonicalForm& eval, ///< [in] evaluation point
354        int deg                    ///< [in] stage of Hensel lifting
355                      );
356
357/// hensel Lifting and early factor detection
358///
359/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
360///         factors without factors which have been detected at an early stage
361///         of Hensel lifting
362/// @sa earlyFactorDetection(), extEarlyFactorDetection() 
363
364inline CFList
365henselLiftAndEarly (
366        CanonicalForm& A,          ///< [in,out] poly to be factored,                                     
367                                   ///< returns poly divided by detected factors 
368                                   ///< in case of success
369        bool& earlySuccess,        ///< [in,out] indicating success
370        CFList& earlyFactors,      ///< [in,out] list of factors detected
371                                   ///< at early stage of Hensel lifting
372        DegreePattern& degs,       ///< [in,out] degree pattern
373        int& liftBound,            ///< [in,out] (adapted) lift bound
374        const CFList& uniFactors,  ///< [in] univariate factors
375        const ExtensionInfo& info, ///< [in] information about extension
376        const CanonicalForm& eval  ///< [in] evaluation point
377                  );
378
379/// Factorization over an extension of initial field
380///
381/// @return @a extBiFactorize returns factorization of F over initial field
382/// @sa biFactorize()
383inline CFList
384extBiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
385                const ExtensionInfo& info  ///< [in] info about extension
386               );
387
388
389#endif
390/* FAC_FQ_BIVAR_H */
391
Note: See TracBrowser for help on using the repository browser.