# source:git/factory/facFqSquarefree.h@8baf483

jengelh-datetimespielwiese
Last change on this file since 8baf483 was 6caa2a6, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: avoid adding of constant factors to squarefree factorization chg: divide out contents first in squarefree factorization
• 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 * @internal @version \$Id$
12 *
13 **/
14/*****************************************************************************/
15
16#ifndef FAC_FQ_SQUAREFREE_H
17#define FAC_FQ_SQUAREFREE_H
18
19#include "cf_assert.h"
20#include "cf_factory.h"
21#include "fac_sqrfree.h"
22
23/// squarefree factorization over a finite field
24/// @a return a list of squarefree factors with multiplicity
25CFFList
26squarefreeFactorization
27                (const CanonicalForm & F, ///<[in] a poly
28                 const Variable & alpha   ///<[in] either an algebraic variable,
29                                          ///< i.e. we are over some F_p (alpha)
30                                          ///< or a variable of level 1, i.e.
31                                          ///< we are F_p or GF
32                );
33
34/// squarefree factorization over \f$F_{p} \f$.
35/// If input is not monic, the leading coefficient is dropped
36///
37/// @return a list of squarefree factors with multiplicity
38inline
39CFFList FpSqrf (const CanonicalForm& F, ///< [in] a poly
40                bool sort= true         ///< [in] sort factors by exponent?
41               )
42{
43  Variable a= 1;
44  int n= F.level();
45  CanonicalForm cont, bufF= F;
46  CFFList bufResult;
47
48  CFFList result;
49  for (int i= n; i >= 1; i++)
50  {
51    cont= content (bufF, i);
52    bufResult= squarefreeFactorization (cont, a);
53    if (bufResult.getFirst().factor().inCoeffDomain())
54      bufResult.removeFirst();
55    result= Union (result, bufResult);
56    bufF /= cont;
57    if (bufF.inCoeffDomain())
58      break;
59  }
60  if (!bufF.inCoeffDomain())
61  {
62    bufResult= squarefreeFactorization (bufF, a);
63    if (bufResult.getFirst().factor().inCoeffDomain())
64      bufResult.removeFirst();
65    result= Union (result, bufResult);
66  }
67  if (sort)
68    result= sortCFFList (result);
69  result.insert (CFFactor (Lc(F), 1));
70  return result;
71}
72
73/// squarefree factorization over \f$F_{p}(\alpha ) \f$.
74/// If input is not monic, the leading coefficient is dropped
75///
76/// @return a list of squarefree factors with multiplicity
77inline
78CFFList FqSqrf (const CanonicalForm& F, ///< [in] a poly
79                const Variable& alpha,  ///< [in] algebraic variable
80                bool sort= true         ///< [in] sort factors by exponent?
81               )
82{
83  int n= F.level();
84  CanonicalForm cont, bufF= F;
85  CFFList bufResult;
86
87  CFFList result;
88  for (int i= n; i >= 1; i++)
89  {
90    cont= content (bufF, i);
91    bufResult= squarefreeFactorization (cont, alpha);
92    if (bufResult.getFirst().factor().inCoeffDomain())
93      bufResult.removeFirst();
94    result= Union (result, bufResult);
95    bufF /= cont;
96    if (bufF.inCoeffDomain())
97      break;
98  }
99  if (!bufF.inCoeffDomain())
100  {
101    bufResult= squarefreeFactorization (bufF, alpha);
102    if (bufResult.getFirst().factor().inCoeffDomain())
103      bufResult.removeFirst();
104    result= Union (result, bufResult);
105  }
106  if (sort)
107    result= sortCFFList (result);
108  result.insert (CFFactor (Lc(F), 1));
109  return result;
110}
111
112/// squarefree factorization over GF.
113/// If input is not monic, the leading coefficient is dropped
114///
115/// @return a list of squarefree factors with multiplicity
116inline
117CFFList GFSqrf (const CanonicalForm& F, ///< [in] a poly
118                bool sort= true         ///< [in] sort factors by exponent?
119               )
120{
121  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
122          "GF as base field expected");
123  return FpSqrf (F, sort);
124}
125
126/// squarefree part of @a F/g, where g is the product of those squarefree
127/// factors whose multiplicity is 0 mod p, if @a F a pth power pthPower= F.
128///
129/// @return @a sqrfPart returns 1, if F is a pthPower, else it returns the
130///         squarefree part of @a F/g, where g is the product of those
131///         squarefree factors whose multiplicity is 0 mod p
132CanonicalForm
133sqrfPart (const CanonicalForm& F,  ///< [in] a poly
134          CanonicalForm& pthPower, ///< [in,out] returns F is F is a pthPower
135          const Variable& alpha    ///< [in] algebraic variable
136         );
137
138/// p^l-th root extraction, where l is maximal
139///
140/// @return @a maxpthRoot returns a p^l-th root of @a F, where @a l is maximal
141/// @sa pthRoot()
142CanonicalForm
143maxpthRoot (const CanonicalForm & F, ///< [in] a poly which is a pth power
144            const int & q,           ///< [in] size of the field
145            int& l                   ///< [in,out] @a l maximal, s.t. @a F is
146                                     ///< a p^l-th power
147           );
148
149#endif
150/* FAC_FQ_SQUAREFREE_H */
151
Note: See TracBrowser for help on using the repository browser.