source: git/factory/libfac/factor/Truefactor.cc @ e3198f

spielwiese
Last change on this file since e3198f was d92d71, checked in by Oleksandr Motsak <motsak@…>, 12 years ago
build libfac.a into factory FIX: libfac builds and uses factory/factory.h FIX: adaptation of Singular to use libfac staff
  • Property mode set to 100644
File size: 12.7 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2// emacs edit mode for this file is -*- C++ -*-
3// $Id$
4///////////////////////////////////////////////////////////////////////////////
5// Factory - Includes
6#include <factory.h>
7#ifndef NOSTREAMIO
8#ifdef HAVE_IOSTREAM
9#include <iostream>
10#define OSTREAM std::ostream
11#define ISTREAM std::istream
12#define CERR std::cerr
13#define CIN std::cin
14#elif defined(HAVE_IOSTREAM_H)
15#include <iostream.h>
16#define OSTREAM ostream
17#define ISTREAM istream
18#define CERR cerr
19#define CIN cin
20#endif
21#endif
22// Factor - Includes
23#include "tmpl_inst.h"
24#include "helpstuff.h"
25// some CC's need this:
26#include "Truefactor.h"
27
28#ifdef TRUEFACTORDEBUG
29#  define DEBUGOUTPUT
30#else
31#  undef DEBUGOUTPUT
32#endif
33
34#include <libfac/factor/debug.h>
35#include "timing.h"
36
37int hasAlgVar(const CanonicalForm &f, const Variable &v)
38{
39  if (f.inBaseDomain()) return 0;
40  if (f.inCoeffDomain())
41  {
42    if (f.mvar()==v) return 1;
43    return hasAlgVar(f.LC(),v);
44  }
45  if (f.inPolyDomain())
46  {
47    if (hasAlgVar(f.LC(),v)) return 1;
48    for( CFIterator i=f; i.hasTerms(); i++)
49    {
50      if (hasAlgVar(i.coeff(),v)) return 1;
51    }
52  }
53  return 0;
54}
55
56int hasVar(const CanonicalForm &f, const Variable &v)
57{
58  if (f.inBaseDomain()) return 0;
59  if (f.inCoeffDomain())
60  {
61    if (f.mvar()==v) return 1;
62    return hasAlgVar(f.LC(),v);
63  }
64  if (f.inPolyDomain())
65  {
66    if (f.mvar()==v) return 1;
67    if (hasVar(f.LC(),v)) return 1;
68    for( CFIterator i=f; i.hasTerms(); i++)
69    {
70      if (hasVar(i.coeff(),v)) return 1;
71    }
72  }
73  return 0;
74}
75
76int hasAlgVar(const CanonicalForm &f)
77{
78  if (f.inBaseDomain()) return 0;
79  if (f.inCoeffDomain())
80  {
81    if (f.level()!=0)
82    {
83      //CERR << "hasAlgVar:" << f.mvar() <<"\n";
84      return 1;
85    }
86    return hasAlgVar(f.LC());
87  }
88  if (f.inPolyDomain())
89  {
90    if (hasAlgVar(f.LC())) return 1;
91    for( CFIterator i=f; i.hasTerms(); i++)
92    {
93      if (hasAlgVar(i.coeff())) return 1;
94    }
95  }
96  return 0;
97}
98
99///////////////////////////////////////////////////////////////
100// generate all different k-subsets of the set with n        //
101// elements and return them in returnlist.                   //
102///////////////////////////////////////////////////////////////
103static void
104combinat( int k, int n, List<IntList> & returnlist ){
105  ListIntList ListofLists;
106  IntList intermediate,intermediate2;
107  int value,j;
108
109  if ( k == 1 ){                     // k=1
110    for ( j=1; j<=n; j++)
111      returnlist.append( IntList(j) );
112  }
113  else{                              // k-1 --> k
114    combinat(k-1,n,returnlist);  // generate (k-1,n)
115    for ( ListIntListIterator l=returnlist; l.hasItem(); l++ ){
116      intermediate = l.getItem();
117      value = intermediate.getLast();
118      if ( value != n )
119        for ( j=value+1; j<=n; j++ ){
120          intermediate2 = intermediate; intermediate2.append(j);
121          ListofLists.append( intermediate2 );
122        }
123    }
124    returnlist = ListofLists;
125  }
126}
127
128///////////////////////////////////////////////////////////////
129// Return the CanonicalForm number nr in  Factorlist.        //
130///////////////////////////////////////////////////////////////
131static CanonicalForm
132getItemNr(int nr, const CFFList & Factorlist ){
133  ListIterator<CFFactor> i=Factorlist;
134  int Nr=nr;
135
136  for ( Nr=1; Nr<nr; Nr++ ) i++;
137  return i.getItem().factor();
138}
139
140///////////////////////////////////////////////////////////////
141// Generate all sets of m factors out of LiftedFactors list. //
142///////////////////////////////////////////////////////////////
143static CFFList
144combine( int m, const CFFList & LiftedFactors ){
145  CFFList result;
146  ListIntList CombinatList;
147  CanonicalForm intermediate;
148
149  combinat(m, LiftedFactors.length(), CombinatList);
150  for ( ListIntListIterator j=CombinatList ; j.hasItem(); j++ ){
151    intermediate=1;
152    for ( IntListIterator k=j.getItem(); k.hasItem(); k++ )
153      intermediate *= getItemNr(k.getItem(), LiftedFactors);
154    if (!hasAlgVar(intermediate))
155    result.append(CFFactor(intermediate,1));
156  }
157  return result;
158}
159
160///////////////////////////////////////////////////////////////
161// Remove element elem from the list L.                      //
162///////////////////////////////////////////////////////////////
163static CFFList
164Remove_from_List( const CFFList & L, const CanonicalForm & elem ){
165  CFFList Returnlist;
166
167  DEBOUTLN(CERR, "Remove_from_List called with L= ",L);
168  DEBOUTLN(CERR, "                     and  elem= ",elem);
169  for ( ListIterator<CFFactor> i = L ; i.hasItem(); i++)
170    if ( i.getItem().factor() != elem )
171      Returnlist.append( i.getItem() );
172
173  return Returnlist;
174}
175
176///////////////////////////////////////////////////////////////
177// Here we solve:          G= F mod ( P, S^h )               //
178///////////////////////////////////////////////////////////////
179static CanonicalForm
180Multmod_power( const CanonicalForm & F, const SFormList & Substituionlist, int h, int levelF){
181  CanonicalForm G;
182
183  G= change_poly(F, Substituionlist, 0);
184  G= mod_power(G, h, levelF);
185  G= change_poly(G, Substituionlist, 1);
186
187  return G;
188}
189
190///////////////////////////////////////////////////////////////
191// Determine the right degree for the list of combinations   //
192// of factors, i.e. delete any element from list CombL which //
193// degree in the main variable levelU exceeeds degU.         //
194///////////////////////////////////////////////////////////////
195static CFFList
196Rightdegree( const CFFList & CombL, int degU, int levelU ){
197  CFFList Returnlist;
198  CFFactor factor;
199
200  for ( ListIterator<CFFactor> i= CombL; i.hasItem(); i++ ){
201    factor= i.getItem();
202    if ( degree(factor.factor(), levelU) <= degU )
203      Returnlist.append(factor);
204  }
205
206  return Returnlist;
207}
208
209///////////////////////////////////////////////////////////////
210// We have properly lifted all the specialized factors. See  //
211// which one works.                                          //
212// We use the (modified) algorithm TRUEFACTORS given by      //
213// Paul S. Wang and Linda Preiss Rothschild:                 //
214// Factoring Multivariate Polynomials Over the Integers      //
215// Math. Comp. V29 Nr131 (July 1975) p. 935-950              //
216///////////////////////////////////////////////////////////////
217CFFList
218Truefactors( const CanonicalForm Ua, int levelU, const SFormList & SubstitutionList, const CFFList & PiList){
219  CanonicalForm U=Ua,a,b,Y;
220  CFFactor factor;
221  CFFList L,FAC,E_all;
222  int c,r = PiList.length(),degU, onemore,M, h = subvardegree(Ua,levelU) + 1;
223  ListIterator<CFFactor> i;
224
225  //CERR << "SubstitutionList="<< SubstitutionList<<"\n";
226// step 1: simply test the generated factors alone
227  for ( i= PiList; i.hasItem();i++){
228    factor = i.getItem();
229    //CanonicalForm test_f=change_poly(factor.factor(),SubstitutionList,0);
230    CanonicalForm test_f=factor.factor();
231    //CERR <<"f:" << factor.factor() << " -> test_f:"<<test_f <<"\n";
232    //CERR << "           1:" << change_poly(factor.factor(),SubstitutionList,1) <<"\n";
233    c= mydivremt(U,test_f,a,b);
234    if (  c  && b == U.genZero() && !hasAlgVar(test_f))
235    // factor.getFactor() divides U
236    {
237      //CERR << " teilt:" << test_f <<"\n";
238      U= a;
239      FAC.append(factor);
240    }
241    else{
242      //CERR << " teilt nicht:" << test_f <<"\n";
243      L.append(factor);
244    }
245  }
246  DEBOUTLN(CERR,"Truefactors: (step1) L  = ", L);
247  DEBOUTLN(CERR,"                     FAC= ", FAC);
248
249// step 2: Do we have to check combinations?
250  degU = L.length();
251  if ( degU == 0 ) // No elements: Return
252    return FAC;
253  else
254    if ( degU < 4 ){ // Less then four elements: no combinations possible
255      FAC.append( CFFactor(U,1) );
256      return FAC;
257    }
258    else {
259      M = 1; r = r - FAC.length(); degU = degree(U, levelU)/2;
260    }
261
262  DEBOUTLN(CERR,"Truefactors: (step2) M   = ", M);
263  DEBOUTLN(CERR,"                     r   = ", r);
264  DEBOUTLN(CERR,"                     degU= ", degU);
265
266// Now do the real work!
267// Test all the combinations of possible factors.
268
269  onemore=1;
270// steps 3 to 6
271  while (1)
272  {
273    // step 3 iff onemore == 1
274    if ( onemore ) M+= 1;  else onemore = 1;
275    // step 4
276    if ( U.isOne() ) break; // Return FAC
277    if ( ( r == 1 ) || ( M >= ( r-1 ) ) || ( M > degU ) )
278    {
279      FAC.append( CFFactor(U,1) );
280      break; // Return FAC union {U}
281    }
282    // step 5
283    E_all = combine(M, L); // generate all combinations of M elements from L
284    DEBOUTLN(CERR,"Truefactors: (step5) E_all= ", E_all);
285    // select combinations with the degree not to exceed degU:
286    E_all = Rightdegree( E_all, degU, levelU );
287    DEBOUTLN(CERR,"Truefactors: (step5) E_all(Rightdegree)= ", E_all);
288    if ( E_all.length() == 0 )
289    {
290      FAC.append( CFFactor(U,1) );
291      break; // Return FAC union {U}
292    }
293    for ( i=E_all; i.hasItem(); i++)
294    {
295      factor = i.getItem();
296      Y = Multmod_power( factor.factor(), SubstitutionList, h, levelU);
297      DEBOUTLN(CERR, "Truefactors: (step6) Testing Y  = ", Y);
298      c = mydivremt(U,Y,a,b);
299      //      if (  c  && b == U.genZero()) { // Y divides U
300      if ( c && b.isZero() )
301      {
302        DEBOUT(CERR,"Truefactors: (step6): ",Y );
303        DEBOUTLN(CERR, "  divides  ",U);
304        U = a;
305        FAC.append(Y); // Y is a real factor
306        onemore = 0;
307        degU = degree(U, levelU)/2; // new degU
308        // L = L \ {factor}
309        // Hier ist noch etwas faul; wir muessen (f=prod(f_i)) die f_i
310        // entfernen und nicht f!
311        L = Remove_from_List( L, factor.factor() );
312        r -= 1;
313        // delete from L any element with degree greater than degU
314        L = Rightdegree( L, degU, levelU );
315      }
316    }
317  }
318  return FAC;
319}
320
321///////////////////////////////////////////////////////////////
322// Check if poly f is in Fp (returns true) or in Fp(a)       //
323///////////////////////////////////////////////////////////////
324static bool is_in_Fp( const CanonicalForm & f )
325{
326  if ( f.inCoeffDomain() )
327    return f.inBaseDomain() ;
328  else
329  {
330    CFIterator i=f;
331    bool ok=true;
332    while ( ok && i.hasTerms() )
333    {
334      ok = is_in_Fp( i.coeff() );
335      i++ ;
336    }
337    return ok;
338  }
339}
340
341///////////////////////////////////////////////////////////////
342// We have factors which possibly lie in an extension of the //
343// base field. If one of these is not over the base field,   //
344// find its norm by (the theoretically handicapped method    //
345// of) multiplying by other elements.                        //
346///////////////////////////////////////////////////////////////
347CFFList TakeNorms(const CFFList & PiList)
348{
349  CFFList CopyPossibleFactors, PossibleFactors, TrueFactors;
350  CFFListIterator i;
351  CFFactor Factor;
352  CanonicalForm intermediate;
353  ListIntList CombinatList;
354  ListIntListIterator j;
355  IntListIterator k;
356
357  // First check if the factors in PiList already lie in Fp-Domain
358  for ( i=PiList; i.hasItem(); i++ )
359  {
360    Factor = i.getItem();
361    if ( is_in_Fp( Factor.factor() ) )
362      TrueFactors.append(Factor);
363    else
364      PossibleFactors.append(Factor);
365  }
366  // Now we have to check if combinations of the remaining factors
367  // (now in PossibleFactors) do lie in Fp-Domain
368  if ( PossibleFactors.length() > 0 ) // there are (at least two) items
369  {
370    int n=2;
371    if ( PossibleFactors.length() < n )  // a little check
372    {
373      factoryError("libfac: ERROR: TakeNorms less then two items remaining!");
374    }
375    while ( n < PossibleFactors.length() )
376    {
377      // generate all combinations of n elements
378      combinat(n, PossibleFactors.length(), CombinatList);
379      for ( j=CombinatList ; j.hasItem(); j++ )
380      {
381        intermediate=1;
382        for ( k=j.getItem(); k.hasItem(); k++ )
383          intermediate *= getItemNr( k.getItem(), PossibleFactors );
384        if ( is_in_Fp( intermediate ) )
385        {
386          TrueFactors.append(intermediate); // found a true factor
387          CopyPossibleFactors=PossibleFactors; // save list
388          for ( k=j.getItem(); k.hasItem(); k++ )
389            //remove combined factors from PossibleFactors
390            PossibleFactors=Remove_from_List(PossibleFactors,
391                                getItemNr( k.getItem(), CopyPossibleFactors ));
392          n-=1; // look for the same number of combined factors:
393          break;
394        }
395        else
396        {
397          //CERR << "Schade!" << "\n";
398        }
399        DEBOUT(CERR, "Truefactor: Combined ", n);
400        DEBOUTLN(CERR, " factors to: ", intermediate);
401      }
402      n += 1;
403    }
404  // All remaining factors in PossibleFactors multiplied
405  // should lie in Fp domain
406    if ( PossibleFactors.length() >=1 )
407    {
408      for ( i=PossibleFactors; i.hasItem(); i++ )
409        intermediate *= i.getItem().factor();
410      // a last check:
411      if ( is_in_Fp(intermediate) )
412      {
413        TrueFactors.append(CFFactor(intermediate,1));
414      }
415      else
416      {
417        factoryError("libfac: TakeNorms: somethings wrong with remaining factors!");
418      }
419    }
420  }
421  return TrueFactors;
422}
423
424////////////////////////////////////////////////////////////
Note: See TracBrowser for help on using the repository browser.