source: git/factory/facFqSquarefree.h @ 0dff6bc

spielwiese
Last change on this file since 0dff6bc was 72f1e4b, checked in by Martin Lee <martinlee84@…>, 12 years ago
fix: several issues with --enable-assertions
  • Property mode set to 100644
File size: 4.7 KB
Line 
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
24CFFList
25squarefreeFactorization
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
47  CFFList result;
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)
67    result= sortCFFList (result);
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
86  CFFList result;
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)
106    result= sortCFFList (result);
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{
120  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
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
131CanonicalForm
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()
141CanonicalForm
142maxpthRoot (const CanonicalForm & F, ///< [in] a poly which is a pth power
143            const 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
Note: See TracBrowser for help on using the repository browser.