source: git/factory/facFqBivar.h @ d1553c

jengelh-datetimespielwiese
Last change on this file since d1553c was d1553c, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: use sqrf instead of sqrfPart
  • Property mode set to 100644
File size: 26.0 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;
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
275  CFFList sqrf= FpSqrf (F, false);
276  CFList bufResult;
277  sqrf.removeFirst();
278  CFListIterator i;
279  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280  {
281    bufResult= biFactorize (iter.getItem().factor(), info);
282    for (i= bufResult; i.hasItem(); i++)
283      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
284                               iter.getItem().exp()));
285  }
286
287  result= Union (result, contentXFactors);
288  result= Union (result, contentYFactors);
289  normalize (result);
290  result.insert (CFFactor (LcF, 1));
291  return result;
292}
293
294/// factorize a bivariate polynomial over \f$ F_{p}(\alpha ) \f$
295///
296/// @return @a FqBiFactorize returns a list of monic factors with
297///         multiplicity, the first element is the leading coefficient.
298/// @sa FpBiFactorize(), FqBiFactorize()
299inline
300CFFList
301FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
302               const Variable & alpha,  ///< [in] algebraic variable
303               bool substCheck= true    ///< [in] enables substitute check
304              )
305{
306  ExtensionInfo info= ExtensionInfo (alpha, false);
307  CFMap N;
308  CanonicalForm F= compress (G, N);
309
310  if (substCheck)
311  {
312    bool foundOne= false;
313    int * substDegree= new int [F.level()];
314    for (int i= 1; i <= F.level(); i++)
315    {
316      substDegree[i-1]= substituteCheck (F, Variable (i));
317      if (substDegree [i-1] > 1)
318      {
319        foundOne= true;
320        subst (F, F, substDegree[i-1], Variable (i));
321      }
322    }
323    if (foundOne)
324    {
325      CFFList result= FqBiFactorize (F, alpha, false);
326      CFFList newResult, tmp;
327      CanonicalForm tmp2;
328      newResult.insert (result.getFirst());
329      result.removeFirst();
330      for (CFFListIterator i= result; i.hasItem(); i++)
331      {
332        tmp2= i.getItem().factor();
333        for (int j= 1; j <= F.level(); j++)
334        {
335          if (substDegree[j-1] > 1)
336            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
337        }
338        tmp= FqBiFactorize (tmp2, alpha, false);
339        tmp.removeFirst();
340        for (CFFListIterator j= tmp; j.hasItem(); j++)
341          newResult.append (CFFactor (j.getItem().factor(),
342                                      j.getItem().exp()*i.getItem().exp()));
343      }
344      decompress (newResult, N);
345      delete [] substDegree;
346      return newResult;
347    }
348    delete [] substDegree;
349  }
350
351  CanonicalForm LcF= Lc (F);
352  CanonicalForm contentX= content (F, 1);
353  CanonicalForm contentY= content (F, 2);
354  F /= (contentX*contentY);
355  CFFList contentXFactors, contentYFactors;
356  contentXFactors= factorize (contentX, alpha);
357  contentYFactors= factorize (contentY, alpha);
358  if (contentXFactors.getFirst().factor().inCoeffDomain())
359    contentXFactors.removeFirst();
360  if (contentYFactors.getFirst().factor().inCoeffDomain())
361    contentYFactors.removeFirst();
362  decompress (contentXFactors, N);
363  decompress (contentYFactors, N);
364  CFFList result;
365  if (F.inCoeffDomain())
366  {
367    result= Union (contentXFactors, contentYFactors);
368    normalize (result);
369    result.insert (CFFactor (LcF, 1));
370    return result;
371  }
372  mat_ZZ M;
373  vec_ZZ S;
374  F= compress (F, M, S);
375
376  CFFList sqrf= FqSqrf (F, alpha, false);
377  CFList bufResult;
378  sqrf.removeFirst();
379  CFListIterator i;
380  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
381  {
382    bufResult= biFactorize (iter.getItem().factor(), info);
383    for (i= bufResult; i.hasItem(); i++)
384      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
385                               iter.getItem().exp()));
386  }
387
388  result= Union (result, contentXFactors);
389  result= Union (result, contentYFactors);
390  normalize (result);
391  result.insert (CFFactor (LcF, 1));
392  return result;
393}
394
395/// factorize a bivariate polynomial over GF
396///
397/// @return @a GFBiFactorize returns a list of monic factors with
398///         multiplicity, the first element is the leading coefficient.
399/// @sa FpBiFactorize(), FqBiFactorize()
400inline
401CFFList
402GFBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
403               bool substCheck= true    ///< [in] enables substitute check
404              )
405{
406  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
407          "GF as base field expected");
408  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
409  CFMap N;
410  CanonicalForm F= compress (G, N);
411
412  if (substCheck)
413  {
414    bool foundOne= false;
415    int * substDegree= new int [F.level()];
416    for (int i= 1; i <= F.level(); i++)
417    {
418      substDegree[i-1]= substituteCheck (F, Variable (i));
419      if (substDegree [i-1] > 1)
420      {
421        foundOne= true;
422        subst (F, F, substDegree[i-1], Variable (i));
423      }
424    }
425    if (foundOne)
426    {
427      CFFList result= GFBiFactorize (F, false);
428      CFFList newResult, tmp;
429      CanonicalForm tmp2;
430      newResult.insert (result.getFirst());
431      result.removeFirst();
432      for (CFFListIterator i= result; i.hasItem(); i++)
433      {
434        tmp2= i.getItem().factor();
435        for (int j= 1; j <= F.level(); j++)
436        {
437          if (substDegree[j-1] > 1)
438            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
439        }
440        tmp= GFBiFactorize (tmp2, false);
441        tmp.removeFirst();
442        for (CFFListIterator j= tmp; j.hasItem(); j++)
443          newResult.append (CFFactor (j.getItem().factor(),
444                                      j.getItem().exp()*i.getItem().exp()));
445      }
446      decompress (newResult, N);
447      delete [] substDegree;
448      return newResult;
449    }
450    delete [] substDegree;
451  }
452
453  CanonicalForm LcF= Lc (F);
454  CanonicalForm contentX= content (F, 1);
455  CanonicalForm contentY= content (F, 2);
456  F /= (contentX*contentY);
457  CFFList contentXFactors, contentYFactors;
458  contentXFactors= factorize (contentX);
459  contentYFactors= factorize (contentY);
460  if (contentXFactors.getFirst().factor().inCoeffDomain())
461    contentXFactors.removeFirst();
462  if (contentYFactors.getFirst().factor().inCoeffDomain())
463    contentYFactors.removeFirst();
464  decompress (contentXFactors, N);
465  decompress (contentYFactors, N);
466  CFFList result;
467  if (F.inCoeffDomain())
468  {
469    result= Union (contentXFactors, contentYFactors);
470    normalize (result);
471    result.insert (CFFactor (LcF, 1));
472    return result;
473  }
474  mat_ZZ M;
475  vec_ZZ S;
476  F= compress (F, M, S);
477
478  CFFList sqrf= GFSqrf (F, false);
479  CFList bufResult;
480  sqrf.removeFirst();
481  CFListIterator i;
482  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
483  {
484    bufResult= biFactorize (iter.getItem().factor(), info);
485    for (i= bufResult; i.hasItem(); i++)
486      result.append (CFFactor (N (decompress (i.getItem(), M, S)),
487                               iter.getItem().exp()));
488  }
489
490  result= Union (result, contentXFactors);
491  result= Union (result, contentYFactors);
492  normalize (result);
493  result.insert (CFFactor (LcF, 1));
494  return result;
495}
496
497/// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer
498///
499/// @return @a prodMod0 computes the above defined product
500/// @sa prodMod()
501CanonicalForm prodMod0 (const CFList& L,       ///< [in] a list of compressed,
502                                               ///< bivariate polynomials
503                        const CanonicalForm& M,///< [in] a power of Variable (2)
504                        const modpk& b= modpk()///< [in] coeff bound
505                       );
506
507/// find an evaluation point p, s.t. F(p,y) is squarefree and
508/// \f$ deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$.
509///
510/// @return @a evalPoint returns an evaluation point, which is valid if and only
511///         if fail == false.
512CanonicalForm
513evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly
514           CanonicalForm & eval,   ///< [in,out] F (p, y)
515           const Variable& alpha,  ///< [in] algebraic variable
516           CFList& list,           ///< [in] list of points already considered
517           const bool& GF,         ///< [in] GaloisFieldDomain?
518           bool& fail              ///< [in,out] equals true, if there is no
519                                   ///< valid evaluation point
520          );
521
522/// Univariate factorization of squarefree monic polys over finite fields via
523/// NTL. If the characteristic is even special GF2 routines of NTL are used.
524///
525/// @return @a uniFactorizer returns a list of monic factors
526CFList
527uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly
528               const Variable& alpha,  ///< [in] algebraic variable
529               const bool& GF          ///< [in] GaloisFieldDomain?
530              );
531
532/// naive factor recombination over an extension of the initial field.
533/// Uses precomputed data to exclude combinations that are not possible.
534///
535/// @return @a extFactorRecombination returns a list of factors over the initial
536///         field, whose shift to zero is reversed.
537/// @sa factorRecombination(), extEarlyFactorDetection()
538CFList
539extFactorRecombination (
540         CFList& factors,          ///< [in,out] list of lifted factors that are
541                                   ///< monic wrt Variable (1),
542                                   ///< original factors-factors found
543         CanonicalForm& F,         ///< [in,out] poly to be factored,
544                                   ///< F/factors found
545         const CanonicalForm& M,   ///< [in] Variable (2)^liftBound
546         const ExtensionInfo& info,///< [in] contains information about
547                                   ///< extension
548         DegreePattern& degs,
549         const CanonicalForm& eval,///< [in] evaluation point
550         int s,                    ///< [in] algorithm starts checking subsets
551                                   ///< of size s
552         int thres                 ///< [in] threshold for the size of subsets
553                                   ///< which are checked, for a full factor
554                                   ///< recombination choose
555                                   ///< thres= factors.length()/2
556                       );
557
558/// naive factor recombination.
559/// Uses precomputed data to exclude combinations that are not possible.
560///
561/// @return @a factorRecombination returns a list of factors of F.
562/// @sa extFactorRecombination(), earlyFactorDetectection()
563CFList
564factorRecombination (
565                CFList& factors,       ///< [in,out] list of lifted factors
566                                       ///< that are monic wrt Variable (1)
567                CanonicalForm& F,      ///< [in,out] poly to be factored
568                const CanonicalForm& M,///< [in] Variable (2)^liftBound
569                DegreePattern& degs,   ///< [in] degree pattern
570                int s,                 ///< [in] algorithm starts checking
571                                       ///< subsets of size s
572                int thres,             ///< [in] threshold for the size of
573                                       ///< subsets which are checked, for a
574                                       ///< full factor recombination choose
575                                       ///< thres= factors.length()/2
576                const modpk& b=modpk() ///< [in] coeff bound
577                    );
578
579/// chooses a field extension.
580///
581/// @return @a chooseExtension returns an extension specified by @a beta of
582///         appropiate size
583Variable chooseExtension (
584                      const Variable & alpha, ///< [in] some algebraic variable
585                      const Variable & beta,  ///< [in] some algebraic variable
586                      int k                   ///< [in] some int
587                         );
588
589/// compute lifting precisions from the shape of the Newton polygon of F
590///
591/// @return @a getLiftPrecisions returns lifting precisions computed from the
592/// shape of the Newton polygon of F
593int *
594getLiftPrecisions (const CanonicalForm& F, ///< [in] a bivariate poly
595                   int& sizeOfOutput,      ///< [in,out] size of the output
596                   int degreeLC            ///< [in] degree of the leading coeff
597                                           ///< [in] of F wrt. Variable (1)
598                  );
599
600
601/// detects factors of @a F at stage @a deg of Hensel lifting.
602/// No combinations of more than one factor are tested. Lift bound and possible
603/// degree pattern are updated.
604///
605/// @sa factorRecombination(), extEarlyFactorDetection()
606void
607earlyFactorDetection (
608           CFList& reconstructedFactors, ///< [in,out] list of reconstructed
609                                         ///< factors
610           CanonicalForm& F,       ///< [in,out] poly to be factored, returns
611                                   ///< poly divided by detected factors in case
612                                   ///< of success
613           CFList& factors,        ///< [in,out] list of factors lifted up to
614                                   ///< @a deg, returns a list of factors
615                                   ///< without detected factors
616           int& adaptedLiftBound,  ///< [in,out] adapted lift bound
617           int*& factorsFoundIndex,///< [in,out] factors already considered
618           DegreePattern& degs,    ///< [in,out] degree pattern, is updated
619                                   ///< whenever we find a factor
620           bool& success,          ///< [in,out] indicating success
621           int deg,                ///< [in] stage of Hensel lifting
622           const modpk& b= modpk() ///< [in] coeff bound
623                     );
624
625/// detects factors of @a F at stage @a deg of Hensel lifting.
626/// No combinations of more than one factor are tested. Lift bound and possible
627/// degree pattern are updated.
628///
629/// @sa factorRecombination(), earlyFactorDetection()
630void
631extEarlyFactorDetection (
632        CFList& reconstructedFactors, ///< [in,out] list of reconstructed
633                                      ///< factors
634        CanonicalForm& F,          ///< [in,out] poly to be factored, returns
635                                   ///< poly divided by detected factors in case
636                                   ///< of success
637        CFList& factors,           ///< [in,out] list of factors lifted up to
638                                   ///< @a deg, returns a list of factors
639                                   ///< without detected factors
640        int& adaptedLiftBound,     ///< [in,out] adapted lift bound
641        int*& factorsFoundIndex,   ///< [in,out] factors already considered
642        DegreePattern& degs,       ///< [in,out] degree pattern, is updated
643                                   ///< whenever we find a factor
644        bool& success,             ///< [in,out] indicating success
645        const ExtensionInfo& info,  ///< [in] information about extension
646        const CanonicalForm& eval, ///< [in] evaluation point
647        int deg                    ///< [in] stage of Hensel lifting
648                      );
649
650/// hensel Lifting and early factor detection
651///
652/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
653///         factors without factors which have been detected at an early stage
654///         of Hensel lifting
655/// @sa earlyFactorDetection(), extEarlyFactorDetection()
656
657CFList
658henselLiftAndEarly (
659        CanonicalForm& A,          ///< [in,out] poly to be factored,
660                                   ///< returns poly divided by detected factors
661                                   ///< in case of success
662        bool& earlySuccess,        ///< [in,out] indicating success
663        CFList& earlyFactors,      ///< [in,out] list of factors detected
664                                   ///< at early stage of Hensel lifting
665        DegreePattern& degs,       ///< [in,out] degree pattern
666        int& liftBound,            ///< [in,out] (adapted) lift bound
667        const CFList& uniFactors,  ///< [in] univariate factors
668        const ExtensionInfo& info, ///< [in] information about extension
669        const CanonicalForm& eval, ///< [in] evaluation point
670        modpk& b                   ///< [in] coeff bound
671                  );
672
673/// hensel Lifting and early factor detection
674///
675/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
676///         factors without factors which have been detected at an early stage
677///         of Hensel lifting
678/// @sa earlyFactorDetection(), extEarlyFactorDetection()
679
680CFList
681henselLiftAndEarly (
682        CanonicalForm& A,          ///< [in,out] poly to be factored,
683                                   ///< returns poly divided by detected factors
684                                   ///< in case of success
685        bool& earlySuccess,        ///< [in,out] indicating success
686        CFList& earlyFactors,      ///< [in,out] list of factors detected
687                                   ///< at early stage of Hensel lifting
688        DegreePattern& degs,       ///< [in,out] degree pattern
689        int& liftBound,            ///< [in,out] (adapted) lift bound
690        const CFList& uniFactors,  ///< [in] univariate factors
691        const ExtensionInfo& info, ///< [in] information about extension
692        const CanonicalForm& eval  ///< [in] evaluation point
693                  );
694
695/// Factorization over an extension of initial field
696///
697/// @return @a extBiFactorize returns factorization of F over initial field
698/// @sa biFactorize()
699CFList
700extBiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
701                const ExtensionInfo& info  ///< [in] info about extension
702               );
703
704#endif
705#endif
706/* FAC_FQ_BIVAR_H */
707
Note: See TracBrowser for help on using the repository browser.