My Project  debian-1:4.1.1-p2+ds-4build4
facFqSquarefree.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqSquarefree.h
5  *
6  * This file provides functions for squarefrees factorizing 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_SQUAREFREE_H
15 #define FAC_FQ_SQUAREFREE_H
16 
17 #include "cf_assert.h"
18 #include "cf_factory.h"
19 #include "fac_sqrfree.h"
20 #include "cf_factory.h"
21 
22 /// squarefree factorization over a finite field
23 /// @a return a list of squarefree factors with multiplicity
24 CFFList
26  (const CanonicalForm & F, ///<[in] a poly
27  const Variable & alpha ///<[in] either an algebraic variable,
28  ///< i.e. we are over some F_p (alpha)
29  ///< or a variable of level 1, i.e.
30  ///< we are F_p or GF
31  );
32 
33 /// squarefree factorization over \f$ F_{p} \f$.
34 /// If input is not monic, the leading coefficient is dropped
35 ///
36 /// @return a list of squarefree factors with multiplicity
37 inline
38 CFFList FpSqrf (const CanonicalForm& F, ///< [in] a poly
39  bool sort= true ///< [in] sort factors by exponent?
40  )
41 {
42  Variable a= 1;
43  int n= F.level();
44  CanonicalForm cont, bufF= F;
45  CFFList bufResult;
46 
48  for (int i= n; i >= 1; i++)
49  {
50  cont= content (bufF, i);
51  bufResult= squarefreeFactorization (cont, a);
52  if (bufResult.getFirst().factor().inCoeffDomain())
53  bufResult.removeFirst();
54  result= Union (result, bufResult);
55  bufF /= cont;
56  if (bufF.inCoeffDomain())
57  break;
58  }
59  if (!bufF.inCoeffDomain())
60  {
61  bufResult= squarefreeFactorization (bufF, a);
62  if (bufResult.getFirst().factor().inCoeffDomain())
63  bufResult.removeFirst();
64  result= Union (result, bufResult);
65  }
66  if (sort)
68  result.insert (CFFactor (Lc(F), 1));
69  return result;
70 }
71 
72 /// squarefree factorization over \f$ F_{p}(\alpha ) \f$.
73 /// If input is not monic, the leading coefficient is dropped
74 ///
75 /// @return a list of squarefree factors with multiplicity
76 inline
77 CFFList FqSqrf (const CanonicalForm& F, ///< [in] a poly
78  const Variable& alpha, ///< [in] algebraic variable
79  bool sort= true ///< [in] sort factors by exponent?
80  )
81 {
82  int n= F.level();
83  CanonicalForm cont, bufF= F;
84  CFFList bufResult;
85 
87  for (int i= n; i >= 1; i++)
88  {
89  cont= content (bufF, i);
90  bufResult= squarefreeFactorization (cont, alpha);
91  if (bufResult.getFirst().factor().inCoeffDomain())
92  bufResult.removeFirst();
93  result= Union (result, bufResult);
94  bufF /= cont;
95  if (bufF.inCoeffDomain())
96  break;
97  }
98  if (!bufF.inCoeffDomain())
99  {
100  bufResult= squarefreeFactorization (bufF, alpha);
101  if (bufResult.getFirst().factor().inCoeffDomain())
102  bufResult.removeFirst();
103  result= Union (result, bufResult);
104  }
105  if (sort)
107  result.insert (CFFactor (Lc(F), 1));
108  return result;
109 }
110 
111 /// squarefree factorization over GF.
112 /// If input is not monic, the leading coefficient is dropped
113 ///
114 /// @return a list of squarefree factors with multiplicity
115 inline
116 CFFList GFSqrf (const CanonicalForm& F, ///< [in] a poly
117  bool sort= true ///< [in] sort factors by exponent?
118  )
119 {
121  "GF as base field expected");
122  return FpSqrf (F, sort);
123 }
124 
125 /// squarefree part of @a F/g, where g is the product of those squarefree
126 /// factors whose multiplicity is 0 mod p, if @a F a pth power pthPower= F.
127 ///
128 /// @return @a sqrfPart returns 1, if F is a pthPower, else it returns the
129 /// squarefree part of @a F/g, where g is the product of those
130 /// squarefree factors whose multiplicity is 0 mod p
132 sqrfPart (const CanonicalForm& F, ///< [in] a poly
133  CanonicalForm& pthPower, ///< [in,out] returns F is F is a pthPower
134  const Variable& alpha ///< [in] algebraic variable
135  );
136 
137 /// p^l-th root extraction, where l is maximal
138 ///
139 /// @return @a maxpthRoot returns a p^l-th root of @a F, where @a l is maximal
140 /// @sa pthRoot()
142 maxpthRoot (const CanonicalForm & F, ///< [in] a poly which is a pth power
143  int q, ///< [in] size of the field
144  int& l ///< [in,out] @a l maximal, s.t. @a F is
145  ///< a p^l-th power
146  );
147 
148 #endif
149 /* FAC_FQ_SQUAREFREE_H */
150 
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int l
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:125
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:22
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
static int gettype()
Definition: cf_factory.h:28
factory's main class
Definition: canonicalform.h:83
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
factory's class for variables
Definition: factory.h:118
Variable alpha
Definition: facAbsBiFact.cc:52
return result
Definition: facAbsBiFact.cc:76
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
CanonicalForm maxpthRoot(const CanonicalForm &F, int q, int &l)
p^l-th root extraction, where l is maximal
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CanonicalForm sqrfPart(const CanonicalForm &F, CanonicalForm &pthPower, const Variable &alpha)
squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mo...
void sort(CFArray &A, int l=0)
quick sort A
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
squarefree part and factorization over Q, Q(a)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)