My Project
Loading...
Searching...
No Matches
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
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
37inline
38CFFList 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
76inline
77CFFList 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
115inline
116CFFList 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
132sqrfPart (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()
142maxpthRoot (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 FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm Lc(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
static void sort(int **points, int sizePoints)
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
#define GaloisFieldDomain
Definition: cf_defs.h:18
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:86
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: variable.h:33
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
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...
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
squarefree part and factorization over Q, Q(a)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)