My Project
Loading...
Searching...
No Matches
Functions
facFqBivar.h File Reference

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

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

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
 
CFList biFactorize (const CanonicalForm &F, const ExtensionInfo &info)
 Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
 
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.
 
intgetLiftPrecisions (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 8305 of file facFqBivar.cc.

8306{
8307 if (F.inCoeffDomain())
8308 return CFList(F);
8309
8310 CanonicalForm A= F;
8312
8313 Variable alpha= info.getAlpha();
8314 Variable beta= info.getBeta();
8315 CanonicalForm gamma= info.getGamma();
8316 CanonicalForm delta= info.getDelta();
8317 int k= info.getGFDegree();
8318 bool extension= info.isInExtension();
8319 if (A.isUnivariate())
8320 {
8321 if (extension == false)
8322 return uniFactorizer (F, alpha, GF);
8323 else
8324 {
8325 CFList source, dest;
8326 A= mapDown (A, info, source, dest);
8327 return uniFactorizer (A, beta, GF);
8328 }
8329 }
8330
8331 CFMap N;
8332 A= compress (A, N);
8333 Variable y= A.mvar();
8334
8335 if (y.level() > 2) return CFList (F);
8336 Variable x= Variable (1);
8337
8338 //remove and factorize content
8341
8344
8345 if (!extension)
8346 {
8349 }
8350
8351 //trivial case
8353 if (A.inCoeffDomain())
8354 {
8357 decompress (factors, N);
8358 return factors;
8359 }
8360 else if (A.isUnivariate())
8361 {
8365 decompress (factors, N);
8366 return factors;
8367 }
8368
8369
8370 //check trivial case
8371 if (degree (A) == 1 || degree (A, 1) == 1 ||
8372 (size (A) == 2 && igcd (degree (A), degree (A,1))==1))
8373 {
8374 factors.append (A);
8375
8377 false, false, N);
8378
8379 if (!extension)
8381 return factors;
8382 }
8383
8384 // check derivatives
8385 bool derivXZero= false;
8388 if (derivX.isZero())
8389 derivXZero= true;
8390 else
8391 {
8392 gcdDerivX= gcd (A, derivX);
8393 if (degree (gcdDerivX) > 0)
8394 {
8401 if (!extension)
8403 return factorsG;
8404 }
8405 }
8406 bool derivYZero= false;
8409 if (derivY.isZero())
8410 derivYZero= true;
8411 else
8412 {
8413 gcdDerivY= gcd (A, derivY);
8414 if (degree (gcdDerivY) > 0)
8415 {
8422 if (!extension)
8424 return factorsG;
8425 }
8426 }
8427 //main variable is chosen s.t. the degree in x is minimal
8428 bool swap= false;
8429 if ((degree (A) > degree (A, x)) || derivXZero)
8430 {
8431 if (!derivYZero)
8432 {
8433 A= swapvar (A, y, x);
8437 swap= true;
8438 }
8439 }
8440
8441 int boundsLength;
8442 bool isIrreducible= false;
8444 if (isIrreducible)
8445 {
8446 delete [] bounds;
8447 factors.append (A);
8448
8450 swap, false, N);
8451
8452 if (!extension)
8454 return factors;
8455 }
8456
8457 int minBound= bounds[0];
8458 for (int i= 1; i < boundsLength; i++)
8459 {
8460 if (bounds[i] != 0)
8462 }
8463
8464 int boundsLength2;
8466 int minBound2= bounds2[0];
8467 for (int i= 1; i < boundsLength2; i++)
8468 {
8469 if (bounds2[i] != 0)
8471 }
8472
8473
8474 bool fail= false;
8479
8480 bool fail2= false;
8485 bool swap2= false;
8486
8487 // several univariate factorizations to obtain more information about the
8488 // degree pattern therefore usually less combinations have to be tried during
8489 // the recombination process
8490 int factorNums= 3;
8491 int subCheck1= substituteCheck (A, x);
8492 int subCheck2= substituteCheck (A, y);
8493 bool symmetric= false;
8494
8496 for (int i= 0; i < factorNums; i++)
8497 {
8498 bufAeval= A;
8501 TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
8502 if (!derivXZero && !fail2 && !symmetric)
8503 {
8504 if (i == 0)
8505 {
8506 buf= swapvar (A, x, y);
8507 symmetric= (A/Lc (A) == buf/Lc (buf));
8508 }
8509 bufAeval2= buf;
8513 "time to find eval point wrt y: ");
8514 }
8515 // first try to change main variable if there is no valid evaluation point
8516 if (fail && (i == 0))
8517 {
8518 if (!derivXZero && !fail2 && !symmetric)
8519 {
8521 int dummy= subCheck2;
8524 tmp= A;
8525 A= buf;
8526 buf= tmp;
8528 swap2= true;
8529 fail= false;
8530 }
8531 else
8532 fail= true;
8533 }
8534
8535 // if there is no valid evaluation point pass to a field extension
8536 if (fail && (i == 0))
8537 {
8540 swap, swap2, N);
8542 delete [] bounds;
8543 delete [] bounds2;
8544 return factors;
8545 }
8546
8547 // there is at least one valid evaluation point
8548 // but we do not compute more univariate factorization over an extension
8549 if (fail && (i != 0))
8550 break;
8551
8552 // univariate factorization
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8559
8560 if (!derivXZero && !fail2 && !symmetric)
8561 {
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8568 }
8569
8570 if (bufUniFactors.length() == 1 ||
8571 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
8572 {
8573 if (extension)
8574 {
8575 CFList source, dest;
8576 appendMapDown (factors, A, info, source, dest);
8577 }
8578 else
8579 factors.append (A);
8580
8582 swap, swap2, N);
8583
8584 if (!extension)
8586 delete [] bounds;
8587 delete [] bounds2;
8588 return factors;
8589 }
8590
8591 if (i == 0 && !extension)
8592 {
8593 if (subCheck1 > 0)
8594 {
8596
8597 if (subCheck > 1 && (subCheck1%subCheck == 0))
8598 {
8600 subst (bufA, bufA, subCheck, x);
8604 swap, swap2, N);
8605 if (!extension)
8607 delete [] bounds;
8608 delete [] bounds2;
8609 return factors;
8610 }
8611 }
8612
8613 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8614 {
8616
8617 if (subCheck > 1 && (subCheck2%subCheck == 0))
8618 {
8620 subst (bufA, bufA, subCheck, y);
8624 swap, swap2, N);
8625 if (!extension)
8627 delete [] bounds;
8628 delete [] bounds2;
8629 return factors;
8630 }
8631 }
8632 }
8633
8634 // degree analysis
8636 if (!derivXZero && !fail2 && !symmetric)
8638
8639 if (i == 0)
8640 {
8641 Aeval= bufAeval;
8644 degs= bufDegs;
8645 if (!derivXZero && !fail2 && !symmetric)
8646 {
8650 degs2= bufDegs2;
8651 }
8652 }
8653 else
8654 {
8655 degs.intersect (bufDegs);
8656 if (!derivXZero && !fail2 && !symmetric)
8657 {
8658 degs2.intersect (bufDegs2);
8660 {
8664 }
8665 }
8667 {
8669 Aeval= bufAeval;
8671 }
8672 }
8673 list.append (bufEvaluation);
8674 if (!derivXZero && !fail2 && !symmetric)
8676 }
8678 "total time for univariate factorizations: ");
8679
8680 if (!derivXZero && !fail2 && !symmetric)
8681 {
8684 && degs.getLength() > degs2.getLength() && minBound2 <= minBound))
8685 {
8686 degs= degs2;
8689 Aeval= Aeval2;
8690 A= buf;
8691 swap2= true;
8692 }
8693 }
8694
8695 if (degs.getLength() == 1) // A is irreducible
8696 {
8697 if (extension)
8698 {
8699 CFList source, dest;
8700 appendMapDown (factors, A, info, source, dest);
8701 }
8702 else
8703 factors.append (A);
8705 swap, swap2, N);
8706 if (!extension)
8708 delete [] bounds;
8709 delete [] bounds2;
8710 return factors;
8711 }
8712
8713 int liftBound= degree (A, y) + 1;
8714
8715 if (swap2)
8716 {
8717 delete [] bounds;
8718 bounds= bounds2;
8720 }
8721
8723 A= A (y + evaluation, y);
8725 "time to shift eval to zero: ");
8726
8727 int degMipo= 1;
8728 if (extension && alpha.level() != 1 && k==1)
8730
8731 DEBOUTLN (cerr, "uniFactors= " << uniFactors);
8732
8733 if ((GF && !extension) || (GF && extension && k != 1))
8734 {
8735 bool earlySuccess= false;
8742 "time for bivariate hensel lifting over Fq: ");
8743 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8744
8746
8748 if (extension)
8750 evaluation, 1, uniFactors.length()/2);
8751 else
8753 uniFactors.length()/2);
8755 "time for naive bivariate factor recombi over Fq: ");
8756
8757 if (earlySuccess)
8759 else if (!earlySuccess && degs.getLength() == 1)
8761 }
8762 else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
8763 {
8765 if (extension)
8766 {
8769 );
8771 }
8772 else if (alpha.level() == 1 && !GF)
8773 {
8777 }
8778 else if (!extension && (alpha != x || GF))
8779 {
8783 }
8785 "time to bivar lift and LLL recombi over Fq: ");
8786 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8787 }
8788 else
8789 {
8790 bool earlySuccess= false;
8797 "time for bivar hensel lifting over Fq: ");
8798 DEBOUTLN (cerr, "lifted factors= " << uniFactors);
8799
8801 if (!extension)
8802 {
8806 "time for small subset naive recombi over Fq: ");
8807
8809 if (degree (A) > 0)
8810 {
8811 CFList tmp;
8813 if (alpha.level() == 1)
8816 );
8817 else
8818 {
8819 if (degree (A) > getCharacteristic())
8822 );
8823 else
8826 );
8827 }
8829 "time to increase precision: ");
8831 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8833 )
8834 {
8836 degs.intersect (bufDegs);
8837 degs.refine ();
8839 degs, evaluation, 4,
8840 uniFactors.length()/2
8841 )
8842 );
8843 }
8844 }
8845 }
8846 else
8847 {
8848 if (beta.level() != 1 || k > 1)
8849 {
8850 if (k > 1)
8851 {
8854 );
8855 }
8856 else
8857 {
8859 evaluation, 1, 3
8860 );
8861 if (degree (A) > 0)
8862 {
8865 degs.intersect (bufDegs);
8866 degs.refine ();
8869 1, tmp.length()/2
8870 )
8871 );
8872 }
8873 }
8874 }
8875 else
8876 {
8878 evaluation, 1, 3
8879 );
8881 if (degree (A) > 0)
8882 {
8883 int degMipo;
8885
8886 CFList source, dest;
8889 info2, source, dest, liftBound
8890 );
8892 if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
8894 )
8895 {
8897 degs.intersect (bufDegs);
8898 degs.refine ();
8901 4, uniFactors.length()/2
8902 )
8903 );
8904 }
8905 }
8906 }
8907 }
8908
8909 if (earlySuccess)
8911 else if (!earlySuccess && degs.getLength() == 1)
8913 }
8914
8915 if (!swap2)
8916 delete [] bounds2;
8917 delete [] bounds;
8918
8920 swap, swap2, N);
8921 if (!extension)
8923
8924 return factors;
8925}
#define swap(_i, _j)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int k
Definition cfEzgcd.cc:99
Variable x
Definition cfModGcd.cc:4081
g
Definition cfModGcd.cc:4089
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
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
DegreePattern provides a functionality to create, intersect and refine degree patterns.
ExtensionInfo contains information about extension.
int length() const
void append(const T &)
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
#define DEBOUTLN(stream, objects)
Definition debug.h:49
Variable alpha
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
Variable beta
Definition facAbsFact.cc:95
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFList *& Aeval
<[in] poly
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
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)
CFListIterator i
Definition facFqBivar.cc:73
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition facFqBivar.cc:86
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
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 "Factoring multivariate 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:59
#define A
Definition sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
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;
61 F /= (contentX*contentY);
63 if (info.getAlpha().level() != 1)
64 {
67 }
68 else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
69 {
72 }
73 else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
74 {
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())
86 if (contentYFactors.getFirst().factor().inCoeffDomain())
88 if (F.inCoeffDomain())
89 {
91 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
92 result.append (N (i.getItem().factor()));
93 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
94 result.append (N (i.getItem().factor()));
96 result.insert (Lc (G));
97 return result;
98 }
99 mpz_t * M=new mpz_t [4];
100 mpz_init (M[0]);
101 mpz_init (M[1]);
102 mpz_init (M[2]);
103 mpz_init (M[3]);
104
105 mpz_t * S=new mpz_t [2];
106 mpz_init (S[0]);
107 mpz_init (S[1]);
108
109 F= compress (F, M, S);
111 for (CFListIterator i= result; i.hasItem(); i++)
112 i.getItem()= N (decompress (i.getItem(), M, S));
113 for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
114 result.append (N(i.getItem().factor()));
115 for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
116 result.append (N (i.getItem().factor()));
118 result.insert (Lc(G));
119
120 mpz_clear (M[0]);
121 mpz_clear (M[1]);
122 mpz_clear (M[2]);
123 mpz_clear (M[3]);
124 delete [] M;
125
126 mpz_clear (S[0]);
127 mpz_clear (S[1]);
128 delete [] S;
129
130 return result;
131}
int i
Definition cfEzgcd.cc:132
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
T 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 808 of file facFqBivar.cc.

809{
810 int i=1, m= 2;
811 // extension of F_p needed
812 if (alpha.level() == 1 && beta.level() == 1 && k == 1)
813 {
814 i= 1;
815 m= 2;
816 } //extension of F_p(alpha) needed but want to factorize over F_p
817 else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
818 {
819 i= 1;
820 m= degree (getMipo (alpha)) + 1;
821 } //extension of F_p(alpha) needed for first time
822 else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
823 {
824 i= 2;
825 m= degree (getMipo (alpha));
826 }
827 else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
828 {
829 m= degree (getMipo (beta));
830 i= degree (getMipo (alpha))/m + 1;
831 }
832 #if defined(HAVE_FLINT)
837 #elif defined(HAVE_NTL)
839 {
841 zz_p::init (getCharacteristic());
842 }
846 #else
847 factoryError("NTL/FLINT missing: chooseExtension");
848 #endif
849 return rootOf (newMipo);
850}
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
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
[in,out]reconstructedFactorslist of reconstructed factors
[in,out]Fpoly to be factored, returns poly divided by detected factors in case of success
[in,out]factorslist of factors lifted up to deg, returns a list of factors without detected factors
[in,out]adaptedLiftBoundadapted lift bound
[in,out]factorsFoundIndexfactors already considered
[in,out]degsdegree pattern, is updated whenever we find a factor
[in,out]successindicating success
[in]degstage of Hensel lifting
[in]evalevaluation point
[in]bcoeff bound

Definition at line 973 of file facFqBivar.cc.

977{
980 factorsFoundIndex, degs, success, deg, eval, b, den);
981}
CanonicalForm den(const CanonicalForm &f)
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)
const CanonicalForm const modpk & b
Definition facFqBivar.cc:63

◆ evalPoint()

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

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

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

Definition at line 86 of file facFqBivar.cc.

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

◆ extBiFactorize()

CFList extBiFactorize ( const CanonicalForm & F,
const ExtensionInfo & info )

Factorization over an extension of initial field.

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

Definition at line 8930 of file facFqBivar.cc.

8931{
8932
8933 CanonicalForm A= F;
8934 Variable alpha= info.getAlpha();
8935 Variable beta= info.getBeta();
8936 int k= info.getGFDegree();
8937 char cGFName= info.getGFName();
8938 CanonicalForm delta= info.getDelta();
8939
8941 Variable x= Variable (1);
8943 if (!GF && alpha == x) // we are in F_p
8944 {
8945 bool extension= true;
8946 int p= getCharacteristic();
8947 if (p*p < (1<<16)) // pass to GF if possible
8948 {
8950 A= A.mapinto();
8953
8957 for (CFListIterator j= factors; j.hasItem(); j++)
8958 j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
8959 prune (vBuf);
8960 }
8961 else // not able to pass to GF, pass to F_p(\alpha)
8962 {
8964 Variable v= rootOf (mipo);
8967 prune (v);
8968 }
8969 return factors;
8970 }
8971 else if (!GF && (alpha != x)) // we are in F_p(\alpha)
8972 {
8973 if (k == 1) // need factorization over F_p
8974 {
8975 int extDeg= degree (getMipo (alpha));
8976 extDeg++;
8978 Variable v= rootOf (mipo);
8981 prune (v);
8982 }
8983 else
8984 {
8985 if (beta == x)
8986 {
8989 bool primFail= false;
8990 Variable vBuf;
8992 ASSERT (!primFail, "failure in integer factorizer");
8993 if (primFail)
8994 ; //ERROR
8995 else
8997
8998 CFList source, dest;
9000 source, dest);
9003 prune (v);
9004 }
9005 else
9006 {
9009 bool primFail= false;
9010 Variable vBuf;
9011 ASSERT (!primFail, "failure in integer factorizer");
9012 if (primFail)
9013 ; //ERROR
9014 else
9015 imPrimElem= mapPrimElem (delta, beta, v);
9016
9017 CFList source, dest;
9019 source= CFList();
9020 dest= CFList();
9021 bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
9024 prune (v);
9025 }
9026 }
9027 return factors;
9028 }
9029 else // we are in GF (p^k)
9030 {
9031 int p= getCharacteristic();
9033 bool extension= true;
9034 if (k == 1) // need factorization over F_p
9035 {
9036 extensionDeg++;
9037 if (ipower (p, extensionDeg) < (1<<16))
9038 // pass to GF(p^k+1)
9039 {
9043 A= GF2FalphaRep (A, vBuf);
9046 factors= biFactorize (A.mapinto(), info2);
9047 prune (vBuf);
9048 }
9049 else // not able to pass to another GF, pass to F_p(\alpha)
9050 {
9054 A= GF2FalphaRep (A, vBuf);
9058 prune (vBuf);
9059 }
9060 }
9061 else // need factorization over GF (p^k)
9062 {
9063 if (ipower (p, 2*extensionDeg) < (1<<16))
9064 // pass to GF (p^2k)
9065 {
9070 }
9071 else // not able to pass to GF (p^2k), pass to F_p (\alpha)
9072 {
9076 A= GF2FalphaRep (A, v1);
9079 bool primFail= false;
9080 Variable vBuf;
9082 ASSERT (!primFail, "failure in integer factorizer");
9083 if (primFail)
9084 ; //ERROR
9085 else
9087
9088 CFList source, dest;
9090 source, dest);
9094 for (CFListIterator i= factors; i.hasItem(); i++)
9096 prune (v1);
9097 }
9098 }
9099 return factors;
9100 }
9101}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
#define ASSERT(expression, message)
Definition cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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...
CanonicalForm mapinto() const
T & getItem() const
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
int j
Definition facHensel.cc:110
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56

◆ extEarlyFactorDetection()

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

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

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

Definition at line 984 of file facFqBivar.cc.

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

◆ extFactorRecombination()

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

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

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

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

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

Definition at line 372 of file facFqBivar.cc.

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

◆ factorRecombination()

CFList factorRecombination ( CFList & factors,
CanonicalForm & F,
const CanonicalForm & N,
DegreePattern & degs,
const CanonicalForm & eval,
int s,
int thres,
const modpk & b,
const CanonicalForm & den )

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

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

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

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

Definition at line 588 of file facFqBivar.cc.

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

◆ 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 {
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);
216 newResult.insert (result.getFirst());
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)
225 }
226 tmp= FpBiFactorize (tmp2, false);
228 for (CFFListIterator j= tmp; j.hasItem(); j++)
229 newResult.append (CFFactor (j.getItem().factor(),
230 j.getItem().exp()*i.getItem().exp()));
231 }
234 return newResult;
235 }
237 }
238
239 CanonicalForm LcF= Lc (F);
242 F /= (contentX*contentY);
246 if (contentXFactors.getFirst().factor().inCoeffDomain())
248 if (contentYFactors.getFirst().factor().inCoeffDomain())
253 if (F.inCoeffDomain())
254 {
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
273 CFFList sqrf= FpSqrf (F, false);
275 "time for bivariate sqrf factors over Fp: ");
279 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
280 {
282 bufResult= biFactorize (iter.getItem().factor(), info);
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
293 result.insert (CFFactor (LcF, 1));
294
295 mpz_clear (M[0]);
296 mpz_clear (M[1]);
297 mpz_clear (M[2]);
298 mpz_clear (M[3]);
299 delete [] M;
300
301 mpz_clear (S[0]);
302 mpz_clear (S[1]);
303 delete [] S;
304
305 return result;
306}
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
CanonicalForm LcF
CFList tmp2
Definition facFqBivar.cc:74
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:190
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FpBiSqrfFactorize()

CFList FpBiSqrfFactorize ( const CanonicalForm & G)
inline

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

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

Definition at line 141 of file facFqBivar.h.

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

◆ FqBiFactorize()

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

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

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

Definition at line 317 of file facFqBivar.h.

321{
323 CFMap N;
325
326 if (substCheck)
327 {
328 bool foundOne= false;
329 int * substDegree= NEW_ARRAY(int,F.level());
330 for (int i= 1; i <= F.level(); i++)
331 {
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);
344 newResult.insert (result.getFirst());
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)
353 }
354 tmp= FqBiFactorize (tmp2, alpha, false);
356 for (CFFListIterator j= tmp; j.hasItem(); j++)
357 newResult.append (CFFactor (j.getItem().factor(),
358 j.getItem().exp()*i.getItem().exp()));
359 }
362 return newResult;
363 }
365 }
366
367 CanonicalForm LcF= Lc (F);
370 F /= (contentX*contentY);
374 if (contentXFactors.getFirst().factor().inCoeffDomain())
376 if (contentYFactors.getFirst().factor().inCoeffDomain())
381 if (F.inCoeffDomain())
382 {
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
402 CFFList sqrf= FqSqrf (F, alpha, false);
404 "time for bivariate sqrf factors over Fq: ");
408 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
409 {
411 bufResult= biFactorize (iter.getItem().factor(), info);
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
422 result.insert (CFFactor (LcF, 1));
423
424 mpz_clear (M[0]);
425 mpz_clear (M[1]);
426 mpz_clear (M[2]);
427 mpz_clear (M[3]);
428 delete [] M;
429
430 mpz_clear (S[0]);
431 mpz_clear (S[1]);
432 delete [] S;
433
434 return result;
435}
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:317
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped

◆ FqBiSqrfFactorize()

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

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

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

Definition at line 156 of file facFqBivar.h.

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

◆ getLiftPrecisions()

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

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

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

Definition at line 1122 of file facFqBivar.cc.

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

◆ 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 {
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);
474 newResult.insert (result.getFirst());
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)
483 }
484 tmp= GFBiFactorize (tmp2, false);
486 for (CFFListIterator j= tmp; j.hasItem(); j++)
487 newResult.append (CFFactor (j.getItem().factor(),
488 j.getItem().exp()*i.getItem().exp()));
489 }
492 return newResult;
493 }
495 }
496
497 CanonicalForm LcF= Lc (F);
500 F /= (contentX*contentY);
504 if (contentXFactors.getFirst().factor().inCoeffDomain())
506 if (contentYFactors.getFirst().factor().inCoeffDomain())
511 if (F.inCoeffDomain())
512 {
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
532 CFFList sqrf= GFSqrf (F, false);
534 "time for bivariate sqrf factors over GF: ");
538 for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
539 {
541 bufResult= biFactorize (iter.getItem().factor(), info);
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
552 result.insert (CFFactor (LcF, 1));
553
554 mpz_clear (M[0]);
555 mpz_clear (M[1]);
556 mpz_clear (M[2]);
557 mpz_clear (M[3]);
558 delete [] M;
559
560 mpz_clear (S[0]);
561 mpz_clear (S[1]);
562 delete [] S;
563
564 return result;
565}
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition facFqBivar.h:446
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
VAR char gf_name
Definition gfops.cc:52

◆ GFBiSqrfFactorize()

CFList GFBiSqrfFactorize ( const CanonicalForm & G)
inline

factorize a squarefree bivariate polynomial over GF

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

Definition at line 172 of file facFqBivar.h.

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

◆ henselLiftAndEarly() [1/2]

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

hensel Lifting and early factor detection

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

Definition at line 1457 of file facFqBivar.cc.

1461{
1462 modpk dummy= modpk();
1463 CanonicalForm den= 1;
1466}
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
return modpk(p, k)

◆ henselLiftAndEarly() [2/2]

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

hensel Lifting and early factor detection

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

Definition at line 1154 of file facFqBivar.cc.

1158{
1159 Variable alpha= info.getAlpha();
1160 Variable beta= info.getBeta();
1161 CanonicalForm gamma= info.getGamma();
1162 CanonicalForm delta= info.getDelta();
1163 bool extension= info.isInExtension();
1164
1165 int sizeOfLiftPre;
1166 int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
1167
1168 Variable x= Variable (1);
1169 Variable y= Variable (2);
1170 CFArray Pi;
1173 On (SW_RATIONAL);
1175 if (!Lc (A).inBaseDomain())
1176 {
1177 bufA /= Lc (A);
1179 bufA *= denBufA;
1180 Off (SW_RATIONAL);
1181 den /= gcd (den, denBufA);
1182 }
1183 else
1184 {
1185 bufA= A;
1186 Off (SW_RATIONAL);
1187 den /= gcd (den, Lc (A));
1188 }
1190 bool mipoHasDen= false;
1191 if (getCharacteristic() == 0 && b.getp() != 0)
1192 {
1193 if (alpha.level() == 1)
1194 {
1195 lcA0= lc (A (0, 2));
1196 A *= b.inverse (lcA0);
1197 A= b (A);
1199 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1200 }
1201 else
1202 {
1203 lcA0= Lc (A (0,2));
1204 On (SW_RATIONAL);
1206 Off (SW_RATIONAL);
1207 CanonicalForm lcA0inverse= b.inverse (lcA0);
1208 A *= lcA0inverse;
1209 A= b (A);
1210 // Lc of bufUniFactors is in Z
1212 i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
1213 }
1214 }
1215 bufUniFactors.insert (LC (A, x));
1217 earlySuccess= false;
1218 int newLiftBound= 0;
1219
1220 int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
1221 int dummy;
1222 int * factorsFoundIndex= new int [uniFactors.length()];
1223 for (int i= 0; i < uniFactors.length(); i++)
1224 factorsFoundIndex [i]= 0;
1225
1227 Variable v= alpha;
1228 if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
1230 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1231 {
1233 if (mipoHasDen)
1234 {
1235 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1236 if (hasFirstAlgVar (iter.getItem(), v))
1237 break;
1238 if (v != alpha)
1239 {
1241 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1242 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1243 A= replacevar (A, alpha, v);
1244 }
1245 }
1246
1247 if (!extension)
1248 {
1249 if (v==alpha)
1253 else
1257 }
1258 else
1262 if (degs.getLength() > 1 && !earlySuccess &&
1264 {
1266 {
1267 bufUniFactors.insert (LC (A, x));
1269 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
1270 if (v!=alpha)
1271 {
1273 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1274 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1275 }
1276 if (!extension)
1277 {
1278 if (v==alpha)
1281 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1282 else
1285 liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
1286 }
1287 else
1290 eval, liftPre[sizeOfLiftPre-1] + 1);
1291 }
1292 }
1293 else if (earlySuccess)
1295
1296 int i= sizeOfLiftPre - 1;
1297 while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
1298 {
1299 if (newLiftBound >= liftPre[i] + 1)
1300 {
1301 bufUniFactors.insert (LC (A, x));
1303 liftPre[i-1] + 1, Pi, diophant, M, b);
1304 if (v!=alpha)
1305 {
1307 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1308 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1309 }
1310 if (!extension)
1311 {
1312 if (v==alpha)
1315 liftPre[i-1] + 1, eval, b, den);
1316 else
1319 liftPre[i-1] + 1, eval, b, den);
1320 }
1321 else
1324 eval, liftPre[i-1] + 1);
1325 }
1326 else
1327 {
1329 break;
1330 }
1331 i--;
1332 }
1333 if (earlySuccess)
1335 //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
1336 }
1337 else
1338 {
1340 if (mipoHasDen)
1341 {
1342 for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
1343 if (hasFirstAlgVar (iter.getItem(), v))
1344 break;
1345 if (v != alpha)
1346 {
1348 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1349 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1350 A= replacevar (A, alpha, v);
1351 }
1352 }
1353 if (!extension)
1354 {
1355 if (v==alpha)
1359 else
1363 }
1364 else
1368 int i= 1;
1369 while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
1370 i++;
1371 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
1372 if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1373 {
1374 bufUniFactors.insert (LC (A, x));
1376 dummy, Pi, diophant, M, b);
1377 if (v!=alpha)
1378 {
1380 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1381 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1382 }
1383 if (!extension)
1384 {
1385 if (v==alpha)
1388 b, den);
1389 else
1392 b, den);
1393 }
1394 else
1397 eval, dummy);
1398 }
1399 while (degs.getLength() > 1 && !earlySuccess && i < 4)
1400 {
1401 if (newLiftBound >= dummy)
1402 {
1403 bufUniFactors.insert (LC (A, x));
1404 dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
1406 dummy, Pi, diophant, M, b);
1407 if (v!=alpha)
1408 {
1410 for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
1411 iter.getItem()= replacevar (iter.getItem(), v, alpha);
1412 }
1413 if (!extension)
1414 {
1415 if (v==alpha)
1418 eval, b, den);
1419 else
1422 eval, b, den);
1423 }
1424 else
1427 eval, dummy);
1428 }
1429 else
1430 {
1432 break;
1433 }
1434 i++;
1435 }
1436 if (earlySuccess)
1438 }
1439
1440 A= bufA;
1441 if (earlyFactors.length() > 0 && degs.getLength() > 1)
1442 {
1443 liftBound= degree (A,y) + 1;
1444 earlySuccess= true;
1446 }
1447
1448 delete [] factorsFoundIndex;
1449 delete [] liftPre;
1450
1451 return bufUniFactors;
1452}
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition cf_ops.cc:271
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
Matrix< CanonicalForm > CFMatrix
CF_NO_INLINE bool isOne() const
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
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 162 of file facFqBivar.cc.

163{
164 Variable x= A.mvar();
165 if (A.inCoeffDomain())
166 return CFList();
167 ASSERT (A.isUnivariate(),
168 "univariate polynomial expected or constant expected");
170 if (GF)
171 {
172 int k= getGFDegree();
173 char cGFName= gf_name;
178#ifdef HAVE_NTL
179 if (getCharacteristic() > 2)
180#else
181 if (getCharacteristic() > 0)
182#endif
183 {
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
189
192
194
197
200
202
204 beta, fq_con);
205
211#else
213 {
215 zz_p::init (getCharacteristic());
216 }
218 zz_pE::init (NTLMipo);
220 MakeMonic (NTLA);
222 zz_pE multi= to_zz_pE (1);
224 x, beta);
225#endif
226 }
227#ifdef HAVE_NTL
228 else
229 {
231 GF2E::init (NTLMipo);
233 MakeMonic (NTLA);
235 GF2E multi= to_GF2E (1);
237 x, beta);
238 }
239#endif
241 for (CFFListIterator i= factorsA; i.hasItem(); i++)
242 {
243 buf= i.getItem().factor();
245 i.getItem()= CFFactor (buf, i.getItem().exp());
246 }
247 prune (beta);
248 }
249 else if (alpha.level() != 1)
250 {
251#ifdef HAVE_NTL
252 if (getCharacteristic() > 2)
253#else
254 if (getCharacteristic() > 0)
255#endif
256 {
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
262
265
267
270
273
275
277 alpha, fq_con);
278
284#else
286 {
288 zz_p::init (getCharacteristic());
289 }
291 zz_pE::init (NTLMipo);
293 MakeMonic (NTLA);
295 zz_pE multi= to_zz_pE (1);
297 x, alpha);
298#endif
299 }
300#ifdef HAVE_NTL
301 else
302 {
304 GF2E::init (NTLMipo);
306 MakeMonic (NTLA);
308 GF2E multi= to_GF2E (1);
310 x, alpha);
311 }
312#endif
313 }
314 else
315 {
316#ifdef HAVE_FLINT
317#ifdef HAVE_NTL
318 if (degree (A) < 300)
319#endif
320 {
327 if (factorsA.getFirst().factor().inCoeffDomain())
331 }
332#ifdef HAVE_NTL
333 else
334#endif
335#endif /* HAVE_FLINT */
336#ifdef HAVE_NTL
337 if (getCharacteristic() > 2)
338 {
340 {
342 zz_p::init (getCharacteristic());
343 }
345 MakeMonic (NTLA);
347 zz_p multi= to_zz_p (1);
349 x);
350 }
351 else
352 {
355 GF2 multi= to_GF2 (1);
357 x);
358 }
359#endif
360 }
362 for (CFFListIterator i= factorsA; i.hasItem(); i++)
363 uniFactors.append (i.getItem().factor());
364 return uniFactors;
365}
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
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.
Factor< CanonicalForm > CFFactor
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)