source: git/factory/facFqBivar.h @ 2537fa0

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