# source:git/factory/facFqBivar.h@72bfc8

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