My Project
Functions
facFqBivar.h File Reference

This file provides functions for factorizing a bivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF. More...

#include "timing.h"
#include "cf_assert.h"
#include "facFqBivarUtil.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "cfNewtonPolygon.h"
#include "fac_util.h"
#include "cf_algorithm.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
 
CFList biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field. More...
 
CFList biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info)
 
CFList FpBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over $ F_{p} $. More...
 
CFList FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
 factorize a squarefree bivariate polynomial over $ F_{p}(\alpha ) $. More...
 
CFList GFBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over GF More...
 
CFFList FpBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p} $ More...
 
CFFList FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p}(\alpha ) $ More...
 
CFFList GFBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over GF More...
 
CanonicalForm prodMod0 (const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
 $ \prod_{f\in L} {f (0, x)} \ mod\ M $ via divide-and-conquer More...
 
CanonicalForm evalPoint (const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
 find an evaluation point p, s.t. F(p,y) is squarefree and $ deg_{y} (F(p,y))= deg_{y} (F(x,y)) $. More...
 
CFList uniFactorizer (const CanonicalForm &A, const Variable &alpha, const bool &GF)
 Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used. More...
 
CFList extFactorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
 naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible. More...
 
CFList factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
 naive factor recombination. Uses precomputed data to exclude combinations that are not possible. More...
 
Variable chooseExtension (const Variable &alpha, const Variable &beta, int k)
 chooses a field extension. More...
 
int * getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
 compute lifting precisions from the shape of the Newton polygon of F More...
 
void earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=modpk())
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
 
void extEarlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
 detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
 
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 More...
 
CFList henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval)
 hensel Lifting and early factor detection More...
 
CFList extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field. More...
 

Detailed Description

This file provides functions for factorizing a bivariate polynomial over $ F_{p} $ , $ F_{p}(\alpha ) $ or GF.

Author
Martin Lee

Definition in file facFqBivar.h.

Function Documentation

◆ biFactorize()

CFList biFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Returns
biFactorize returns a list of factors of F. If F is not monic its leading coefficient is not outputted.
See also
extBifactorize()

Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.

Parameters
[in]Fa sqrfree bivariate poly
[in]infoinformation about extension

Definition at line 8305 of file facFqBivar.cc.

8306{
8307 if (F.inCoeffDomain())
8308 return CFList(F);
8309
8310 CanonicalForm A= F;
8311 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8312
8315 CanonicalForm gamma= info.getGamma();
8317 int k= info.getGFDegree();
8318 bool extension= info.isInExtension();
8319 if (A.isUnivariate())
8320 {
8321 if (extension == false)
8322 return uniFactorizer (F, alpha, GF);
8323 else
8324 {
8325 CFList source, dest;
8326 A= mapDown (A, info, source, dest);
8327 return uniFactorizer (A, beta, GF);
8328 }
8329 }
8330
8331 CFMap N;
8332 A= compress (A, N);
8333 Variable y= A.mvar();
8334
8335 if (y.level() > 2) return CFList (F);
8336 Variable x= Variable (1);
8337
8338 //remove and factorize content
8339 CanonicalForm contentAx= content (A, x);
8340 CanonicalForm contentAy= content (A);
8341
8342 A= A/(contentAx*contentAy);
8343 CFList contentAxFactors, contentAyFactors;
8344
8345 if (!extension)
8346 {
8347 contentAxFactors= uniFactorizer (contentAx, alpha, GF);
8348 contentAyFactors= uniFactorizer (contentAy, alpha, GF);
8349 }
8350
8351 //trivial case
8352 CFList factors;
8353 if (A.inCoeffDomain())
8354 {
8355 append (factors, contentAxFactors);
8356 append (factors, contentAyFactors);
8357 decompress (factors, N);
8358 return factors;
8359 }
8360 else if (A.isUnivariate())
8361 {
8362 factors= uniFactorizer (A, alpha, GF);
8363 append (factors, contentAxFactors);
8364 append (factors, contentAyFactors);
8365 decompress (factors, N);
8366 return factors;
8367 }
8368
8369
8370 //check trivial case
8371 if (degree (A) == 1 || degree (A, 1) == 1 ||
8372 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8373 {
8374 factors.append (A);
8375
8376 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8377 false, false, N);
8378
8379 if (!extension)
8380 normalize (factors);
8381 return factors;
8382 }
8383
8384 // check derivatives
8385 bool derivXZero= false;
8386 CanonicalForm derivX= deriv (A, x);
8387 CanonicalForm gcdDerivX;
8388 if (derivX.isZero())
8389 derivXZero= true;
8390 else
8391 {
8392 gcdDerivX= gcd (A, derivX);
8393 if (degree (gcdDerivX) > 0)
8394 {
8395 CanonicalForm g= A/gcdDerivX;
8396 CFList factorsG=
8397 Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
8398 append (factorsG, contentAxFactors);
8399 append (factorsG, contentAyFactors);
8400 decompress (factorsG, N);
8401 if (!extension)
8402 normalize (factorsG);
8403 return factorsG;
8404 }
8405 }
8406 bool derivYZero= false;
8407 CanonicalForm derivY= deriv (A, y);
8408 CanonicalForm gcdDerivY;
8409 if (derivY.isZero())
8410 derivYZero= true;
8411 else
8412 {
8413 gcdDerivY= gcd (A, derivY);
8414 if (degree (gcdDerivY) > 0)
8415 {
8416 CanonicalForm g= A/gcdDerivY;
8417 CFList factorsG=
8418 Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
8419 append (factorsG, contentAxFactors);
8420 append (factorsG, contentAyFactors);
8421 decompress (factorsG, N);
8422 if (!extension)
8423 normalize (factorsG);
8424 return factorsG;
8425 }
8426 }
8427 //main variable is chosen s.t. the degree in x is minimal
8428 bool swap= false;
8429 if ((degree (A) > degree (A, x)) || derivXZero)
8430 {
8431 if (!derivYZero)
8432 {
8433 A= swapvar (A, y, x);
8434 swap= derivXZero;
8435 derivXZero= derivYZero;
8436 derivYZero= swap;
8437 swap= true;
8438 }
8439 }
8440
8441 int boundsLength;
8442 bool isIrreducible= false;
8443 int * bounds= computeBounds (A, boundsLength, isIrreducible);
8444 if (isIrreducible)
8445 {
8446 delete [] bounds;
8447 factors.append (A);
8448
8449 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8450 swap, false, N);
8451
8452 if (!extension)
8453 normalize (factors);
8454 return factors;
8455 }
8456
8457 int minBound= bounds[0];
8458 for (int i= 1; i < boundsLength; i++)
8459 {
8460 if (bounds[i] != 0)
8461 minBound= tmin (minBound, bounds[i]);
8462 }
8463
8464 int boundsLength2;
8465 int * bounds2= computeBoundsWrtDiffMainvar (A, boundsLength2, isIrreducible);
8466 int minBound2= bounds2[0];
8467 for (int i= 1; i < boundsLength2; i++)
8468 {
8469 if (bounds2[i] != 0)
8470 minBound2= tmin (minBound2, bounds2[i]);
8471 }
8472
8473
8474 bool fail= false;
8475 CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
8476 CFList uniFactors, list, bufUniFactors;
8477 DegreePattern degs;
8478 DegreePattern bufDegs;
8479
8480 bool fail2= false;
8481 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8482 CFList bufUniFactors2, list2, uniFactors2;
8483 DegreePattern degs2;
8484 DegreePattern bufDegs2;
8485 bool swap2= false;
8486
8487 // several univariate factorizations to obtain more information about the
8488 // degree pattern therefore usually less combinations have to be tried during
8489 // the recombination process
8490 int factorNums= 3;
8491 int subCheck1= substituteCheck (A, x);
8492 int subCheck2= substituteCheck (A, y);
8493 bool symmetric= false;
8494
8495 TIMING_START (fac_fq_uni_total);
8496 for (int i= 0; i < factorNums; i++)
8497 {
8498 bufAeval= A;
8499 TIMING_START (fac_fq_bi_evaluation);
8500 bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
8501 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8502 if (!derivXZero && !fail2 && !symmetric)
8503 {
8504 if (i == 0)
8505 {
8506 buf= swapvar (A, x, y);
8507 symmetric= (A/Lc (A) == buf/Lc (buf));
8508 }
8509 bufAeval2= buf;
8510 TIMING_START (fac_fq_bi_evaluation);
8511 bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
8512 TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
8513 "time to find eval point wrt y: ");
8514 }
8515 // first try to change main variable if there is no valid evaluation point
8516 if (fail && (i == 0))
8517 {
8518 if (!derivXZero && !fail2 && !symmetric)
8519 {
8520 bufEvaluation= bufEvaluation2;
8521 int dummy= subCheck2;
8522 subCheck2= subCheck1;
8523 subCheck1= dummy;
8524 tmp= A;
8525 A= buf;
8526 buf= tmp;
8527 bufAeval= bufAeval2;
8528 swap2= true;
8529 fail= false;
8530 }
8531 else
8532 fail= true;
8533 }
8534
8535 // if there is no valid evaluation point pass to a field extension
8536 if (fail && (i == 0))
8537 {
8538 factors= extBiFactorize (A, info);
8539 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8540 swap, swap2, N);
8541 normalize (factors);
8542 delete [] bounds;
8543 delete [] bounds2;
8544 return factors;
8545 }
8546
8547 // there is at least one valid evaluation point
8548 // but we do not compute more univariate factorization over an extension
8549 if (fail && (i != 0))
8550 break;
8551
8552 // univariate factorization
8553 TIMING_START (fac_fq_uni_factorizer);
8554 bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
8555 TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8558 (prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
8559
8560 if (!derivXZero && !fail2 && !symmetric)
8561 {
8562 TIMING_START (fac_fq_uni_factorizer);
8563 bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
8564 TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8567 (prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
8568 }
8569
8570 if (bufUniFactors.length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8572 {
8573 if (extension)
8574 {
8575 CFList source, dest;
8576 appendMapDown (factors, A, info, source, dest);
8577 }
8578 else
8579 factors.append (A);
8580
8581 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8582 swap, swap2, N);
8583
8584 if (!extension)
8585 normalize (factors);
8586 delete [] bounds;
8587 delete [] bounds2;
8588 return factors;
8589 }
8590
8591 if (i == 0 && !extension)
8592 {
8593 if (subCheck1 > 0)
8594 {
8595 int subCheck= substituteCheck (bufUniFactors);
8596
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 {
8599 CanonicalForm bufA= A;
8600 subst (bufA, bufA, subCheck, x);
8601 factors= biFactorize (bufA, info);
8602 reverseSubst (factors, subCheck, x);
8603 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8604 swap, swap2, N);
8605 if (!extension)
8606 normalize (factors);
8607 delete [] bounds;
8608 delete [] bounds2;
8609 return factors;
8610 }
8611 }
8612
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8614 {
8615 int subCheck= substituteCheck (bufUniFactors2);
8616
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 {
8619 CanonicalForm bufA= A;
8620 subst (bufA, bufA, subCheck, y);
8621 factors= biFactorize (bufA, info);
8622 reverseSubst (factors, subCheck, y);
8623 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8624 swap, swap2, N);
8625 if (!extension)
8626 normalize (factors);
8627 delete [] bounds;
8628 delete [] bounds2;
8629 return factors;
8630 }
8631 }
8632 }
8633
8634 // degree analysis
8635 bufDegs = DegreePattern (bufUniFactors);
8636 if (!derivXZero && !fail2 && !symmetric)
8637 bufDegs2= DegreePattern (bufUniFactors2);
8638
8639 if (i == 0)
8640 {
8641 Aeval= bufAeval;
8642 evaluation= bufEvaluation;
8643 uniFactors= bufUniFactors;
8644 degs= bufDegs;
8645 if (!derivXZero && !fail2 && !symmetric)
8646 {
8647 Aeval2= bufAeval2;
8648 evaluation2= bufEvaluation2;
8649 uniFactors2= bufUniFactors2;
8650 degs2= bufDegs2;
8651 }
8652 }
8653 else
8654 {
8655 degs.intersect (bufDegs);
8656 if (!derivXZero && !fail2 && !symmetric)
8657 {
8658 degs2.intersect (bufDegs2);
8659 if (bufUniFactors2.length() < uniFactors2.length())
8660 {
8661 uniFactors2= bufUniFactors2;
8662 Aeval2= bufAeval2;
8663 evaluation2= bufEvaluation2;
8664 }
8665 }
8666 if (bufUniFactors.length() < uniFactors.length())
8667 {
8668 uniFactors= bufUniFactors;
8669 Aeval= bufAeval;
8670 evaluation= bufEvaluation;
8671 }
8672 }
8673 list.append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8675 list2.append (bufEvaluation2);
8676 }
8677 TIMING_END_AND_PRINT (fac_fq_uni_total,
8678 "total time for univariate factorizations: ");
8679
8680 if (!derivXZero && !fail2 && !symmetric)
8681 {
8682 if ((uniFactors.length() > uniFactors2.length() && minBound2 <= minBound)||
8683 (uniFactors.length() == uniFactors2.length()
8684 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8685 {
8686 degs= degs2;
8687 uniFactors= uniFactors2;
8688 evaluation= evaluation2;
8689 Aeval= Aeval2;
8690 A= buf;
8691 swap2= true;
8692 }
8693 }
8694
8695 if (degs.getLength() == 1) // A is irreducible
8696 {
8697 if (extension)
8698 {
8699 CFList source, dest;
8700 appendMapDown (factors, A, info, source, dest);
8701 }
8702 else
8703 factors.append (A);
8704 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8705 swap, swap2, N);
8706 if (!extension)
8707 normalize (factors);
8708 delete [] bounds;
8709 delete [] bounds2;
8710 return factors;
8711 }
8712
8713 int liftBound= degree (A, y) + 1;
8714
8715 if (swap2)
8716 {
8717 delete [] bounds;
8718 bounds= bounds2;
8719 minBound= minBound2;
8720 }
8721
8722 TIMING_START (fac_fq_bi_shift_to_zero);
8723 A= A (y + evaluation, y);
8724 TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
8725 "time to shift eval to zero: ");
8726
8727 int degMipo= 1;
8728 if (extension && alpha.level() != 1 && k==1)
8729 degMipo= degree (getMipo (alpha));
8730
8731 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8732
8733 if ((GF && !extension) || (GF && extension && k != 1))
8734 {
8735 bool earlySuccess= false;
8736 CFList earlyFactors;
8737 TIMING_START (fac_fq_bi_hensel_lift);
8738 uniFactors= henselLiftAndEarly
8739 (A, earlySuccess, earlyFactors, degs, liftBound,
8740 uniFactors, info, evaluation);
8741 TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8744
8745 CanonicalForm MODl= power (y, liftBound);
8746
8747 TIMING_START (fac_fq_bi_factor_recombination);
8748 if (extension)
8749 factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8750 evaluation, 1, uniFactors.length()/2);
8751 else
8752 factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
8753 uniFactors.length()/2);
8754 TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8757 if (earlySuccess)
8758 factors= Union (earlyFactors, factors);
8759 else if (!earlySuccess && degs.getLength() == 1)
8760 factors= earlyFactors;
8761 }
8762 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8763 {
8764 TIMING_START (fac_fq_bi_hensel_lift);
8765 if (extension)
8766 {
8767 CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
8769 );
8770 factors= Union (lll, factors);
8771 }
8772 else if (alpha.level() == 1 && !GF)
8773 {
8774 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8775 symmetric, evaluation);
8776 factors= Union (lll, factors);
8777 }
8778 else if (!extension && (alpha != x || GF))
8779 {
8780 CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
8781 symmetric, evaluation);
8782 factors= Union (lll, factors);
8783 }
8784 TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8787 }
8788 else
8789 {
8790 bool earlySuccess= false;
8791 CFList earlyFactors;
8792 TIMING_START (fac_fq_bi_hensel_lift);
8793 uniFactors= henselLiftAndEarly
8794 (A, earlySuccess, earlyFactors, degs, liftBound,
8795 uniFactors, info, evaluation);
8796 TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8799
8800 CanonicalForm MODl= power (y, liftBound);
8801 if (!extension)
8802 {
8803 TIMING_START (fac_fq_bi_factor_recombination);
8804 factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1, 3);
8805 TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
8806 "time for small subset naive recombi over Fq: ");
8807
8808 int oldUniFactorsLength= uniFactors.length();
8809 if (degree (A) > 0)
8810 {
8811 CFList tmp;
8812 TIMING_START (fac_fq_bi_hensel_lift);
8813 if (alpha.level() == 1)
8814 tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8815 liftBound, evaluation
8816 );
8817 else
8818 {
8819 if (degree (A) > getCharacteristic())
8820 tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
8821 1, alpha, liftBound, evaluation
8822 );
8823 else
8824 tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
8825 alpha, liftBound, evaluation
8826 );
8827 }
8828 TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
8829 "time to increase precision: ");
8830 factors= Union (factors, tmp);
8831 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8832 && uniFactors.length() != oldUniFactorsLength)
8833 )
8834 {
8835 DegreePattern bufDegs= DegreePattern (uniFactors);
8836 degs.intersect (bufDegs);
8837 degs.refine ();
8838 factors= Union (factors, factorRecombination (uniFactors, A, MODl,
8839 degs, evaluation, 4,
8840 uniFactors.length()/2
8841 )
8842 );
8843 }
8844 }
8845 }
8846 else
8847 {
8848 if (beta.level() != 1 || k > 1)
8849 {
8850 if (k > 1)
8851 {
8852 factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8853 evaluation, 1, uniFactors.length()/2
8854 );
8855 }
8856 else
8857 {
8858 factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8859 evaluation, 1, 3
8860 );
8861 if (degree (A) > 0)
8862 {
8863 CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
8864 DegreePattern bufDegs= DegreePattern (tmp);
8865 degs.intersect (bufDegs);
8866 degs.refine ();
8867 factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
8868 degs, evaluation,
8869 1, tmp.length()/2
8870 )
8871 );
8872 }
8873 }
8874 }
8875 else
8876 {
8877 factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
8878 evaluation, 1, 3
8879 );
8880 int oldUniFactorsLength= uniFactors.length();
8881 if (degree (A) > 0)
8882 {
8883 int degMipo;
8884 ExtensionInfo info2= init4ext (info, evaluation, degMipo);
8885
8886 CFList source, dest;
8887 CFList tmp= extIncreasePrecision (A, uniFactors, 0,
8888 uniFactors.length(), 1, evaluation,
8889 info2, source, dest, liftBound
8890 );
8891 factors= Union (factors, tmp);
8892 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8893 && uniFactors.length() != oldUniFactorsLength)
8894 )
8895 {
8896 DegreePattern bufDegs= DegreePattern (uniFactors);
8897 degs.intersect (bufDegs);
8898 degs.refine ();
8899 factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
8900 info, degs, evaluation,
8901 4, uniFactors.length()/2
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8909 if (earlySuccess)
8910 factors= Union (earlyFactors, factors);
8911 else if (!earlySuccess && degs.getLength() == 1)
8912 factors= earlyFactors;
8913 }
8914
8915 if (!swap2)
8916 delete [] bounds2;
8917 delete [] bounds;
8918
8919 appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
8920 swap, swap2, N);
8921 if (!extension)
8922 normalize (factors);
8923
8924 return factors;
8925}
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
#define GaloisFieldDomain
Definition: cf_defs.h:18
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:124
int igcd(int a, int b)
Definition: cf_util.cc:56
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() 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
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
int getGFDegree() const
getter
bool isInExtension() const
getter
CanonicalForm getGamma() const
getter
CanonicalForm getDelta() const
getter
Variable getAlpha() const
getter
Variable getBeta() const
getter
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
int level() const
Definition: factory.h:143
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
Variable alpha
Definition: facAbsBiFact.cc:52
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
Variable beta
Definition: facAbsFact.cc:95
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)
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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...
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
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
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
Definition: facFqBivar.cc:8305
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:3477
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
Definition: facFqBivar.cc:7714
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition: facFqBivar.cc:8930
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
Definition: facFqBivar.cc:4269
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
Definition: facFqBivar.cc:3828
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
Definition: facFqBivar.cc:6861
CFListIterator i
Definition: facFqBivar.cc:73
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:372
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition: facFqBivar.cc:86
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:1154
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition: facFqBivar.cc:162
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:588
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
Definition: facFqBivar.cc:7659
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
Definition: facFqBivar.cc:4136
const ExtensionInfo & info
< [in] sqrfree poly
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
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:1027
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ biSqrfFactorizeHelper()

CFList biSqrfFactorizeHelper ( const CanonicalForm G,
const ExtensionInfo info 
)
inline

Definition at line 55 of file facFqBivar.h.

56{
57 CFMap N;
59 CanonicalForm contentX= content (F, 1);
60 CanonicalForm contentY= content (F, 2);
61 F /= (contentX*contentY);
62 CFFList contentXFactors, contentYFactors;
63 if (info.getAlpha().level() != 1)
64 {
65 contentXFactors= factorize (contentX, info.getAlpha());
66 contentYFactors= factorize (contentY, info.getAlpha());
67 }
68 else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
69 {
70 contentXFactors= factorize (contentX);
71 contentYFactors= factorize (contentY);
72 }
73 else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
74 {
75 CFList bufContentX, bufContentY;
76 bufContentX= biFactorize (contentX, info);
77 bufContentY= biFactorize (contentY, info);
78 for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
79 contentXFactors.append (CFFactor (iter.getItem(), 1));
80 for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
81 contentYFactors.append (CFFactor (iter.getItem(), 1));
82 }
83
84 if (contentXFactors.getFirst().factor().inCoeffDomain())
85 contentXFactors.removeFirst();
86 if (contentYFactors.getFirst().factor().inCoeffDomain())
87 contentYFactors.removeFirst();
88 if (F.inCoeffDomain())
89 {
91 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
92 result.append (N (i.getItem().factor()));
93 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
94 result.append (N (i.getItem().factor()));
96 result.insert (Lc (G));
97 return result;
98 }
99 mpz_t * M=new mpz_t [4];
100 mpz_init (M[0]);
101 mpz_init (M[1]);
102 mpz_init (M[2]);
103 mpz_init (M[3]);
104
105 mpz_t * S=new mpz_t [2];
106 mpz_init (S[0]);
107 mpz_init (S[1]);
108
109 F= compress (F, M, S);
111 for (CFListIterator i= result; i.hasItem(); i++)
112 i.getItem()= N (decompress (i.getItem(), M, S));
113 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
114 result.append (N(i.getItem().factor()));
115 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
116 result.append (N (i.getItem().factor()));
118 result.insert (Lc(G));
119
120 mpz_clear (M[0]);
121 mpz_clear (M[1]);
122 mpz_clear (M[2]);
123 mpz_clear (M[3]);
124 delete [] M;
125
126 mpz_clear (S[0]);
127 mpz_clear (S[1]);
128 delete [] S;
129
130 return result;
131}
int i
Definition: cfEzgcd.cc:132
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:409
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
CFFListIterator iter
Definition: facAbsBiFact.cc:54
return result
Definition: facAbsBiFact.cc:76
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Definition: facFqBivar.cc:8305
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define M
Definition: sirandom.c:25

◆ chooseExtension()

Variable chooseExtension ( const Variable alpha,
const Variable beta,
int  k 
)

chooses a field extension.

Returns
chooseExtension returns an extension specified by beta of appropiate size
Parameters
[in]alphasome algebraic variable
[in]betasome algebraic variable
[in]ksome int

Definition at line 808 of file facFqBivar.cc.

809{
810 int i=1, m= 2;
811 // extension of F_p needed
812 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
813 {
814 i= 1;
815 m= 2;
816 } //extension of F_p(alpha) needed but want to factorize over F_p
817 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
818 {
819 i= 1;
820 m= degree (getMipo (alpha)) + 1;
821 } //extension of F_p(alpha) needed for first time
822 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
823 {
824 i= 2;
825 m= degree (getMipo (alpha));
826 }
827 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
828 {
829 m= degree (getMipo (beta));
830 i= degree (getMipo (alpha))/m + 1;
831 }
832 #if defined(HAVE_FLINT)
833 nmod_poly_t Irredpoly;
835 nmod_poly_randtest_monic_irreducible(Irredpoly,FLINTrandom,i*m+1);
836 CanonicalForm newMipo= convertnmod_poly_t2FacCF(Irredpoly,Variable (1));
837 #elif defined(HAVE_NTL)
839 {
842 }
843 zz_pX NTLIrredpoly;
844 BuildIrred (NTLIrredpoly, i*m);
845 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
846 #else
847 factoryError("NTL/FLINT missing: chooseExtension");
848 #endif
849 return rootOf (newMipo);
850}
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
int m
Definition: cfEzgcd.cc:128
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
nmod_poly_init(FLINTmipo, getCharacteristic())
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
void init()
Definition: lintree.cc:864

◆ earlyFactorDetection()

void earlyFactorDetection ( CFList reconstructedFactors,
CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
int *&  factorsFoundIndex,
DegreePattern degs,
bool &  success,
int  deg,
const CanonicalForm eval,
const modpk b = modpk() 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also
factorRecombination(), extEarlyFactorDetection()
Parameters
[in,out]reconstructedFactorslist of reconstructed factors
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]degstage of Hensel lifting
[in]evalevaluation point
[in]bcoeff bound

Definition at line 973 of file facFqBivar.cc.

977{
979 earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
980 factorsFoundIndex, degs, success, deg, eval, b, den);
981}
CanonicalForm den(const CanonicalForm &f)
CFList & eval
Definition: facFactorize.cc:47
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den)
Definition: facFqBivar.cc:854
const CanonicalForm const modpk & b
Definition: facFqBivar.cc:63

◆ evalPoint()

CanonicalForm evalPoint ( const CanonicalForm F,
CanonicalForm eval,
const Variable alpha,
CFList list,
const bool &  GF,
bool &  fail 
)

find an evaluation point p, s.t. F(p,y) is squarefree and $ deg_{y} (F(p,y))= deg_{y} (F(x,y)) $.

Returns
evalPoint returns an evaluation point, which is valid if and only if fail == false.
Parameters
[in]Fcompressed, bivariate poly
[in,out]evalF (p, y)
[in]alphaalgebraic variable
[in]listlist of points already considered
[in]GFGaloisFieldDomain?
[in,out]failequals true, if there is no valid evaluation point

Definition at line 86 of file facFqBivar.cc.

89{
90 fail= false;
93 FFRandom genFF;
94 GFRandom genGF;
95 CanonicalForm random, mipo;
96 double bound;
97 int p= getCharacteristic ();
98 if (alpha.level() != 1)
99 {
100 mipo= getMipo (alpha);
101 int d= degree (mipo);
102 bound= pow ((double) p, (double) d);
103 }
104 else if (GF)
105 {
106 int d= getGFDegree();
107 bound= ipower (p, d);
108 }
109 else
110 bound= p;
111
112 random= 0;
113 do
114 {
115 if (list.length() >= bound)
116 {
117 fail= true;
118 break;
119 }
120 if (list.isEmpty())
121 random= 0;
122 else if (GF)
123 {
124 if (list.length() == 1)
125 random= getGFGenerator();
126 else
127 random= genGF.generate();
128 }
129 else if (list.length() < p || alpha.level() == 1)
130 random= genFF.generate();
131 else if (alpha != x && list.length() >= p)
132 {
133 if (list.length() == p)
134 random= alpha;
135 else
136 {
137 AlgExtRandomF genAlgExt (alpha);
138 random= genAlgExt.generate();
139 }
140 }
141 if (find (list, random)) continue;
142 eval= F (random, x);
143 if (degree (eval) != degree (F, y))
144 { //leading coeff vanishes
145 if (!find (list, random))
146 list.append (random);
147 continue;
148 }
149 if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
150 { //evaluated polynomial is not squarefree
151 if (!find (list, random))
152 list.append (random);
153 continue;
154 }
155 } while (find (list, random));
156
157 return random;
158}
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
int getGFDegree()
Definition: cf_char.cc:75
CanonicalForm getGFGenerator()
Definition: cf_char.cc:81
int p
Definition: cfModGcd.cc:4078
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
generate random elements in F_p(alpha)
Definition: cf_random.h:70
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
Definition: cf_random.cc:68
generate random elements in GF
Definition: cf_random.h:32
CanonicalForm generate() const
Definition: cf_random.cc:78
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm mipo
Definition: facAlgExt.cc:57
template bool find(const List< CanonicalForm > &, const CanonicalForm &)

◆ extBiFactorize()

CFList extBiFactorize ( const CanonicalForm F,
const ExtensionInfo info 
)

Factorization over an extension of initial field.

Returns
extBiFactorize returns factorization of F over initial field
See also
biFactorize()
Parameters
[in]Fpoly to be factored
[in]infoinfo about extension

Definition at line 8930 of file facFqBivar.cc.

8931{
8932
8933 CanonicalForm A= F;
8936 int k= info.getGFDegree();
8937 char cGFName= info.getGFName();
8939
8940 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8941 Variable x= Variable (1);
8942 CFList factors;
8943 if (!GF && alpha == x) // we are in F_p
8944 {
8945 bool extension= true;
8946 int p= getCharacteristic();
8947 if (p*p < (1<<16)) // pass to GF if possible
8948 {
8950 A= A.mapinto();
8951 ExtensionInfo info2= ExtensionInfo (extension);
8952 factors= biFactorize (A, info2);
8953
8956 Variable vBuf= rootOf (mipo.mapinto());
8957 for (CFListIterator j= factors; j.hasItem(); j++)
8958 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8959 prune (vBuf);
8960 }
8961 else // not able to pass to GF, pass to F_p(\alpha)
8962 {
8964 Variable v= rootOf (mipo);
8965 ExtensionInfo info2= ExtensionInfo (v);
8966 factors= biFactorize (A, info2);
8967 prune (v);
8968 }
8969 return factors;
8970 }
8971 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8972 {
8973 if (k == 1) // need factorization over F_p
8974 {
8975 int extDeg= degree (getMipo (alpha));
8976 extDeg++;
8978 Variable v= rootOf (mipo);
8979 ExtensionInfo info2= ExtensionInfo (v);
8980 factors= biFactorize (A, info2);
8981 prune (v);
8982 }
8983 else
8984 {
8985 if (beta == x)
8986 {
8988 CanonicalForm primElem, imPrimElem;
8989 bool primFail= false;
8990 Variable vBuf;
8991 primElem= primitiveElement (alpha, vBuf, primFail);
8992 ASSERT (!primFail, "failure in integer factorizer");
8993 if (primFail)
8994 ; //ERROR
8995 else
8996 imPrimElem= mapPrimElem (primElem, alpha, v);
8997
8998 CFList source, dest;
8999 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
9000 source, dest);
9001 ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
9002 factors= biFactorize (bufA, info2);
9003 prune (v);
9004 }
9005 else
9006 {
9008 CanonicalForm primElem, imPrimElem;
9009 bool primFail= false;
9010 Variable vBuf;
9011 ASSERT (!primFail, "failure in integer factorizer");
9012 if (primFail)
9013 ; //ERROR
9014 else
9015 imPrimElem= mapPrimElem (delta, beta, v);
9016
9017 CFList source, dest;
9018 CanonicalForm bufA= mapDown (A, info, source, dest);
9019 source= CFList();
9020 dest= CFList();
9021 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9022 ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
9023 factors= biFactorize (bufA, info2);
9024 prune (v);
9025 }
9026 }
9027 return factors;
9028 }
9029 else // we are in GF (p^k)
9030 {
9031 int p= getCharacteristic();
9032 int extensionDeg= getGFDegree();
9033 bool extension= true;
9034 if (k == 1) // need factorization over F_p
9035 {
9036 extensionDeg++;
9037 if (ipower (p, extensionDeg) < (1<<16))
9038 // pass to GF(p^k+1)
9039 {
9042 Variable vBuf= rootOf (mipo.mapinto());
9043 A= GF2FalphaRep (A, vBuf);
9044 setCharacteristic (p, extensionDeg, 'Z');
9045 ExtensionInfo info2= ExtensionInfo (extension);
9046 factors= biFactorize (A.mapinto(), info2);
9047 prune (vBuf);
9048 }
9049 else // not able to pass to another GF, pass to F_p(\alpha)
9050 {
9053 Variable vBuf= rootOf (mipo.mapinto());
9054 A= GF2FalphaRep (A, vBuf);
9055 Variable v= chooseExtension (vBuf, beta, k);
9056 ExtensionInfo info2= ExtensionInfo (v, extension);
9057 factors= biFactorize (A, info2);
9058 prune (vBuf);
9059 }
9060 }
9061 else // need factorization over GF (p^k)
9062 {
9063 if (ipower (p, 2*extensionDeg) < (1<<16))
9064 // pass to GF (p^2k)
9065 {
9066 setCharacteristic (p, 2*extensionDeg, 'Z');
9067 ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
9068 factors= biFactorize (GFMapUp (A, extensionDeg), info2);
9069 setCharacteristic (p, extensionDeg, cGFName);
9070 }
9071 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9072 {
9075 Variable v1= rootOf (mipo.mapinto());
9076 A= GF2FalphaRep (A, v1);
9077 Variable v2= chooseExtension (v1, v1, k);
9078 CanonicalForm primElem, imPrimElem;
9079 bool primFail= false;
9080 Variable vBuf;
9081 primElem= primitiveElement (v1, vBuf, primFail);
9082 ASSERT (!primFail, "failure in integer factorizer");
9083 if (primFail)
9084 ; //ERROR
9085 else
9086 imPrimElem= mapPrimElem (primElem, v1, v2);
9087
9088 CFList source, dest;
9089 CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
9090 source, dest);
9091 ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
9092 factors= biFactorize (bufA, info2);
9093 setCharacteristic (p, k, cGFName);
9094 for (CFListIterator i= factors; i.hasItem(); i++)
9096 prune (v1);
9097 }
9098 }
9099 return factors;
9100 }
9101}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:451
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:343
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:71
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:204
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:241
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:196
CanonicalForm mapinto() const
char getGFName() const
getter
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition: facFqBivar.cc:808
int j
Definition: facHensel.cc:110
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56

◆ extEarlyFactorDetection()

void extEarlyFactorDetection ( CFList reconstructedFactors,
CanonicalForm F,
CFList factors,
int &  adaptedLiftBound,
int *&  factorsFoundIndex,
DegreePattern degs,
bool &  success,
const ExtensionInfo info,
const CanonicalForm eval,
int  deg 
)

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated.

See also
factorRecombination(), earlyFactorDetection()
Parameters
[in,out]reconstructedFactorslist of reconstructed factors
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]infoinformation about extension
[in]evalevaluation point
[in]degstage of Hensel lifting

Definition at line 984 of file facFqBivar.cc.

989{
992 CanonicalForm gamma= info.getGamma();
994 int k= info.getGFDegree();
995 DegreePattern bufDegs1= degs, bufDegs2;
997 CFList T= factors;
998 Variable y= F.mvar();
999 Variable x= Variable (1);
1000 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
1001 CanonicalForm M= power (y, deg);
1002 adaptedLiftBound= 0;
1003 bool trueFactor= false;
1004 int d= degree (F), l= 0;
1005 CFList source, dest;
1006 int degMipoBeta= 1;
1007 if (!k && beta.level() != 1)
1008 degMipoBeta= degree (getMipo (beta));
1009 CanonicalForm quot;
1010 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1011 {
1012 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1013 continue;
1014 else
1015 {
1016 g= mulMod2 (i.getItem(), LCBuf, M);
1017 g /= content (g, x);
1018 if (fdivides (g, buf, quot))
1019 {
1020 buf2= g (y - eval, y);
1021 buf2 /= Lc (buf2);
1022
1023 if (!k && beta == x)
1024 {
1025 if (degree (buf2, alpha) < degMipoBeta)
1026 {
1027 appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1028 factorsFoundIndex[l]= 1;
1029 buf= quot;
1030 d -= degree (g);
1031 LCBuf= LC (buf, x);
1032 trueFactor= true;
1033 }
1034 }
1035 else
1036 {
1037 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1038 {
1039 appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1040 factorsFoundIndex[l]= 1;
1041 buf= quot;
1042 d -= degree (g);
1043 LCBuf= LC (buf, x);
1044 trueFactor= true;
1045 }
1046 }
1047 if (trueFactor)
1048 {
1049 T= Difference (T, CFList (i.getItem()));
1050 F= buf;
1051
1052 // compute new possible degree pattern
1053 bufDegs2= DegreePattern (T);
1054 bufDegs1.intersect (bufDegs2);
1055 bufDegs1.refine ();
1056 trueFactor= false;
1057 if (bufDegs1.getLength() <= 1)
1058 {
1059 if (!buf.inCoeffDomain())
1060 {
1061 buf= buf (y - eval, y);
1062 buf /= Lc (buf);
1063 appendMapDown (reconstructedFactors, buf, info, source, dest);
1064 F= 1;
1065 }
1066 break;
1067 }
1068 }
1069 }
1070 }
1071 }
1072 adaptedLiftBound= d + 1;
1073 if (adaptedLiftBound < deg)
1074 {
1075 degs= bufDegs1;
1076 success= true;
1077 }
1078 if (bufDegs1.getLength() <= 1)
1079 degs= bufDegs1;
1080}
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int find(const int x) const
find an element x
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
CanonicalForm buf2
Definition: facFqBivar.cc:75
const CanonicalForm & M
Definition: facFqBivar.cc:62
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2988
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR jList * T
Definition: janet.cc:30

◆ extFactorRecombination()

CFList extFactorRecombination ( CFList factors,
CanonicalForm F,
const CanonicalForm N,
const ExtensionInfo info,
DegreePattern degs,
const CanonicalForm eval,
int  s,
int  thres 
)

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Returns
extFactorRecombination returns a list of factors over the initial field, whose shift to zero is reversed.
See also
factorRecombination(), extEarlyFactorDetection()

naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.

Parameters
[in,out]factorslist of lifted factors that are monic wrt Variable (1), original factors-factors found
[in,out]Fpoly to be factored, F/factors found
[in]NVariable (2)^liftBound
[in]infocontains information about extension
[in]evalevaluation point
[in]salgorithm starts checking subsets of size s
[in]thresthreshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2

Definition at line 372 of file facFqBivar.cc.

376{
377 if (factors.length() == 0)
378 {
379 F= 1;
380 return CFList();
381 }
382 if (F.inCoeffDomain())
383 return CFList();
384
387 CanonicalForm gamma= info.getGamma();
389 int k= info.getGFDegree();
390
392 int l= degree (N);
393 Variable y= F.mvar();
394 Variable x= Variable (1);
395 CFList source, dest;
396 if (degs.getLength() <= 1 || factors.length() == 1)
397 {
398 CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
399 F= 1;
400 return result;
401 }
402
403 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
404 (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
405 int degMipoBeta= 1;
406 if (!k && beta.level() != 1)
407 degMipoBeta= degree (getMipo (beta));
408
409 CFList T, S, Diff;
410 T= factors;
411
413 CanonicalForm buf, buf2, quot;
414
415 buf= F;
416
417 CanonicalForm g, LCBuf= LC (buf, x);
418 int * v= new int [T.length()];
419 for (int i= 0; i < T.length(); i++)
420 v[i]= 0;
421
422 CFArray TT;
423 DegreePattern bufDegs1, bufDegs2;
424 bufDegs1= degs;
425 int subsetDeg;
426 TT= copy (factors);
427 bool nosubset= false;
428 bool recombination= false;
429 bool trueFactor= false;
431 CanonicalForm buf0= buf (0, x)*LCBuf;
432 while (T.length() >= 2*s && s <= thres)
433 {
434 while (nosubset == false)
435 {
436 if (T.length() == s)
437 {
438 delete [] v;
439 if (recombination)
440 {
441 T.insert (LCBuf);
442 g= prodMod (T, M);
443 T.removeFirst();
444 g /= content(g);
445 g= g (y - eval, y);
446 g /= Lc (g);
447 appendTestMapDown (result, g, info, source, dest);
448 F= 1;
449 return result;
450 }
451 else
452 {
453 appendMapDown (result, F (y - eval, y), info, source, dest);
454 F= 1;
455 return result;
456 }
457 }
458 S= subset (v, s, TT, nosubset);
459 if (nosubset) break;
460 subsetDeg= subsetDegree (S);
461 // skip those combinations that are not possible
462 if (!degs.find (subsetDeg))
463 continue;
464 else
465 {
466 test= prodMod0 (S, M);
467 test *= LCBuf;
468 test = mod (test, M);
469 if (fdivides (test, buf0))
470 {
471 S.insert (LCBuf);
472 g= prodMod (S, M);
473 S.removeFirst();
474 g /= content (g, x);
475 if (fdivides (g, buf, quot))
476 {
477 buf2= g (y - eval, y);
478 buf2 /= Lc (buf2);
479
480 if (!k && beta.level() == 1)
481 {
482 if (degree (buf2, alpha) < degMipoBeta)
483 {
484 buf= quot;
485 LCBuf= LC (buf, x);
486 recombination= true;
487 appendTestMapDown (result, buf2, info, source, dest);
488 trueFactor= true;
489 }
490 }
491 else
492 {
493 if (!isInExtension (buf2, gamma, k, delta, source, dest))
494 {
495 buf= quot;
496 LCBuf= LC (buf, x);
497 recombination= true;
498 appendTestMapDown (result, buf2, info, source, dest);
499 trueFactor= true;
500 }
501 }
502 if (trueFactor)
503 {
504 T= Difference (T, S);
505 l -= degree (g);
506 M= power (y, l);
507 buf0= buf (0, x)*LCBuf;
508
509 // compute new possible degree pattern
510 bufDegs2= DegreePattern (T);
511 bufDegs1.intersect (bufDegs2);
512 bufDegs1.refine ();
513 if (T.length() < 2*s || T.length() == s ||
514 bufDegs1.getLength() == 1)
515 {
516 delete [] v;
517 if (recombination)
518 {
519 buf= buf (y-eval,y);
520 buf /= Lc (buf);
521 appendTestMapDown (result, buf, info, source,
522 dest);
523 F= 1;
524 return result;
525 }
526 else
527 {
528 appendMapDown (result, F (y - eval, y), info, source, dest);
529 F= 1;
530 return result;
531 }
532 }
533 trueFactor= false;
534 TT= copy (T);
535 indexUpdate (v, s, T.length(), nosubset);
536 if (nosubset) break;
537 }
538 }
539 }
540 }
541 }
542 s++;
543 if (T.length() < 2*s || T.length() == s)
544 {
545 delete [] v;
546 if (recombination)
547 {
548 buf= buf (y-eval,y);
549 buf /= Lc (buf);
550 appendTestMapDown (result, buf, info, source, dest);
551 F= 1;
552 return result;
553 }
554 else
555 {
556 appendMapDown (result, F (y - eval, y), info, source, dest);
557 F= 1;
558 return result;
559 }
560 }
561 for (int i= 0; i < T.length(); i++)
562 v[i]= 0;
563 nosubset= false;
564 }
565 if (T.length() < 2*s)
566 {
567 appendMapDown (result, F (y - eval, y), info, source, dest);
568 F= 1;
569 delete [] v;
570 return result;
571 }
572
573 if (s > thres)
574 {
575 factors= T;
576 F= buf;
577 degs= bufDegs1;
578 }
579
580 delete [] v;
581 return result;
582}
CanonicalForm test
Definition: cfModGcd.cc:4096
void insert(const T &)
Definition: ftmpl_list.cc:193
const CanonicalForm int s
Definition: facAbsFact.cc:51
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
CFArray copy(const CFList &list)
write elements of list into an array
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
return mod(mulNTL(buf1, buf2, b), M)
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
Definition: facMul.cc:3182

◆ 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. Uses precomputed data to exclude combinations that are not possible.

Returns
factorRecombination returns a list of factors of F.
See also
extFactorRecombination(), earlyFactorDetectection()

naive factor recombination. Uses precomputed data to exclude combinations that are not possible.

Parameters
[in,out]factorslist of lifted factors that are monic wrt Variable (1)
[in,out]Fpoly to be factored
[in]NVariable (2)^liftBound
[in]degsdegree pattern
[in]evalevaluation point
[in]salgorithm starts checking subsets of size s
[in]thresthreshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2
[in]bcoeff bound
[in]denbound on the den if over Q (a)

Definition at line 588 of file facFqBivar.cc.

593{
594 if (factors.length() == 0)
595 {
596 F= 1;
597 return CFList ();
598 }
599 if (F.inCoeffDomain())
600 return CFList();
601 Variable y= Variable (2);
602 if (degs.getLength() <= 1 || factors.length() == 1)
603 {
604 CFList result= CFList (F(y-eval,y));
605 F= 1;
606 return result;
607 }
608#ifdef DEBUGOUTPUT
609 if (b.getp() == 0)
610 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
611 (mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
612 else
613 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
614 (mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
615#endif
616
617 CFList T, S;
618
620 int l= degree (N);
621 T= factors;
623 Variable x= Variable (1);
624 CanonicalForm denom= den, denQuot;
625 CanonicalForm LCBuf= LC (F, x)*denom;
626 CanonicalForm g, quot, buf= F;
627 int * v= new int [T.length()];
628 for (int i= 0; i < T.length(); i++)
629 v[i]= 0;
630 bool nosubset= false;
631 CFArray TT;
632 DegreePattern bufDegs1, bufDegs2;
633 bufDegs1= degs;
634 int subsetDeg;
635 TT= copy (factors);
636 bool recombination= false;
638 bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
639 getCharacteristic() > 0;
640 if (!isRat)
641 On (SW_RATIONAL);
642 CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
643 if (!isRat)
645 while (T.length() >= 2*s && s <= thres)
646 {
647 while (nosubset == false)
648 {
649 if (T.length() == s)
650 {
651 delete [] v;
652 if (recombination)
653 {
654 T.insert (LCBuf);
655 g= prodMod (T, M);
656 if (b.getp() != 0)
657 g= b(g);
658 T.removeFirst();
659 g /= content (g,x);
660 result.append (g(y-eval,y));
661 F= 1;
662 return result;
663 }
664 else
665 {
666 result= CFList (F(y-eval,y));
667 F= 1;
668 return result;
669 }
670 }
671 S= subset (v, s, TT, nosubset);
672 if (nosubset) break;
673 subsetDeg= subsetDegree (S);
674 // skip those combinations that are not possible
675 if (!degs.find (subsetDeg))
676 continue;
677 else
678 {
679 if (!isRat)
680 On (SW_RATIONAL);
681 test= prodMod0 (S, M);
682 if (!isRat)
683 {
684 test *= bCommonDen (test);
686 }
687 test= mulNTL (test, LCBuf, b);
688 test= mod (test, M);
689 if (uniFdivides (test, buf0))
690 {
691 if (!isRat)
692 On (SW_RATIONAL);
693 S.insert (LCBuf);
694 g= prodMod (S, M);
695 S.removeFirst();
696 if (!isRat)
697 {
698 g *= bCommonDen(g);
700 }
701 if (b.getp() != 0)
702 g= b(g);
703 if (!isRat)
704 On (SW_RATIONAL);
705 g /= content (g, x);
706 if (!isRat)
707 {
708 On (SW_RATIONAL);
709 if (!Lc (g).inBaseDomain())
710 g /= Lc (g);
711 g *= bCommonDen (g);
713 g /= icontent (g);
714 On (SW_RATIONAL);
715 }
716 if (fdivides (g, buf, quot))
717 {
718 denom *= abs (lc (g));
719 recombination= true;
720 result.append (g (y-eval,y));
721 if (b.getp() != 0)
722 {
723 denQuot= bCommonDen (quot);
724 buf= quot*denQuot;
726 denom /= gcd (denom, denQuot);
727 On (SW_RATIONAL);
728 }
729 else
730 buf= quot;
731 LCBuf= LC (buf, x)*denom;
732 T= Difference (T, S);
733 l -= degree (g);
734 M= power (y, l);
735 buf0= mulNTL (buf (0, x), LCBuf);
736 if (!isRat)
738 // compute new possible degree pattern
739 bufDegs2= DegreePattern (T);
740 bufDegs1.intersect (bufDegs2);
741 bufDegs1.refine ();
742 if (T.length() < 2*s || T.length() == s ||
743 bufDegs1.getLength() == 1)
744 {
745 delete [] v;
746 if (recombination)
747 {
748 result.append (buf (y-eval,y));
749 F= 1;
750 return result;
751 }
752 else
753 {
754 result= CFList (F (y-eval,y));
755 F= 1;
756 return result;
757 }
758 }
759 TT= copy (T);
760 indexUpdate (v, s, T.length(), nosubset);
761 if (nosubset) break;
762 }
763 if (!isRat)
765 }
766 }
767 }
768 s++;
769 if (T.length() < 2*s || T.length() == s)
770 {
771 delete [] v;
772 if (recombination)
773 {
774 result.append (buf(y-eval,y));
775 F= 1;
776 return result;
777 }
778 else
779 {
780 result= CFList (F(y-eval,y));
781 F= 1;
782 return result;
783 }
784 }
785 for (int i= 0; i < T.length(); i++)
786 v[i]= 0;
787 nosubset= false;
788 }
789 delete [] v;
790 if (T.length() < 2*s)
791 {
792 result.append (F(y-eval,y));
793 F= 1;
794 return result;
795 }
796
797 if (s > thres)
798 {
799 factors= T;
800 F= buf;
801 degs= bufDegs1;
802 }
803
804 return result;
805}
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition: facMul.cc:413
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
Definition: facMul.cc:3761

◆ FpBiFactorize()

CFFList FpBiFactorize ( const CanonicalForm G,
bool  substCheck = true 
)
inline

factorize a bivariate polynomial over $ F_{p} $

Returns
FpBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FqBiFactorize(), GFBiFactorize()
Parameters
[in]Ga bivariate poly
[in]substCheckenables substitute check

Definition at line 190 of file facFqBivar.h.

193{
195 CFMap N;
197
198 if (substCheck)
199 {
200 bool foundOne= false;
201 int * substDegree= NEW_ARRAY(int,F.level());
202 for (int i= 1; i <= F.level(); i++)
203 {
204 substDegree[i-1]= substituteCheck (F, Variable (i));
205 if (substDegree [i-1] > 1)
206 {
207 foundOne= true;
208 subst (F, F, substDegree[i-1], Variable (i));
209 }
210 }
211 if (foundOne)
212 {
213 CFFList result= FpBiFactorize (F, false);
214 CFFList newResult, tmp;
216 newResult.insert (result.getFirst());
217 result.removeFirst();
218 for (CFFListIterator i= result; i.hasItem(); i++)
219 {
220 tmp2= i.getItem().factor();
221 for (int j= 1; j <= F.level(); j++)
222 {
223 if (substDegree[j-1] > 1)
224 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225 }
226 tmp= FpBiFactorize (tmp2, false);
227 tmp.removeFirst();
228 for (CFFListIterator j= tmp; j.hasItem(); j++)
229 newResult.append (CFFactor (j.getItem().factor(),
230 j.getItem().exp()*i.getItem().exp()));
231 }
232 decompress (newResult, N);
233 DELETE_ARRAY(substDegree);
234 return newResult;
235 }
236 DELETE_ARRAY(substDegree);
237 }
238
239 CanonicalForm LcF= Lc (F);
240 CanonicalForm contentX= content (F, 1);
241 CanonicalForm contentY= content (F, 2);
242 F /= (contentX*contentY);
243 CFFList contentXFactors, contentYFactors;
244 contentXFactors= factorize (contentX);
245 contentYFactors= factorize (contentY);
246 if (contentXFactors.getFirst().factor().inCoeffDomain())
247 contentXFactors.removeFirst();
248 if (contentYFactors.getFirst().factor().inCoeffDomain())
249 contentYFactors.removeFirst();
250 decompress (contentXFactors, N);
251 decompress (contentYFactors, N);
253 if (F.inCoeffDomain())
254 {
255 result= Union (contentXFactors, contentYFactors);
257 result.insert (CFFactor (LcF, 1));
258 return result;
259 }
260 mpz_t * M=new mpz_t [4];
261 mpz_init (M[0]);
262 mpz_init (M[1]);
263 mpz_init (M[2]);
264 mpz_init (M[3]);
265
266 mpz_t * S=new mpz_t [2];
267 mpz_init (S[0]);
268 mpz_init (S[1]);
269
270 F= compress (F, M, S);
271
272 TIMING_START (fac_fq_bi_sqrf);
273 CFFList sqrf= FpSqrf (F, false);
274 TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
275 "time for bivariate sqrf factors over Fp: ");
276 CFList bufResult;
277 sqrf.removeFirst();
279 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280 {
281 TIMING_START (fac_fq_bi_factor_sqrf);
282 bufResult= biFactorize (iter.getItem().factor(), info);
283 TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
284 "time to factor bivariate sqrf factors over Fp: ");
285 for (i= bufResult; i.hasItem(); i++)
286 result.append (CFFactor (N (decompress (i.getItem(), M, S)),
287 iter.getItem().exp()));
288 }
289
290 result= Union (result, contentXFactors);
291 result= Union (result, contentYFactors);
293 result.insert (CFFactor (LcF, 1));
294
295 mpz_clear (M[0]);
296 mpz_clear (M[1]);
297 mpz_clear (M[2]);
298 mpz_clear (M[3]);
299 delete [] M;
300
301 mpz_clear (S[0]);
302 mpz_clear (S[1]);
303 delete [] S;
304
305 return result;
306}
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
CFList tmp2
Definition: facFqBivar.cc:74
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:190
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FpBiSqrfFactorize()

CFList FpBiSqrfFactorize ( const CanonicalForm G)
inline

factorize a squarefree bivariate polynomial over $ F_{p} $.

Returns
FpBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FqBiSqrfFactorize(), GFBiSqrfFactorize()
Parameters
[in]Ga bivariate poly

Definition at line 141 of file facFqBivar.h.

143{
145 return biSqrfFactorizeHelper (G, info);
146}
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition: facFqBivar.h:55

◆ FqBiFactorize()

CFFList FqBiFactorize ( const CanonicalForm G,
const Variable alpha,
bool  substCheck = true 
)
inline

factorize a bivariate polynomial over $ F_{p}(\alpha ) $

Returns
FqBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpBiFactorize(), FqBiFactorize()
Parameters
[in]Ga bivariate poly
[in]alphaalgebraic variable
[in]substCheckenables substitute check

Definition at line 317 of file facFqBivar.h.

321{
323 CFMap N;
325
326 if (substCheck)
327 {
328 bool foundOne= false;
329 int * substDegree= NEW_ARRAY(int,F.level());
330 for (int i= 1; i <= F.level(); i++)
331 {
332 substDegree[i-1]= substituteCheck (F, Variable (i));
333 if (substDegree [i-1] > 1)
334 {
335 foundOne= true;
336 subst (F, F, substDegree[i-1], Variable (i));
337 }
338 }
339 if (foundOne)
340 {
341 CFFList result= FqBiFactorize (F, alpha, false);
342 CFFList newResult, tmp;
344 newResult.insert (result.getFirst());
345 result.removeFirst();
346 for (CFFListIterator i= result; i.hasItem(); i++)
347 {
348 tmp2= i.getItem().factor();
349 for (int j= 1; j <= F.level(); j++)
350 {
351 if (substDegree[j-1] > 1)
352 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
353 }
354 tmp= FqBiFactorize (tmp2, alpha, false);
355 tmp.removeFirst();
356 for (CFFListIterator j= tmp; j.hasItem(); j++)
357 newResult.append (CFFactor (j.getItem().factor(),
358 j.getItem().exp()*i.getItem().exp()));
359 }
360 decompress (newResult, N);
361 DELETE_ARRAY(substDegree);
362 return newResult;
363 }
364 DELETE_ARRAY(substDegree);
365 }
366
367 CanonicalForm LcF= Lc (F);
368 CanonicalForm contentX= content (F, 1);
369 CanonicalForm contentY= content (F, 2);
370 F /= (contentX*contentY);
371 CFFList contentXFactors, contentYFactors;
372 contentXFactors= factorize (contentX, alpha);
373 contentYFactors= factorize (contentY, alpha);
374 if (contentXFactors.getFirst().factor().inCoeffDomain())
375 contentXFactors.removeFirst();
376 if (contentYFactors.getFirst().factor().inCoeffDomain())
377 contentYFactors.removeFirst();
378 decompress (contentXFactors, N);
379 decompress (contentYFactors, N);
381 if (F.inCoeffDomain())
382 {
383 result= Union (contentXFactors, contentYFactors);
385 result.insert (CFFactor (LcF, 1));
386 return result;
387 }
388
389 mpz_t * M=new mpz_t [4];
390 mpz_init (M[0]);
391 mpz_init (M[1]);
392 mpz_init (M[2]);
393 mpz_init (M[3]);
394
395 mpz_t * S=new mpz_t [2];
396 mpz_init (S[0]);
397 mpz_init (S[1]);
398
399 F= compress (F, M, S);
400
401 TIMING_START (fac_fq_bi_sqrf);
402 CFFList sqrf= FqSqrf (F, alpha, false);
403 TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
404 "time for bivariate sqrf factors over Fq: ");
405 CFList bufResult;
406 sqrf.removeFirst();
408 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
409 {
410 TIMING_START (fac_fq_bi_factor_sqrf);
411 bufResult= biFactorize (iter.getItem().factor(), info);
412 TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
413 "time to factor bivariate sqrf factors over Fq: ");
414 for (i= bufResult; i.hasItem(); i++)
415 result.append (CFFactor (N (decompress (i.getItem(), M, S)),
416 iter.getItem().exp()));
417 }
418
419 result= Union (result, contentXFactors);
420 result= Union (result, contentYFactors);
422 result.insert (CFFactor (LcF, 1));
423
424 mpz_clear (M[0]);
425 mpz_clear (M[1]);
426 mpz_clear (M[2]);
427 mpz_clear (M[3]);
428 delete [] M;
429
430 mpz_clear (S[0]);
431 mpz_clear (S[1]);
432 delete [] S;
433
434 return result;
435}
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:317
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FqBiSqrfFactorize()

CFList FqBiSqrfFactorize ( const CanonicalForm G,
const Variable alpha 
)
inline

factorize a squarefree bivariate polynomial over $ F_{p}(\alpha ) $.

Returns
FqBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpBiSqrfFactorize(), GFBiSqrfFactorize()
Parameters
[in]Ga bivariate poly
[in]alphaalgebraic variable

Definition at line 156 of file facFqBivar.h.

159{
161 return biSqrfFactorizeHelper (G, info);
162}

◆ getLiftPrecisions()

int * getLiftPrecisions ( const CanonicalForm F,
int &  sizeOfOutput,
int  degreeLC 
)

compute lifting precisions from the shape of the Newton polygon of F

Returns
getLiftPrecisions returns lifting precisions computed from the shape of the Newton polygon of F
Parameters
[in]Fa bivariate poly
[in,out]sizeOfOutputsize of the output
[in]degreeLCdegree of the leading coeff [in] of F wrt. Variable (1)

Definition at line 1122 of file facFqBivar.cc.

1123{
1124 int sizeOfNewtonPoly;
1125 int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
1126 int sizeOfRightSide;
1127 int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1128 int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
1129 degreeLC);
1130 delete [] rightSide;
1131 for (int i= 0; i < sizeOfNewtonPoly; i++)
1132 delete [] newtonPolyg[i];
1133 delete [] newtonPolyg;
1134 return result;
1135}
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
Definition: facFqBivar.cc:1083

◆ GFBiFactorize()

CFFList GFBiFactorize ( const CanonicalForm G,
bool  substCheck = true 
)
inline

factorize a bivariate polynomial over GF

Returns
GFBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
See also
FpBiFactorize(), FqBiFactorize()
Parameters
[in]Ga bivariate poly
[in]substCheckenables substitute check

Definition at line 446 of file facFqBivar.h.

449{
451 "GF as base field expected");
453 CFMap N;
455
456 if (substCheck)
457 {
458 bool foundOne= false;
459 int * substDegree=NEW_ARRAY(int,F.level());
460 for (int i= 1; i <= F.level(); i++)
461 {
462 substDegree[i-1]= substituteCheck (F, Variable (i));
463 if (substDegree [i-1] > 1)
464 {
465 foundOne= true;
466 subst (F, F, substDegree[i-1], Variable (i));
467 }
468 }
469 if (foundOne)
470 {
471 CFFList result= GFBiFactorize (F, false);
472 CFFList newResult, tmp;
474 newResult.insert (result.getFirst());
475 result.removeFirst();
476 for (CFFListIterator i= result; i.hasItem(); i++)
477 {
478 tmp2= i.getItem().factor();
479 for (int j= 1; j <= F.level(); j++)
480 {
481 if (substDegree[j-1] > 1)
482 tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
483 }
484 tmp= GFBiFactorize (tmp2, false);
485 tmp.removeFirst();
486 for (CFFListIterator j= tmp; j.hasItem(); j++)
487 newResult.append (CFFactor (j.getItem().factor(),
488 j.getItem().exp()*i.getItem().exp()));
489 }
490 decompress (newResult, N);
491 DELETE_ARRAY(substDegree);
492 return newResult;
493 }
494 DELETE_ARRAY(substDegree);
495 }
496
497 CanonicalForm LcF= Lc (F);
498 CanonicalForm contentX= content (F, 1);
499 CanonicalForm contentY= content (F, 2);
500 F /= (contentX*contentY);
501 CFFList contentXFactors, contentYFactors;
502 contentXFactors= factorize (contentX);
503 contentYFactors= factorize (contentY);
504 if (contentXFactors.getFirst().factor().inCoeffDomain())
505 contentXFactors.removeFirst();
506 if (contentYFactors.getFirst().factor().inCoeffDomain())
507 contentYFactors.removeFirst();
508 decompress (contentXFactors, N);
509 decompress (contentYFactors, N);
511 if (F.inCoeffDomain())
512 {
513 result= Union (contentXFactors, contentYFactors);
515 result.insert (CFFactor (LcF, 1));
516 return result;
517 }
518
519 mpz_t * M=new mpz_t [4];
520 mpz_init (M[0]);
521 mpz_init (M[1]);
522 mpz_init (M[2]);
523 mpz_init (M[3]);
524
525 mpz_t * S=new mpz_t [2];
526 mpz_init (S[0]);
527 mpz_init (S[1]);
528
529 F= compress (F, M, S);
530
531 TIMING_START (fac_fq_bi_sqrf);
532 CFFList sqrf= GFSqrf (F, false);
533 TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
534 "time for bivariate sqrf factors over GF: ");
535 CFList bufResult;
536 sqrf.removeFirst();
538 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
539 {
540 TIMING_START (fac_fq_bi_factor_sqrf);
541 bufResult= biFactorize (iter.getItem().factor(), info);
542 TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
543 "time to factor bivariate sqrf factors over GF: ");
544 for (i= bufResult; i.hasItem(); i++)
545 result.append (CFFactor (N (decompress (i.getItem(), M, S)),
546 iter.getItem().exp()));
547 }
548
549 result= Union (result, contentXFactors);
550 result= Union (result, contentYFactors);
552 result.insert (CFFactor (LcF, 1));
553
554 mpz_clear (M[0]);
555 mpz_clear (M[1]);
556 mpz_clear (M[2]);
557 mpz_clear (M[3]);
558 delete [] M;
559
560 mpz_clear (S[0]);
561 mpz_clear (S[1]);
562 delete [] S;
563
564 return result;
565}
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:446
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
VAR char gf_name
Definition: gfops.cc:52

◆ GFBiSqrfFactorize()

CFList GFBiSqrfFactorize ( const CanonicalForm G)
inline

factorize a squarefree bivariate polynomial over GF

Returns
GFBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
See also
FpBiSqrfFactorize(), FqBiSqrfFactorize()
Parameters
[in]Ga bivariate poly

Definition at line 172 of file facFqBivar.h.

174{
176 "GF as base field expected");
178 return biSqrfFactorizeHelper (G, info);
179}

◆ henselLiftAndEarly() [1/2]

CFList henselLiftAndEarly ( CanonicalForm A,
bool &  earlySuccess,
CFList earlyFactors,
DegreePattern degs,
int &  liftBound,
const CFList uniFactors,
const ExtensionInfo info,
const CanonicalForm eval 
)

hensel Lifting and early factor detection

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point

Definition at line 1457 of file facFqBivar.cc.

1461{
1462 modpk dummy= modpk();
1463 CanonicalForm den= 1;
1464 return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
1465 uniFactors, info, eval, dummy, den);
1466}
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
return modpk(p, k)

◆ henselLiftAndEarly() [2/2]

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

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
[in,out]Apoly to be factored, returns poly divided by detected factors in case of success
[in,out]earlySuccessindicating success
[in,out]earlyFactorslist of factors detected at early stage of Hensel lifting
[in,out]degsdegree pattern
[in,out]liftBound(adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point
[in]bcoeff bound
[in]denbound on the den if over Q(a)

Definition at line 1154 of file facFqBivar.cc.

1158{
1161 CanonicalForm gamma= info.getGamma();
1163 bool extension= info.isInExtension();
1164
1165 int sizeOfLiftPre;
1166 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1167
1168 Variable x= Variable (1);
1169 Variable y= Variable (2);
1170 CFArray Pi;
1171 CFList diophant;
1172 CFList bufUniFactors= uniFactors;
1173 On (SW_RATIONAL);
1174 CanonicalForm bufA= A;
1175 if (!Lc (A).inBaseDomain())
1176 {
1177 bufA /= Lc (A);
1178 CanonicalForm denBufA= bCommonDen (bufA);
1179 bufA *= denBufA;
1180 Off (SW_RATIONAL);
1181 den /= gcd (den, denBufA);
1182 }
1183 else
1184 {
1185 bufA= A;
1186 Off (SW_RATIONAL);
1187 den /= gcd (den, Lc (A));
1188 }
1189 CanonicalForm lcA0= 0;
1190 bool mipoHasDen= false;
1191 if (getCharacteristic() == 0 && b.getp() != 0)
1192 {
1193 if (alpha.level() == 1)
1194 {
1195 lcA0= lc (A (0, 2));
1196 A *= b.inverse (lcA0);
1197 A= b (A);
1198 for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1199 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1200 }
1201 else
1202 {
1203 lcA0= Lc (A (0,2));
1204 On (SW_RATIONAL);
1205 mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
1206 Off (SW_RATIONAL);
1207 CanonicalForm lcA0inverse= b.inverse (lcA0);
1208 A *= lcA0inverse;
1209 A= b (A);
1210 // Lc of bufUniFactors is in Z
1211 for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
1212 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1213 }
1214 }
1215 bufUniFactors.insert (LC (A, x));
1216 CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
1217 earlySuccess= false;
1218 int newLiftBound= 0;
1219
1220 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1221 int dummy;
1222 int * factorsFoundIndex= new int [uniFactors.length()];
1223 for (int i= 0; i < uniFactors.length(); i++)
1224 factorsFoundIndex [i]= 0;
1225
1226 CFList bufBufUniFactors;
1227 Variable v= alpha;
1228 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1229 henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
1230 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1231 {
1232 henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1233 if (mipoHasDen)
1234 {
1235 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1236 if (hasFirstAlgVar (iter.getItem(), v))
1237 break;
1238 if (v != alpha)
1239 {
1240 bufBufUniFactors= bufUniFactors;
1241 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1243 A= replacevar (A, alpha, v);
1244 }
1245 }
1246
1247 if (!extension)
1248 {
1249 if (v==alpha)
1250 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1251 factorsFoundIndex, degs, earlySuccess,
1252 smallFactorDeg, eval, b, den);
1253 else
1254 earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1255 factorsFoundIndex, degs, earlySuccess,
1256 smallFactorDeg, eval, b, den);
1257 }
1258 else
1259 extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1260 factorsFoundIndex, degs, earlySuccess, info,
1261 eval, smallFactorDeg);
1262 if (degs.getLength() > 1 && !earlySuccess &&
1263 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1264 {
1265 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1266 {
1267 bufUniFactors.insert (LC (A, x));
1268 henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1269 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1270 if (v!=alpha)
1271 {
1272 bufBufUniFactors= bufUniFactors;
1273 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1275 }
1276 if (!extension)
1277 {
1278 if (v==alpha)
1279 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1280 factorsFoundIndex, degs, earlySuccess,
1281 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1282 else
1283 earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1284 factorsFoundIndex, degs, earlySuccess,
1285 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1286 }
1287 else
1288 extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1289 factorsFoundIndex, degs, earlySuccess, info,
1290 eval, liftPre[sizeOfLiftPre-1] + 1);
1291 }
1292 }
1293 else if (earlySuccess)
1294 liftBound= newLiftBound;
1295
1296 int i= sizeOfLiftPre - 1;
1297 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1298 {
1299 if (newLiftBound >= liftPre[i] + 1)
1300 {
1301 bufUniFactors.insert (LC (A, x));
1302 henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
1303 liftPre[i-1] + 1, Pi, diophant, M, b);
1304 if (v!=alpha)
1305 {
1306 bufBufUniFactors= bufUniFactors;
1307 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1309 }
1310 if (!extension)
1311 {
1312 if (v==alpha)
1313 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1314 factorsFoundIndex, degs, earlySuccess,
1315 liftPre[i-1] + 1, eval, b, den);
1316 else
1317 earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1318 factorsFoundIndex, degs, earlySuccess,
1319 liftPre[i-1] + 1, eval, b, den);
1320 }
1321 else
1322 extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1323 factorsFoundIndex, degs, earlySuccess, info,
1324 eval, liftPre[i-1] + 1);
1325 }
1326 else
1327 {
1328 liftBound= newLiftBound;
1329 break;
1330 }
1331 i--;
1332 }
1333 if (earlySuccess)
1334 liftBound= newLiftBound;
1335 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1336 }
1337 else
1338 {
1339 henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
1340 if (mipoHasDen)
1341 {
1342 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1343 if (hasFirstAlgVar (iter.getItem(), v))
1344 break;
1345 if (v != alpha)
1346 {
1347 bufBufUniFactors= bufUniFactors;
1348 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1350 A= replacevar (A, alpha, v);
1351 }
1352 }
1353 if (!extension)
1354 {
1355 if (v==alpha)
1356 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1357 factorsFoundIndex, degs, earlySuccess,
1358 smallFactorDeg, eval, b, den);
1359 else
1360 earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
1361 factorsFoundIndex, degs, earlySuccess,
1362 smallFactorDeg, eval, b, den);
1363 }
1364 else
1365 extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1366 factorsFoundIndex, degs, earlySuccess, info,
1367 eval, smallFactorDeg);
1368 int i= 1;
1369 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1370 i++;
1371 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1372 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1373 {
1374 bufUniFactors.insert (LC (A, x));
1375 henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
1376 dummy, Pi, diophant, M, b);
1377 if (v!=alpha)
1378 {
1379 bufBufUniFactors= bufUniFactors;
1380 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1382 }
1383 if (!extension)
1384 {
1385 if (v==alpha)
1386 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1387 factorsFoundIndex, degs, earlySuccess, dummy,eval,
1388 b, den);
1389 else
1390 earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
1391 factorsFoundIndex, degs, earlySuccess, dummy,eval,
1392 b, den);
1393 }
1394 else
1395 extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
1396 factorsFoundIndex, degs, earlySuccess, info,
1397 eval, dummy);
1398 }
1399 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1400 {
1401 if (newLiftBound >= dummy)
1402 {
1403 bufUniFactors.insert (LC (A, x));
1404 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1405 henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
1406 dummy, Pi, diophant, M, b);
1407 if (v!=alpha)
1408 {
1409 bufBufUniFactors= bufUniFactors;
1410 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1412 }
1413 if (!extension)
1414 {
1415 if (v==alpha)
1416 earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
1417 factorsFoundIndex, degs, earlySuccess, dummy,
1418 eval, b, den);
1419 else
1420 earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
1421 factorsFoundIndex, degs, earlySuccess, dummy,
1422 eval, b, den);
1423 }
1424 else
1425 extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
1426 factorsFoundIndex, degs, earlySuccess, info,
1427 eval, dummy);
1428 }
1429 else
1430 {
1431 liftBound= newLiftBound;
1432 break;
1433 }
1434 i++;
1435 }
1436 if (earlySuccess)
1437 liftBound= newLiftBound;
1438 }
1439
1440 A= bufA;
1441 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1442 {
1443 liftBound= degree (A,y) + 1;
1444 earlySuccess= true;
1445 deleteFactors (bufUniFactors, factorsFoundIndex);
1446 }
1447
1448 delete [] factorsFoundIndex;
1449 delete [] liftPre;
1450
1451 return bufUniFactors;
1452}
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
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
Matrix< CanonicalForm > CFMatrix
CF_NO_INLINE bool isOne() const
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition: facFqBivar.cc:984
void deleteFactors(CFList &factors, int *factorsFoundIndex)
Definition: facFqBivar.cc:1138
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition: facFqBivar.cc:1122
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
Definition: facHensel.cc:1274
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
Definition: facHensel.cc:1343

◆ prodMod0()

CanonicalForm prodMod0 ( const CFList L,
const CanonicalForm M,
const modpk b = modpk() 
)

$ \prod_{f\in L} {f (0, x)} \ mod\ M $ via divide-and-conquer

Returns
prodMod0 computes the above defined product
See also
prodMod()
Parameters
[in]La list of compressed, bivariate polynomials
[in]Ma power of Variable (2)
[in]bcoeff bound

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_fq_bi_sqrf  ) const

◆ uniFactorizer()

CFList uniFactorizer ( const CanonicalForm A,
const Variable alpha,
const bool &  GF 
)

Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used.

Returns
uniFactorizer returns a list of monic factors
Parameters
[in]Asquarefree univariate poly
[in]alphaalgebraic variable
[in]GFGaloisFieldDomain?

Definition at line 162 of file facFqBivar.cc.

163{
164 Variable x= A.mvar();
165 if (A.inCoeffDomain())
166 return CFList();
167 ASSERT (A.isUnivariate(),
168 "univariate polynomial expected or constant expected");
169 CFFList factorsA;
170 if (GF)
171 {
172 int k= getGFDegree();
173 char cGFName= gf_name;
178#ifdef HAVE_NTL
179 if (getCharacteristic() > 2)
180#else
181 if (getCharacteristic() > 0)
182#endif
183 {
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
185 nmod_poly_t FLINTmipo, leadingCoeff;
186 fq_nmod_ctx_t fq_con;
187 fq_nmod_poly_t FLINTA;
188 fq_nmod_poly_factor_t FLINTFactorsA;
189
190 nmod_poly_init (FLINTmipo, getCharacteristic());
192
193 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
194
196 fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
197
198 fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
199 nmod_poly_init (leadingCoeff, getCharacteristic());
200
201 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
202
203 factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
204 beta, fq_con);
205
206 fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
207 fq_nmod_poly_clear (FLINTA, fq_con);
208 nmod_poly_clear (FLINTmipo);
209 nmod_poly_clear (leadingCoeff);
211#else
213 {
216 }
217 zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
218 zz_pE::init (NTLMipo);
219 zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
220 MakeMonic (NTLA);
221 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
222 zz_pE multi= to_zz_pE (1);
223 factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
224 x, beta);
225#endif
226 }
227#ifdef HAVE_NTL
228 else
229 {
230 GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
231 GF2E::init (NTLMipo);
232 GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
233 MakeMonic (NTLA);
234 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
235 GF2E multi= to_GF2E (1);
236 factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
237 x, beta);
238 }
239#endif
241 for (CFFListIterator i= factorsA; i.hasItem(); i++)
242 {
243 buf= i.getItem().factor();
245 i.getItem()= CFFactor (buf, i.getItem().exp());
246 }
247 prune (beta);
248 }
249 else if (alpha.level() != 1)
250 {
251#ifdef HAVE_NTL
252 if (getCharacteristic() > 2)
253#else
254 if (getCharacteristic() > 0)
255#endif
256 {
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
258 nmod_poly_t FLINTmipo, leadingCoeff;
259 fq_nmod_ctx_t fq_con;
260 fq_nmod_poly_t FLINTA;
261 fq_nmod_poly_factor_t FLINTFactorsA;
262
263 nmod_poly_init (FLINTmipo, getCharacteristic());
265
266 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
267
269 fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
270
271 fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
272 nmod_poly_init (leadingCoeff, getCharacteristic());
273
274 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
275
276 factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
277 alpha, fq_con);
278
279 fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
280 fq_nmod_poly_clear (FLINTA, fq_con);
281 nmod_poly_clear (FLINTmipo);
282 nmod_poly_clear (leadingCoeff);
284#else
286 {
289 }
290 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
291 zz_pE::init (NTLMipo);
292 zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
293 MakeMonic (NTLA);
294 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
295 zz_pE multi= to_zz_pE (1);
296 factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
297 x, alpha);
298#endif
299 }
300#ifdef HAVE_NTL
301 else
302 {
303 GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
304 GF2E::init (NTLMipo);
305 GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
306 MakeMonic (NTLA);
307 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
308 GF2E multi= to_GF2E (1);
309 factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
310 x, alpha);
311 }
312#endif
313 }
314 else
315 {
316#ifdef HAVE_FLINT
317#ifdef HAVE_NTL
318 if (degree (A) < 300)
319#endif
320 {
321 nmod_poly_t FLINTA;
322 convertFacCF2nmod_poly_t (FLINTA, A);
323 nmod_poly_factor_t result;
324 nmod_poly_factor_init (result);
325 mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
326 factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
327 if (factorsA.getFirst().factor().inCoeffDomain())
328 factorsA.removeFirst();
329 nmod_poly_factor_clear (result);
330 nmod_poly_clear (FLINTA);
331 }
332#ifdef HAVE_NTL
333 else
334#endif
335#endif /* HAVE_FLINT */
336#ifdef HAVE_NTL
337 if (getCharacteristic() > 2)
338 {
340 {
343 }
344 zz_pX NTLA= convertFacCF2NTLzzpX (A);
345 MakeMonic (NTLA);
346 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
347 zz_p multi= to_zz_p (1);
348 factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
349 x);
350 }
351 else
352 {
353 GF2X NTLA= convertFacCF2NTLGF2X (A);
354 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
355 GF2 multi= to_GF2 (1);
356 factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
357 x);
358 }
359#endif
360 }
361 CFList uniFactors;
362 for (CFFListIterator i= factorsA; i.hasItem(); i++)
363 uniFactors.append (i.getItem().factor());
364 return uniFactors;
365}
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
Factor< CanonicalForm > CFFactor
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)