My Project
Loading...
Searching...
No Matches
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
 
static void normalize (CFAFList &L)
 normalize factors, i.e. make factors monic
 
CFAFList uniAbsFactorize (const CanonicalForm &F, bool full=false)
 univariate absolute factorization over Q
 

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 212 of file facAbsBiFact.cc.

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

◆ 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