My Project
Functions
facAbsBiFact.h File Reference

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo More...

#include "canonicalform.h"

Go to the source code of this file.

Functions

CFAFList absBiFactorizeMain (const CanonicalForm &F, bool full=false)
 main absolute factorization routine, expects bivariate poly which is irreducible over Q More...
 
static void normalize (CFAFList &L)
 normalize factors, i.e. make factors monic More...
 
CFAFList uniAbsFactorize (const CanonicalForm &F, bool full=false)
 univariate absolute factorization over Q More...
 

Detailed Description

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo

Author
Martin Lee

Definition in file facAbsBiFact.h.

Function Documentation

◆ absBiFactorizeMain()

CFAFList absBiFactorizeMain ( const CanonicalForm F,
bool  full = false 
)

main absolute factorization routine, expects bivariate poly which is irreducible over Q

Returns
absBiFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor
Parameters
[in]Fs.a.
[in]fulltrue if all factors should be returned

Definition at line 211 of file facAbsBiFact.cc.

212 {
214  bool isRat= isOn (SW_RATIONAL);
215  Off (SW_RATIONAL);
216  F /= icontent (F);
217  On (SW_RATIONAL);
218 
219  mpz_t * M=new mpz_t [4];
220  mpz_init (M[0]);
221  mpz_init (M[1]);
222  mpz_init (M[2]);
223  mpz_init (M[3]);
224 
225  mpz_t * S=new mpz_t [2];
226  mpz_init (S[0]);
227  mpz_init (S[1]);
228 
229  F= compress (F, M, S);
230 
231  if (F.isUnivariate())
232  {
233  if (degree (F) == 1)
234  {
235  mpz_clear (M[0]);
236  mpz_clear (M[1]);
237  mpz_clear (M[2]);
238  mpz_clear (M[3]);
239  delete [] M;
240 
241  mpz_clear (S[0]);
242  mpz_clear (S[1]);
243  delete [] S;
244  if (!isRat)
245  Off (SW_RATIONAL);
246  return CFAFList (CFAFactor (G, 1, 1));
247  }
249  if (result.getFirst().factor().inCoeffDomain())
250  result.removeFirst();
252  iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
253  iter.getItem().minpoly(),iter.getItem().exp());
254  mpz_clear (M[0]);
255  mpz_clear (M[1]);
256  mpz_clear (M[2]);
257  mpz_clear (M[3]);
258  delete [] M;
259 
260  mpz_clear (S[0]);
261  mpz_clear (S[1]);
262  delete [] S;
263  if (!isRat)
264  Off (SW_RATIONAL);
265  return result;
266  }
267 
268  if (degree (F, 1) == 1 || degree (F, 2) == 1)
269  {
270  mpz_clear (M[0]);
271  mpz_clear (M[1]);
272  mpz_clear (M[2]);
273  mpz_clear (M[3]);
274  delete [] M;
275 
276  mpz_clear (S[0]);
277  mpz_clear (S[1]);
278  delete [] S;
279  if (!isRat)
280  Off (SW_RATIONAL);
281  return CFAFList (CFAFactor (G, 1, 1));
282  }
283  int minTdeg, tdegF= totaldegree (F);
284  CanonicalForm Fp, smallestFactor;
285  int p;
286  CFFList factors;
287  Variable alpha;
288  bool rec= false;
289  Variable x= Variable (1);
290  Variable y= Variable (2);
291  CanonicalForm bufF= F;
293  CFArray eval= CFArray (2);
294  int absValue= 1;
295 differentevalpoint:
296  while (1)
297  {
298  TIMING_START (fac_evalpoint);
299  p= choosePoint (F, tdegF, eval, rec, absValue);
300  TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
301 
302  //after here isOn (SW_RATIONAL)==false
304  Fp=F.mapinto();
305  factors= factorize (Fp);
306 
307  if (factors.getFirst().factor().inCoeffDomain())
308  factors.removeFirst();
309 
310  if (factors.length() == 1 && factors.getFirst().exp() == 1)
311  {
312  if (absIrredTest (Fp))
313  {
314  if (isRat)
315  On (SW_RATIONAL);
317  mpz_clear (M[0]);
318  mpz_clear (M[1]);
319  mpz_clear (M[2]);
320  mpz_clear (M[3]);
321  delete [] M;
322 
323  mpz_clear (S[0]);
324  mpz_clear (S[1]);
325  delete [] S;
326  return CFAFList (CFAFactor (G, 1, 1));
327  }
328  else
329  {
330  setCharacteristic (0);
332  {
333  if (isRat)
334  On (SW_RATIONAL);
335  mpz_clear (M[0]);
336  mpz_clear (M[1]);
337  mpz_clear (M[2]);
338  mpz_clear (M[3]);
339  delete [] M;
340 
341  mpz_clear (S[0]);
342  mpz_clear (S[1]);
343  delete [] S;
344  return CFAFList (CFAFactor (G, 1, 1));
345  }
346  rec= true;
347  continue;
348  }
349  }
350  iter= factors;
351  smallestFactor= iter.getItem().factor();
352  while (smallestFactor.isUnivariate() && iter.hasItem())
353  {
354  iter++;
355  if (!iter.hasItem())
356  break;
357  smallestFactor= iter.getItem().factor();
358  }
359 
360  minTdeg= totaldegree (smallestFactor);
361  if (iter.hasItem())
362  iter++;
363  for (; iter.hasItem(); iter++)
364  {
365  if (!iter.getItem().factor().isUnivariate() &&
366  (totaldegree (iter.getItem().factor()) < minTdeg))
367  {
368  smallestFactor= iter.getItem().factor();
369  minTdeg= totaldegree (smallestFactor);
370  }
371  }
372  if (tdegF % minTdeg == 0)
373  break;
375  rec=true;
376  }
377  CanonicalForm Gp= Fp/smallestFactor;
378  Gp= Gp /Lc (Gp);
379 
380  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
381  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
382  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
383  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
384 
385  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
386  !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
387  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
388  !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
389  if (!xValid || !yValid)
390  {
391  rec= true;
392  setCharacteristic (0);
393  goto differentevalpoint;
394  }
395 
396  setCharacteristic (0);
397 
399 
400  CFArray mipos= CFArray (2);
401  CFFList mipoFactors;
402  for (int i= 1; i < 3; i++)
403  {
404  CanonicalForm Fi= F(eval[i-1],i);
405 
406  int s= tdegF/minTdeg + 1;
407  CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
408  bound *= power (CanonicalForm (s),s-1);
409  bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
410 
411  CanonicalForm B = p;
412  long k = 1L;
413  while ( B < bound ) {
414  B *= p;
415  k++;
416  }
417 
418  //TODO take floor (log2(k))
419  k= k+1;
420 #ifdef HAVE_FLINT
421  fmpz_poly_t FLINTFi;
422  convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
424  nmod_poly_t FLINTFpi, FLINTGpi;
425  if (i == 2)
426  {
427  convertFacCF2nmod_poly_t (FLINTFpi,
428  smallestFactorEvalx/lc (smallestFactorEvalx));
429  convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
430  }
431  else
432  {
433  convertFacCF2nmod_poly_t (FLINTFpi,
434  smallestFactorEvaly/lc (smallestFactorEvaly));
435  convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
436  }
437  nmod_poly_factor_t nmodFactors;
438  nmod_poly_factor_init (nmodFactors);
439  nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
440  nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
441 
442  // the following fix is due to interface changes from FLINT 2.3 -> FLINT 2.4
443 # ifndef slong
444 # define slong long
445 # endif
446 
447  slong * link= new slong [2];
448  fmpz_poly_t *v= new fmpz_poly_t[2];
449  fmpz_poly_t *w= new fmpz_poly_t[2];
450  fmpz_poly_init(v[0]);
451  fmpz_poly_init(v[1]);
452  fmpz_poly_init(w[0]);
453  fmpz_poly_init(w[1]);
454 
455  fmpz_poly_factor_t liftedFactors;
456  fmpz_poly_factor_init (liftedFactors);
457  _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
458  nmodFactors, k);
459 
460  nmod_poly_factor_clear (nmodFactors);
461  nmod_poly_clear (FLINTFpi);
462  nmod_poly_clear (FLINTGpi);
463 
465  CanonicalForm liftedSmallestFactor=
466  convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
467 
468  CanonicalForm otherFactor=
469  convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
470  modpk pk= modpk (p, k);
471 #elif defined(HAVE_NTL)
472  modpk pk= modpk (p, k);
473  ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
475 
476  if (fac_NTL_char != p)
477  {
478  fac_NTL_char= p;
479  zz_p::init (p);
480  }
481  zz_pX NTLFpi, NTLGpi;
482  if (i == 2)
483  {
484  NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
485  NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
486  }
487  else
488  {
489  NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
490  NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
491  }
492  vec_zz_pX modFactors;
493  modFactors.SetLength(2);
494  modFactors[0]= NTLFpi;
495  modFactors[1]= NTLGpi;
496  vec_ZZX liftedFactors;
497  MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
499  CanonicalForm liftedSmallestFactor=
500  convertNTLZZX2CF (liftedFactors[0], x);
501 
502  CanonicalForm otherFactor=
503  convertNTLZZX2CF (liftedFactors[1], x);
504 #else
505  factoryError("absBiFactorizeMain: NTL/FLINT missing");
506 #endif
507 
509  liftedSmallestFactor= pk (liftedSmallestFactor);
510  if (i == 2)
511  liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
512  else
513  liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
514 
516  CFMatrix *M= new CFMatrix (s, s);
517  (*M)(s,s)= power (CanonicalForm (p), k);
518  for (int j= 1; j < s; j++)
519  {
520  (*M) (j,j)= 1;
521  (*M) (j+1,j)= -liftedSmallestFactor;
522  }
523 
524  #ifdef HAVE_FLINT
525  fmpz_mat_t FLINTM;
527  fmpq_t delta,eta;
528  fmpq_init(delta); fmpq_set_si(delta,1,1);
529  fmpq_init(eta); fmpq_set_si(eta,3,4);
530  fmpz_mat_transpose(FLINTM,FLINTM);
531  fmpz_mat_lll_storjohann(FLINTM,delta,eta);
532  fmpz_mat_transpose(FLINTM,FLINTM);
533  delete M;
535  fmpz_mat_clear(FLINTM);
536  #elif defined(HAVE_NTL)
537  mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
538 
539  ZZ det;
540 
541  transpose (*NTLM, *NTLM);
542  (void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
543  transpose (*NTLM, *NTLM);
544  delete M;
546  delete NTLM;
547  #else
548  factoryError("NTL/FLINT missing: absBiFactorizeMain");
549  #endif
550 
551  mipo= 0;
552  for (int j= 1; j <= s; j++)
553  mipo += (*M) (j,1)*power (x,s-j);
554 
555  delete M;
556  mipoFactors= factorize (mipo);
557  if (mipoFactors.getFirst().factor().inCoeffDomain())
558  mipoFactors.removeFirst();
559 
560 #ifdef HAVE_FLINT
561  fmpz_poly_clear (v[0]);
562  fmpz_poly_clear (v[1]);
563  fmpz_poly_clear (w[0]);
564  fmpz_poly_clear (w[1]);
565  delete [] v;
566  delete [] w;
567  delete [] link;
568  fmpz_poly_factor_clear (liftedFactors);
569 #endif
570 
571  if (mipoFactors.length() > 1 ||
572  (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
574  {
575  rec=true;
576  goto differentevalpoint;
577  }
578  else
579  mipos[i-1]= mipo;
580  }
581 
582  if (degree (mipos[0]) != degree (mipos[1]))
583  {
584  rec=true;
585  goto differentevalpoint;
586  }
587 
588  On (SW_RATIONAL);
589  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
590  alpha= rootOf (mipos[0]);
591  else
592  alpha= rootOf (mipos[1]);
593 
594  int wrongMipo= 0;
595 
596  Variable beta;
597  if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
598  {
599  mipoFactors= factorize (mipos[1], alpha);
600  if (mipoFactors.getFirst().factor().inCoeffDomain())
601  mipoFactors.removeFirst();
602  for (iter= mipoFactors; iter.hasItem(); iter++)
603  {
604  if (degree (iter.getItem().factor()) > 1)
605  wrongMipo++;
606  }
607  if (wrongMipo == mipoFactors.length())
608  {
609  rec=true;
610  goto differentevalpoint;
611  }
612  wrongMipo= 0;
613  beta= rootOf (mipos[1]);
614  mipoFactors= factorize (mipos[0], beta);
615  if (mipoFactors.getFirst().factor().inCoeffDomain())
616  mipoFactors.removeFirst();
617  for (iter= mipoFactors; iter.hasItem(); iter++)
618  {
619  if (degree (iter.getItem().factor()) > 1)
620  wrongMipo++;
621  }
622  if (wrongMipo == mipoFactors.length())
623  {
624  rec=true;
625  goto differentevalpoint;
626  }
627  }
628  else
629  {
630  mipoFactors= factorize (mipos[0], alpha);
631  if (mipoFactors.getFirst().factor().inCoeffDomain())
632  mipoFactors.removeFirst();
633  for (iter= mipoFactors; iter.hasItem(); iter++)
634  {
635  if (degree (iter.getItem().factor()) > 1)
636  wrongMipo++;
637  }
638  if (wrongMipo == mipoFactors.length())
639  {
640  rec=true;
641  goto differentevalpoint;
642  }
643  wrongMipo= 0;
644  beta= rootOf (mipos[0]);
645  mipoFactors= factorize (mipos[1], beta);
646  if (mipoFactors.getFirst().factor().inCoeffDomain())
647  mipoFactors.removeFirst();
648  for (iter= mipoFactors; iter.hasItem(); iter++)
649  {
650  if (degree (iter.getItem().factor()) > 1)
651  wrongMipo++;
652  }
653  if (wrongMipo == mipoFactors.length())
654  {
655  rec=true;
656  goto differentevalpoint;
657  }
658  }
659 
660 
662  if (degree (F,1) > minTdeg)
663  F1= F (eval[1], 2);
664  else
665  F1= F (eval[0], 1);
666 
667  CFFList QaF1Factors;
668  bool swap= false;
669  if (F1.level() == 2)
670  {
671  swap= true;
672  F1=swapvar (F1, x, y);
673  F= swapvar (F, x, y);
674  }
675 
676  wrongMipo= 0;
677  QaF1Factors= factorize (F1, alpha);
678  if (QaF1Factors.getFirst().factor().inCoeffDomain())
679  QaF1Factors.removeFirst();
680  for (iter= QaF1Factors; iter.hasItem(); iter++)
681  {
682  if (degree (iter.getItem().factor()) > minTdeg)
683  wrongMipo++;
684  }
685 
686  if (wrongMipo == QaF1Factors.length())
687  {
688  rec= true;
689  F= bufF;
690  goto differentevalpoint;
691  }
692 
694  if (swap)
695  evaluation= eval[0];
696  else
697  evaluation= eval[1];
698 
699  F *= bCommonDen (F);
700  F= F (y + evaluation, y);
701 
702  int liftBound= degree (F,y) + 1;
703 
704  modpk b= modpk();
705 
706  CanonicalForm den= 1;
707 
708  mipo= getMipo (alpha);
709 
710  CFList uniFactors;
711  for (iter=QaF1Factors; iter.hasItem(); iter++)
712  uniFactors.append (iter.getItem().factor());
713 
714  F /= Lc (F1);
715  #ifdef HAVE_FLINT
716  // init
717  fmpz_t FLINTf,FLINTD;
718  fmpz_init(FLINTf);
719  fmpz_init(FLINTD);
720  fmpz_poly_t FLINTmipo;
721  fmpz_poly_t FLINTLcf;
722  //conversion
723  convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
724  convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (F*bCommonDen (F)));
725  // resultant, discriminant
726  fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
727  fmpz_poly_discriminant(FLINTD,FLINTmipo);
728  fmpz_mul(FLINTf,FLINTD,FLINTf);
729  den= abs (convertFmpz2CF(FLINTf));
730  // clean up
731  fmpz_clear(FLINTf);
732  // FLINTD is used below
733  fmpz_poly_clear(FLINTLcf);
734  fmpz_poly_clear(FLINTmipo);
735  #elif defined(HAVE_NTL)
736  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
737  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
738  ZZ NTLf= resultant (NTLmipo, NTLLcf);
739  ZZ NTLD= discriminant (NTLmipo);
740  den= abs (convertZZ2CF (NTLD*NTLf));
741  #else
742  factoryError("NTL/FLINT missing: absBiFactorizeMain");
743  #endif
744 
745  // make factors elements of Z(a)[x] disable for modularDiophant
746  CanonicalForm multiplier= 1;
747  for (CFListIterator i= uniFactors; i.hasItem(); i++)
748  {
749  multiplier *= bCommonDen (i.getItem());
750  i.getItem()= i.getItem()*bCommonDen(i.getItem());
751  }
752  F *= multiplier;
753  F *= bCommonDen (F);
754 
755  Off (SW_RATIONAL);
756  int ii= 0;
757  #ifdef HAVE_FLINT
758  CanonicalForm discMipo= convertFmpz2CF(FLINTD);
759  fmpz_clear(FLINTD);
760  #elif defined(HAVE_NTL)
761  CanonicalForm discMipo= convertZZ2CF (NTLD);
762  #endif
763  findGoodPrime (bufF*discMipo,ii);
764  findGoodPrime (F1*discMipo,ii);
765  findGoodPrime (F*discMipo,ii);
766 
767  int pp=cf_getBigPrime(ii);
768  b = coeffBound( F, pp, mipo );
769  modpk bb= coeffBound (F1, pp, mipo);
770  if (bb.getk() > b.getk() ) b=bb;
771  bb= coeffBound (F, pp, mipo);
772  if (bb.getk() > b.getk() ) b=bb;
773 
774  ExtensionInfo dummy= ExtensionInfo (alpha, false);
775  DegreePattern degs= DegreePattern (uniFactors);
776 
777  bool earlySuccess= false;
778  CFList earlyFactors;
779  uniFactors= henselLiftAndEarly
780  (F, earlySuccess, earlyFactors, degs, liftBound,
781  uniFactors, dummy, evaluation, b, den);
782 
783  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
784 
785  CanonicalForm MODl= power (y, liftBound);
786 
787  On (SW_RATIONAL);
788  F *= bCommonDen (F);
789  Off (SW_RATIONAL);
790 
791  CFList biFactors;
792 
793  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
794  uniFactors.length()/2, b, den);
795 
796  On (SW_RATIONAL);
797 
798  if (earlySuccess)
799  biFactors= Union (earlyFactors, biFactors);
800  else if (!earlySuccess && degs.getLength() == 1)
801  biFactors= earlyFactors;
802 
803  bool swap2= false;
804  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
805  if (isOn (SW_RATIONAL))
806  normalize (biFactors);
807 
809  bool found= false;
810 
811  for (CFListIterator i= biFactors; i.hasItem(); i++)
812  {
813  if (full)
814  result.append (CFAFactor (decompress (i.getItem(), M, S),
815  getMipo (alpha), 1));
816 
817  if (totaldegree (i.getItem()) == minTdeg)
818  {
819  if (!full)
820  result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
821  getMipo (alpha), 1));
822  found= true;
823 
824  if (!full)
825  break;
826  }
827  }
828 
829  if (!found)
830  {
831  rec= true;
832  F= bufF;
833  goto differentevalpoint;
834  }
835 
836  if (isRat)
837  On (SW_RATIONAL);
838  else
839  Off (SW_RATIONAL);
840 
841  mpz_clear (M[0]);
842  mpz_clear (M[1]);
843  mpz_clear (M[2]);
844  mpz_clear (M[3]);
845  delete [] M;
846 
847  mpz_clear (S[0]);
848  mpz_clear (S[1]);
849  delete [] S;
850 
851  return result;
852 }
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z 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
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1153
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:495
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1138
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:285
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
#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
CanonicalForm mapinto(const CanonicalForm &f)
AFactor< CanonicalForm > CFAFactor
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
Array< CanonicalForm > CFArray
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
Matrix< CanonicalForm > CFMatrix
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm den(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
List< CFAFactor > CFAFList
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular Las Vegas Algorithms for Pol...
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithms for Polynomial Absolute Fa...
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 )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( 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:31
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:33
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
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
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
CanonicalForm mapinto() const
bool isUnivariate() const
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition: DegreePattern.h:32
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:127
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:59
int getk() const
Definition: fac_util.h:36
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
bool full
Definition: facAbsBiFact.cc:38
CFFListIterator iter
Definition: facAbsBiFact.cc:53
Variable alpha
Definition: facAbsBiFact.cc:51
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
Definition: facAbsBiFact.cc:80
return result
Definition: facAbsBiFact.cc:75
#define slong
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
Variable beta
Definition: facAbsFact.cc:95
const CanonicalForm & w
Definition: facAbsFact.cc:51
CanonicalForm mipo
Definition: facAlgExt.cc:57
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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
b *CanonicalForm B
Definition: facBivar.cc:52
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
bool found
Definition: facFactorize.cc:55
CFList & eval
Definition: facFactorize.cc:47
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...
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
int j
Definition: facHensel.cc:110
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
number absValue(poly p)
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
void init()
Definition: lintree.cc:864
#define M
Definition: sirandom.c:25
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
int F1(int a1, int &r1)
F1.
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ normalize()

static void normalize ( CFAFList L)
inlinestatic

normalize factors, i.e. make factors monic

Definition at line 37 of file facAbsBiFact.h.

38 {
39  for (CFAFListIterator i= L; i.hasItem(); i++)
40  i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
41  i.getItem().minpoly(), i.getItem().exp());
42 }

◆ uniAbsFactorize()

CFAFList uniAbsFactorize ( const CanonicalForm F,
bool  full = false 
)

univariate absolute factorization over Q

Returns
uniAbsFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor
Parameters
[in]Funivariate poly irreducible over Q
[in]fulltrue if all factors should be returned