source: git/factory/facFqBivar.h @ 3c702a

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