main absolute factorization routine, expects bivariate poly which is irreducible over Q
213{
219
220 mpz_t *
M=
new mpz_t [4];
225
226 mpz_t * S=new mpz_t [2];
227 mpz_init (S[0]);
228 mpz_init (S[1]);
229
231
233 {
235 {
241
242 mpz_clear (S[0]);
243 mpz_clear (S[1]);
244 delete [] S;
245 if (!isRat)
248 }
250 if (
result.getFirst().factor().inCoeffDomain())
254 iter.getItem().minpoly(),
iter.getItem().exp());
260
261 mpz_clear (S[0]);
262 mpz_clear (S[1]);
263 delete [] S;
264 if (!isRat)
267 }
268
270 {
276
277 mpz_clear (S[0]);
278 mpz_clear (S[1]);
279 delete [] S;
280 if (!isRat)
283 }
289 bool rec= false;
296differentevalpoint:
297 while (1)
298 {
302
303
307
310
312 {
314 {
315 if (isRat)
323
324 mpz_clear (S[0]);
325 mpz_clear (S[1]);
326 delete [] S;
328 }
329 else
330 {
333 {
334 if (isRat)
341
342 mpz_clear (S[0]);
343 mpz_clear (S[1]);
344 delete [] S;
346 }
347 rec= true;
348 continue;
349 }
350 }
352 smallestFactor=
iter.getItem().factor();
354 {
357 break;
358 smallestFactor=
iter.getItem().factor();
359 }
360
365 {
366 if (!
iter.getItem().factor().isUnivariate() &&
368 {
369 smallestFactor=
iter.getItem().factor();
371 }
372 }
373 if (tdegF % minTdeg == 0)
374 break;
376 rec=true;
377 }
380
385
387 !
gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
389 !
gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
390 if (!xValid || !yValid)
391 {
392 rec= true;
394 goto differentevalpoint;
395 }
396
398
400
403 for (
int i= 1;
i < 3;
i++)
404 {
406
407 int s= tdegF/minTdeg + 1;
411
417 }
418
419
421#ifdef HAVE_FLINT
422 fmpz_poly_t FLINTFi;
425 nmod_poly_t FLINTFpi, FLINTGpi;
427 {
429 smallestFactorEvalx/
lc (smallestFactorEvalx));
431 }
432 else
433 {
435 smallestFactorEvaly/
lc (smallestFactorEvaly));
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
444# ifndef slong
445# define slong long
446# endif
447
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,
460
461 nmod_poly_factor_clear (nmodFactors);
464
468
472#elif defined(HAVE_NTL)
476
478 {
481 }
482 zz_pX NTLFpi, NTLGpi;
484 {
487 }
488 else
489 {
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);
502
505#else
507#endif
508
510 liftedSmallestFactor= pk (liftedSmallestFactor);
512 liftedSmallestFactor= liftedSmallestFactor (
eval[0],1);
513 else
514 liftedSmallestFactor= liftedSmallestFactor (
eval[1],1);
515
519 for (
int j= 1;
j <
s;
j++)
520 {
522 (*M) (
j+1,
j)= -liftedSmallestFactor;
523 }
524
525 #ifdef HAVE_FLINT
526 fmpz_mat_t FLINTM;
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);
536 fmpz_mat_clear(FLINTM);
537 #elif defined(HAVE_NTL)
539
540 ZZ det;
541
542 transpose (*NTLM, *NTLM);
543 (void) LLL (det, *NTLM, 1L, 1L);
544 transpose (*NTLM, *NTLM);
547 delete NTLM;
548 #else
550 #endif
551
553 for (
int j= 1;
j <=
s;
j++)
555
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]);
568 delete [] link;
569 fmpz_poly_factor_clear (liftedFactors);
570#endif
571
572 if (mipoFactors.
length() > 1 ||
574 mipo.inCoeffDomain())
575 {
576 rec=true;
577 goto differentevalpoint;
578 }
579 else
581 }
582
584 {
585 rec=true;
586 goto differentevalpoint;
587 }
588
592 else
594
595 int wrongMipo= 0;
596
599 {
604 {
606 wrongMipo++;
607 }
608 if (wrongMipo == mipoFactors.
length())
609 {
610 rec=true;
611 goto differentevalpoint;
612 }
613 wrongMipo= 0;
619 {
621 wrongMipo++;
622 }
623 if (wrongMipo == mipoFactors.
length())
624 {
625 rec=true;
626 goto differentevalpoint;
627 }
628 }
629 else
630 {
635 {
637 wrongMipo++;
638 }
639 if (wrongMipo == mipoFactors.
length())
640 {
641 rec=true;
642 goto differentevalpoint;
643 }
644 wrongMipo= 0;
650 {
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)
665 else
667
671 {
675 }
676
677 wrongMipo= 0;
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
697 else
699
702
703 int liftBound=
degree (F,
y) + 1;
704
706
708
710
714
716 #ifdef HAVE_FLINT
717
718 fmpz_t FLINTf,FLINTD;
719 fmpz_init(FLINTf);
720 fmpz_init(FLINTD);
721 fmpz_poly_t FLINTmipo;
722 fmpz_poly_t FLINTLcf;
723
726
727 fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
728 fmpz_poly_discriminant(FLINTD,FLINTmipo);
729 fmpz_mul(FLINTf,FLINTD,FLINTf);
731
732 fmpz_clear(FLINTf);
733
734 fmpz_poly_clear(FLINTLcf);
735 fmpz_poly_clear(FLINTmipo);
736 #elif defined(HAVE_NTL)
740 ZZ NTLD= discriminant (NTLmipo);
742 #else
744 #endif
745
746
749 {
752 }
753 F *= multiplier;
755
757 int ii= 0;
758 #ifdef HAVE_FLINT
760 fmpz_clear(FLINTD);
761 #elif defined(HAVE_NTL)
763 #endif
767
771 if (bb.
getk() >
b.getk() )
b=bb;
773 if (bb.
getk() >
b.getk() )
b=bb;
774
777
778 bool earlySuccess= false;
781 (F, earlySuccess, earlyFactors, degs, liftBound,
783
784 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
785
787
791
793
796
798
799 if (earlySuccess)
800 biFactors=
Union (earlyFactors, biFactors);
801 else if (!earlySuccess && degs.
getLength() == 1)
802 biFactors= earlyFactors;
803
804 bool swap2= false;
808
811
813 {
817
819 {
824
826 break;
827 }
828 }
829
831 {
832 rec= true;
833 F= bufF;
834 goto differentevalpoint;
835 }
836
837 if (isRat)
839 else
841
847
848 mpz_clear (S[0]);
849 mpz_clear (S[1]);
850 delete [] S;
851
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)
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)
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
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
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
int cf_getBigPrime(int i)
VAR void(* factoryError)(const char *s)
DegreePattern provides a functionality to create, intersect and refine degree patterns.
int getLength() const
getter
ExtensionInfo contains information about extension.
factory's class for variables
class to do operations mod p^k for int's p and k
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
#define DEBOUTLN(stream, objects)
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
const CanonicalForm int const CFList & evaluation
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
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)
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
const Variable & v
< [in] a sqrfree bivariate poly
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 °s, 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 °s, 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 ...
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool delta(X x, Y y, D d)
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
int F1(int a1, int &r1)
F1.
#define TIMING_END_AND_PRINT(t, msg)