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

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