source: git/factory/facFqSquarefree.cc @ 72ebdb

spielwiese
Last change on this file since 72ebdb was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 5.6 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqSquarefree.cc
5 *
6 * This file provides functions for squarefrees factorizing over
7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, as decribed in "Factoring
8 * multivariate polynomials over a finite field" by L. Bernardin
9 *
10 * @author Martin Lee
11 *
12 * @internal @version \$Id$
13 *
14 **/
15/*****************************************************************************/
16
17#include "config.h"
18
19#include "canonicalform.h"
20
21#include "cf_gcd_smallp.h"
22#include "cf_iter.h"
23#include "cf_map.h"
24#include "cf_util.h"
25#include "cf_factory.h"
26#include "facFqSquarefree.h"
27
28static inline
29CanonicalForm
30pthRoot (const CanonicalForm & F, const int & q)
31{
32  CanonicalForm A= F;
33  int p= getCharacteristic ();
34  if (A.inCoeffDomain())
35  {
36    A= power (A, q/p);
37    return A;
38  }
39  else
40  {
41    CanonicalForm buf= 0;
42    for (CFIterator i= A; i.hasTerms(); i++)
43      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q);
44    return buf;
45  }
46}
47
48CanonicalForm
49maxpthRoot (const CanonicalForm & F, const int & q, int& l)
50{
51  CanonicalForm result= F;
52  bool derivZero= true;
53  l= 0;
54  while (derivZero)
55  {
56    for (int i= 1; i <= result.level(); i++)
57    {
58      if (!deriv (result, Variable (i)).isZero())
59      {
60        derivZero= false;
61        break;
62      }
63    }
64    if (!derivZero)
65      break;
66    result= pthRoot (result, q);
67    l++;
68  }
69  return result;
70}
71
72static inline
73CFFList
74sqrfPosDer (const CanonicalForm & F, const Variable & x,
75            CanonicalForm & c)
76{
77  CanonicalForm b= deriv (F, x);
78  c= gcd (F, b);
79  CanonicalForm w= F/c;
80  CanonicalForm v= b/c;
81  CanonicalForm u= v - deriv (w, x);
82  int j= 1;
83  int p= getCharacteristic();
84  CanonicalForm g;
85  CFFList result;
86  while (j < p - 1 && degree(u) >= 0)
87  {
88    g= gcd (w, u);
89    if (degree(g) > 0)
90      result.append (CFFactor (g, j));
91    w= w/g;
92    c= c/w;
93    v= u/g;
94    u= v - deriv (w, x);
95    j++;
96  }
97  if (degree(w) > 0)
98    result.append (CFFactor (w, j));
99  return result;
100}
101
102CFFList
103squarefreeFactorization (const CanonicalForm & F, const Variable & alpha)
104{
105  int p= getCharacteristic();
106  CanonicalForm A= F;
107  CFMap M;
108  A= compress (A, M);
109  Variable x= A.mvar();
110  int l= x.level();
111  int k;
112  bool GF= false;
113  if (CFFactory::gettype() == GaloisFieldDomain)
114    k= getGFDegree();
115  else if (alpha.level() != 1)
116    k= degree (getMipo (alpha));
117  else
118    k= 1;
119  Variable buf, buf2;
120  CanonicalForm tmp;
121
122  CFFList tmp1, tmp2;
123  bool found;
124  for (int i= l; i > 0; i--)
125  {
126    buf= Variable (i);
127    if (degree (deriv (A, buf)) >= 0)
128    {
129      tmp1= sqrfPosDer (A, buf, tmp);
130      A= tmp;
131      for (CFFListIterator j= tmp1; j.hasItem(); j++)
132      {
133        found= false;
134        CFFListIterator k= tmp2;
135        if (!k.hasItem()) tmp2.append (j.getItem());
136        else
137        {
138          for (; k.hasItem(); k++)
139          {
140            if (k.getItem().exp() == j.getItem().exp())
141            {
142              k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
143                                     j.getItem().exp());
144              found= true;
145            }
146          }
147          if (found == false)
148            tmp2.append(j.getItem());
149        }
150      }
151    }
152  }
153
154  bool degcheck= false;;
155  for (int i= l; i > 0; i--)
156  if (degree (A, Variable(i)) >= p)
157    degcheck= true;
158
159  if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
160    return CFFList (CFFactor (F/Lc(F), 1));
161
162  CanonicalForm buffer= pthRoot (A, ipower (p, k));
163
164  tmp1= squarefreeFactorization (buffer, alpha);
165
166  CFFList result;
167  buf= alpha;
168  for (CFFListIterator i= tmp2; i.hasItem(); i++)
169  {
170    for (CFFListIterator j= tmp1; j.hasItem(); j++)
171    {
172      tmp= gcd (i.getItem().factor(), j.getItem().factor());
173      i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
174      j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
175      if (degree (tmp) > 0 && tmp.level() > 0)
176        result.append (CFFactor (M (tmp),
177                       j.getItem().exp()*p + i.getItem().exp()));
178    }
179  }
180  for (CFFListIterator i= tmp2; i.hasItem(); i++)
181    if (degree (i.getItem().factor()) > 0 && i.getItem().factor().level() >= 0)
182      result.append (CFFactor (M (i.getItem().factor()), i.getItem().exp()));
183  for (CFFListIterator j= tmp1; j.hasItem(); j++)
184    if (degree (j.getItem().factor()) > 0 && j.getItem().factor().level() >= 0)
185      result.append (CFFactor (M (j.getItem().factor()), j.getItem().exp()*p));
186  return result;
187}
188
189CanonicalForm
190sqrfPart (const CanonicalForm& F, CanonicalForm& pthPower,
191          const Variable& alpha)
192{
193  if (F.inCoeffDomain())
194  {
195    pthPower= 1;
196    return F;
197  }
198  CFMap M;
199  CanonicalForm A= compress (F, M);
200  Variable vBuf= alpha;
201  CanonicalForm w, v, b;
202  pthPower= 1;
203  CanonicalForm result;
204  int i= 1;
205  bool allZero= true;
206  for (; i <= A.level(); i++)
207  {
208    if (!deriv (A, Variable (i)).isZero())
209    {
210      allZero= false;
211      break;
212    }
213  }
214  if (allZero)
215  {
216    pthPower= F;
217    return 1;
218  }
219  w= gcd (A, deriv (A, Variable (i)));
220
221  b= A/w;
222  result= b;
223  if (degree (w) < 1)
224    return M (result);
225  i++;
226  for (; i <= A.level(); i++)
227  {
228    if (!deriv (w, Variable (i)).isZero())
229    {
230      b= w;
231      w= gcd (w, deriv (w, Variable (i)));
232      b /= w;
233      if (degree (b) < 1)
234        break;
235      CanonicalForm g;
236      g= gcd (b, result);
237      if (degree (g) > 0)
238        result *= b/g;
239      if (degree (g) <= 0)
240        result *= b;
241    }
242  }
243  result= M (result);
244  return result;
245}
246
Note: See TracBrowser for help on using the repository browser.