My Project
Loading...
Searching...
No Matches
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 8303 of file facFqBivar.cc.

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

807{
808 int i=1, m= 2;
809 // extension of F_p needed
810 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
811 {
812 i= 1;
813 m= 2;
814 } //extension of F_p(alpha) needed but want to factorize over F_p
815 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
816 {
817 i= 1;
818 m= degree (getMipo (alpha)) + 1;
819 } //extension of F_p(alpha) needed for first time
820 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
821 {
822 i= 2;
823 m= degree (getMipo (alpha));
824 }
825 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
826 {
827 m= degree (getMipo (beta));
828 i= degree (getMipo (alpha))/m + 1;
829 }
830 #if defined(HAVE_FLINT)
831 nmod_poly_t Irredpoly;
833 nmod_poly_randtest_monic_irreducible(Irredpoly,FLINTrandom,i*m+1);
834 CanonicalForm newMipo= convertnmod_poly_t2FacCF(Irredpoly,Variable (1));
835 #elif defined(HAVE_NTL)
837 {
839 zz_p::init (getCharacteristic());
840 }
841 zz_pX NTLIrredpoly;
842 BuildIrred (NTLIrredpoly, i*m);
843 CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
844 #else
845 factoryError("NTL/FLINT missing: chooseExtension");
846 #endif
847 return rootOf (newMipo);
848}
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 rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162

◆ 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 971 of file facFqBivar.cc.

975{
977 earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
978 factorsFoundIndex, degs, success, deg, eval, b, den);
979}
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:852
const CanonicalForm const modpk & b
Definition: facFqBivar.cc:61

◆ 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 84 of file facFqBivar.cc.

87{
88 fail= false;
91 FFRandom genFF;
92 GFRandom genGF;
93 CanonicalForm random, mipo;
94 double bound;
95 int p= getCharacteristic ();
96 if (alpha.level() != 1)
97 {
99 int d= degree (mipo);
100 bound= pow ((double) p, (double) d);
101 }
102 else if (GF)
103 {
104 int d= getGFDegree();
105 bound= ipower (p, d);
106 }
107 else
108 bound= p;
109
110 random= 0;
111 do
112 {
113 if (list.length() >= bound)
114 {
115 fail= true;
116 break;
117 }
118 if (list.isEmpty())
119 random= 0;
120 else if (GF)
121 {
122 if (list.length() == 1)
123 random= getGFGenerator();
124 else
125 random= genGF.generate();
126 }
127 else if (list.length() < p || alpha.level() == 1)
128 random= genFF.generate();
129 else if (alpha != x && list.length() >= p)
130 {
131 if (list.length() == p)
132 random= alpha;
133 else
134 {
135 AlgExtRandomF genAlgExt (alpha);
136 random= genAlgExt.generate();
137 }
138 }
139 if (find (list, random)) continue;
140 eval= F (random, x);
141 if (degree (eval) != degree (F, y))
142 { //leading coeff vanishes
143 if (!find (list, random))
144 list.append (random);
145 continue;
146 }
147 if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
148 { //evaluated polynomial is not squarefree
149 if (!find (list, random))
150 list.append (random);
151 continue;
152 }
153 } while (find (list, random));
154
155 return random;
156}
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 8928 of file facFqBivar.cc.

8929{
8930
8931 CanonicalForm A= F;
8932 Variable alpha= info.getAlpha();
8933 Variable beta= info.getBeta();
8934 int k= info.getGFDegree();
8935 char cGFName= info.getGFName();
8936 CanonicalForm delta= info.getDelta();
8937
8938 bool GF= (CFFactory::gettype() == GaloisFieldDomain);
8939 Variable x= Variable (1);
8940 CFList factors;
8941 if (!GF && alpha == x) // we are in F_p
8942 {
8943 bool extension= true;
8944 int p= getCharacteristic();
8945 if (p*p < (1<<16)) // pass to GF if possible
8946 {
8948 A= A.mapinto();
8949 ExtensionInfo info2= ExtensionInfo (extension);
8950 factors= biFactorize (A, info2);
8951
8954 Variable vBuf= rootOf (mipo.mapinto());
8955 for (CFListIterator j= factors; j.hasItem(); j++)
8956 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8957 prune (vBuf);
8958 }
8959 else // not able to pass to GF, pass to F_p(\alpha)
8960 {
8962 Variable v= rootOf (mipo);
8963 ExtensionInfo info2= ExtensionInfo (v);
8964 factors= biFactorize (A, info2);
8965 prune (v);
8966 }
8967 return factors;
8968 }
8969 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8970 {
8971 if (k == 1) // need factorization over F_p
8972 {
8973 int extDeg= degree (getMipo (alpha));
8974 extDeg++;
8976 Variable v= rootOf (mipo);
8977 ExtensionInfo info2= ExtensionInfo (v);
8978 factors= biFactorize (A, info2);
8979 prune (v);
8980 }
8981 else
8982 {
8983 if (beta == x)
8984 {
8986 CanonicalForm primElem, imPrimElem;
8987 bool primFail= false;
8988 Variable vBuf;
8989 primElem= primitiveElement (alpha, vBuf, primFail);
8990 ASSERT (!primFail, "failure in integer factorizer");
8991 if (primFail)
8992 ; //ERROR
8993 else
8994 imPrimElem= mapPrimElem (primElem, alpha, v);
8995
8996 CFList source, dest;
8997 CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
8998 source, dest);
8999 ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
9000 factors= biFactorize (bufA, info2);
9001 prune (v);
9002 }
9003 else
9004 {
9006 CanonicalForm primElem, imPrimElem;
9007 bool primFail= false;
9008 Variable vBuf;
9009 ASSERT (!primFail, "failure in integer factorizer");
9010 if (primFail)
9011 ; //ERROR
9012 else
9013 imPrimElem= mapPrimElem (delta, beta, v);
9014
9015 CFList source, dest;
9016 CanonicalForm bufA= mapDown (A, info, source, dest);
9017 source= CFList();
9018 dest= CFList();
9019 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9020 ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
9021 factors= biFactorize (bufA, info2);
9022 prune (v);
9023 }
9024 }
9025 return factors;
9026 }
9027 else // we are in GF (p^k)
9028 {
9029 int p= getCharacteristic();
9030 int extensionDeg= getGFDegree();
9031 bool extension= true;
9032 if (k == 1) // need factorization over F_p
9033 {
9034 extensionDeg++;
9035 if (ipower (p, extensionDeg) < (1<<16))
9036 // pass to GF(p^k+1)
9037 {
9040 Variable vBuf= rootOf (mipo.mapinto());
9041 A= GF2FalphaRep (A, vBuf);
9042 setCharacteristic (p, extensionDeg, 'Z');
9043 ExtensionInfo info2= ExtensionInfo (extension);
9044 factors= biFactorize (A.mapinto(), info2);
9045 prune (vBuf);
9046 }
9047 else // not able to pass to another GF, pass to F_p(\alpha)
9048 {
9051 Variable vBuf= rootOf (mipo.mapinto());
9052 A= GF2FalphaRep (A, vBuf);
9053 Variable v= chooseExtension (vBuf, beta, k);
9054 ExtensionInfo info2= ExtensionInfo (v, extension);
9055 factors= biFactorize (A, info2);
9056 prune (vBuf);
9057 }
9058 }
9059 else // need factorization over GF (p^k)
9060 {
9061 if (ipower (p, 2*extensionDeg) < (1<<16))
9062 // pass to GF (p^2k)
9063 {
9064 setCharacteristic (p, 2*extensionDeg, 'Z');
9065 ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
9066 factors= biFactorize (GFMapUp (A, extensionDeg), info2);
9067 setCharacteristic (p, extensionDeg, cGFName);
9068 }
9069 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9070 {
9073 Variable v1= rootOf (mipo.mapinto());
9074 A= GF2FalphaRep (A, v1);
9075 Variable v2= chooseExtension (v1, v1, k);
9076 CanonicalForm primElem, imPrimElem;
9077 bool primFail= false;
9078 Variable vBuf;
9079 primElem= primitiveElement (v1, vBuf, primFail);
9080 ASSERT (!primFail, "failure in integer factorizer");
9081 if (primFail)
9082 ; //ERROR
9083 else
9084 imPrimElem= mapPrimElem (primElem, v1, v2);
9085
9086 CFList source, dest;
9087 CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
9088 source, dest);
9089 ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
9090 factors= biFactorize (bufA, info2);
9091 setCharacteristic (p, k, cGFName);
9092 for (CFListIterator i= factors; i.hasItem(); i++)
9094 prune (v1);
9095 }
9096 }
9097 return factors;
9098 }
9099}
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:450
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:342
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
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:240
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:195
CanonicalForm mapinto() const
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:806
int j
Definition: facHensel.cc:110
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
void prune(Variable &alpha)
Definition: variable.cc:261

◆ 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 982 of file facFqBivar.cc.

987{
988 Variable alpha= info.getAlpha();
989 Variable beta= info.getBeta();
990 CanonicalForm gamma= info.getGamma();
991 CanonicalForm delta= info.getDelta();
992 int k= info.getGFDegree();
993 DegreePattern bufDegs1= degs, bufDegs2;
995 CFList T= factors;
996 Variable y= F.mvar();
997 Variable x= Variable (1);
998 CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
999 CanonicalForm M= power (y, deg);
1000 adaptedLiftBound= 0;
1001 bool trueFactor= false;
1002 int d= degree (F), l= 0;
1003 CFList source, dest;
1004 int degMipoBeta= 1;
1005 if (!k && beta.level() != 1)
1006 degMipoBeta= degree (getMipo (beta));
1007 CanonicalForm quot;
1008 for (CFListIterator i= factors; i.hasItem(); i++, l++)
1009 {
1010 if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
1011 continue;
1012 else
1013 {
1014 g= mulMod2 (i.getItem(), LCBuf, M);
1015 g /= content (g, x);
1016 if (fdivides (g, buf, quot))
1017 {
1018 buf2= g (y - eval, y);
1019 buf2 /= Lc (buf2);
1020
1021 if (!k && beta == x)
1022 {
1023 if (degree (buf2, alpha) < degMipoBeta)
1024 {
1025 appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1026 factorsFoundIndex[l]= 1;
1027 buf= quot;
1028 d -= degree (g);
1029 LCBuf= LC (buf, x);
1030 trueFactor= true;
1031 }
1032 }
1033 else
1034 {
1035 if (!isInExtension (buf2, gamma, k, delta, source, dest))
1036 {
1037 appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
1038 factorsFoundIndex[l]= 1;
1039 buf= quot;
1040 d -= degree (g);
1041 LCBuf= LC (buf, x);
1042 trueFactor= true;
1043 }
1044 }
1045 if (trueFactor)
1046 {
1047 T= Difference (T, CFList (i.getItem()));
1048 F= buf;
1049
1050 // compute new possible degree pattern
1051 bufDegs2= DegreePattern (T);
1052 bufDegs1.intersect (bufDegs2);
1053 bufDegs1.refine ();
1054 trueFactor= false;
1055 if (bufDegs1.getLength() <= 1)
1056 {
1057 if (!buf.inCoeffDomain())
1058 {
1059 buf= buf (y - eval, y);
1060 buf /= Lc (buf);
1061 appendMapDown (reconstructedFactors, buf, info, source, dest);
1062 F= 1;
1063 }
1064 break;
1065 }
1066 }
1067 }
1068 }
1069 }
1070 adaptedLiftBound= d + 1;
1071 if (adaptedLiftBound < deg)
1072 {
1073 degs= bufDegs1;
1074 success= true;
1075 }
1076 if (bufDegs1.getLength() <= 1)
1077 degs= bufDegs1;
1078}
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:73
const CanonicalForm & M
Definition: facFqBivar.cc:60
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition: facMul.cc:2986
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 370 of file facFqBivar.cc.

374{
375 if (factors.length() == 0)
376 {
377 F= 1;
378 return CFList();
379 }
380 if (F.inCoeffDomain())
381 return CFList();
382
383 Variable alpha= info.getAlpha();
384 Variable beta= info.getBeta();
385 CanonicalForm gamma= info.getGamma();
386 CanonicalForm delta= info.getDelta();
387 int k= info.getGFDegree();
388
390 int l= degree (N);
391 Variable y= F.mvar();
392 Variable x= Variable (1);
393 CFList source, dest;
394 if (degs.getLength() <= 1 || factors.length() == 1)
395 {
396 CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
397 F= 1;
398 return result;
399 }
400
401 DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
402 (mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
403 int degMipoBeta= 1;
404 if (!k && beta.level() != 1)
405 degMipoBeta= degree (getMipo (beta));
406
407 CFList T, S, Diff;
408 T= factors;
409
411 CanonicalForm buf, buf2, quot;
412
413 buf= F;
414
415 CanonicalForm g, LCBuf= LC (buf, x);
416 int * v= new int [T.length()];
417 for (int i= 0; i < T.length(); i++)
418 v[i]= 0;
419
420 CFArray TT;
421 DegreePattern bufDegs1, bufDegs2;
422 bufDegs1= degs;
423 int subsetDeg;
424 TT= copy (factors);
425 bool nosubset= false;
426 bool recombination= false;
427 bool trueFactor= false;
429 CanonicalForm buf0= buf (0, x)*LCBuf;
430 while (T.length() >= 2*s && s <= thres)
431 {
432 while (nosubset == false)
433 {
434 if (T.length() == s)
435 {
436 delete [] v;
437 if (recombination)
438 {
439 T.insert (LCBuf);
440 g= prodMod (T, M);
441 T.removeFirst();
442 g /= content(g);
443 g= g (y - eval, y);
444 g /= Lc (g);
445 appendTestMapDown (result, g, info, source, dest);
446 F= 1;
447 return result;
448 }
449 else
450 {
451 appendMapDown (result, F (y - eval, y), info, source, dest);
452 F= 1;
453 return result;
454 }
455 }
456 S= subset (v, s, TT, nosubset);
457 if (nosubset) break;
458 subsetDeg= subsetDegree (S);
459 // skip those combinations that are not possible
460 if (!degs.find (subsetDeg))
461 continue;
462 else
463 {
464 test= prodMod0 (S, M);
465 test *= LCBuf;
466 test = mod (test, M);
467 if (fdivides (test, buf0))
468 {
469 S.insert (LCBuf);
470 g= prodMod (S, M);
471 S.removeFirst();
472 g /= content (g, x);
473 if (fdivides (g, buf, quot))
474 {
475 buf2= g (y - eval, y);
476 buf2 /= Lc (buf2);
477
478 if (!k && beta.level() == 1)
479 {
480 if (degree (buf2, alpha) < degMipoBeta)
481 {
482 buf= quot;
483 LCBuf= LC (buf, x);
484 recombination= true;
485 appendTestMapDown (result, buf2, info, source, dest);
486 trueFactor= true;
487 }
488 }
489 else
490 {
491 if (!isInExtension (buf2, gamma, k, delta, source, dest))
492 {
493 buf= quot;
494 LCBuf= LC (buf, x);
495 recombination= true;
496 appendTestMapDown (result, buf2, info, source, dest);
497 trueFactor= true;
498 }
499 }
500 if (trueFactor)
501 {
502 T= Difference (T, S);
503 l -= degree (g);
504 M= power (y, l);
505 buf0= buf (0, x)*LCBuf;
506
507 // compute new possible degree pattern
508 bufDegs2= DegreePattern (T);
509 bufDegs1.intersect (bufDegs2);
510 bufDegs1.refine ();
511 if (T.length() < 2*s || T.length() == s ||
512 bufDegs1.getLength() == 1)
513 {
514 delete [] v;
515 if (recombination)
516 {
517 buf= buf (y-eval,y);
518 buf /= Lc (buf);
519 appendTestMapDown (result, buf, info, source,
520 dest);
521 F= 1;
522 return result;
523 }
524 else
525 {
526 appendMapDown (result, F (y - eval, y), info, source, dest);
527 F= 1;
528 return result;
529 }
530 }
531 trueFactor= false;
532 TT= copy (T);
533 indexUpdate (v, s, T.length(), nosubset);
534 if (nosubset) break;
535 }
536 }
537 }
538 }
539 }
540 s++;
541 if (T.length() < 2*s || T.length() == s)
542 {
543 delete [] v;
544 if (recombination)
545 {
546 buf= buf (y-eval,y);
547 buf /= Lc (buf);
548 appendTestMapDown (result, buf, info, source, dest);
549 F= 1;
550 return result;
551 }
552 else
553 {
554 appendMapDown (result, F (y - eval, y), info, source, dest);
555 F= 1;
556 return result;
557 }
558 }
559 for (int i= 0; i < T.length(); i++)
560 v[i]= 0;
561 nosubset= false;
562 }
563 if (T.length() < 2*s)
564 {
565 appendMapDown (result, F (y - eval, y), info, source, dest);
566 F= 1;
567 delete [] v;
568 return result;
569 }
570
571 if (s > thres)
572 {
573 factors= T;
574 F= buf;
575 degs= bufDegs1;
576 }
577
578 delete [] v;
579 return result;
580}
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:3180

◆ 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 586 of file facFqBivar.cc.

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

◆ 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:50
CFList tmp2
Definition: facFqBivar.cc:72
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 1120 of file facFqBivar.cc.

1121{
1122 int sizeOfNewtonPoly;
1123 int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
1124 int sizeOfRightSide;
1125 int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1126 int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
1127 degreeLC);
1128 delete [] rightSide;
1129 for (int i= 0; i < sizeOfNewtonPoly; i++)
1130 delete [] newtonPolyg[i];
1131 delete [] newtonPolyg;
1132 return result;
1133}
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 * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
Definition: facFqBivar.cc:1081

◆ 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 1455 of file facFqBivar.cc.

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

◆ 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 1152 of file facFqBivar.cc.

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

161{
162 Variable x= A.mvar();
163 if (A.inCoeffDomain())
164 return CFList();
165 ASSERT (A.isUnivariate(),
166 "univariate polynomial expected or constant expected");
167 CFFList factorsA;
168 if (GF)
169 {
170 int k= getGFDegree();
171 char cGFName= gf_name;
176#ifdef HAVE_NTL
177 if (getCharacteristic() > 2)
178#else
179 if (getCharacteristic() > 0)
180#endif
181 {
182#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
183 nmod_poly_t FLINTmipo, leadingCoeff;
184 fq_nmod_ctx_t fq_con;
185 fq_nmod_poly_t FLINTA;
186 fq_nmod_poly_factor_t FLINTFactorsA;
187
188 nmod_poly_init (FLINTmipo, getCharacteristic());
190
191 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
192
194 fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
195
196 fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
197 nmod_poly_init (leadingCoeff, getCharacteristic());
198
199 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
200
201 factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
202 beta, fq_con);
203
204 fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
205 fq_nmod_poly_clear (FLINTA, fq_con);
206 nmod_poly_clear (FLINTmipo);
207 nmod_poly_clear (leadingCoeff);
209#else
211 {
213 zz_p::init (getCharacteristic());
214 }
215 zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
216 zz_pE::init (NTLMipo);
217 zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
218 MakeMonic (NTLA);
219 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
220 zz_pE multi= to_zz_pE (1);
221 factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
222 x, beta);
223#endif
224 }
225#ifdef HAVE_NTL
226 else
227 {
228 GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
229 GF2E::init (NTLMipo);
230 GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
231 MakeMonic (NTLA);
232 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
233 GF2E multi= to_GF2E (1);
234 factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
235 x, beta);
236 }
237#endif
239 for (CFFListIterator i= factorsA; i.hasItem(); i++)
240 {
241 buf= i.getItem().factor();
243 i.getItem()= CFFactor (buf, i.getItem().exp());
244 }
245 prune (beta);
246 }
247 else if (alpha.level() != 1)
248 {
249#ifdef HAVE_NTL
250 if (getCharacteristic() > 2)
251#else
252 if (getCharacteristic() > 0)
253#endif
254 {
255#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
256 nmod_poly_t FLINTmipo, leadingCoeff;
257 fq_nmod_ctx_t fq_con;
258 fq_nmod_poly_t FLINTA;
259 fq_nmod_poly_factor_t FLINTFactorsA;
260
261 nmod_poly_init (FLINTmipo, getCharacteristic());
263
264 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
265
267 fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
268
269 fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
270 nmod_poly_init (leadingCoeff, getCharacteristic());
271
272 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
273
274 factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
275 alpha, fq_con);
276
277 fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
278 fq_nmod_poly_clear (FLINTA, fq_con);
279 nmod_poly_clear (FLINTmipo);
280 nmod_poly_clear (leadingCoeff);
282#else
284 {
286 zz_p::init (getCharacteristic());
287 }
288 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
289 zz_pE::init (NTLMipo);
290 zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
291 MakeMonic (NTLA);
292 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
293 zz_pE multi= to_zz_pE (1);
294 factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
295 x, alpha);
296#endif
297 }
298#ifdef HAVE_NTL
299 else
300 {
301 GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
302 GF2E::init (NTLMipo);
303 GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
304 MakeMonic (NTLA);
305 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
306 GF2E multi= to_GF2E (1);
307 factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
308 x, alpha);
309 }
310#endif
311 }
312 else
313 {
314#ifdef HAVE_FLINT
315#ifdef HAVE_NTL
316 if (degree (A) < 300)
317#endif
318 {
319 nmod_poly_t FLINTA;
320 convertFacCF2nmod_poly_t (FLINTA, A);
321 nmod_poly_factor_t result;
322 nmod_poly_factor_init (result);
323 mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
324 factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
325 if (factorsA.getFirst().factor().inCoeffDomain())
326 factorsA.removeFirst();
327 nmod_poly_factor_clear (result);
328 nmod_poly_clear (FLINTA);
329 }
330#ifdef HAVE_NTL
331 else
332#endif
333#endif /* HAVE_FLINT */
334#ifdef HAVE_NTL
335 if (getCharacteristic() > 2)
336 {
338 {
340 zz_p::init (getCharacteristic());
341 }
342 zz_pX NTLA= convertFacCF2NTLzzpX (A);
343 MakeMonic (NTLA);
344 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
345 zz_p multi= to_zz_p (1);
346 factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
347 x);
348 }
349 else
350 {
351 GF2X NTLA= convertFacCF2NTLGF2X (A);
352 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
353 GF2 multi= to_GF2 (1);
354 factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
355 x);
356 }
357#endif
358 }
359 CFList uniFactors;
360 for (CFFListIterator i= factorsA; i.hasItem(); i++)
361 uniFactors.append (i.getItem().factor());
362 return uniFactors;
363}
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)