My Project  debian-1:4.1.1-p2+ds-4build2
Functions | Variables
facBivar.cc File Reference
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "cf_algorithm.h"
#include "facFqBivar.h"
#include "facBivar.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_primes.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_uni_factorizer) TIMING_DEFINE_PRINT(fac_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_bi_evaluation) TIMING_DEFINE_PRINT(fac_bi_shift_to_zero) modpk coeffBound(const CanonicalForm &f
 
 for (i=1;i<=k;i++)
 
 DELETE_ARRAY (degs)
 
 while (B< b)
 
return modpk (p, k)
 
void findGoodPrime (const CanonicalForm &f, int &start)
 find a big prime p from our tables such that no term of f vanishes mod p More...
 
modpk coeffBound (const CanonicalForm &f, int p, const CanonicalForm &mipo)
 compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo) More...
 
CFList conv (const CFFList &L)
 convert a CFFList to a CFList by dropping the multiplicity More...
 
bool testPoint (const CanonicalForm &F, CanonicalForm &G, int i)
 
CanonicalForm evalPoint (const CanonicalForm &F, int &i)
 
CFList biFactorize (const CanonicalForm &F, const Variable &v)
 

Variables

int p
 
int M = 0
 
int i
 
int k = f.level()
 
CanonicalForm b = 1
 
b *CanonicalForm B = p
 

Detailed Description

bivariate factorization over Q(a)

Author
Martin Lee

Definition in file facBivar.cc.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm F,
const Variable v 
)

Definition at line 187 of file facBivar.cc.

188 {
189  if (F.inCoeffDomain())
190  return CFList(F);
191 
192  bool extension= (v.level() != 1);
194  if (isOn (SW_RATIONAL))
195  A= F*bCommonDen (F);
196  else
197  A= F;
198 
200  if (extension)
201  mipo= getMipo (v);
202 
203  if (A.isUnivariate())
204  {
205  CFFList buf;
206  if (extension)
207  buf= factorize (A, v);
208  else
209  buf= factorize (A, true);
210  CFList result= conv (buf);
211  if (result.getFirst().inCoeffDomain())
212  result.removeFirst();
213  return result;
214  }
215 
216  CFMap N;
217  A= compress (A, N);
218  Variable y= A.mvar();
219 
220  if (y.level() > 2) return CFList (F);
221  Variable x= Variable (1);
222 
223  CanonicalForm contentAx= content (A, x);
224  CanonicalForm contentAy= content (A);
225 
226  A= A/(contentAx*contentAy);
227  CFFList contentAxFactors, contentAyFactors;
228 
229  if (extension)
230  {
231  if (!contentAx.inCoeffDomain())
232  {
233  contentAxFactors= factorize (contentAx, v);
234  if (contentAxFactors.getFirst().factor().inCoeffDomain())
235  contentAxFactors.removeFirst();
236  }
237  if (!contentAy.inCoeffDomain())
238  {
239  contentAyFactors= factorize (contentAy, v);
240  if (contentAyFactors.getFirst().factor().inCoeffDomain())
241  contentAyFactors.removeFirst();
242  }
243  }
244  else
245  {
246  if (!contentAx.inCoeffDomain())
247  {
248  contentAxFactors= factorize (contentAx, true);
249  if (contentAxFactors.getFirst().factor().inCoeffDomain())
250  contentAxFactors.removeFirst();
251  }
252  if (!contentAy.inCoeffDomain())
253  {
254  contentAyFactors= factorize (contentAy, true);
255  if (contentAyFactors.getFirst().factor().inCoeffDomain())
256  contentAyFactors.removeFirst();
257  }
258  }
259 
260  //check trivial case
261  if (degree (A) == 1 || degree (A, 1) == 1 ||
262  (size (A) == 2 && igcd (degree (A), degree (A,1)) == 1))
263  {
264  CFList factors;
265  factors.append (A);
266 
267  appendSwapDecompress (factors, conv (contentAxFactors),
268  conv (contentAyFactors), false, false, N);
269 
270  normalize (factors);
271  return factors;
272  }
273 
274  //trivial case
275  CFList factors;
276  if (A.inCoeffDomain())
277  {
278  append (factors, conv (contentAxFactors));
279  append (factors, conv (contentAyFactors));
280  decompress (factors, N);
281  return factors;
282  }
283  else if (A.isUnivariate())
284  {
285  if (extension)
286  factors= conv (factorize (A, v));
287  else
288  factors= conv (factorize (A, true));
289  append (factors, conv (contentAxFactors));
290  append (factors, conv (contentAyFactors));
291  decompress (factors, N);
292  return factors;
293  }
294 
295  if (irreducibilityTest (A))
296  {
297  CFList factors;
298  factors.append (A);
299 
300  appendSwapDecompress (factors, conv (contentAxFactors),
301  conv (contentAyFactors), false, false, N);
302 
303  normalize (factors);
304  return factors;
305  }
306  bool swap= false;
307  if (degree (A) > degree (A, x))
308  {
309  A= swapvar (A, y, x);
310  swap= true;
311  }
312 
313  CanonicalForm Aeval, bufAeval, buf;
314  CFList uniFactors, list, bufUniFactors;
315  DegreePattern degs;
316  DegreePattern bufDegs;
317 
318  CanonicalForm Aeval2, bufAeval2;
319  CFList bufUniFactors2, list2, uniFactors2;
320  DegreePattern degs2;
321  DegreePattern bufDegs2;
322  bool swap2= false;
323 
324  // several univariate factorizations to obtain more information about the
325  // degree pattern therefore usually less combinations have to be tried during
326  // the recombination process
327  int factorNums= 2;
328  int subCheck1= substituteCheck (A, x);
329  int subCheck2= substituteCheck (A, y);
330  buf= swapvar (A,x,y);
331  int evaluation, evaluation2, bufEvaluation= 0, bufEvaluation2= 0;
332  for (int i= 0; i < factorNums; i++)
333  {
334  bufAeval= A;
335  TIMING_START (fac_bi_evaluation);
336  bufAeval= evalPoint (A, bufEvaluation);
337  TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
338 
339  bufAeval2= buf;
340  TIMING_START (fac_bi_evaluation);
341  bufAeval2= evalPoint (buf, bufEvaluation2);
342  TIMING_END_AND_PRINT (fac_bi_evaluation,
343  "time for eval point over Q in y: ");
344 
345  // univariate factorization
346  TIMING_START (fac_uni_factorizer);
347  if (extension)
348  bufUniFactors= conv (factorize (bufAeval, v));
349  else
350  bufUniFactors= conv (factorize (bufAeval, true));
351  TIMING_END_AND_PRINT (fac_uni_factorizer,
352  "time for univariate factorization over Q: ");
353  DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
354  (prod (bufUniFactors) == bufAeval));
355 
356  if (bufUniFactors.getFirst().inCoeffDomain())
357  bufUniFactors.removeFirst();
358 
359  if (bufUniFactors.length() == 1)
360  {
361  factors.append (A);
362 
363  appendSwapDecompress (factors, conv (contentAxFactors),
364  conv (contentAyFactors), swap, swap2, N);
365 
366  if (isOn (SW_RATIONAL))
367  normalize (factors);
368  return factors;
369  }
370 
371  TIMING_START (fac_uni_factorizer);
372  if (extension)
373  bufUniFactors2= conv (factorize (bufAeval2, v));
374  else
375  bufUniFactors2= conv (factorize (bufAeval2, true));
376  TIMING_END_AND_PRINT (fac_uni_factorizer,
377  "time for univariate factorization in y over Q: ");
378  DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
379  (prod (bufUniFactors2) == bufAeval2));
380 
381  if (bufUniFactors2.getFirst().inCoeffDomain())
382  bufUniFactors2.removeFirst();
383  if (bufUniFactors2.length() == 1)
384  {
385  factors.append (A);
386 
387  appendSwapDecompress (factors, conv (contentAxFactors),
388  conv (contentAyFactors), swap, swap2, N);
389 
390  if (isOn (SW_RATIONAL))
391  normalize (factors);
392  return factors;
393  }
394 
395  if (i == 0)
396  {
397  if (subCheck1 > 0)
398  {
399  int subCheck= substituteCheck (bufUniFactors);
400 
401  if (subCheck > 1 && (subCheck1%subCheck == 0))
402  {
403  CanonicalForm bufA= A;
404  subst (bufA, bufA, subCheck, x);
405  factors= biFactorize (bufA, v);
406  reverseSubst (factors, subCheck, x);
407  appendSwapDecompress (factors, conv (contentAxFactors),
408  conv (contentAyFactors), swap, swap2, N);
409  if (isOn (SW_RATIONAL))
410  normalize (factors);
411  return factors;
412  }
413  }
414 
415  if (subCheck2 > 0)
416  {
417  int subCheck= substituteCheck (bufUniFactors2);
418 
419  if (subCheck > 1 && (subCheck2%subCheck == 0))
420  {
421  CanonicalForm bufA= A;
422  subst (bufA, bufA, subCheck, y);
423  factors= biFactorize (bufA, v);
424  reverseSubst (factors, subCheck, y);
425  appendSwapDecompress (factors, conv (contentAxFactors),
426  conv (contentAyFactors), swap, swap2, N);
427  if (isOn (SW_RATIONAL))
428  normalize (factors);
429  return factors;
430  }
431  }
432  }
433 
434  // degree analysis
435  bufDegs = DegreePattern (bufUniFactors);
436  bufDegs2= DegreePattern (bufUniFactors2);
437 
438  if (i == 0)
439  {
440  Aeval= bufAeval;
441  evaluation= bufEvaluation;
442  uniFactors= bufUniFactors;
443  degs= bufDegs;
444  Aeval2= bufAeval2;
445  evaluation2= bufEvaluation2;
446  uniFactors2= bufUniFactors2;
447  degs2= bufDegs2;
448  }
449  else
450  {
451  degs.intersect (bufDegs);
452  degs2.intersect (bufDegs2);
453  if (bufUniFactors2.length() < uniFactors2.length())
454  {
455  uniFactors2= bufUniFactors2;
456  Aeval2= bufAeval2;
457  evaluation2= bufEvaluation2;
458  }
459  if (bufUniFactors.length() < uniFactors.length())
460  {
461  uniFactors= bufUniFactors;
462  Aeval= bufAeval;
463  evaluation= bufEvaluation;
464  }
465  }
466  if (bufEvaluation > 0)
467  bufEvaluation++;
468  else
469  bufEvaluation= -bufEvaluation + 1;
470  if (bufEvaluation > 0)
471  bufEvaluation2++;
472  else
473  bufEvaluation2= -bufEvaluation2 + 1;
474  }
475 
476  if (uniFactors.length() > uniFactors2.length() ||
477  (uniFactors.length() == uniFactors2.length()
478  && degs.getLength() > degs2.getLength()))
479  {
480  degs= degs2;
481  uniFactors= uniFactors2;
482  evaluation= evaluation2;
483  Aeval= Aeval2;
484  A= buf;
485  swap2= true;
486  }
487 
488  if (degs.getLength() == 1) // A is irreducible
489  {
490  factors.append (A);
491  appendSwapDecompress (factors, conv (contentAxFactors),
492  conv (contentAyFactors), swap, swap2, N);
493  if (isOn (SW_RATIONAL))
494  normalize (factors);
495  return factors;
496  }
497 
498  A *= bCommonDen (A);
499  A= A (y + evaluation, y);
500 
501  int liftBound= degree (A, y) + 1;
502 
503  modpk b= modpk();
504  bool mipoHasDen= false;
505  CanonicalForm den= 1;
506  if (!extension)
507  {
508  Off (SW_RATIONAL);
509  int i= 0;
510  findGoodPrime(F,i);
512  findGoodPrime(A,i);
513  if (i >= cf_getNumBigPrimes())
514  printf ("out of primes\n"); //TODO exit
515 
516  int p=cf_getBigPrime(i);
517  b = coeffBound( A, p );
518  modpk bb= coeffBound (Aeval, p);
519  if (bb.getk() > b.getk() ) b=bb;
520  bb= coeffBound (F, p);
521  if (bb.getk() > b.getk() ) b=bb;
522  }
523  else
524  {
525  A /= Lc (Aeval);
526  mipoHasDen= !bCommonDen(mipo).isOne();
527  mipo *= bCommonDen (mipo);
528  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
529  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
530  ZZ NTLf= resultant (NTLmipo, NTLLcf);
531  ZZ NTLD= discriminant (NTLmipo);
532  den= abs (convertZZ2CF (NTLD*NTLf));
533 
534  // make factors elements of Z(a)[x] disable for modularDiophant
535  CanonicalForm multiplier= 1;
536  for (CFListIterator i= uniFactors; i.hasItem(); i++)
537  {
538  multiplier *= bCommonDen (i.getItem());
539  i.getItem()= i.getItem()*bCommonDen(i.getItem());
540  }
541  A *= multiplier;
542  A *= bCommonDen (A);
543 
544  Off (SW_RATIONAL);
545  int i= 0;
546  CanonicalForm discMipo= convertZZ2CF (NTLD);
547  findGoodPrime (F*discMipo,i);
548  findGoodPrime (Aeval*discMipo,i);
549  findGoodPrime (A*discMipo,i);
550 
551  int p=cf_getBigPrime(i);
552  b = coeffBound( A, p, mipo );
553  modpk bb= coeffBound (Aeval, p, mipo);
554  if (bb.getk() > b.getk() ) b=bb;
555  bb= coeffBound (F, p, mipo);
556  if (bb.getk() > b.getk() ) b=bb;
557  }
558 
559  ExtensionInfo dummy= ExtensionInfo (false);
560  if (extension)
561  dummy= ExtensionInfo (v, false);
562  bool earlySuccess= false;
563  CFList earlyFactors;
564  TIMING_START (fac_bi_hensel_lift);
565  uniFactors= henselLiftAndEarly
566  (A, earlySuccess, earlyFactors, degs, liftBound,
567  uniFactors, dummy, evaluation, b, den);
568  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
569  "time for bivariate hensel lifting over Q: ");
570  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
571 
572  CanonicalForm MODl= power (y, liftBound);
573 
574  if (mipoHasDen)
575  {
576  Variable vv;
577  for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
578  if (hasFirstAlgVar (iter.getItem(), vv))
579  break;
580  for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
581  iter.getItem()= replacevar (iter.getItem(), vv, v);
582  prune (vv);
583  }
584 
585  On (SW_RATIONAL);
586  A *= bCommonDen (A);
587  Off (SW_RATIONAL);
588 
589  TIMING_START (fac_bi_factor_recombination);
590  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
591  uniFactors.length()/2, b, den);
592  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
593  "time for bivariate factor recombination over Q: ");
594 
595  On (SW_RATIONAL);
596 
597  if (earlySuccess)
598  factors= Union (earlyFactors, factors);
599  else if (!earlySuccess && degs.getLength() == 1)
600  factors= earlyFactors;
601 
602  appendSwapDecompress (factors, conv (contentAxFactors),
603  conv (contentAyFactors), swap, swap2, N);
604  if (isOn (SW_RATIONAL))
605  normalize (factors);
606 
607  return factors;
608 }

◆ coeffBound()

modpk coeffBound ( const CanonicalForm f,
int  p,
const CanonicalForm mipo 
)

compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)

Definition at line 97 of file facBivar.cc.

98 {
99  int * degs = degrees( f );
100  int M = 0, i, k = f.level();
101  CanonicalForm K= 1;
102  for ( i = 1; i <= k; i++ )
103  {
104  M += degs[i];
105  K *= degs[i] + 1;
106  }
107  DELETE_ARRAY(degs);
108  K /= power (CanonicalForm (2), k/2);
109  K *= power (CanonicalForm (2), M);
110  int N= degree (mipo);
112  b= 2*power (maxNorm (f), N)*power (maxNorm (mipo), 4*N)*K*
113  power (CanonicalForm (2), N)*
114  power (CanonicalForm (N+1), 4*N);
115  b /= power (abs (lc (mipo)), N);
116 
117  CanonicalForm B = p;
118  k = 1;
119  while ( B < b ) {
120  B *= p;
121  k++;
122  }
123  return modpk( p, k );
124 }

◆ conv()

CFList conv ( const CFFList L)

convert a CFFList to a CFList by dropping the multiplicity

Definition at line 126 of file facBivar.cc.

127 {
128  CFList result;
129  for (CFFListIterator i= L; i.hasItem(); i++)
130  result.append (i.getItem().factor());
131  return result;
132 }

◆ DELETE_ARRAY()

DELETE_ARRAY ( degs  )

◆ evalPoint()

CanonicalForm evalPoint ( const CanonicalForm F,
int &  i 
)

Definition at line 145 of file facBivar.cc.

146 {
147  Variable x= Variable (1);
148  Variable y= Variable (2);
150 
151  int k;
152 
153  if (i == 0)
154  {
155  if (testPoint (F, result, i))
156  return result;
157  }
158  do
159  {
160  if (i > 0)
161  k= 1;
162  else
163  k= 2;
164  while (k < 3)
165  {
166  if (k == 1)
167  {
168  if (testPoint (F, result, i))
169  return result;
170  }
171  else
172  {
173  if (testPoint (F, result, -i))
174  {
175  i= -i;
176  return result;
177  }
178  else if (i < 0)
179  i= -i;
180  }
181  k++;
182  }
183  i++;
184  } while (1);
185 }

◆ findGoodPrime()

void findGoodPrime ( const CanonicalForm f,
int &  start 
)

find a big prime p from our tables such that no term of f vanishes mod p

Definition at line 61 of file facBivar.cc.

62 {
63  if (! f.inBaseDomain() )
64  {
65  CFIterator i = f;
66  for(;;)
67  {
68  if ( i.hasTerms() )
69  {
70  findGoodPrime(i.coeff(),start);
71  if (0==cf_getBigPrime(start)) return;
72  if((i.exp()!=0) && ((i.exp() % cf_getBigPrime(start))==0))
73  {
74  start++;
75  i=f;
76  }
77  else i++;
78  }
79  else break;
80  }
81  }
82  else
83  {
84  if (f.inZ())
85  {
86  if (0==cf_getBigPrime(start)) return;
87  while((!f.isZero()) && (mod(f,cf_getBigPrime(start))==0))
88  {
89  start++;
90  if (0==cf_getBigPrime(start)) return;
91  }
92  }
93  }
94 }

◆ for()

for ( i  = 1; i <= ki++)

Definition at line 43 of file facBivar.cc.

44  {
45  M += degs[i];
46  b *= degs[i] + 1;
47  }

◆ modpk()

return modpk ( p  ,
k   
)

◆ testPoint()

bool testPoint ( const CanonicalForm F,
CanonicalForm G,
int  i 
)

Definition at line 134 of file facBivar.cc.

135 {
136  G= F (i, 2);
137  if (G.inCoeffDomain() || degree (F, 1) > degree (G, 1))
138  return false;
139 
140  if (degree (gcd (deriv (G, G.mvar()), G)) > 0)
141  return false;
142  return true;
143 }

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_uni_factorizer  ) const &

◆ while()

while ( )

Definition at line 54 of file facBivar.cc.

54  {
55  B *= p;
56  k++;
57  }

Variable Documentation

◆ b

b = 1

Definition at line 42 of file facBivar.cc.

◆ B

Definition at line 52 of file facBivar.cc.

◆ i

int i

Definition at line 41 of file facBivar.cc.

◆ k

k = f.level()

Definition at line 41 of file facBivar.cc.

◆ M

int M = 0

Definition at line 41 of file facBivar.cc.

◆ p

int p
Initial value:
{
int * degs = degrees( f )

Definition at line 39 of file facBivar.cc.

i
int i
Definition: facBivar.cc:41
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:489
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
f
FILE * f
Definition: checklibs.c:9
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
DegreePattern
Definition: DegreePattern.h:31
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CFMap
class CFMap
Definition: cf_map.h:84
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
testPoint
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
Definition: facBivar.cc:134
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:77
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition: facFqBivarUtil.cc:1295
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
Definition: cf_algorithm.cc:534
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
buf
int status int void * buf
Definition: si_signals.h:59
k
int k
Definition: facBivar.cc:41
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Definition: facFqBivarUtil.cc:70
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
Aeval
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
conv
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
factorRecombination
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:561
DegreePattern::intersect
void intersect(const DegreePattern &degPat)
intersect two degree patterns
Definition: DegreePattern.cc:68
M
int M
Definition: facBivar.cc:41
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
prune
void prune(Variable &alpha)
Definition: variable.cc:261
Variable::level
int level() const
Definition: factory.h:134
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
den
CanonicalForm den(const CanonicalForm &f)
Definition: canonicalform.h:333
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition: cfNewtonPolygon.cc:853
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition: facFqBivarUtil.cc:1089
modpk
class to do operations mod p^k for int's p and k
Definition: fac_util.h:22
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
p
int p
Definition: facBivar.cc:39
igcd
int igcd(int a, int b)
Definition: cf_util.cc:51
DegreePattern::getLength
int getLength() const
getter
Definition: DegreePattern.h:86
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
modpk::getk
int getk() const
Definition: fac_util.h:36
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
B
b *CanonicalForm B
Definition: facBivar.cc:52
coeffBound
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
Definition: facBivar.cc:97
ExtensionInfo
Definition: ExtensionInfo.h:50
b
CanonicalForm b
Definition: facBivar.cc:42
resultant
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:173
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List
Definition: ftmpl_list.h:20
swap
#define swap(_i, _j)
replacevar
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
findGoodPrime
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
Definition: facBivar.cc:61
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1115
biFactorize
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:187
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition: facAlgFuncUtil.cc:120
modpk
return modpk(p, k)
A
#define A
Definition: sirandom.c:23
evalPoint
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
Definition: facBivar.cc:145
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
irreducibilityTest
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
Definition: cfNewtonPolygon.cc:1123
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
ListIterator
Definition: ftmpl_list.h:17
DELETE_ARRAY
DELETE_ARRAY(degs)