source: git/factory/facFqBivar.h @ e65b1a4

spielwiese
Last change on this file since e65b1a4 was 1a3011e, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: avoid double checking of factors during henselLiftAndEarly chg: lower liftBound in bivariate factorization
  • Property mode set to 100644
File size: 27.4 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 * @author Martin Lee
10 *
11 * @internal @version \$Id$
12 *
13 **/
14/*****************************************************************************/
15
16#ifndef FAC_FQ_BIVAR_H
17#define FAC_FQ_BIVAR_H
18
19// #include "config.h"
20
21#include "cf_assert.h"
22
23#include "facFqBivarUtil.h"
24#include "DegreePattern.h"
25#include "ExtensionInfo.h"
26#include "cf_util.h"
27#include "facFqSquarefree.h"
28#include "cf_map.h"
29#include "cfNewtonPolygon.h"
30
31static const double log2exp= 1.442695041;
32
33#ifdef HAVE_NTL
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 & G ///< [in] a bivariate poly
56                         )
57{
58  ExtensionInfo info= ExtensionInfo (false);
59  CFMap N;
60  CanonicalForm F= compress (G, N);
61  CanonicalForm contentX= content (F, 1);
62  CanonicalForm contentY= content (F, 2);
63  F /= (contentX*contentY);
64  CFFList contentXFactors, contentYFactors;
65  contentXFactors= factorize (contentX);
66  contentYFactors= factorize (contentY);
67  if (contentXFactors.getFirst().factor().inCoeffDomain())
68    contentXFactors.removeFirst();
69  if (contentYFactors.getFirst().factor().inCoeffDomain())
70    contentYFactors.removeFirst();
71  if (F.inCoeffDomain())
72  {
73    CFList result;
74    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
75      result.append (N (i.getItem().factor()));
76    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
77      result.append (N (i.getItem().factor()));
78    normalize (result);
79    result.insert (Lc (G));
80    return result;
81  }
82  mat_ZZ M;
83  vec_ZZ S;
84  F= compress (F, M, S);
85  CFList result= biFactorize (F, info);
86  for (CFListIterator i= result; i.hasItem(); i++)
87    i.getItem()= N (decompress (i.getItem(), M, S));
88  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
89    result.append (N(i.getItem().factor()));
90  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
91    result.append (N (i.getItem().factor()));
92  normalize (result);
93  result.insert (Lc(G));
94  return result;
95}
96
97/// factorize a squarefree bivariate polynomial over \f$ F_{p}(\alpha ) \f$.
98///
99/// @return @a FqBiSqrfFactorize returns a list of monic factors, the first
100///         element is the leading coefficient.
101/// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize()
102inline
103CFList FqBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
104                          const Variable& alpha    ///< [in] algebraic variable
105                         )
106{
107  ExtensionInfo info= ExtensionInfo (alpha, false);
108  CFMap N;
109  CanonicalForm F= compress (G, N);
110  CanonicalForm contentX= content (F, 1);
111  CanonicalForm contentY= content (F, 2);
112  F /= (contentX*contentY);
113  CFFList contentXFactors, contentYFactors;
114  contentXFactors= factorize (contentX, alpha);
115  contentYFactors= factorize (contentY, alpha);
116  if (contentXFactors.getFirst().factor().inCoeffDomain())
117    contentXFactors.removeFirst();
118  if (contentYFactors.getFirst().factor().inCoeffDomain())
119    contentYFactors.removeFirst();
120  if (F.inCoeffDomain())
121  {
122    CFList result;
123    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
124      result.append (N (i.getItem().factor()));
125    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
126      result.append (N (i.getItem().factor()));
127    normalize (result);
128    result.insert (Lc (G));
129    return result;
130  }
131  mat_ZZ M;
132  vec_ZZ S;
133  F= compress (F, M, S);
134  CFList result= biFactorize (F, info);
135  for (CFListIterator i= result; i.hasItem(); i++)
136    i.getItem()= N (decompress (i.getItem(), M, S));
137  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
138    result.append (N(i.getItem().factor()));
139  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
140    result.append (N (i.getItem().factor()));
141  normalize (result);
142  result.insert (Lc(G));
143  return result;
144}
145
146/// factorize a squarefree bivariate polynomial over GF
147///
148/// @return @a GFBiSqrfFactorize returns a list of monic factors, the first
149///         element is the leading coefficient.
150/// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize()
151inline
152CFList GFBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
153                         )
154{
155  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
156          "GF as base field expected");
157  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
158  CFMap N;
159  CanonicalForm F= compress (G, N);
160  CanonicalForm contentX= content (F, 1);
161  CanonicalForm contentY= content (F, 2);
162  F /= (contentX*contentY);
163  CFList contentXFactors, contentYFactors;
164  contentXFactors= biFactorize (contentX, info);
165  contentYFactors= biFactorize (contentY, info);
166  if (contentXFactors.getFirst().inCoeffDomain())
167    contentXFactors.removeFirst();
168  if (contentYFactors.getFirst().inCoeffDomain())
169    contentYFactors.removeFirst();
170  if (F.inCoeffDomain())
171  {
172    CFList result;
173    for (CFListIterator i= contentXFactors; i.hasItem(); i++)
174      result.append (N (i.getItem()));
175    for (CFListIterator i= contentYFactors; i.hasItem(); i++)
176      result.append (N (i.getItem()));
177    normalize (result);
178    result.insert (Lc (G));
179    return result;
180  }
181  mat_ZZ M;
182  vec_ZZ S;
183  F= compress (F, M, S);
184  CFList result= biFactorize (F, info);
185  for (CFListIterator i= result; i.hasItem(); i++)
186    i.getItem()= N (decompress (i.getItem(), M, S));
187  for (CFListIterator i= contentXFactors; i.hasItem(); i++)
188    result.append (N(i.getItem()));
189  for (CFListIterator i= contentYFactors; i.hasItem(); i++)
190    result.append (N (i.getItem()));
191  normalize (result);
192  result.insert (Lc(G));
193  return result;
194}
195
196/// factorize a bivariate polynomial over \f$ F_{p} \f$
197///
198/// @return @a FpBiFactorize returns a list of monic factors with
199///         multiplicity, the first element is the leading coefficient.
200/// @sa FqBiFactorize(), GFBiFactorize()
201inline
202CFFList
203FpBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
204               bool substCheck= true    ///< [in] enables substitute check
205              )
206{
207  ExtensionInfo info= ExtensionInfo (false);
208  CFMap N;
209  CanonicalForm F= compress (G, N);
210
211  if (substCheck)
212  {
213    bool foundOne= false;
214    int * substDegree= new int [F.level()];
215    for (int i= 1; i <= F.level(); i++)
216    {
217      substDegree[i-1]= substituteCheck (F, Variable (i));
218      if (substDegree [i-1] > 1)
219      {
220        foundOne= true;
221        subst (F, F, substDegree[i-1], Variable (i));
222      }
223    }
224    if (foundOne)
225    {
226      CFFList result= FpBiFactorize (F, false);
227      CFFList newResult, tmp;
228      CanonicalForm tmp2;
229      newResult.insert (result.getFirst());
230      result.removeFirst();
231      for (CFFListIterator i= result; i.hasItem(); i++)
232      {
233        tmp2= i.getItem().factor();
234        for (int j= 1; j <= F.level(); j++)
235        {
236          if (substDegree[j-1] > 1)
237            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
238        }
239        tmp= FpBiFactorize (tmp2, false);
240        tmp.removeFirst();
241        for (CFFListIterator j= tmp; j.hasItem(); j++)
242          newResult.append (CFFactor (j.getItem().factor(),
243                                      j.getItem().exp()*i.getItem().exp()));
244      }
245      decompress (newResult, N);
246      delete [] substDegree;
247      return newResult;
248    }
249    delete [] substDegree;
250  }
251
252  CanonicalForm LcF= Lc (F);
253  CanonicalForm contentX= content (F, 1);
254  CanonicalForm contentY= content (F, 2);
255  F /= (contentX*contentY);
256  CFFList contentXFactors, contentYFactors;
257  contentXFactors= factorize (contentX);
258  contentYFactors= factorize (contentY);
259  if (contentXFactors.getFirst().factor().inCoeffDomain())
260    contentXFactors.removeFirst();
261  if (contentYFactors.getFirst().factor().inCoeffDomain())
262    contentYFactors.removeFirst();
263  decompress (contentXFactors, N);
264  decompress (contentYFactors, N);
265  CFFList result, resultRoot;
266  if (F.inCoeffDomain())
267  {
268    result= Union (contentXFactors, contentYFactors);
269    normalize (result);
270    result.insert (CFFactor (LcF, 1));
271    return result;
272  }
273  mat_ZZ M;
274  vec_ZZ S;
275  F= compress (F, M, S);
276  CanonicalForm pthRoot, A;
277  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, info.getAlpha());
278  CFList buf, bufRoot;
279  int p= getCharacteristic();
280  int l;
281  if (degree (pthRoot) > 0)
282  {
283    pthRoot= maxpthRoot (pthRoot, p, l);
284    result= FpBiFactorize (pthRoot, false);
285    result.removeFirst();
286    for (CFFListIterator i= result; i.hasItem(); i++)
287      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
288                             i.getItem().exp()*ipower (p,l));
289    result= Union (result, contentXFactors);
290    result= Union (result, contentYFactors);
291    normalize (result);
292    result.insert (CFFactor (LcF, 1));
293    return result;
294  }
295  else
296  {
297    buf= biFactorize (sqrfP, info);
298    A= F/LcF;
299    result= multiplicity (A, buf);
300    for (CFFListIterator i= result; i.hasItem(); i++)
301      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
302                             i.getItem().exp());
303  }
304  if (degree (A) > 0)
305  {
306    resultRoot= FpBiFactorize (A, false);
307    resultRoot.removeFirst();
308    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
309      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
310                             i.getItem().exp());
311    result= Union (result, resultRoot);
312  }
313  result= Union (result, contentXFactors);
314  result= Union (result, contentYFactors);
315  normalize (result);
316  result.insert (CFFactor (LcF, 1));
317  return result;
318}
319
320/// factorize a bivariate polynomial over \f$ F_{p}(\alpha ) \f$
321///
322/// @return @a FqBiFactorize returns a list of monic factors with
323///         multiplicity, the first element is the leading coefficient.
324/// @sa FpBiFactorize(), FqBiFactorize()
325inline
326CFFList
327FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
328               const Variable & alpha,  ///< [in] algebraic variable
329               bool substCheck= true    ///< [in] enables substitute check
330              )
331{
332  ExtensionInfo info= ExtensionInfo (alpha, false);
333  CFMap N;
334  CanonicalForm F= compress (G, N);
335
336  if (substCheck)
337  {
338    bool foundOne= false;
339    int * substDegree= new int [F.level()];
340    for (int i= 1; i <= F.level(); i++)
341    {
342      substDegree[i-1]= substituteCheck (F, Variable (i));
343      if (substDegree [i-1] > 1)
344      {
345        foundOne= true;
346        subst (F, F, substDegree[i-1], Variable (i));
347      }
348    }
349    if (foundOne)
350    {
351      CFFList result= FqBiFactorize (F, alpha, false);
352      CFFList newResult, tmp;
353      CanonicalForm tmp2;
354      newResult.insert (result.getFirst());
355      result.removeFirst();
356      for (CFFListIterator i= result; i.hasItem(); i++)
357      {
358        tmp2= i.getItem().factor();
359        for (int j= 1; j <= F.level(); j++)
360        {
361          if (substDegree[j-1] > 1)
362            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
363        }
364        tmp= FqBiFactorize (tmp2, alpha, false);
365        tmp.removeFirst();
366        for (CFFListIterator j= tmp; j.hasItem(); j++)
367          newResult.append (CFFactor (j.getItem().factor(),
368                                      j.getItem().exp()*i.getItem().exp()));
369      }
370      decompress (newResult, N);
371      delete [] substDegree;
372      return newResult;
373    }
374    delete [] substDegree;
375  }
376
377  CanonicalForm LcF= Lc (F);
378  CanonicalForm contentX= content (F, 1);
379  CanonicalForm contentY= content (F, 2);
380  F /= (contentX*contentY);
381  CFFList contentXFactors, contentYFactors;
382  contentXFactors= factorize (contentX, alpha);
383  contentYFactors= factorize (contentY, alpha);
384  if (contentXFactors.getFirst().factor().inCoeffDomain())
385    contentXFactors.removeFirst();
386  if (contentYFactors.getFirst().factor().inCoeffDomain())
387    contentYFactors.removeFirst();
388  decompress (contentXFactors, N);
389  decompress (contentYFactors, N);
390  CFFList result, resultRoot;
391  if (F.inCoeffDomain())
392  {
393    result= Union (contentXFactors, contentYFactors);
394    normalize (result);
395    result.insert (CFFactor (LcF, 1));
396    return result;
397  }
398  mat_ZZ M;
399  vec_ZZ S;
400  CanonicalForm oldF= F;
401  F= compress (F, M, S);
402  CanonicalForm pthRoot, A, tmp;
403  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
404  CFList buf, bufRoot;
405  int p= getCharacteristic();
406  int q= ipower (p, degree (getMipo (alpha)));
407  int l;
408  if (degree (pthRoot) > 0)
409  {
410    pthRoot= maxpthRoot (pthRoot, q, l);
411    result= FqBiFactorize (pthRoot, alpha, false);
412    result.removeFirst();
413    for (CFFListIterator i= result; i.hasItem(); i++)
414      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
415                             i.getItem().exp()*ipower (p,l));
416    result= Union (result, contentXFactors);
417    result= Union (result, contentYFactors);
418    normalize (result);
419    result.insert (CFFactor (LcF, 1));
420    return result;
421  }
422  else
423  {
424    buf= biFactorize (sqrfP, info);
425    A= F/LcF;
426    result= multiplicity (A, buf);
427    for (CFFListIterator i= result; i.hasItem(); i++)
428      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
429                             i.getItem().exp());
430  }
431  if (degree (A) > 0)
432  {
433    resultRoot= FqBiFactorize (A, alpha, false);
434    resultRoot.removeFirst();
435    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
436      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
437                             i.getItem().exp());
438    result= Union (result, resultRoot);
439  }
440  result= Union (result, contentXFactors);
441  result= Union (result, contentYFactors);
442  normalize (result);
443  result.insert (CFFactor (LcF, 1));
444  return result;
445}
446
447/// factorize a bivariate polynomial over GF
448///
449/// @return @a GFBiFactorize returns a list of monic factors with
450///         multiplicity, the first element is the leading coefficient.
451/// @sa FpBiFactorize(), FqBiFactorize()
452inline
453CFFList
454GFBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
455               bool substCheck= true    ///< [in] enables substitute check
456              )
457{
458  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
459          "GF as base field expected");
460  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
461  CFMap N;
462  CanonicalForm F= compress (G, N);
463
464  if (substCheck)
465  {
466    bool foundOne= false;
467    int * substDegree= new int [F.level()];
468    for (int i= 1; i <= F.level(); i++)
469    {
470      substDegree[i-1]= substituteCheck (F, Variable (i));
471      if (substDegree [i-1] > 1)
472      {
473        foundOne= true;
474        subst (F, F, substDegree[i-1], Variable (i));
475      }
476    }
477    if (foundOne)
478    {
479      CFFList result= GFBiFactorize (F, false);
480      CFFList newResult, tmp;
481      CanonicalForm tmp2;
482      newResult.insert (result.getFirst());
483      result.removeFirst();
484      for (CFFListIterator i= result; i.hasItem(); i++)
485      {
486        tmp2= i.getItem().factor();
487        for (int j= 1; j <= F.level(); j++)
488        {
489          if (substDegree[j-1] > 1)
490            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
491        }
492        tmp= GFBiFactorize (tmp2, false);
493        tmp.removeFirst();
494        for (CFFListIterator j= tmp; j.hasItem(); j++)
495          newResult.append (CFFactor (j.getItem().factor(),
496                                      j.getItem().exp()*i.getItem().exp()));
497      }
498      decompress (newResult, N);
499      delete [] substDegree;
500      return newResult;
501    }
502    delete [] substDegree;
503  }
504
505  CanonicalForm LcF= Lc (F);
506  CanonicalForm contentX= content (F, 1);
507  CanonicalForm contentY= content (F, 2);
508  F /= (contentX*contentY);
509  CFFList contentXFactors, contentYFactors;
510  contentXFactors= factorize (contentX);
511  contentYFactors= factorize (contentY);
512  if (contentXFactors.getFirst().factor().inCoeffDomain())
513    contentXFactors.removeFirst();
514  if (contentYFactors.getFirst().factor().inCoeffDomain())
515    contentYFactors.removeFirst();
516  decompress (contentXFactors, N);
517  decompress (contentYFactors, N);
518  CFFList result, resultRoot;
519  if (F.inCoeffDomain())
520  {
521    result= Union (contentXFactors, contentYFactors);
522    normalize (result);
523    result.insert (CFFactor (LcF, 1));
524    return result;
525  }
526  mat_ZZ M;
527  vec_ZZ S;
528  F= compress (F, M, S);
529  CanonicalForm pthRoot, A;
530  CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, info.getAlpha());
531  CFList buf;
532  int p= getCharacteristic();
533  int q= ipower (p, getGFDegree());
534  int l;
535  if (degree (pthRoot) > 0)
536  {
537    pthRoot= maxpthRoot (pthRoot, q, l);
538    result= GFBiFactorize (pthRoot, false);
539    result.removeFirst();
540    for (CFFListIterator i= result; i.hasItem(); i++)
541      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
542                             i.getItem().exp()*ipower (p,l));
543    result= Union (result, contentXFactors);
544    result= Union (result, contentYFactors);
545    normalize (result);
546    result.insert (CFFactor (LcF, 1));
547    return result;
548  }
549  else
550  {
551    buf= biFactorize (sqrfP, info);
552    A= F/LcF;
553    result= multiplicity (A, buf);
554    for (CFFListIterator i= result; i.hasItem(); i++)
555      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
556                             i.getItem().exp());
557  }
558  if (degree (A) > 0)
559  {
560    resultRoot= GFBiFactorize (A, false);
561    resultRoot.removeFirst();
562    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
563      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
564                             i.getItem().exp());
565    result= Union (result, resultRoot);
566  }
567  result= Union (result, contentXFactors);
568  result= Union (result, contentYFactors);
569  normalize (result);
570  result.insert (CFFactor (LcF, 1));
571  return result;
572}
573
574/// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer
575///
576/// @return @a prodMod0 computes the above defined product
577/// @sa prodMod()
578CanonicalForm prodMod0 (const CFList& L,       ///< [in] a list of compressed,
579                                               ///< bivariate polynomials
580                        const CanonicalForm& M ///< [in] a power of Variable (2)
581                       );
582
583/// find an evaluation point p, s.t. F(p,y) is squarefree and
584/// \f$ deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$.
585///
586/// @return @a evalPoint returns an evaluation point, which is valid if and only
587///         if fail == false.
588CanonicalForm
589evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly
590           CanonicalForm & eval,   ///< [in,out] F (p, y)
591           const Variable& alpha,  ///< [in] algebraic variable
592           CFList& list,           ///< [in] list of points already considered
593           const bool& GF,         ///< [in] GaloisFieldDomain?
594           bool& fail              ///< [in,out] equals true, if there is no
595                                   ///< valid evaluation point
596          );
597
598/// Univariate factorization of squarefree monic polys over finite fields via
599/// NTL. If the characteristic is even special GF2 routines of NTL are used.
600///
601/// @return @a uniFactorizer returns a list of monic factors
602CFList
603uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly
604               const Variable& alpha,  ///< [in] algebraic variable
605               const bool& GF          ///< [in] GaloisFieldDomain?
606              );
607
608/// naive factor recombination over an extension of the initial field.
609/// Uses precomputed data to exclude combinations that are not possible.
610///
611/// @return @a extFactorRecombination returns a list of factors over the initial
612///         field, whose shift to zero is reversed.
613/// @sa factorRecombination(), extEarlyFactorDetection()
614CFList
615extFactorRecombination (
616         CFList& factors,          ///< [in,out] list of lifted factors that are
617                                   ///< monic wrt Variable (1),
618                                   ///< original factors-factors found
619         CanonicalForm& F,         ///< [in,out] poly to be factored,
620                                   ///< F/factors found
621         const CanonicalForm& M,   ///< [in] Variable (2)^liftBound
622         const ExtensionInfo& info,///< [in] contains information about
623                                   ///< extension
624         DegreePattern& degs,
625         const CanonicalForm& eval,///< [in] evaluation point
626         int s,                    ///< [in] algorithm starts checking subsets
627                                   ///< of size s
628         int thres                 ///< [in] threshold for the size of subsets
629                                   ///< which are checked, for a full factor
630                                   ///< recombination choose
631                                   ///< thres= factors.length()/2
632                       );
633
634/// naive factor recombination.
635/// Uses precomputed data to exclude combinations that are not possible.
636///
637/// @return @a factorRecombination returns a list of factors of F.
638/// @sa extFactorRecombination(), earlyFactorDetectection()
639CFList
640factorRecombination (
641                CFList& factors,       ///< [in,out] list of lifted factors
642                                       ///< that are monic wrt Variable (1)
643                CanonicalForm& F,      ///< [in,out] poly to be factored
644                const CanonicalForm& M,///< [in] Variable (2)^liftBound
645                DegreePattern& degs,   ///< [in] degree pattern
646                int s,                 ///< [in] algorithm starts checking
647                                       ///< subsets of size s
648                int thres              ///< [in] threshold for the size of
649                                       ///< subsets which are checked, for a
650                                       ///< full factor recombination choose
651                                       ///< thres= factors.length()/2
652                    );
653
654/// chooses a field extension.
655///
656/// @return @a chooseExtension returns an extension specified by @a beta of
657///         appropiate size
658Variable chooseExtension (
659                      const Variable & alpha, ///< [in] some algebraic variable
660                      const Variable & beta,  ///< [in] some algebraic variable
661                      int k                   ///< [in] some int
662                         );
663
664/// compute lifting precisions from the shape of the Newton polygon of F
665///
666/// @return @a getLiftPrecisions returns lifting precisions computed from the
667/// shape of the Newton polygon of F
668int *
669getLiftPrecisions (const CanonicalForm& F, ///< [in] a bivariate poly
670                   int& sizeOfOutput,      ///< [in,out] size of the output
671                   int degreeLC            ///< [in] degree of the leading coeff
672                                           ///< [in] of F wrt. Variable (1)
673                  );
674
675
676/// detects factors of @a F at stage @a deg of Hensel lifting.
677/// No combinations of more than one factor are tested. Lift bound and possible
678/// degree pattern are updated.
679///
680/// @sa factorRecombination(), extEarlyFactorDetection()
681void
682earlyFactorDetection (
683           CFList& reconstructedFactors, ///< [in,out] list of reconstructed
684                                         ///< factors
685           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
686                                   ///< poly divided by detected factors in case
687                                   ///< of success
688           CFList& factors,        ///< [in,out] list of factors lifted up to
689                                   ///< @a deg, returns a list of factors
690                                   ///< without detected factors
691           int& adaptedLiftBound,  ///< [in,out] adapted lift bound
692           int*& factorsFoundIndex,///< [in,out] factors already considered
693           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
694                                   ///< whenever we find a factor
695           bool& success,          ///< [in,out] indicating success
696           int deg                 ///< [in] stage of Hensel lifting
697                     );
698
699/// detects factors of @a F at stage @a deg of Hensel lifting.
700/// No combinations of more than one factor are tested. Lift bound and possible
701/// degree pattern are updated.
702///
703/// @sa factorRecombination(), earlyFactorDetection()
704void
705extEarlyFactorDetection (
706        CFList& reconstructedFactors, ///< [in,out] list of reconstructed
707                                      ///< factors
708        CanonicalForm& F,          ///< [in,out] poly to be factored, returns
709                                   ///< poly divided by detected factors in case
710                                   ///< of success
711        CFList& factors,           ///< [in,out] list of factors lifted up to
712                                   ///< @a deg, returns a list of factors
713                                   ///< without detected factors
714        int& adaptedLiftBound,     ///< [in,out] adapted lift bound
715        int*& factorsFoundIndex,   ///< [in,out] factors already considered
716        DegreePattern& degs,       ///< [in,out] degree pattern, is updated
717                                   ///< whenever we find a factor
718        bool& success,             ///< [in,out] indicating success
719        const ExtensionInfo& info,  ///< [in] information about extension
720        const CanonicalForm& eval, ///< [in] evaluation point
721        int deg                    ///< [in] stage of Hensel lifting
722                      );
723
724/// hensel Lifting and early factor detection
725///
726/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
727///         factors without factors which have been detected at an early stage
728///         of Hensel lifting
729/// @sa earlyFactorDetection(), extEarlyFactorDetection()
730
731CFList
732henselLiftAndEarly (
733        CanonicalForm& A,          ///< [in,out] poly to be factored,
734                                   ///< returns poly divided by detected factors
735                                   ///< in case of success
736        bool& earlySuccess,        ///< [in,out] indicating success
737        CFList& earlyFactors,      ///< [in,out] list of factors detected
738                                   ///< at early stage of Hensel lifting
739        DegreePattern& degs,       ///< [in,out] degree pattern
740        int& liftBound,            ///< [in,out] (adapted) lift bound
741        const CFList& uniFactors,  ///< [in] univariate factors
742        const ExtensionInfo& info, ///< [in] information about extension
743        const CanonicalForm& eval  ///< [in] evaluation point
744                  );
745
746/// Factorization over an extension of initial field
747///
748/// @return @a extBiFactorize returns factorization of F over initial field
749/// @sa biFactorize()
750CFList
751extBiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
752                const ExtensionInfo& info  ///< [in] info about extension
753               );
754
755#endif
756#endif
757/* FAC_FQ_BIVAR_H */
758
Note: See TracBrowser for help on using the repository browser.