Loading...
Searching...
No Matches
facFqBivar.h File Reference

This file provides functions for factorizing a bivariate polynomial over , 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 .
CFList | FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha)
| factorize a squarefree bivariate polynomial over .
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
CFFList | FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
| factorize a bivariate polynomial over
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())
| 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 .
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 , 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] | F | a sqrfree bivariate poly
  [in] | info | information about extension

Definition at line 8306 of file facFqBivar.cc.

{
if (F.inCoeffDomain())
return CFList(F);
CanonicalForm A= F;
bool GF= (CFFactory::gettype() == GaloisFieldDomain);
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
bool extension= info.isInExtension();
if (A.isUnivariate())
{
if (extension == false)
return uniFactorizer (F, alpha, GF);
else
{
CFList source, dest;
A= mapDown (A, info, source, dest);
return uniFactorizer (A, beta, GF);
}
}
CFMap N;
A= compress (A, N);
Variable y= A.mvar();
if (y.level() > 2) return CFList (F);
Variable x= Variable (1);
//remove and factorize content
CanonicalForm contentAx= content (A, x);
CanonicalForm contentAy= content (A);
A= A/(contentAx*contentAy);
CFList contentAxFactors, contentAyFactors;
if (!extension)
{
contentAxFactors= uniFactorizer (contentAx, alpha, GF);
contentAyFactors= uniFactorizer (contentAy, alpha, GF);
}
//trivial case
CFList factors;
if (A.inCoeffDomain())
{
append (factors, contentAxFactors);
append (factors, contentAyFactors);
decompress (factors, N);
return factors;
}
else if (A.isUnivariate())
{
factors= uniFactorizer (A, alpha, GF);
append (factors, contentAxFactors);
append (factors, contentAyFactors);
decompress (factors, N);
return factors;
}
//check trivial case
if (degree (A) == 1 || degree (A, 1) == 1 ||
(size (A) == 2 && igcd (degree (A), degree (A,1))==1))
{
factors.append (A);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
false, false, N);
if (!extension)
normalize (factors);
return factors;
}
// check derivatives
bool derivXZero= false;
CanonicalForm derivX= deriv (A, x);
CanonicalForm gcdDerivX;
if (derivX.isZero())
derivXZero= true;
else
{
gcdDerivX= gcd (A, derivX);
if (degree (gcdDerivX) > 0)
{
CanonicalForm g= A/gcdDerivX;
CFList factorsG=
Union (biFactorize (g, info), biFactorize (gcdDerivX, info));
append (factorsG, contentAxFactors);
append (factorsG, contentAyFactors);
decompress (factorsG, N);
if (!extension)
normalize (factorsG);
return factorsG;
}
}
bool derivYZero= false;
CanonicalForm derivY= deriv (A, y);
CanonicalForm gcdDerivY;
if (derivY.isZero())
derivYZero= true;
else
{
gcdDerivY= gcd (A, derivY);
if (degree (gcdDerivY) > 0)
{
CanonicalForm g= A/gcdDerivY;
CFList factorsG=
Union (biFactorize (g, info), biFactorize (gcdDerivY, info));
append (factorsG, contentAxFactors);
append (factorsG, contentAyFactors);
decompress (factorsG, N);
if (!extension)
normalize (factorsG);
return factorsG;
}
}
//main variable is chosen s.t. the degree in x is minimal
bool swap= false;
if ((degree (A) > degree (A, x)) || derivXZero)
{
if (!derivYZero)
{
A= swapvar (A, y, x);
swap= derivXZero;
derivXZero= derivYZero;
derivYZero= swap;
swap= true;
}
}
int boundsLength;
bool isIrreducible= false;
int * bounds= computeBounds (A, boundsLength, isIrreducible);
if (isIrreducible)
{
delete [] bounds;
factors.append (A);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, false, N);
if (!extension)
normalize (factors);
return factors;
}
int minBound= bounds[0];
for (int i= 1; i < boundsLength; i++)
{
if (bounds[i] != 0)
minBound= tmin (minBound, bounds[i]);
}
int boundsLength2;
int * bounds2= computeBoundsWrtDiffMainvar (A, boundsLength2, isIrreducible);
int minBound2= bounds2[0];
for (int i= 1; i < boundsLength2; i++)
{
if (bounds2[i] != 0)
minBound2= tmin (minBound2, bounds2[i]);
}
bool fail= false;
CanonicalForm Aeval, evaluation, bufAeval, bufEvaluation, buf, tmp;
CFList uniFactors, list, bufUniFactors;
DegreePattern degs;
DegreePattern bufDegs;
bool fail2= false;
CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
CFList bufUniFactors2, list2, uniFactors2;
DegreePattern degs2;
DegreePattern bufDegs2;
bool swap2= false;
// several univariate factorizations to obtain more information about the
// degree pattern therefore usually less combinations have to be tried during
// the recombination process
int factorNums= 3;
int subCheck1= substituteCheck (A, x);
int subCheck2= substituteCheck (A, y);
bool symmetric= false;
TIMING_START (fac_fq_uni_total);
for (int i= 0; i < factorNums; i++)
{
bufAeval= A;
TIMING_START (fac_fq_bi_evaluation);
bufEvaluation= evalPoint (A, bufAeval, alpha, list, GF, fail);
TIMING_END_AND_PRINT (fac_fq_bi_evaluation, "time to find eval point: ");
if (!derivXZero && !fail2 && !symmetric)
{
if (i == 0)
{
buf= swapvar (A, x, y);
symmetric= (A/Lc (A) == buf/Lc (buf));
}
bufAeval2= buf;
TIMING_START (fac_fq_bi_evaluation);
bufEvaluation2= evalPoint (buf, bufAeval2, alpha, list2, GF, fail2);
TIMING_END_AND_PRINT (fac_fq_bi_evaluation,
"time to find eval point wrt y: ");
}
// first try to change main variable if there is no valid evaluation point
if (fail && (i == 0))
{
if (!derivXZero && !fail2 && !symmetric)
{
bufEvaluation= bufEvaluation2;
int dummy= subCheck2;
subCheck2= subCheck1;
subCheck1= dummy;
tmp= A;
A= buf;
buf= tmp;
bufAeval= bufAeval2;
swap2= true;
fail= false;
}
else
fail= true;
}
// if there is no valid evaluation point pass to a field extension
if (fail && (i == 0))
{
factors= extBiFactorize (A, info);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
normalize (factors);
delete [] bounds;
delete [] bounds2;
return factors;
}
// there is at least one valid evaluation point
// but we do not compute more univariate factorization over an extension
if (fail && (i != 0))
break;
// univariate factorization
TIMING_START (fac_fq_uni_factorizer);
bufUniFactors= uniFactorizer (bufAeval, alpha, GF);
TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
"time for univariate factorization over Fq: ");
DEBOUTLN (cerr, "Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
(prod (bufUniFactors)*Lc (bufAeval) == bufAeval));
if (!derivXZero && !fail2 && !symmetric)
{
TIMING_START (fac_fq_uni_factorizer);
bufUniFactors2= uniFactorizer (bufAeval2, alpha, GF);
TIMING_END_AND_PRINT (fac_fq_uni_factorizer,
"time for univariate factorization in y over Fq: ");
DEBOUTLN (cerr, "Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
(prod (bufUniFactors2)*Lc (bufAeval2) == bufAeval2));
}
if (bufUniFactors.length() == 1 ||
(!fail2 && !derivXZero && !symmetric && (bufUniFactors2.length() == 1)))
{
if (extension)
{
CFList source, dest;
appendMapDown (factors, A, info, source, dest);
}
else
factors.append (A);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
if (!extension)
normalize (factors);
delete [] bounds;
delete [] bounds2;
return factors;
}
if (i == 0 && !extension)
{
if (subCheck1 > 0)
{
int subCheck= substituteCheck (bufUniFactors);
if (subCheck > 1 && (subCheck1%subCheck == 0))
{
CanonicalForm bufA= A;
subst (bufA, bufA, subCheck, x);
factors= biFactorize (bufA, info);
reverseSubst (factors, subCheck, x);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
if (!extension)
normalize (factors);
delete [] bounds;
delete [] bounds2;
return factors;
}
}
if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
{
int subCheck= substituteCheck (bufUniFactors2);
if (subCheck > 1 && (subCheck2%subCheck == 0))
{
CanonicalForm bufA= A;
subst (bufA, bufA, subCheck, y);
factors= biFactorize (bufA, info);
reverseSubst (factors, subCheck, y);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
if (!extension)
normalize (factors);
delete [] bounds;
delete [] bounds2;
return factors;
}
}
}
// degree analysis
bufDegs = DegreePattern (bufUniFactors);
if (!derivXZero && !fail2 && !symmetric)
bufDegs2= DegreePattern (bufUniFactors2);
if (i == 0)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
uniFactors= bufUniFactors;
degs= bufDegs;
if (!derivXZero && !fail2 && !symmetric)
{
Aeval2= bufAeval2;
evaluation2= bufEvaluation2;
uniFactors2= bufUniFactors2;
degs2= bufDegs2;
}
}
else
{
degs.intersect (bufDegs);
if (!derivXZero && !fail2 && !symmetric)
{
degs2.intersect (bufDegs2);
if (bufUniFactors2.length() < uniFactors2.length())
{
uniFactors2= bufUniFactors2;
Aeval2= bufAeval2;
evaluation2= bufEvaluation2;
}
}
if (bufUniFactors.length() < uniFactors.length())
{
uniFactors= bufUniFactors;
Aeval= bufAeval;
evaluation= bufEvaluation;
}
}
list.append (bufEvaluation);
if (!derivXZero && !fail2 && !symmetric)
list2.append (bufEvaluation2);
}
TIMING_END_AND_PRINT (fac_fq_uni_total,
"total time for univariate factorizations: ");
if (!derivXZero && !fail2 && !symmetric)
{
if ((uniFactors.length() > uniFactors2.length() && minBound2 <= minBound)||
(uniFactors.length() == uniFactors2.length()
&& degs.getLength() > degs2.getLength() && minBound2 <= minBound))
{
degs= degs2;
uniFactors= uniFactors2;
evaluation= evaluation2;
Aeval= Aeval2;
A= buf;
swap2= true;
}
}
if (degs.getLength() == 1) // A is irreducible
{
if (extension)
{
CFList source, dest;
appendMapDown (factors, A, info, source, dest);
}
else
factors.append (A);
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
if (!extension)
normalize (factors);
delete [] bounds;
delete [] bounds2;
return factors;
}
int liftBound= degree (A, y) + 1;
if (swap2)
{
delete [] bounds;
bounds= bounds2;
minBound= minBound2;
}
TIMING_START (fac_fq_bi_shift_to_zero);
A= A (y + evaluation, y);
TIMING_END_AND_PRINT (fac_fq_bi_shift_to_zero,
"time to shift eval to zero: ");
int degMipo= 1;
if (extension && alpha.level() != 1 && k==1)
degMipo= degree (getMipo (alpha));
DEBOUTLN (cerr, "uniFactors= " << uniFactors);
if ((GF && !extension) || (GF && extension && k != 1))
{
bool earlySuccess= false;
CFList earlyFactors;
TIMING_START (fac_fq_bi_hensel_lift);
uniFactors= henselLiftAndEarly
(A, earlySuccess, earlyFactors, degs, liftBound,
uniFactors, info, evaluation);
TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
"time for bivariate hensel lifting over Fq: ");
DEBOUTLN (cerr, "lifted factors= " << uniFactors);
CanonicalForm MODl= power (y, liftBound);
TIMING_START (fac_fq_bi_factor_recombination);
if (extension)
factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
evaluation, 1, uniFactors.length()/2);
else
factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
uniFactors.length()/2);
TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
"time for naive bivariate factor recombi over Fq: ");
if (earlySuccess)
factors= Union (earlyFactors, factors);
else if (!earlySuccess && degs.getLength() == 1)
factors= earlyFactors;
}
else if (degree (A) > 4 && beta.level() == 1 && (2*minBound)/degMipo < 32)
{
TIMING_START (fac_fq_bi_hensel_lift);
if (extension)
{
CFList lll= extHenselLiftAndLatticeRecombi (A, uniFactors, info, degs,
evaluation
);
factors= Union (lll, factors);
}
else if (alpha.level() == 1 && !GF)
{
CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
symmetric, evaluation);
factors= Union (lll, factors);
}
else if (!extension && (alpha != x || GF))
{
CFList lll= henselLiftAndLatticeRecombi (A, uniFactors, alpha, degs,
symmetric, evaluation);
factors= Union (lll, factors);
}
TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
"time to bivar lift and LLL recombi over Fq: ");
DEBOUTLN (cerr, "lifted factors= " << uniFactors);
}
else
{
bool earlySuccess= false;
CFList earlyFactors;
TIMING_START (fac_fq_bi_hensel_lift);
uniFactors= henselLiftAndEarly
(A, earlySuccess, earlyFactors, degs, liftBound,
uniFactors, info, evaluation);
TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
"time for bivar hensel lifting over Fq: ");
DEBOUTLN (cerr, "lifted factors= " << uniFactors);
CanonicalForm MODl= power (y, liftBound);
if (!extension)
{
TIMING_START (fac_fq_bi_factor_recombination);
factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1, 3);
TIMING_END_AND_PRINT (fac_fq_bi_factor_recombination,
"time for small subset naive recombi over Fq: ");
int oldUniFactorsLength= uniFactors.length();
if (degree (A) > 0)
{
CFList tmp;
TIMING_START (fac_fq_bi_hensel_lift);
if (alpha.level() == 1)
tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
liftBound, evaluation
);
else
{
if (degree (A) > getCharacteristic())
tmp= increasePrecisionFq2Fp (A, uniFactors, 0, uniFactors.length(),
1, alpha, liftBound, evaluation
);
else
tmp= increasePrecision (A, uniFactors, 0, uniFactors.length(), 1,
alpha, liftBound, evaluation
);
}
TIMING_END_AND_PRINT (fac_fq_bi_hensel_lift,
"time to increase precision: ");
factors= Union (factors, tmp);
if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
&& uniFactors.length() != oldUniFactorsLength)
)
{
DegreePattern bufDegs= DegreePattern (uniFactors);
degs.intersect (bufDegs);
degs.refine ();
factors= Union (factors, factorRecombination (uniFactors, A, MODl,
degs, evaluation, 4,
uniFactors.length()/2
)
);
}
}
}
else
{
if (beta.level() != 1 || k > 1)
{
if (k > 1)
{
factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
evaluation, 1, uniFactors.length()/2
);
}
else
{
factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
evaluation, 1, 3
);
if (degree (A) > 0)
{
CFList tmp= increasePrecision2 (A, uniFactors, alpha, liftBound);
DegreePattern bufDegs= DegreePattern (tmp);
degs.intersect (bufDegs);
degs.refine ();
factors= Union (factors, extFactorRecombination (tmp, A, MODl, info,
degs, evaluation,
1, tmp.length()/2
)
);
}
}
}
else
{
factors= extFactorRecombination (uniFactors, A, MODl, info, degs,
evaluation, 1, 3
);
int oldUniFactorsLength= uniFactors.length();
if (degree (A) > 0)
{
int degMipo;
ExtensionInfo info2= init4ext (info, evaluation, degMipo);
CFList source, dest;
CFList tmp= extIncreasePrecision (A, uniFactors, 0,
uniFactors.length(), 1, evaluation,
info2, source, dest, liftBound
);
factors= Union (factors, tmp);
if (tmp.length() == 0 || (tmp.length() > 0 && uniFactors.length() != 0
&& uniFactors.length() != oldUniFactorsLength)
)
{
DegreePattern bufDegs= DegreePattern (uniFactors);
degs.intersect (bufDegs);
degs.refine ();
factors= Union (factors,extFactorRecombination (uniFactors, A, MODl,
info, degs, evaluation,
4, uniFactors.length()/2
)
);
}
}
}
}
if (earlySuccess)
factors= Union (earlyFactors, factors);
else if (!earlySuccess && degs.getLength() == 1)
factors= earlyFactors;
}
if (!swap2)
delete [] bounds2;
delete [] bounds;
appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
swap, swap2, N);
if (!extension)
normalize (factors);
return factors;
}
swap
#define swap(_i, _j)
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition cfNewtonPolygon.cc:853
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition cf_map_ext.cc:124
igcd
int igcd(int a, int b)
Definition cf_util.cc:56
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
DegreePattern
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition DegreePattern.h:32
DegreePattern::intersect
void intersect(const DegreePattern &degPat)
intersect two degree patterns
Definition DegreePattern.cc:68
DegreePattern::getLength
int getLength() const
getter
Definition DegreePattern.h:86
DegreePattern::refine
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
Definition DegreePattern.cc:105
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
alpha
Variable alpha
Definition facAbsBiFact.cc:52
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
beta
Variable beta
Definition facAbsFact.cc:95
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
biFactorize
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition facBivar.cc:188
Aeval
CFList *& Aeval
<[in] poly
Definition facFactorize.h:31
computeBounds
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
Definition facFqBivarUtil.cc:768
appendSwapDecompress
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...
Definition facFqBivarUtil.cc:70
appendMapDown
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
Definition facFqBivarUtil.cc:267
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1089
computeBoundsWrtDiffMainvar
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
Definition facFqBivarUtil.cc:922
biFactorize
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoringmultivariate polynomials over a f...
Definition facFqBivar.cc:8306
increasePrecision
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
Definition facFqBivar.cc:3478
extHenselLiftAndLatticeRecombi
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern &degPat, const CanonicalForm &eval)
Definition facFqBivar.cc:7715
extBiFactorize
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition facFqBivar.cc:8931
increasePrecisionFq2Fp
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
Definition facFqBivar.cc:4270
extIncreasePrecision
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
Definition facFqBivar.cc:3829
henselLiftAndLatticeRecombi
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern &degPat, bool symmetric, const CanonicalForm &eval)
Definition facFqBivar.cc:6862
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 as decribed in "Factoringmultivariate polynomials over a finite field" by ...
Definition facFqBivar.cc:373
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 .
Definition facFqBivar.cc:87
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition facFqBivar.cc:1155
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 ...
Definition facFqBivar.cc:163
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 as decribed in "Factoringmultivariate polynomials over a finite field" by ...
Definition facFqBivar.cc:589
init4ext
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int &degMipo)
Definition facFqBivar.cc:7660
increasePrecision2
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
Definition facFqBivar.cc:4137
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
info
#define info
Definition libparse.cc:1256
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
buf
int status int void * buf
Definition si_signals.h:69
A
#define A
Definition sirandom.c:24
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## biSqrfFactorizeHelper()

CFList biSqrfFactorizeHelper | ( | const CanonicalForm & | G,
|  | const ExtensionInfo & | info )

inline

Definition at line 55 of file facFqBivar.h.

{
CFMap N;
CanonicalForm F= compress (G, N);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
if (info.getAlpha().level() != 1)
{
contentXFactors= factorize (contentX, info.getAlpha());
contentYFactors= factorize (contentY, info.getAlpha());
}
else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
{
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
}
else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
{
CFList bufContentX, bufContentY;
bufContentX= biFactorize (contentX, info);
bufContentY= biFactorize (contentY, info);
for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
contentXFactors.append (CFFactor (iter.getItem(), 1));
for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
contentYFactors.append (CFFactor (iter.getItem(), 1));
}
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
if (F.inCoeffDomain())
{
CFList result;
for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
normalize (result);
result.insert (Lc (G));
return result;
}
mpz_t * M=new mpz_t [4];
mpz_init (M[0]);
mpz_init (M[1]);
mpz_init (M[2]);
mpz_init (M[3]);
mpz_t * S=new mpz_t [2];
mpz_init (S[0]);
mpz_init (S[1]);
F= compress (F, M, S);
CFList result= biFactorize (F, info);
for (CFListIterator i= result; i.hasItem(); i++)
i.getItem()= N (decompress (i.getItem(), M, S));
for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
result.append (N(i.getItem().factor()));
for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
normalize (result);
result.insert (Lc(G));
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return result;
}
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
result
return result
Definition facAbsBiFact.cc:76
biFactorize
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Definition facFqBivar.cc:8306
G
STATIC_VAR TreeM * G
Definition janet.cc:31
M
#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] | alpha | some algebraic variable
  [in] | beta | some algebraic variable
  [in] | k | some int

Definition at line 809 of file facFqBivar.cc.

{
int i=1, m= 2;
// extension of F_p needed
if (alpha.level() == 1 && beta.level() == 1 && k == 1)
{
i= 1;
m= 2;
} //extension of F_p(alpha) needed but want to factorize over F_p
else if (alpha.level() != 1 && beta.level() == 1 && k == 1)
{
i= 1;
m= degree (getMipo (alpha)) + 1;
} //extension of F_p(alpha) needed for first time
else if (alpha.level() != 1 && beta.level() == 1 && k != 1)
{
i= 2;
m= degree (getMipo (alpha));
}
else if (alpha.level() != 1 && beta.level() != 1 && k != 1)
{
m= degree (getMipo (beta));
i= degree (getMipo (alpha))/m + 1;
}
#if defined(HAVE_FLINT)
nmod_poly_t Irredpoly;
nmod_poly_init(Irredpoly,getCharacteristic());
nmod_poly_randtest_monic_irreducible(Irredpoly,FLINTrandom,i*m+1);
CanonicalForm newMipo= convertnmod_poly_t2FacCF(Irredpoly,Variable (1));
#elif defined(HAVE_NTL)
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char= getCharacteristic();
zz_p::init (getCharacteristic());
}
zz_pX NTLIrredpoly;
BuildIrred (NTLIrredpoly, i*m);
CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
#else
factoryError("NTL/FLINT missing: chooseExtension");
#endif
return rootOf (newMipo);
}
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition FLINTconvert.cc:208
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
m
int m
Definition cfEzgcd.cc:128
FLINTrandom
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:23
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
rootOf
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] | reconstructedFactors | list of reconstructed factors
  [in,out] | F | poly to be factored, returns poly divided by detected factors in case of success
  [in,out] | factors | list of factors lifted up to deg, returns a list of factors without detected factors
  [in,out] | adaptedLiftBound | adapted lift bound
  [in,out] | factorsFoundIndex | factors already considered
  [in,out] | degs | degree pattern, is updated whenever we find a factor
  [in,out] | success | indicating success
  [in] | deg | stage of Hensel lifting
  [in] | eval | evaluation point
  [in] | b | coeff bound

Definition at line 974 of file facFqBivar.cc.

{
CanonicalForm den= 1;
earlyFactorDetection (reconstructedFactors, F, factors, adaptedLiftBound,
factorsFoundIndex, degs, success, deg, eval, b, den);
}
den
CanonicalForm den(const CanonicalForm &f)
Definition canonicalform.h:340
b
CanonicalForm b
Definition cfModGcd.cc:4111
eval
CFList & eval
Definition facFactorize.cc:47
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, CanonicalForm &den)
Definition facFqBivar.cc:855

## 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 .

Returns
  evalPoint returns an evaluation point, which is valid if and only if fail == false.

Parameters

  [in] | F | compressed, bivariate poly
  [in,out] | eval | F (p, y)
  [in] | alpha | algebraic variable
  [in] | list | list of points already considered
  [in] | GF | GaloisFieldDomain?
  [in,out] | fail | equals true, if there is no valid evaluation point

Definition at line 87 of file facFqBivar.cc.

{
fail= false;
Variable x= Variable(2);
Variable y= Variable(1);
FFRandom genFF;
GFRandom genGF;
CanonicalForm random, mipo;
double bound;
int p= getCharacteristic ();
if (alpha.level() != 1)
{
mipo= getMipo (alpha);
int d= degree (mipo);
bound= pow ((double) p, (double) d);
}
else if (GF)
{
int d= getGFDegree();
bound= ipower (p, d);
}
else
bound= p;
random= 0;
do
{
if (list.length() >= bound)
{
fail= true;
break;
}
if (list.isEmpty())
random= 0;
else if (GF)
{
if (list.length() == 1)
random= getGFGenerator();
else
random= genGF.generate();
}
else if (list.length() < p || alpha.level() == 1)
random= genFF.generate();
else if (alpha != x && list.length() >= p)
{
if (list.length() == p)
random= alpha;
else
{
AlgExtRandomF genAlgExt (alpha);
random= genAlgExt.generate();
}
}
if (find (list, random)) continue;
eval= F (random, x);
if (degree (eval) != degree (F, y))
{ //leading coeff vanishes
if (!find (list, random))
list.append (random);
continue;
}
if (degree (gcd (deriv (eval, eval.mvar()), eval), eval.mvar()) > 0)
{ //evaluated polynomial is not squarefree
if (!find (list, random))
list.append (random);
continue;
}
} while (find (list, random));
return random;
}
pow
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
getGFGenerator
CanonicalForm getGFGenerator()
Definition cf_char.cc:81
p
int p
Definition cfModGcd.cc:4086
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
AlgExtRandomF
generate random elements in F_p(alpha)
Definition cf_random.h:70
FFRandom
generate random elements in F_p
Definition cf_random.h:44
FFRandom::generate
CanonicalForm generate() const
Definition cf_random.cc:65
GFRandom
generate random elements in GF
Definition cf_random.h:32
GFRandom::generate
CanonicalForm generate() const
Definition cf_random.cc:75
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
find
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] | F | poly to be factored
  [in] | info | info about extension

Definition at line 8931 of file facFqBivar.cc.

{
CanonicalForm A= F;
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
int k= info.getGFDegree();
char cGFName= info.getGFName();
CanonicalForm delta= info.getDelta();
bool GF= (CFFactory::gettype() == GaloisFieldDomain);
Variable x= Variable (1);
CFList factors;
if (!GF && alpha == x) // we are in F_p
{
bool extension= true;
int p= getCharacteristic();
if (p*p < (1<<16)) // pass to GF if possible
{
setCharacteristic (getCharacteristic(), 2, 'Z');
A= A.mapinto();
ExtensionInfo info2= ExtensionInfo (extension);
factors= biFactorize (A, info2);
CanonicalForm mipo= gf_mipo;
setCharacteristic (getCharacteristic());
Variable vBuf= rootOf (mipo.mapinto());
for (CFListIterator j= factors; j.hasItem(); j++)
j.getItem()= GF2FalphaRep (j.getItem(), vBuf);
prune (vBuf);
}
else // not able to pass to GF, pass to F_p(\alpha)
{
CanonicalForm mipo= randomIrredpoly (2, x);
Variable v= rootOf (mipo);
ExtensionInfo info2= ExtensionInfo (v);
factors= biFactorize (A, info2);
prune (v);
}
return factors;
}
else if (!GF && (alpha != x)) // we are in F_p(\alpha)
{
if (k == 1) // need factorization over F_p
{
int extDeg= degree (getMipo (alpha));
extDeg++;
CanonicalForm mipo= randomIrredpoly (extDeg, x);
Variable v= rootOf (mipo);
ExtensionInfo info2= ExtensionInfo (v);
factors= biFactorize (A, info2);
prune (v);
}
else
{
if (beta == x)
{
Variable v= chooseExtension (alpha, beta, k);
CanonicalForm primElem, imPrimElem;
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (alpha, vBuf, primFail);
ASSERT (!primFail, "failure in integer factorizer");
if (primFail)
; //ERROR
else
imPrimElem= mapPrimElem (primElem, alpha, v);
CFList source, dest;
CanonicalForm bufA= mapUp (A, alpha, v, primElem, imPrimElem,
source, dest);
ExtensionInfo info2= ExtensionInfo (v, alpha, imPrimElem, primElem);
factors= biFactorize (bufA, info2);
prune (v);
}
else
{
Variable v= chooseExtension (alpha, beta, k);
CanonicalForm primElem, imPrimElem;
bool primFail= false;
Variable vBuf;
ASSERT (!primFail, "failure in integer factorizer");
if (primFail)
; //ERROR
else
imPrimElem= mapPrimElem (delta, beta, v);
CFList source, dest;
CanonicalForm bufA= mapDown (A, info, source, dest);
source= CFList();
dest= CFList();
bufA= mapUp (bufA, beta, v, delta, imPrimElem, source, dest);
ExtensionInfo info2= ExtensionInfo (v, beta, imPrimElem, delta);
factors= biFactorize (bufA, info2);
prune (v);
}
}
return factors;
}
else // we are in GF (p^k)
{
int p= getCharacteristic();
int extensionDeg= getGFDegree();
bool extension= true;
if (k == 1) // need factorization over F_p
{
extensionDeg++;
if (ipower (p, extensionDeg) < (1<<16))
// pass to GF(p^k+1)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable vBuf= rootOf (mipo.mapinto());
A= GF2FalphaRep (A, vBuf);
setCharacteristic (p, extensionDeg, 'Z');
ExtensionInfo info2= ExtensionInfo (extension);
factors= biFactorize (A.mapinto(), info2);
prune (vBuf);
}
else // not able to pass to another GF, pass to F_p(\alpha)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable vBuf= rootOf (mipo.mapinto());
A= GF2FalphaRep (A, vBuf);
Variable v= chooseExtension (vBuf, beta, k);
ExtensionInfo info2= ExtensionInfo (v, extension);
factors= biFactorize (A, info2);
prune (vBuf);
}
}
else // need factorization over GF (p^k)
{
if (ipower (p, 2*extensionDeg) < (1<<16))
// pass to GF (p^2k)
{
setCharacteristic (p, 2*extensionDeg, 'Z');
ExtensionInfo info2= ExtensionInfo (k, cGFName, extension);
factors= biFactorize (GFMapUp (A, extensionDeg), info2);
setCharacteristic (p, extensionDeg, cGFName);
}
else // not able to pass to GF (p^2k), pass to F_p (\alpha)
{
CanonicalForm mipo= gf_mipo;
setCharacteristic (p);
Variable v1= rootOf (mipo.mapinto());
A= GF2FalphaRep (A, v1);
Variable v2= chooseExtension (v1, v1, k);
CanonicalForm primElem, imPrimElem;
bool primFail= false;
Variable vBuf;
primElem= primitiveElement (v1, vBuf, primFail);
ASSERT (!primFail, "failure in integer factorizer");
if (primFail)
; //ERROR
else
imPrimElem= mapPrimElem (primElem, v1, v2);
CFList source, dest;
CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
source, dest);
ExtensionInfo info2= ExtensionInfo (v2, v1, imPrimElem, primElem);
factors= biFactorize (bufA, info2);
setCharacteristic (p, k, cGFName);
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem()= Falpha2GFRep (i.getItem());
prune (v1);
}
}
return factors;
}
}
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
randomIrredpoly
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
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition cf_map_ext.cc:451
primitiveElement
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition cf_map_ext.cc:343
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
Falpha2GFRep
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition cf_map_ext.cc:204
GFMapUp
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition cf_map_ext.cc:241
GF2FalphaRep
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition cf_map_ext.cc:196
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
chooseExtension
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition facFqBivar.cc:809
j
int j
Definition facHensel.cc:110
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
gf_mipo
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] | reconstructedFactors | list of reconstructed factors
  [in,out] | F | poly to be factored, returns poly divided by detected factors in case of success
  [in,out] | factors | list of factors lifted up to deg, returns a list of factors without detected factors
  [in,out] | adaptedLiftBound | adapted lift bound
  [in,out] | factorsFoundIndex | factors already considered
  [in,out] | degs | degree pattern, is updated whenever we find a factor
  [in,out] | success | indicating success
  [in] | info | information about extension
  [in] | eval | evaluation point
  [in] | deg | stage of Hensel lifting

Definition at line 985 of file facFqBivar.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
DegreePattern bufDegs1= degs, bufDegs2;
CFList result;
CFList T= factors;
Variable y= F.mvar();
Variable x= Variable (1);
CanonicalForm buf= F, LCBuf= LC (buf, x), g, buf2;
CanonicalForm M= power (y, deg);
adaptedLiftBound= 0;
bool trueFactor= false;
int d= degree (F), l= 0;
CFList source, dest;
int degMipoBeta= 1;
if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
CanonicalForm quot;
for (CFListIterator i= factors; i.hasItem(); i++, l++)
{
if (!bufDegs1.find (degree (i.getItem(), 1)) || factorsFoundIndex[l] == 1)
continue;
else
{
g= mulMod2 (i.getItem(), LCBuf, M);
g /= content (g, x);
if (fdivides (g, buf, quot))
{
buf2= g (y - eval, y);
buf2 /= Lc (buf2);
if (!k && beta == x)
{
if (degree (buf2, alpha) < degMipoBeta)
{
appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
factorsFoundIndex[l]= 1;
buf= quot;
d -= degree (g);
LCBuf= LC (buf, x);
trueFactor= true;
}
}
else
{
if (!isInExtension (buf2, gamma, k, delta, source, dest))
{
appendTestMapDown (reconstructedFactors, buf2, info, source, dest);
factorsFoundIndex[l]= 1;
buf= quot;
d -= degree (g);
LCBuf= LC (buf, x);
trueFactor= true;
}
}
if (trueFactor)
{
T= Difference (T, CFList (i.getItem()));
F= buf;
// compute new possible degree pattern
bufDegs2= DegreePattern (T);
bufDegs1.intersect (bufDegs2);
bufDegs1.refine ();
trueFactor= false;
if (bufDegs1.getLength() <= 1)
{
if (!buf.inCoeffDomain())
{
buf= buf (y - eval, y);
buf /= Lc (buf);
appendMapDown (reconstructedFactors, buf, info, source, dest);
F= 1;
}
break;
}
}
}
}
}
adaptedLiftBound= d + 1;
if (adaptedLiftBound < deg)
{
degs= bufDegs1;
success= true;
}
if (bufDegs1.getLength() <= 1)
degs= bufDegs1;
}
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
l
int l
Definition cfEzgcd.cc:100
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
DegreePattern::find
int find(const int x) const
find an element x
Definition DegreePattern.h:159
appendTestMapDown
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
Definition facFqBivarUtil.cc:223
isInExtension
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)
Definition facFqBivarUtil.cc:184
buf2
CanonicalForm buf2
Definition facFqBivar.cc:76
mulMod2
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2992
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
T
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] | factors | list of lifted factors that are monic wrt Variable (1), original factors-factors found
  [in,out] | F | poly to be factored, F/factors found
  [in] | N | Variable (2)^liftBound
  [in] | info | contains information about extension
  [in] | eval | evaluation point
  [in] | s | algorithm starts checking subsets of size s
  [in] | thres | threshold 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.

{
if (factors.length() == 0)
{
F= 1;
return CFList();
}
if (F.inCoeffDomain())
return CFList();
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
CanonicalForm M= N;
int l= degree (N);
Variable y= F.mvar();
Variable x= Variable (1);
CFList source, dest;
if (degs.getLength() <= 1 || factors.length() == 1)
{
CFList result= CFList(mapDown (F(y-eval, y), info, source, dest));
F= 1;
return result;
}
DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, M) == F " <<
(mod (LC (F, 1)*prodMod (factors, M), M)/Lc (mod (LC (F, 1)*prodMod (factors, M), M)) == F/Lc (F)));
int degMipoBeta= 1;
if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
CFList T, S, Diff;
T= factors;
CFList result;
CanonicalForm buf, buf2, quot;
buf= F;
CanonicalForm g, LCBuf= LC (buf, x);
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
CFArray TT;
DegreePattern bufDegs1, bufDegs2;
bufDegs1= degs;
int subsetDeg;
TT= copy (factors);
bool nosubset= false;
bool recombination= false;
bool trueFactor= false;
CanonicalForm test;
CanonicalForm buf0= buf (0, x)*LCBuf;
while (T.length() >= 2*s && s <= thres)
{
while (nosubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombination)
{
T.insert (LCBuf);
g= prodMod (T, M);
T.removeFirst();
g /= content(g);
g= g (y - eval, y);
g /= Lc (g);
appendTestMapDown (result, g, info, source, dest);
F= 1;
return result;
}
else
{
appendMapDown (result, F (y - eval, y), info, source, dest);
F= 1;
return result;
}
}
S= subset (v, s, TT, nosubset);
if (nosubset) break;
subsetDeg= subsetDegree (S);
// skip those combinations that are not possible
if (!degs.find (subsetDeg))
continue;
else
{
test= prodMod0 (S, M);
test *= LCBuf;
test = mod (test, M);
if (fdivides (test, buf0))
{
S.insert (LCBuf);
g= prodMod (S, M);
S.removeFirst();
g /= content (g, x);
if (fdivides (g, buf, quot))
{
buf2= g (y - eval, y);
buf2 /= Lc (buf2);
if (!k && beta.level() == 1)
{
if (degree (buf2, alpha) < degMipoBeta)
{
buf= quot;
LCBuf= LC (buf, x);
recombination= true;
appendTestMapDown (result, buf2, info, source, dest);
trueFactor= true;
}
}
else
{
if (!isInExtension (buf2, gamma, k, delta, source, dest))
{
buf= quot;
LCBuf= LC (buf, x);
recombination= true;
appendTestMapDown (result, buf2, info, source, dest);
trueFactor= true;
}
}
if (trueFactor)
{
T= Difference (T, S);
l -= degree (g);
M= power (y, l);
buf0= buf (0, x)*LCBuf;
// compute new possible degree pattern
bufDegs2= DegreePattern (T);
bufDegs1.intersect (bufDegs2);
bufDegs1.refine ();
if (T.length() < 2*s || T.length() == s ||
bufDegs1.getLength() == 1)
{
delete [] v;
if (recombination)
{
buf= buf (y-eval,y);
buf /= Lc (buf);
appendTestMapDown (result, buf, info, source,
dest);
F= 1;
return result;
}
else
{
appendMapDown (result, F (y - eval, y), info, source, dest);
F= 1;
return result;
}
}
trueFactor= false;
TT= copy (T);
indexUpdate (v, s, T.length(), nosubset);
if (nosubset) break;
}
}
}
}
}
s++;
if (T.length() < 2*s || T.length() == s)
{
delete [] v;
if (recombination)
{
buf= buf (y-eval,y);
buf /= Lc (buf);
appendTestMapDown (result, buf, info, source, dest);
F= 1;
return result;
}
else
{
appendMapDown (result, F (y - eval, y), info, source, dest);
F= 1;
return result;
}
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
nosubset= false;
}
if (T.length() < 2*s)
{
appendMapDown (result, F (y - eval, y), info, source, dest);
F= 1;
delete [] v;
return result;
}
if (s > thres)
{
factors= T;
F= buf;
degs= bufDegs1;
}
delete [] v;
return result;
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
test
CanonicalForm test
Definition cfModGcd.cc:4104
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
s
const CanonicalForm int s
Definition facAbsFact.cc:51
subsetDegree
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
Definition facFqBivarUtil.cc:428
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition facFqBivarUtil.cc:373
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
subset
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...
Definition facFqBivarUtil.cc:309
mod
return mod(mulNTL(buf1, buf2, b), M)
prodMod0
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
recombination
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...
Definition facFqFactorize.cc:2114
prodMod
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

  [in,out] | factors | list of lifted factors that are monic wrt Variable (1)
  [in,out] | F | poly to be factored
  [in] | N | Variable (2)^liftBound
  [in] | degs | degree pattern
  [in] | eval | evaluation point
  [in] | s | algorithm starts checking subsets of size s
  [in] | thres | threshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2
  [in] | b | coeff bound
  [in] | den | bound on the den if over Q (a)

Definition at line 589 of file facFqBivar.cc.

{
if (factors.length() == 0)
{
F= 1;
return CFList ();
}
if (F.inCoeffDomain())
return CFList();
Variable y= Variable (2);
if (degs.getLength() <= 1 || factors.length() == 1)
{
CFList result= CFList (F(y-eval,y));
F= 1;
return result;
}
#ifdef DEBUGOUTPUT
if (b.getp() == 0)
DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
(mod (LC (F, 1)*prodMod (factors, N),N)/Lc (mod (LC (F, 1)*prodMod (factors, N),N)) == F/Lc(F)));
else
DEBOUTLN (cerr, "LC (F, 1)*prodMod (factors, N) == F " <<
(mod (b(LC (F, 1)*prodMod (factors, N)),N)/Lc (mod (b(LC (F, 1)*prodMod (factors, N)),N)) == F/Lc(F)));
#endif
CFList T, S;
CanonicalForm M= N;
int l= degree (N);
T= factors;
CFList result;
Variable x= Variable (1);
CanonicalForm denom= den, denQuot;
CanonicalForm LCBuf= LC (F, x)*denom;
CanonicalForm g, quot, buf= F;
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
bool nosubset= false;
CFArray TT;
DegreePattern bufDegs1, bufDegs2;
bufDegs1= degs;
int subsetDeg;
TT= copy (factors);
bool recombination= false;
CanonicalForm test;
bool isRat= (isOn (SW_RATIONAL) && getCharacteristic() == 0) ||
getCharacteristic() > 0;
if (!isRat)
On (SW_RATIONAL);
CanonicalForm buf0= mulNTL (buf (0, x), LCBuf);
if (!isRat)
Off (SW_RATIONAL);
while (T.length() >= 2*s && s <= thres)
{
while (nosubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombination)
{
T.insert (LCBuf);
g= prodMod (T, M);
if (b.getp() != 0)
g= b(g);
T.removeFirst();
g /= content (g,x);
result.append (g(y-eval,y));
F= 1;
return result;
}
else
{
result= CFList (F(y-eval,y));
F= 1;
return result;
}
}
S= subset (v, s, TT, nosubset);
if (nosubset) break;
subsetDeg= subsetDegree (S);
// skip those combinations that are not possible
if (!degs.find (subsetDeg))
continue;
else
{
if (!isRat)
On (SW_RATIONAL);
test= prodMod0 (S, M);
if (!isRat)
{
test *= bCommonDen (test);
Off (SW_RATIONAL);
}
test= mulNTL (test, LCBuf, b);
test= mod (test, M);
if (uniFdivides (test, buf0))
{
if (!isRat)
On (SW_RATIONAL);
S.insert (LCBuf);
g= prodMod (S, M);
S.removeFirst();
if (!isRat)
{
g *= bCommonDen(g);
Off (SW_RATIONAL);
}
if (b.getp() != 0)
g= b(g);
if (!isRat)
On (SW_RATIONAL);
g /= content (g, x);
if (!isRat)
{
On (SW_RATIONAL);
if (!Lc (g).inBaseDomain())
g /= Lc (g);
g *= bCommonDen (g);
Off (SW_RATIONAL);
g /= icontent (g);
On (SW_RATIONAL);
}
if (fdivides (g, buf, quot))
{
denom *= abs (lc (g));
recombination= true;
result.append (g (y-eval,y));
if (b.getp() != 0)
{
denQuot= bCommonDen (quot);
buf= quot*denQuot;
Off (SW_RATIONAL);
denom /= gcd (denom, denQuot);
On (SW_RATIONAL);
}
else
buf= quot;
LCBuf= LC (buf, x)*denom;
T= Difference (T, S);
l -= degree (g);
M= power (y, l);
buf0= mulNTL (buf (0, x), LCBuf);
if (!isRat)
Off (SW_RATIONAL);
// compute new possible degree pattern
bufDegs2= DegreePattern (T);
bufDegs1.intersect (bufDegs2);
bufDegs1.refine ();
if (T.length() < 2*s || T.length() == s ||
bufDegs1.getLength() == 1)
{
delete [] v;
if (recombination)
{
result.append (buf (y-eval,y));
F= 1;
return result;
}
else
{
result= CFList (F (y-eval,y));
F= 1;
return result;
}
}
TT= copy (T);
indexUpdate (v, s, T.length(), nosubset);
if (nosubset) break;
}
if (!isRat)
Off (SW_RATIONAL);
}
}
}
s++;
if (T.length() < 2*s || T.length() == s)
{
delete [] v;
if (recombination)
{
result.append (buf(y-eval,y));
F= 1;
return result;
}
else
{
result= CFList (F(y-eval,y));
F= 1;
return result;
}
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
nosubset= false;
}
delete [] v;
if (T.length() < 2*s)
{
result.append (F(y-eval,y));
F= 1;
return result;
}
if (s > thres)
{
factors= T;
F= buf;
degs= bufDegs1;
}
return result;
}
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
b
const CanonicalForm const modpk & b
Definition facFqBivar.cc:64
mulNTL
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
uniFdivides
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

Returns
  FpBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

See also
  FqBiFactorize(), GFBiFactorize()

Parameters

  [in] | G | a bivariate poly
  [in] | substCheck | enables substitute check

Definition at line 190 of file facFqBivar.h.

{
ExtensionInfo info= ExtensionInfo (false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= FpBiFactorize (F, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= FpBiFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
mpz_t * M=new mpz_t [4];
mpz_init (M[0]);
mpz_init (M[1]);
mpz_init (M[2]);
mpz_init (M[3]);
mpz_t * S=new mpz_t [2];
mpz_init (S[0]);
mpz_init (S[1]);
F= compress (F, M, S);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= FpSqrf (F, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over Fp: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over Fp: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return result;
}
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
tmp2
CFList tmp2
Definition facFqBivar.cc:75
FpBiFactorize
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:190
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:38

## FpBiSqrfFactorize()

CFList FpBiSqrfFactorize | ( | const CanonicalForm & | G | ) |

inline

factorize a squarefree bivariate polynomial over .

Returns
  FpBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

See also
  FqBiSqrfFactorize(), GFBiSqrfFactorize()

Parameters

  [in] | G | a bivariate poly

Definition at line 141 of file facFqBivar.h.

{
ExtensionInfo info= ExtensionInfo (false);
return biSqrfFactorizeHelper (G, info);
}
biSqrfFactorizeHelper
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

Returns
  FqBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

See also
  FpBiFactorize(), FqBiFactorize()

Parameters

  [in] | G | a bivariate poly
  [in] | alpha | algebraic variable
  [in] | substCheck | enables substitute check

Definition at line 317 of file facFqBivar.h.

{
ExtensionInfo info= ExtensionInfo (alpha, false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= FqBiFactorize (F, alpha, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= FqBiFactorize (tmp2, alpha, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX, alpha);
contentYFactors= factorize (contentY, alpha);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
mpz_t * M=new mpz_t [4];
mpz_init (M[0]);
mpz_init (M[1]);
mpz_init (M[2]);
mpz_init (M[3]);
mpz_t * S=new mpz_t [2];
mpz_init (S[0]);
mpz_init (S[1]);
F= compress (F, M, S);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= FqSqrf (F, alpha, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over Fq: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over Fq: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return result;
}
FqBiFactorize
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:317
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:77

## FqBiSqrfFactorize()

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

inline

factorize a squarefree bivariate polynomial over .

Returns
  FqBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

See also
  FpBiSqrfFactorize(), GFBiSqrfFactorize()

Parameters

  [in] | G | a bivariate poly
  [in] | alpha | algebraic variable

Definition at line 156 of file facFqBivar.h.

{
ExtensionInfo info= ExtensionInfo (alpha, false);
return biSqrfFactorizeHelper (G, info);
}

## 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] | F | a bivariate poly
  [in,out] | sizeOfOutput | size of the output
  [in] | degreeLC | degree of the leading coeff [in] of F wrt. Variable (1)

Definition at line 1123 of file facFqBivar.cc.

{
int sizeOfNewtonPoly;
int ** newtonPolyg= newtonPolygon (F, sizeOfNewtonPoly);
int sizeOfRightSide;
int * rightSide= getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
int * result= getCombinations(rightSide, sizeOfRightSide, sizeOfOutput,
degreeLC);
delete [] rightSide;
for (int i= 0; i < sizeOfNewtonPoly; i++)
delete [] newtonPolyg[i];
delete [] newtonPolyg;
return result;
}
getRightSide
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...
Definition cfNewtonPolygon.cc:1071
newtonPolygon
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
Definition cfNewtonPolygon.cc:282
getCombinations
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
Definition facFqBivar.cc:1084

## 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] | G | a bivariate poly
  [in] | substCheck | enables substitute check

Definition at line 446 of file facFqBivar.h.

{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree=NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= GFBiFactorize (F, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= GFBiFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
mpz_t * M=new mpz_t [4];
mpz_init (M[0]);
mpz_init (M[1]);
mpz_init (M[2]);
mpz_init (M[3]);
mpz_t * S=new mpz_t [2];
mpz_init (S[0]);
mpz_init (S[1]);
F= compress (F, M, S);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= GFSqrf (F, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over GF: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over GF: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return result;
}
GFBiFactorize
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition facFqBivar.h:446
GFSqrf
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:116
gf_name
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] | G | a bivariate poly

Definition at line 172 of file facFqBivar.h.

{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
return biSqrfFactorizeHelper (G, info);
}

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

Definition at line 1458 of file facFqBivar.cc.

{
modpk dummy= modpk();
CanonicalForm den= 1;
return henselLiftAndEarly (A, earlySuccess, earlyFactors, degs, liftBound,
uniFactors, info, eval, dummy, den);
}
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk
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] | A | poly to be factored, returns poly divided by detected factors in case of success
  [in,out] | earlySuccess | indicating success
  [in,out] | earlyFactors | list of factors detected at early stage of Hensel lifting
  [in,out] | degs | degree pattern
  [in,out] | liftBound | (adapted) lift bound
  [in] | uniFactors | univariate factors
  [in] | info | information about extension
  [in] | eval | evaluation point
  [in] | b | coeff bound
  [in] | den | bound on the den if over Q(a)

Definition at line 1155 of file facFqBivar.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
bool extension= info.isInExtension();
int sizeOfLiftPre;
int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
Variable x= Variable (1);
Variable y= Variable (2);
CFArray Pi;
CFList diophant;
CFList bufUniFactors= uniFactors;
On (SW_RATIONAL);
CanonicalForm bufA= A;
if (!Lc (A).inBaseDomain())
{
bufA /= Lc (A);
CanonicalForm denBufA= bCommonDen (bufA);
bufA *= denBufA;
Off (SW_RATIONAL);
den /= gcd (den, denBufA);
}
else
{
bufA= A;
Off (SW_RATIONAL);
den /= gcd (den, Lc (A));
}
CanonicalForm lcA0= 0;
bool mipoHasDen= false;
if (getCharacteristic() == 0 && b.getp() != 0)
{
if (alpha.level() == 1)
{
lcA0= lc (A (0, 2));
A *= b.inverse (lcA0);
A= b (A);
for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
}
else
{
lcA0= Lc (A (0,2));
On (SW_RATIONAL);
mipoHasDen= !bCommonDen(getMipo(alpha)).isOne();
Off (SW_RATIONAL);
CanonicalForm lcA0inverse= b.inverse (lcA0);
A *= lcA0inverse;
A= b (A);
// Lc of bufUniFactors is in Z
for (CFListIterator i= bufUniFactors; i.hasItem(); i++)
i.getItem()= b (i.getItem()*b.inverse (lc (i.getItem())));
}
}
bufUniFactors.insert (LC (A, x));
CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
earlySuccess= false;
int newLiftBound= 0;
int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
int dummy;
int * factorsFoundIndex= new int [uniFactors.length()];
for (int i= 0; i < uniFactors.length(); i++)
factorsFoundIndex [i]= 0;
CFList bufBufUniFactors;
Variable v= alpha;
if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M, b, true);
else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
{
henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
if (mipoHasDen)
{
for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
if (hasFirstAlgVar (iter.getItem(), v))
break;
if (v != alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
A= replacevar (A, alpha, v);
}
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
smallFactorDeg, eval, b, den);
else
earlyFactorDetection(earlyFactors, bufA, bufBufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
smallFactorDeg, eval, b, den);
}
else
extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, smallFactorDeg);
if (degs.getLength() > 1 && !earlySuccess &&
smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
{
if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
{
bufUniFactors.insert (LC (A, x));
henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M, b);
if (v!=alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
else
earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess,
liftPre[sizeOfLiftPre-1] + 1, eval, b, den);
}
else
extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, liftPre[sizeOfLiftPre-1] + 1);
}
}
else if (earlySuccess)
liftBound= newLiftBound;
int i= sizeOfLiftPre - 1;
while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
{
if (newLiftBound >= liftPre[i] + 1)
{
bufUniFactors.insert (LC (A, x));
henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
liftPre[i-1] + 1, Pi, diophant, M, b);
if (v!=alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
liftPre[i-1] + 1, eval, b, den);
else
earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess,
liftPre[i-1] + 1, eval, b, den);
}
else
extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, liftPre[i-1] + 1);
}
else
{
liftBound= newLiftBound;
break;
}
i--;
}
if (earlySuccess)
liftBound= newLiftBound;
//after here all factors are lifted to liftPre[sizeOfLiftPre-1]
}
else
{
henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M, b, true);
if (mipoHasDen)
{
for (CFListIterator iter= bufUniFactors; iter.hasItem(); iter++)
if (hasFirstAlgVar (iter.getItem(), v))
break;
if (v != alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
A= replacevar (A, alpha, v);
}
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
smallFactorDeg, eval, b, den);
else
earlyFactorDetection (earlyFactors, bufA, bufBufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess,
smallFactorDeg, eval, b, den);
}
else
extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, smallFactorDeg);
int i= 1;
while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
i++;
dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
{
bufUniFactors.insert (LC (A, x));
henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
dummy, Pi, diophant, M, b);
if (v!=alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, dummy,eval,
b, den);
else
earlyFactorDetection (earlyFactors, bufA,bufBufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, dummy,eval,
b, den);
}
else
extEarlyFactorDetection (earlyFactors, bufA,bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, dummy);
}
while (degs.getLength() > 1 && !earlySuccess && i < 4)
{
if (newLiftBound >= dummy)
{
bufUniFactors.insert (LC (A, x));
dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
dummy, Pi, diophant, M, b);
if (v!=alpha)
{
bufBufUniFactors= bufUniFactors;
for (CFListIterator iter= bufBufUniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), v, alpha);
}
if (!extension)
{
if (v==alpha)
earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
factorsFoundIndex, degs, earlySuccess, dummy,
eval, b, den);
else
earlyFactorDetection (earlyFactors,bufA,bufBufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess, dummy,
eval, b, den);
}
else
extEarlyFactorDetection (earlyFactors,bufA,bufUniFactors,newLiftBound,
factorsFoundIndex, degs, earlySuccess, info,
eval, dummy);
}
else
{
liftBound= newLiftBound;
break;
}
i++;
}
if (earlySuccess)
liftBound= newLiftBound;
}
A= bufA;
if (earlyFactors.length() > 0 && degs.getLength() > 1)
{
liftBound= degree (A,y) + 1;
earlySuccess= true;
deleteFactors (bufUniFactors, factorsFoundIndex);
}
delete [] factorsFoundIndex;
delete [] liftPre;
return bufUniFactors;
}
replacevar
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
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
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 test...
Definition facFqBivar.cc:985
deleteFactors
void deleteFactors(CFList &factors, int *factorsFoundIndex)
Definition facFqBivar.cc:1139
getLiftPrecisions
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition facFqBivar.cc:1123
henselLift12
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
Definition facHensel.cc:1274
henselLiftResume12
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
Definition facHensel.cc:1343

## prodMod0()

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

via divide-and-conquer

Returns
  prodMod0 computes the above defined product

See also
  prodMod()

Parameters

  [in] | L | a list of compressed, bivariate polynomials
  [in] | M | a power of Variable (2)
  [in] | b | coeff 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] | A | squarefree univariate poly
  [in] | alpha | algebraic variable
  [in] | GF | GaloisFieldDomain?

Definition at line 163 of file facFqBivar.cc.

{
Variable x= A.mvar();
if (A.inCoeffDomain())
return CFList();
ASSERT (A.isUnivariate(),
"univariate polynomial expected or constant expected");
CFFList factorsA;
if (GF)
{
int k= getGFDegree();
char cGFName= gf_name;
CanonicalForm mipo= gf_mipo;
setCharacteristic (getCharacteristic());
Variable beta= rootOf (mipo.mapinto());
CanonicalForm buf= GF2FalphaRep (A, beta);
#ifdef HAVE_NTL
if (getCharacteristic() > 2)
#else
if (getCharacteristic() > 0)
#endif
{
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
nmod_poly_t FLINTmipo, leadingCoeff;
fq_nmod_ctx_t fq_con;
fq_nmod_poly_t FLINTA;
fq_nmod_poly_factor_t FLINTFactorsA;
nmod_poly_init (FLINTmipo, getCharacteristic());
convertFacCF2nmod_poly_t (FLINTmipo, mipo.mapinto());
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
convertFacCF2Fq_nmod_poly_t (FLINTA, buf, fq_con);
fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
nmod_poly_init (leadingCoeff, getCharacteristic());
fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
beta, fq_con);
fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
fq_nmod_poly_clear (FLINTA, fq_con);
nmod_poly_clear (FLINTmipo);
nmod_poly_clear (leadingCoeff);
fq_nmod_ctx_clear (fq_con);
#else
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char= getCharacteristic();
zz_p::init (getCharacteristic());
}
zz_pX NTLMipo= convertFacCF2NTLzzpX (mipo.mapinto());
zz_pE::init (NTLMipo);
zz_pEX NTLA= convertFacCF2NTLzz_pEX (buf, NTLMipo);
MakeMonic (NTLA);
vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
zz_pE multi= to_zz_pE (1);
factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
x, beta);
#endif
}
#ifdef HAVE_NTL
else
{
GF2X NTLMipo= convertFacCF2NTLGF2X (mipo.mapinto());
GF2E::init (NTLMipo);
GF2EX NTLA= convertFacCF2NTLGF2EX (buf, NTLMipo);
MakeMonic (NTLA);
vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
GF2E multi= to_GF2E (1);
factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
x, beta);
}
#endif
setCharacteristic (getCharacteristic(), k, cGFName);
for (CFFListIterator i= factorsA; i.hasItem(); i++)
{
buf= i.getItem().factor();
buf= Falpha2GFRep (buf);
i.getItem()= CFFactor (buf, i.getItem().exp());
}
prune (beta);
}
else if (alpha.level() != 1)
{
#ifdef HAVE_NTL
if (getCharacteristic() > 2)
#else
if (getCharacteristic() > 0)
#endif
{
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
nmod_poly_t FLINTmipo, leadingCoeff;
fq_nmod_ctx_t fq_con;
fq_nmod_poly_t FLINTA;
fq_nmod_poly_factor_t FLINTFactorsA;
nmod_poly_init (FLINTmipo, getCharacteristic());
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
convertFacCF2Fq_nmod_poly_t (FLINTA, A, fq_con);
fq_nmod_poly_make_monic (FLINTA, FLINTA, fq_con);
fq_nmod_poly_factor_init (FLINTFactorsA, fq_con);
nmod_poly_init (leadingCoeff, getCharacteristic());
fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA, fq_con);
factorsA= convertFLINTFq_nmod_poly_factor2FacCFFList (FLINTFactorsA, x,
alpha, fq_con);
fq_nmod_poly_factor_clear (FLINTFactorsA, fq_con);
fq_nmod_poly_clear (FLINTA, fq_con);
nmod_poly_clear (FLINTmipo);
nmod_poly_clear (leadingCoeff);
fq_nmod_ctx_clear (fq_con);
#else
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char= getCharacteristic();
zz_p::init (getCharacteristic());
}
zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
zz_pE::init (NTLMipo);
zz_pEX NTLA= convertFacCF2NTLzz_pEX (A, NTLMipo);
MakeMonic (NTLA);
vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
zz_pE multi= to_zz_pE (1);
factorsA= convertNTLvec_pair_zzpEX_long2FacCFFList (NTLFactorsA, multi,
x, alpha);
#endif
}
#ifdef HAVE_NTL
else
{
GF2X NTLMipo= convertFacCF2NTLGF2X (getMipo (alpha));
GF2E::init (NTLMipo);
GF2EX NTLA= convertFacCF2NTLGF2EX (A, NTLMipo);
MakeMonic (NTLA);
vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
GF2E multi= to_GF2E (1);
factorsA= convertNTLvec_pair_GF2EX_long2FacCFFList (NTLFactorsA, multi,
x, alpha);
}
#endif
}
else
{
#ifdef HAVE_FLINT
#ifdef HAVE_NTL
if (degree (A) < 300)
#endif
{
nmod_poly_t FLINTA;
convertFacCF2nmod_poly_t (FLINTA, A);
nmod_poly_factor_t result;
nmod_poly_factor_init (result);
mp_limb_t leadingCoeff= nmod_poly_factor (result, FLINTA);
factorsA= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, x);
if (factorsA.getFirst().factor().inCoeffDomain())
factorsA.removeFirst();
nmod_poly_factor_clear (result);
nmod_poly_clear (FLINTA);
}
#ifdef HAVE_NTL
else
#endif
#endif /* HAVE_FLINT */
#ifdef HAVE_NTL
if (getCharacteristic() > 2)
{
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char= getCharacteristic();
zz_p::init (getCharacteristic());
}
zz_pX NTLA= convertFacCF2NTLzzpX (A);
MakeMonic (NTLA);
vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
zz_p multi= to_zz_p (1);
factorsA= convertNTLvec_pair_zzpX_long2FacCFFList (NTLFactorsA, multi,
x);
}
else
{
GF2X NTLA= convertFacCF2NTLGF2X (A);
vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
GF2 multi= to_GF2 (1);
factorsA= convertNTLvec_pair_GF2X_long2FacCFFList (NTLFactorsA, multi,
x);
}
#endif
}
CFList uniFactors;
for (CFFListIterator i= factorsA; i.hasItem(); i++)
uniFactors.append (i.getItem().factor());
return uniFactors;
}
convertFLINTFq_nmod_poly_factor2FacCFFList
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
Definition FLINTconvert.cc:379
convertFacCF2Fq_nmod_poly_t
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
Definition FLINTconvert.cc:526
convertFLINTnmod_poly_factor2FacCFFList
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
Definition FLINTconvert.cc:337
convertNTLvec_pair_GF2X_long2FacCFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition NTLconvert.cc:446
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition NTLconvert.cc:1064
convertNTLvec_pair_zzpEX_long2FacCFFList
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition NTLconvert.cc:870
convertNTLvec_pair_GF2EX_long2FacCFFList
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition NTLconvert.cc:959
convertNTLvec_pair_zzpX_long2FacCFFList
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition NTLconvert.cc:399
convertFacCF2NTLGF2EX
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition NTLconvert.cc:1007
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
convertFacCF2NTLGF2X
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition NTLconvert.cc:184
fq_con
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)