My Project
Functions | Variables
facBivar.cc File Reference

bivariate factorization over Q(a) More...

#include "config.h"
#include "cf_assert.h"
#include "cf_util.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 188 of file facBivar.cc.

189 {
190  if (F.inCoeffDomain())
191  return CFList(F);
192 
193  bool extension= (v.level() != 1);
195  if (isOn (SW_RATIONAL))
196  A= F*bCommonDen (F);
197  else
198  A= F;
199 
201  if (extension)
202  mipo= getMipo (v);
203 
204  if (A.isUnivariate())
205  {
206  CFFList buf;
207  if (extension)
208  buf= factorize (A, v);
209  else
210  buf= factorize (A, true);
211  CFList result= conv (buf);
212  if (result.getFirst().inCoeffDomain())
213  result.removeFirst();
214  return result;
215  }
216 
217  CFMap N;
218  A= compress (A, N);
219  Variable y= A.mvar();
220 
221  if (y.level() > 2) return CFList (F);
222  Variable x= Variable (1);
223 
224  CanonicalForm contentAx= content (A, x);
225  CanonicalForm contentAy= content (A);
226 
227  A= A/(contentAx*contentAy);
228  CFFList contentAxFactors, contentAyFactors;
229 
230  if (extension)
231  {
232  if (!contentAx.inCoeffDomain())
233  {
234  contentAxFactors= factorize (contentAx, v);
235  if (contentAxFactors.getFirst().factor().inCoeffDomain())
236  contentAxFactors.removeFirst();
237  }
238  if (!contentAy.inCoeffDomain())
239  {
240  contentAyFactors= factorize (contentAy, v);
241  if (contentAyFactors.getFirst().factor().inCoeffDomain())
242  contentAyFactors.removeFirst();
243  }
244  }
245  else
246  {
247  if (!contentAx.inCoeffDomain())
248  {
249  contentAxFactors= factorize (contentAx, true);
250  if (contentAxFactors.getFirst().factor().inCoeffDomain())
251  contentAxFactors.removeFirst();
252  }
253  if (!contentAy.inCoeffDomain())
254  {
255  contentAyFactors= factorize (contentAy, true);
256  if (contentAyFactors.getFirst().factor().inCoeffDomain())
257  contentAyFactors.removeFirst();
258  }
259  }
260 
261  //check trivial case
262  if (degree (A) == 1 || degree (A, 1) == 1 ||
263  (size (A) == 2 && igcd (degree (A), degree (A,1)) == 1))
264  {
265  CFList factors;
266  factors.append (A);
267 
268  appendSwapDecompress (factors, conv (contentAxFactors),
269  conv (contentAyFactors), false, false, N);
270 
271  normalize (factors);
272  return factors;
273  }
274 
275  //trivial case
276  CFList factors;
277  if (A.inCoeffDomain())
278  {
279  append (factors, conv (contentAxFactors));
280  append (factors, conv (contentAyFactors));
281  decompress (factors, N);
282  return factors;
283  }
284  else if (A.isUnivariate())
285  {
286  if (extension)
287  factors= conv (factorize (A, v));
288  else
289  factors= conv (factorize (A, true));
290  append (factors, conv (contentAxFactors));
291  append (factors, conv (contentAyFactors));
292  decompress (factors, N);
293  return factors;
294  }
295 
296  if (irreducibilityTest (A))
297  {
298  CFList factors;
299  factors.append (A);
300 
301  appendSwapDecompress (factors, conv (contentAxFactors),
302  conv (contentAyFactors), false, false, N);
303 
304  normalize (factors);
305  return factors;
306  }
307  bool swap= false;
308  if (degree (A) > degree (A, x))
309  {
310  A= swapvar (A, y, x);
311  swap= true;
312  }
313 
314  CanonicalForm Aeval, bufAeval, buf;
315  CFList uniFactors, list, bufUniFactors;
316  DegreePattern degs;
317  DegreePattern bufDegs;
318 
319  CanonicalForm Aeval2, bufAeval2;
320  CFList bufUniFactors2, list2, uniFactors2;
321  DegreePattern degs2;
322  DegreePattern bufDegs2;
323  bool swap2= false;
324 
325  // several univariate factorizations to obtain more information about the
326  // degree pattern therefore usually less combinations have to be tried during
327  // the recombination process
328  int factorNums= 2;
329  int subCheck1= substituteCheck (A, x);
330  int subCheck2= substituteCheck (A, y);
331  buf= swapvar (A,x,y);
332  int evaluation, evaluation2, bufEvaluation= 0, bufEvaluation2= 0;
333  for (int i= 0; i < factorNums; i++)
334  {
335  bufAeval= A;
336  TIMING_START (fac_bi_evaluation);
337  bufAeval= evalPoint (A, bufEvaluation);
338  TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
339 
340  bufAeval2= buf;
341  TIMING_START (fac_bi_evaluation);
342  bufAeval2= evalPoint (buf, bufEvaluation2);
343  TIMING_END_AND_PRINT (fac_bi_evaluation,
344  "time for eval point over Q in y: ");
345 
346  // univariate factorization
347  TIMING_START (fac_uni_factorizer);
348  if (extension)
349  bufUniFactors= conv (factorize (bufAeval, v));
350  else
351  bufUniFactors= conv (factorize (bufAeval, true));
352  TIMING_END_AND_PRINT (fac_uni_factorizer,
353  "time for univariate factorization over Q: ");
354  DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
355  (prod (bufUniFactors) == bufAeval));
356 
357  if (bufUniFactors.getFirst().inCoeffDomain())
358  bufUniFactors.removeFirst();
359 
360  if (bufUniFactors.length() == 1)
361  {
362  factors.append (A);
363 
364  appendSwapDecompress (factors, conv (contentAxFactors),
365  conv (contentAyFactors), swap, swap2, N);
366 
367  if (isOn (SW_RATIONAL))
368  normalize (factors);
369  return factors;
370  }
371 
372  TIMING_START (fac_uni_factorizer);
373  if (extension)
374  bufUniFactors2= conv (factorize (bufAeval2, v));
375  else
376  bufUniFactors2= conv (factorize (bufAeval2, true));
377  TIMING_END_AND_PRINT (fac_uni_factorizer,
378  "time for univariate factorization in y over Q: ");
379  DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
380  (prod (bufUniFactors2) == bufAeval2));
381 
382  if (bufUniFactors2.getFirst().inCoeffDomain())
383  bufUniFactors2.removeFirst();
384  if (bufUniFactors2.length() == 1)
385  {
386  factors.append (A);
387 
388  appendSwapDecompress (factors, conv (contentAxFactors),
389  conv (contentAyFactors), swap, swap2, N);
390 
391  if (isOn (SW_RATIONAL))
392  normalize (factors);
393  return factors;
394  }
395 
396  if (i == 0)
397  {
398  if (subCheck1 > 0)
399  {
400  int subCheck= substituteCheck (bufUniFactors);
401 
402  if (subCheck > 1 && (subCheck1%subCheck == 0))
403  {
404  CanonicalForm bufA= A;
405  subst (bufA, bufA, subCheck, x);
406  factors= biFactorize (bufA, v);
407  reverseSubst (factors, subCheck, x);
408  appendSwapDecompress (factors, conv (contentAxFactors),
409  conv (contentAyFactors), swap, swap2, N);
410  if (isOn (SW_RATIONAL))
411  normalize (factors);
412  return factors;
413  }
414  }
415 
416  if (subCheck2 > 0)
417  {
418  int subCheck= substituteCheck (bufUniFactors2);
419 
420  if (subCheck > 1 && (subCheck2%subCheck == 0))
421  {
422  CanonicalForm bufA= A;
423  subst (bufA, bufA, subCheck, y);
424  factors= biFactorize (bufA, v);
425  reverseSubst (factors, subCheck, y);
426  appendSwapDecompress (factors, conv (contentAxFactors),
427  conv (contentAyFactors), swap, swap2, N);
428  if (isOn (SW_RATIONAL))
429  normalize (factors);
430  return factors;
431  }
432  }
433  }
434 
435  // degree analysis
436  bufDegs = DegreePattern (bufUniFactors);
437  bufDegs2= DegreePattern (bufUniFactors2);
438 
439  if (i == 0)
440  {
441  Aeval= bufAeval;
442  evaluation= bufEvaluation;
443  uniFactors= bufUniFactors;
444  degs= bufDegs;
445  Aeval2= bufAeval2;
446  evaluation2= bufEvaluation2;
447  uniFactors2= bufUniFactors2;
448  degs2= bufDegs2;
449  }
450  else
451  {
452  degs.intersect (bufDegs);
453  degs2.intersect (bufDegs2);
454  if (bufUniFactors2.length() < uniFactors2.length())
455  {
456  uniFactors2= bufUniFactors2;
457  Aeval2= bufAeval2;
458  evaluation2= bufEvaluation2;
459  }
460  if (bufUniFactors.length() < uniFactors.length())
461  {
462  uniFactors= bufUniFactors;
463  Aeval= bufAeval;
464  evaluation= bufEvaluation;
465  }
466  }
467  if (bufEvaluation > 0)
468  bufEvaluation++;
469  else
470  bufEvaluation= -bufEvaluation + 1;
471  if (bufEvaluation > 0)
472  bufEvaluation2++;
473  else
474  bufEvaluation2= -bufEvaluation2 + 1;
475  }
476 
477  if (uniFactors.length() > uniFactors2.length() ||
478  (uniFactors.length() == uniFactors2.length()
479  && degs.getLength() > degs2.getLength()))
480  {
481  degs= degs2;
482  uniFactors= uniFactors2;
483  evaluation= evaluation2;
484  Aeval= Aeval2;
485  A= buf;
486  swap2= true;
487  }
488 
489  if (degs.getLength() == 1) // A is irreducible
490  {
491  factors.append (A);
492  appendSwapDecompress (factors, conv (contentAxFactors),
493  conv (contentAyFactors), swap, swap2, N);
494  if (isOn (SW_RATIONAL))
495  normalize (factors);
496  return factors;
497  }
498 
499  A *= bCommonDen (A);
500  A= A (y + evaluation, y);
501 
502  int liftBound= degree (A, y) + 1;
503 
504  modpk b= modpk();
505  bool mipoHasDen= false;
506  CanonicalForm den= 1;
507  if (!extension)
508  {
509  Off (SW_RATIONAL);
510  int i= 0;
511  findGoodPrime(F,i);
513  findGoodPrime(A,i);
514  if (i >= cf_getNumBigPrimes())
515  printf ("out of primes\n"); //TODO exit
516 
517  int p=cf_getBigPrime(i);
518  b = coeffBound( A, p );
519  modpk bb= coeffBound (Aeval, p);
520  if (bb.getk() > b.getk() ) b=bb;
521  bb= coeffBound (F, p);
522  if (bb.getk() > b.getk() ) b=bb;
523  }
524  else
525  {
526  A /= Lc (Aeval);
527  mipoHasDen= !bCommonDen(mipo).isOne();
528  mipo *= bCommonDen (mipo);
529  #ifdef HAVE_FLINT
530  // init
531  fmpz_t FLINTf,FLINTD;
532  fmpz_init(FLINTf);
533  fmpz_init(FLINTD);
534  fmpz_poly_t FLINTmipo;
535  fmpz_poly_t FLINTLcf;
536  //conversion
537  convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
538  convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (A*bCommonDen (A)));
539  // resultant, discriminant
540  fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
541  fmpz_poly_discriminant(FLINTD,FLINTmipo);
542  fmpz_mul(FLINTf,FLINTD,FLINTf);
543  // conversion
544  den= abs (convertFmpz2CF(FLINTf));
545  // clean up
546  fmpz_clear(FLINTf);
547  // FLINTD is used below
548  fmpz_poly_clear(FLINTLcf);
549  fmpz_poly_clear(FLINTmipo);
550  #elif defined(HAVE_NTL)
551  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
552  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (A*bCommonDen (A)));
553  ZZ NTLf= resultant (NTLmipo, NTLLcf);
554  ZZ NTLD= discriminant (NTLmipo);
555  den= abs (convertZZ2CF (NTLD*NTLf));
556  #else
557  factoryError("NTL/FLINT missing: biFactorize");
558  #endif
559 
560  // make factors elements of Z(a)[x] disable for modularDiophant
561  CanonicalForm multiplier= 1;
562  for (CFListIterator i= uniFactors; i.hasItem(); i++)
563  {
564  multiplier *= bCommonDen (i.getItem());
565  i.getItem()= i.getItem()*bCommonDen(i.getItem());
566  }
567  A *= multiplier;
568  A *= bCommonDen (A);
569 
570  Off (SW_RATIONAL);
571  int i= 0;
572  #ifdef HAVE_FLINT
573  CanonicalForm discMipo= convertFmpz2CF(FLINTD);
574  fmpz_clear(FLINTD);
575  #elif defined(HAVE_NTL)
576  CanonicalForm discMipo= convertZZ2CF (NTLD);
577  #else
578  factoryError("NTL/FLINT missing: biFactorize");
579  #endif
580  findGoodPrime (F*discMipo,i);
581  findGoodPrime (Aeval*discMipo,i);
582  findGoodPrime (A*discMipo,i);
583 
584  int p=cf_getBigPrime(i);
585  b = coeffBound( A, p, mipo );
586  modpk bb= coeffBound (Aeval, p, mipo);
587  if (bb.getk() > b.getk() ) b=bb;
588  bb= coeffBound (F, p, mipo);
589  if (bb.getk() > b.getk() ) b=bb;
590  }
591 
592  ExtensionInfo dummy= ExtensionInfo (false);
593  if (extension)
594  dummy= ExtensionInfo (v, false);
595  bool earlySuccess= false;
596  CFList earlyFactors;
597  TIMING_START (fac_bi_hensel_lift);
598  uniFactors= henselLiftAndEarly
599  (A, earlySuccess, earlyFactors, degs, liftBound,
600  uniFactors, dummy, evaluation, b, den);
601  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
602  "time for bivariate hensel lifting over Q: ");
603  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
604 
605  CanonicalForm MODl= power (y, liftBound);
606 
607  if (mipoHasDen)
608  {
609  Variable vv;
610  for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
611  if (hasFirstAlgVar (iter.getItem(), vv))
612  break;
613  for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
614  iter.getItem()= replacevar (iter.getItem(), vv, v);
615  //prune (vv);
616  }
617 
618  On (SW_RATIONAL);
619  A *= bCommonDen (A);
620  Off (SW_RATIONAL);
621 
622  TIMING_START (fac_bi_factor_recombination);
623  factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
624  uniFactors.length()/2, b, den);
625  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
626  "time for bivariate factor recombination over Q: ");
627 
628  On (SW_RATIONAL);
629 
630  if (earlySuccess)
631  factors= Union (earlyFactors, factors);
632  else if (!earlySuccess && degs.getLength() == 1)
633  factors= earlyFactors;
634 
635  appendSwapDecompress (factors, conv (contentAxFactors),
636  conv (contentAyFactors), swap, swap2, N);
637  if (isOn (SW_RATIONAL))
638  normalize (factors);
639 
640  return factors;
641 }
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:495
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
#define swap(_i, _j)
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
List< CanonicalForm > CFList
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
Variable x
Definition: cfModGcd.cc:4084
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int igcd(int a, int b)
Definition: cf_util.cc:56
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:32
void intersect(const DegreePattern &degPat)
intersect two degree patterns
int getLength() const
getter
Definition: DegreePattern.h:86
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:134
int level() const
Definition: factory.h:150
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
int getk() const
Definition: fac_util.h:36
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
CanonicalForm mipo
Definition: facAlgExt.cc:57
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
return modpk(p, k)
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
CanonicalForm b
Definition: facBivar.cc:42
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
Definition: facBivar.cc:145
int p
Definition: facBivar.cc:39
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition: facBivar.cc:188
int i
Definition: facBivar.cc:41
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
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
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...
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
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:1152
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:586
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026

◆ 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)

Parameters
[in]fpoly over Z[a]
[in]psome positive integer
[in]mipominimal polynomial with denominator 1

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 }
CanonicalForm lc(const CanonicalForm &f)
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
FILE * f
Definition: checklibs.c:9
int M
Definition: facBivar.cc:41
DELETE_ARRAY(degs)
b *CanonicalForm B
Definition: facBivar.cc:52
int k
Definition: facBivar.cc:41

◆ conv()

CFList conv ( const CFFList L)

convert a CFFList to a CFList by dropping the multiplicity

Parameters
[in]La CFFList

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 }
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
Definition: facBivar.cc:134

◆ 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

Parameters
[in]fpoly over Z or Z[a]
[in,out]startindex of big prime in cf_primetab.h

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 }
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
class to iterate through CanonicalForm's
Definition: cf_iter.h:44

◆ 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 }
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
STATIC_VAR TreeM * G
Definition: janet.cc:31
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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 38 of file facBivar.cc.