source: git/factory/facFqBivar.h @ 7a1151

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