My Project
Loading...
Searching...
No Matches
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.
 
CFList biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info)
 
CFList FpBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over $ F_{p} $.
 
CFList FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
 factorize a squarefree bivariate polynomial over $ F_{p}(\alpha ) $.
 
CFList GFBiSqrfFactorize (const CanonicalForm &G)
 factorize a squarefree bivariate polynomial over GF
 
CFFList FpBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p} $
 
CFFList FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
 factorize a bivariate polynomial over $ F_{p}(\alpha ) $
 
CFFList GFBiFactorize (const CanonicalForm &G, bool substCheck=true)
 factorize a bivariate polynomial over GF
 
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
 
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)) $.
 
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.
 
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.
 
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.
 
Variable chooseExtension (const Variable &alpha, const Variable &beta, int k)
 chooses a field extension.
 
int * getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
 compute lifting precisions from the shape of the Newton polygon of F
 
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.
 
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.
 
CFList henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
 hensel Lifting and early factor detection
 
CFList 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
 
CFList extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization over an extension of initial field.
 

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

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

◆ 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}
ListIterator< CFFactor > CFFListIterator
ListIterator< CanonicalForm > CFListIterator
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
T factor() const
T getFirst() const
void removeFirst()
CFFListIterator iter
return result
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
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 809 of file facFqBivar.cc.

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

◆ 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
reconstructedFactors[in,out] list of reconstructed factors
F[in,out] poly to be factored, returns poly divided by detected factors in case of success
factors[in,out] list of factors lifted up to deg, returns a list of factors without detected factors
adaptedLiftBound[in,out] adapted lift bound
factorsFoundIndex[in,out] factors already considered
degs[in,out] degree pattern, is updated whenever we find a factor
success[in,out] indicating success
[in]degstage of Hensel lifting
[in]evalevaluation point
[in]bcoeff bound

Definition at line 974 of file facFqBivar.cc.

978{
980 earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
981 factorsFoundIndex, degs, success, deg, eval, b, den);
982}
CanonicalForm den(const CanonicalForm &f)
CanonicalForm b
Definition cfModGcd.cc:4111
CFList & eval
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)

◆ 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
eval[in,out] F (p, y)
[in]alphaalgebraic variable
[in]listlist of points already considered
[in]GFGaloisFieldDomain?
fail[in,out] equals true, if there is no valid evaluation point

Definition at line 87 of file facFqBivar.cc.

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

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

◆ extEarlyFactorDetection()

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

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

See also
factorRecombination(), earlyFactorDetection()
Parameters
reconstructedFactors[in,out] list of reconstructed factors
F[in,out] poly to be factored, returns poly divided by detected factors in case of success
factors[in,out] list of factors lifted up to deg, returns a list of factors without detected factors
adaptedLiftBound[in,out] adapted lift bound
factorsFoundIndex[in,out] factors already considered
degs[in,out] degree pattern, is updated whenever we find a factor
success[in,out] indicating success
[in]infoinformation about extension
[in]evalevaluation point
[in]degstage of Hensel lifting

Definition at line 985 of file facFqBivar.cc.

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

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

◆ 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
factors[in,out] list of lifted factors that are monic wrt Variable (1)
F[in,out] poly 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 589 of file facFqBivar.cc.

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

◆ 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
int level() const
level() returns the level of CO.
CanonicalForm LcF
CFList tmp2
Definition facFqBivar.cc:75
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
sizeOfOutput[in,out] size of the output
[in]degreeLCdegree of the leading coeff [in] of F wrt. Variable (1)

Definition at line 1123 of file facFqBivar.cc.

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

◆ 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
A[in,out] poly to be factored, returns poly divided by detected factors in case of success
earlySuccess[in,out] indicating success
earlyFactors[in,out] list of factors detected at early stage of Hensel lifting
degs[in,out] degree pattern
liftBound[in,out] (adapted) lift bound
[in]uniFactorsunivariate factors
[in]infoinformation about extension
[in]evalevaluation point

Definition at line 1458 of file facFqBivar.cc.

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

◆ henselLiftAndEarly() [2/2]

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

hensel Lifting and early factor detection

Returns
henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
See also
earlyFactorDetection(), extEarlyFactorDetection()
Parameters
A[in,out] poly to be factored, returns poly divided by detected factors in case of success
earlySuccess[in,out] indicating success
earlyFactors[in,out] list of factors detected at early stage of Hensel lifting
degs[in,out] degree pattern
liftBound[in,out] (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 1155 of file facFqBivar.cc.

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

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

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