Loading...
Searching...
No Matches
facFqFactorize.cc File Reference

This file implements functions for factoring a multivariate polynomial over a finite field. More...

`#include "config.h"`
`#include <math.h>`
`#include "cf_assert.h"`
`#include "debug.h"`
`#include "timing.h"`
`#include "facFqFactorizeUtil.h"`
`#include "facFqFactorize.h"`
`#include "cf_random.h"`
`#include "facHensel.h"`
`#include "cf_irred.h"`
`#include "cf_map_ext.h"`
`#include "facSparseHensel.h"`
`#include "facMul.h"`
`#include "cfUnivarGcd.h"`

Go to the source code of this file.

## Macros

#define | CHAR_THRESHOLD 8

## Functions

TIMING_DEFINE_PRINT (fac_fq_bi_factorizer) TIMING_DEFINE_PRINT(fac_fq_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_fq_evaluation) TIMING_DEFINE_PRINT(fac_fq_recover_factors) TIMING_DEFINE_PRINT(fac_fq_preprocess_and_content) TIMING_DEFINE_PRINT(fac_fq_bifactor_total) TIMING_DEFINE_PRINT(fac_fq_luckswang) TIMING_DEFINE_PRINT(fac_fq_lcheuristic) TIMING_DEFINE_PRINT(fac_fq_content) TIMING_DEFINE_PRINT(fac_fq_check_mainvar) TIMING_DEFINE_PRINT(fac_fq_compress) static inline CanonicalForm listGCD(const CFList &L)

static CanonicalForm | myContent (const CanonicalForm &F)
static CanonicalForm | listGCD (const CFList &L)
static CanonicalForm | myContent (const CanonicalForm &F, const Variable &x)
CanonicalForm | myCompress (const CanonicalForm &F, CFMap &N)
| compress a polynomial s.t. and no gaps between the variables occur
CFList | extFactorRecombination (const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
| Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations.
CFList | factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M)
| Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.
int | liftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
| Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
int | extLiftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
| Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted.
CFList | earlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
| detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
CFList | extEarlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
| detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
CFList | evalPoints (const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)

evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials.

static int | newMainVariableSearch (CanonicalForm &A, CFList &Aeval, CFList &evaluation, const Variable &alpha, const int lev, CanonicalForm &g)
CanonicalForm | lcmContent (const CanonicalForm &A, CFList &contentAi)
| compute the LCM of the contents of A wrt to each variable occuring in A.
CFList | henselLiftAndEarly (CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
| hensel Lifting and early factor detection
void | gcdFreeBasis (CFFList &factors1, CFFList &factors2)
| gcd free basis of two lists of factors
CFList | distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length)
| distribute content
int | testFactors (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CFList | precomputeLeadingCoeff (const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
| computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
void | evaluationWRTDifferentSecondVars (CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
| evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty
static CanonicalForm | prodEval (const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
void | checkHelper (const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
CFList | checkOneToOne (const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
| check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly.
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 factors2
void | factorizationWRTDifferentSecondVars (const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
CFList | conv (const CFArray &A)
void | getLeadingCoeffs (const CanonicalForm &A, CFList *&Aeval)
| extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables
void | sortByUniFactors (CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
| sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary
CFList | buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
| plug in evalPoint for y in a list of polys
void | refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
| refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
void | prepareLeadingCoeffs (CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
| normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly
CFList | extNonMonicFactorRecombination (const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
void | changeSecondVariable (CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
| changes the second variable to be w and updates all relevant data
void | distributeLCmultiplier (CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
| distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients
void | LCHeuristic (CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
| heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors
void | LCHeuristicCheck (const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
| checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
void | LCHeuristic2 (const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
| heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
void | LCHeuristic3 (const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
| heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic.
void | LCHeuristic4 (const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
| heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful.
CFList | extFactorize (const CanonicalForm &F, const ExtensionInfo &info)
| multivariate factorization over an extension of the initial field
CFList | multiFactorize (const CanonicalForm &F, const ExtensionInfo &info)

## Detailed Description

This file implements functions for factoring a multivariate polynomial over a finite field.

ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by L. Bernardin & M. Monagon. Precomputation of leading coefficients is described in "Sparse Hensel lifting" by E. Kaltofen

Author
  Martin Lee

Definition in file facFqFactorize.cc.

## Macro Definition Documentation

## CHAR_THRESHOLD

#define CHAR_THRESHOLD 8

Definition at line 749 of file facFqFactorize.cc.

## Function Documentation

## buildUniFactors()

CFList buildUniFactors | ( | const CFList & | biFactors,
|  | const CanonicalForm & | evalPoint,
|  | const Variable & | y )

plug in evalPoint for y in a list of polys

Returns
  returns a list of the evaluated polys, these evaluated polys are made monic

Parameters

  [in] | biFactors | a list of polys
  [in] | evalPoint | some evaluation point
  [in] | y | some variable

Definition at line 2321 of file facFqFactorize.cc.

{
CFList result;
CanonicalForm tmp;
for (CFListIterator i= biFactors; i.hasItem(); i++)
{
tmp= mod (i.getItem(), y - evalPoint);
tmp /= Lc (tmp);
result.append (tmp);
}
return result;
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
i
int i
Definition cfEzgcd.cc:132
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition cfModResultant.cc:311
CanonicalForm
factory's main class
Definition canonicalform.h:86
result
return result
Definition facAbsBiFact.cc:76
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

## changeSecondVariable()

void changeSecondVariable | ( | CanonicalForm & | A,
|  | CFList & | biFactors,
|  | CFList & | evaluation,
|  | CFList *& | oldAeval,
|  | int | lengthAeval2,
|  | const CFList & | uniFactors,
|  | const Variable & | w )

changes the second variable to be w and updates all relevant data

Parameters

  [in,out] | A | a multivariate poly
  [in,out] | biFactors | bivariate factors
  [in,out] | evaluation | evaluation point
  [in,out] | oldAeval | old bivariate factors wrt. different second vars
  [in] | lengthAeval2 | length of oldAeval
  [in] | uniFactors | univariate factors
  [in] | w | some variable

Definition at line 2544 of file facFqFactorize.cc.

{
Variable y= Variable (2);
A= swapvar (A, y, w);
int i= A.level();
CanonicalForm evalPoint;
for (CFListIterator iter= evaluation; iter.hasItem(); iter++, i--)
{
if (i == w.level())
{
evalPoint= iter.getItem();
iter.getItem()= evaluation.getLast();
evaluation.removeLast();
evaluation.append (evalPoint);
break;
}
}
for (i= 0; i < lengthAeval2; i++)
{
if (oldAeval[i].isEmpty())
continue;
if (oldAeval[i].getFirst().level() == w.level())
{
CFArray tmp= copy (oldAeval[i]);
oldAeval[i]= biFactors;
for (CFListIterator iter= oldAeval[i]; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), w, y);
for (int ii= 0; ii < tmp.size(); ii++)
tmp[ii]= swapvar (tmp[ii], w, y);
CFArray tmp2= CFArray (tmp.size());
CanonicalForm buf;
for (int ii= 0; ii < tmp.size(); ii++)
{
buf= tmp[ii] (evaluation.getLast(),y);
buf /= Lc (buf);
tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
}
biFactors= CFList();
for (int j= 0; j < tmp2.size(); j++)
biFactors.append (tmp2[j]);
}
}
}
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
Array::size
int size() const
Definition ftmpl_array.cc:92
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
w
const CanonicalForm & w
Definition facAbsFact.cc:51
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
tmp2
CFList tmp2
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110
buf
int status int void * buf
Definition si_signals.h:69
A
#define A
Definition sirandom.c:24

## checkHelper()

void checkHelper | ( | const CanonicalForm & | f1,
|  | CFList & | factors1,
|  | CFList & | factors2,
|  | CFList & | l1,
|  | CFList & | l2 )

Definition at line 2022 of file facFqFactorize.cc.

{
CanonicalForm g1= f1, g2;
CFListIterator iter1= factors1, iter2= factors2;
for (; iter1.hasItem(); iter1++, iter2++)
{
g2= gcd (g1, iter1.getItem());
if (!g2.inCoeffDomain())
{
l1.append (iter1.getItem());
l2.append (iter2.getItem());
g1 /= g2;
}
}
factors1= Difference (factors1, l1);
factors2= Difference (factors2, l2);
}
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## checkOneToOne()

CFList checkOneToOne | ( | const CFList & | factors1,
|  | const CFList & | factors2,
|  | CFList & | factors3,
|  | const CanonicalForm & | evalPoint,
|  | const Variable & | x )

check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and recombine if necessary. The recombined factors of factors1 are returned and factors3 is recombined accordingly.

Definition at line 2046 of file facFqFactorize.cc.

{
CFList uniFactorsOfFactors1;
CFList result, result2;
CFList bad1= factors2;
CFListIterator iter, iter2, iter3;
CanonicalForm tmp;
int pos;
for (iter= factors1; iter.hasItem(); iter++)
{
tmp= iter.getItem() (evalPoint, x);
tmp /= Lc (tmp);
if ((pos= findItem (factors2, tmp)))
{
result2.append (getItem (factors3, pos));
result.append (iter.getItem());
bad1= Difference (bad1, CFList (tmp));
}
else
uniFactorsOfFactors1.append (tmp);
}
CFList bad2, bad3;
bad2= Difference (factors1, result);
bad3= Difference (factors3, result2);
CFList tmp2, tmp3;
CanonicalForm g1, g2, g3, g4;
while (!uniFactorsOfFactors1.isEmpty())
{
tmp= uniFactorsOfFactors1.getFirst();
checkHelper (tmp, bad1, bad3, tmp2, tmp3);
g1= prod (tmp2);
g2= prod (tmp3);
tmp2= CFList();
tmp3= CFList();
checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
g3= prod (tmp2);
g4= prod (tmp3);
tmp2= CFList();
tmp3= CFList();
do
{
checkHelper (g3, bad1, bad3, tmp2, tmp3);
g1 *= prod (tmp2);
g2 *= prod (tmp3);
tmp2= CFList();
tmp3= CFList();
checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
g3 *= prod (tmp2);
g4 *= prod (tmp3);
tmp2= CFList();
tmp3= CFList();
} while (!bad2.isEmpty() && !bad3.isEmpty());
result.append (g4);
result2.append (g2);
}
if (factors3.length() != result2.length())
factors3= result2;
return result;
}
x
Variable x
Definition cfModGcd.cc:4090
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::length
int length() const
Definition ftmpl_list.cc:273
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
checkHelper
void checkHelper(const CanonicalForm &f1, CFList &factors1, CFList &factors2, CFList &l1, CFList &l2)
Definition facFqFactorize.cc:2022
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100

## conv()

CFList conv | ( | const CFArray & | A | ) |

Definition at line 2224 of file facFqFactorize.cc.

{
CFList result;
for (int i= A.max(); i >= A.min(); i--)
result.insert (A[i]);
return result;
}

## distributeContent()

CFList distributeContent | ( | const CFList & | L,
|  | const CFList * | differentSecondVarFactors,
|  | int | length )

distribute content

Returns
  returns a list result of polys such that prod (result)= prod (L) but the first entry of L may be (partially) factorized and these factors are distributed onto other entries in L

Parameters

  [in] | L | list of polys, first entry the content to be distributed
  [in] | differentSecondVarFactors | factorization wrt different second vars
  [in] | length | length ofdifferentSecondVarFactors

Definition at line 1295 of file facFqFactorize.cc.

{
CFList l= L;
CanonicalForm content= l.getFirst();
if (content.inCoeffDomain())
return l;
if (l.length() == 1)
{
CFList result;
for (int i= 0; i < length; i++)
{
if (differentSecondVarFactors[i].isEmpty())
continue;
if (result.isEmpty())
{
result= differentSecondVarFactors[i];
for (CFListIterator iter= result; iter.hasItem(); iter++)
content /= iter.getItem();
}
else
{
CFListIterator iter1= result;
for (CFListIterator iter2= differentSecondVarFactors[i];iter2.hasItem();
iter2++, iter1++)
{
iter1.getItem() *= iter2.getItem();
content /= iter2.getItem();
}
}
}
result.insert (content);
return result;
}
Variable v;
CFListIterator iter1, iter2;
CanonicalForm tmp, g;
CFList multiplier;
for (int i= 0; i < length; i++)
{
if (differentSecondVarFactors[i].isEmpty())
continue;
iter1= l;
iter1++;
tmp= 1;
for (iter2= differentSecondVarFactors[i]; iter2.hasItem();
iter2++, iter1++)
{
if (iter2.getItem().inCoeffDomain())
{
multiplier.append (1);
continue;
}
v= iter2.getItem().mvar();
if (degree (iter2.getItem()) == degree (iter1.getItem(),v))
{
multiplier.append (1);
continue;
}
g= gcd (iter2.getItem(), content);
if (!g.inCoeffDomain())
{
tmp *= g;
multiplier.append (g);
}
else
multiplier.append (1);
}
if (!tmp.isOne() && fdivides (tmp, content))
{
iter1= l;
iter1++;
content /= tmp;
for (iter2= multiplier; iter2.hasItem(); iter1++, iter2++)
iter1.getItem() *= iter2.getItem();
}
multiplier= CFList();
}
l.removeFirst();
l.insert (content);
return l;
}
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
l
int l
Definition cfEzgcd.cc:100
g
g
Definition cfModGcd.cc:4098
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
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257

## distributeLCmultiplier()

void distributeLCmultiplier | ( | CanonicalForm & | A,
|  | CFList & | leadingCoeffs,
|  | CFList & | biFactors,
|  | const CFList & | evaluation,
|  | const CanonicalForm & | LCmultipler )

distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients

Parameters

  [in,out] | A | some poly
  [in,out] | leadingCoeffs | leading coefficients
  [in,out] | biFactors | bivariate factors
  [in] | evaluation | eval. point
  [in] | LCmultipler | multiplier

Definition at line 2591 of file facFqFactorize.cc.

{
CanonicalForm tmp= power (LCmultipler, biFactors.length() - 1);
A *= tmp;
tmp= LCmultipler;
CFListIterator iter= leadingCoeffs;
for (;iter.hasItem(); iter++)
iter.getItem() *= LCmultipler;
iter= evaluation;
for (int i= A.level(); i > 2; i--, iter++)
tmp= tmp (iter.getItem(), i);
if (!tmp.inCoeffDomain())
{
for (CFListIterator i= biFactors; i.hasItem(); i++)
{
i.getItem() *= tmp/LC (i.getItem(), 1);
i.getItem() /= Lc (i.getItem());
}
}
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310

## earlyFactorDetect()

CFList earlyFactorDetect | ( | CanonicalForm & | F,
|  | CFList & | factors,
|  | int & | adaptedLiftBound,
|  | bool & | success,
|  | const int | deg,
|  | const CFList & | MOD,
|  | const int | bound )

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.

Returns
  earlyFactorDetect returns a list of factors of F (possibly incomplete), in case of success. Otherwise an empty list.

See also
  factorRecombination(), extEarlyFactorDetect()

Parameters

  [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] | success | indicating success
  [in] | deg | stage of Hensel lifting
  [in] | MOD | a list of powers of Variables
  [in] | bound | initial lift bound

Definition at line 612 of file facFqFactorize.cc.

{
CFList result;
CFList T= factors;
CanonicalForm buf= F;
Variable y= F.mvar();
Variable x= Variable (1);
CanonicalForm LCBuf= LC (buf, x);
CanonicalForm g, quot;
CFList M= MOD;
M.append (power (y, deg));
adaptedLiftBound= 0;
int d= bound;
int e= 0;
int nBuf;
for (CFListIterator i= factors; i.hasItem(); i++)
{
g= mulMod (i.getItem(), LCBuf, M);
g /= myContent (g);
if (fdivides (g, buf, quot))
{
result.append (g);
nBuf= degree (g, y) + degree (LC (g, x), y);
d -= nBuf;
e= tmax (e, nBuf);
buf= quot;
LCBuf= LC (buf, x);
T= Difference (T, CFList (i.getItem()));
}
}
adaptedLiftBound= d;
if (adaptedLiftBound < deg)
{
if (adaptedLiftBound < degree (F) + 1)
{
if (d == 1)
adaptedLiftBound= tmin (e + 1, deg);
else
adaptedLiftBound= deg;
}
factors= T;
F= buf;
success= true;
}
return result;
}
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
myContent
static CanonicalForm myContent(const CanonicalForm &F)
Definition facFqFactorize.cc:59
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition facMul.cc:3086
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
T
STATIC_VAR jList * T
Definition janet.cc:30
M
#define M
Definition sirandom.c:25

## evalPoints()

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

evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials.

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

Parameters

  [in] | F | a compressed poly
  [in,out] | eval | an empty list, returns F successive evaluated
  [in] | alpha | algebraic variable
  [in,out] | list | a list of points already considered, a point is encoded as a poly of degree F.level()-1 in Variable(1)
  [in] | GF | GF?
  [in,out] | fail | indicates failure

Definition at line 751 of file facFqFactorize.cc.

{
int k= F.level() - 1;
Variable x= Variable (1);
CanonicalForm LCF=LC (F, x);
CFList LCFeval;
CFList result;
FFRandom genFF;
GFRandom genGF;
int p= getCharacteristic ();
if (p < CHAR_THRESHOLD)
{
if (!GF && alpha.level() == 1)
{
fail= true;
return CFList();
}
else if (!GF && alpha.level() != 1)
{
if ((p == 2 && degree (getMipo (alpha)) < 6) ||
(p == 3 && degree (getMipo (alpha)) < 4) ||
(p == 5 && degree (getMipo (alpha)) < 3))
{
fail= true;
return CFList();
}
}
}
double bound;
if (alpha != x)
{
bound= pow ((double) p, (double) degree (getMipo(alpha)));
bound *= (double) k;
}
else if (GF)
{
bound= pow ((double) p, (double) getGFDegree());
bound *= (double) k;
}
else
bound= pow ((double) p, (double) k);
CanonicalForm random;
CanonicalForm deriv_x, gcd_deriv;
do
{
random= 0;
// possible overflow if list.length() does not fit into a int
if (list.length() >= bound)
{
fail= true;
break;
}
for (int i= 0; i < k; i++)
{
if (list.isEmpty())
result.append (0);
else if (GF)
{
result.append (genGF.generate());
random += result.getLast()*power (x, i);
}
else if (alpha.level() != 1)
{
AlgExtRandomF genAlgExt (alpha);
result.append (genAlgExt.generate());
random += result.getLast()*power (x, i);
}
else
{
result.append (genFF.generate());
random += result.getLast()*power (x, i);
}
}
if (find (list, random))
{
result= CFList();
continue;
}
int l= F.level();
eval.insert (F);
LCFeval.insert (LCF);
bool bad= false;
for (CFListIterator i= result; i.hasItem(); i++, l--)
{
eval.insert (eval.getFirst()(i.getItem(), l));
LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
{
if (!find (list, random))
list.append (random);
result= CFList();
eval= CFList();
LCFeval= CFList();
bad= true;
break;
}
if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
{
if (!find (list, random))
list.append (random);
result= CFList();
eval= CFList();
LCFeval= CFList();
bad= true;
break;
}
}
if (bad)
continue;
if (degree (eval.getFirst()) != degree (F, 1))
{
if (!find (list, random))
list.append (random);
result= CFList();
LCFeval= CFList();
eval= CFList();
continue;
}
deriv_x= deriv (eval.getFirst(), x);
gcd_deriv= gcd (eval.getFirst(), deriv_x);
if (degree (gcd_deriv) > 0)
{
if (!find (list, random))
list.append (random);
result= CFList();
LCFeval= CFList();
eval= CFList();
continue;
}
CFListIterator i= eval;
i++;
CanonicalForm contentx= content (i.getItem(), x);
if (degree (contentx) > 0)
{
if (!find (list, random))
list.append (random);
result= CFList();
LCFeval= CFList();
eval= CFList();
continue;
}
contentx= content (i.getItem());
if (degree (contentx) > 0)
{
if (!find (list, random))
list.append (random);
result= CFList();
LCFeval= CFList();
eval= CFList();
continue;
}
if (list.length() >= bound)
{
fail= true;
break;
}
} while (find (list, random));
if (!eval.isEmpty())
eval.removeFirst();
return result;
}
pow
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
AlgExtRandomF
generate random elements in F_p(alpha)
Definition cf_random.h:70
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
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
alpha
Variable alpha
Definition facAbsBiFact.cc:52
contentx
CanonicalForm contentx
Definition facFactorize.cc:128
gcd_deriv
CanonicalForm gcd_deriv
Definition facFactorize.cc:58
LCFeval
CFList LCFeval
Definition facFactorize.cc:53
LCF
CanonicalForm LCF
Definition facFactorize.cc:52
deriv_x
CanonicalForm deriv_x
Definition facFactorize.cc:58
bad
bool bad
Definition facFactorize.cc:64
eval
CFList & eval
Definition facFactorize.cc:47
CHAR_THRESHOLD
#define CHAR_THRESHOLD
Definition facFqFactorize.cc:749
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)

## evaluationWRTDifferentSecondVars()

void evaluationWRTDifferentSecondVars | ( | CFList *& | Aeval,
|  | const CFList & | evaluation,
|  | const CanonicalForm & | A )

evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty

Parameters

  [in,out] | Aeval | an array of length n-2 if variable at level i > 2 admits a valid evaluation this entry contains A successively evaluated at this point otherwise an empty list
  [in] | evaluation | a valid evaluation point for main variable at level 1 and second variable at level 2
  [in] | A | some poly

Definition at line 1966 of file facFqFactorize.cc.

{
CanonicalForm tmp;
CFList tmp2;
CFListIterator iter;
bool preserveDegree= true;
Variable x= Variable (1);
int j, degAi, degA1= degree (A,1);
for (int i= A.level(); i > 2; i--)
{
tmp= A;
tmp2= CFList();
iter= evaluation;
preserveDegree= true;
degAi= degree (A,i);
for (j= A.level(); j > 1; j--, iter++)
{
if (j == i)
continue;
else
{
tmp= tmp (iter.getItem(), j);
tmp2.insert (tmp);
if ((degree (tmp, i) != degAi) ||
(degree (tmp, 1) != degA1))
{
preserveDegree= false;
break;
}
}
}
if (!content(tmp,1).inCoeffDomain())
preserveDegree= false;
if (!content(tmp).inCoeffDomain())
preserveDegree= false;
if (!(gcd (deriv (tmp,x), tmp)).inCoeffDomain())
preserveDegree= false;
if (preserveDegree)
Aeval [i - 3]= tmp2;
else
Aeval [i - 3]= CFList();
}
}
Aeval
CFList *& Aeval
<[in] poly
Definition facFactorize.h:31

## extEarlyFactorDetect()

CFList extEarlyFactorDetect | ( | CanonicalForm & | F,
|  | CFList & | factors,
|  | int & | adaptedLiftBound,
|  | bool & | success,
|  | const ExtensionInfo & | info,
|  | const CFList & | eval,
|  | const int | deg,
|  | const CFList & | MOD,
|  | const int | bound )

detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.

Returns
  extEarlyFactorDetect returns a list of factors of F (possibly incomplete), whose shift to zero is reversed, in case of success. Otherwise an empty list.

See also
  factorRecombination(), earlyFactorDetection()

Parameters

  [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] | success | indicating succes
  [in] | info | info about extension
  [in] | eval | evaluation point
  [in] | deg | stage of Hensel lifting
  [in] | MOD | a list of powers of Variables
  [in] | bound | initial lift bound

Definition at line 665 of file facFqFactorize.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
CFList result;
CFList T= factors;
CanonicalForm buf= F;
Variable y= F.mvar();
Variable x= Variable (1);
CanonicalForm LCBuf= LC (buf, x);
CanonicalForm g, gg, quot;
CFList M= MOD;
M.append (power (y, deg));
adaptedLiftBound= 0;
int d= bound;
int e= 0;
int nBuf;
CFList source, dest;
int degMipoBeta= 1;
if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
for (CFListIterator i= factors; i.hasItem(); i++)
{
g= mulMod (i.getItem(), LCBuf, M);
g /= myContent (g);
if (fdivides (g, buf, quot))
{
gg= reverseShift (g, eval);
gg /= Lc (gg);
if (!k && beta == x)
{
if (degree (gg, alpha) < degMipoBeta)
{
appendTestMapDown (result, gg, info, source, dest);
buf= quot;
nBuf= degree (g, y) + degree (LC (g, x), y);
d -= nBuf;
e= tmax (e, nBuf);
LCBuf= LC (buf, x);
T= Difference (T, CFList (i.getItem()));
}
}
else
{
if (!isInExtension (gg, gamma, k, delta, source, dest))
{
appendTestMapDown (result, gg, info, source, dest);
buf= quot;
nBuf= degree (g, y) + degree (LC (g, x), y);
d -= nBuf;
e= tmax (e, nBuf);
LCBuf= LC (buf, x);
T= Difference (T, CFList (i.getItem()));
}
}
}
}
adaptedLiftBound= d;
if (adaptedLiftBound < deg)
{
if (adaptedLiftBound < degree (F) + 1)
{
if (d == 1)
adaptedLiftBound= tmin (e + 1, deg);
else
adaptedLiftBound= deg;
}
success= true;
factors= T;
F= buf;
}
return result;
}
beta
Variable beta
Definition facAbsFact.cc:95
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
reverseShift
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Definition facFqFactorizeUtil.cc:148
info
#define info
Definition libparse.cc:1256
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160

## extFactorize()

CFList extFactorize | ( | const CanonicalForm & | F,
|  | const ExtensionInfo & | info )

multivariate factorization over an extension of the initial field

Factorization over an extension of initial field.

Parameters

  [in] | F | poly to be factored
  [in] | info | info about extension

Definition at line 3661 of file facFqFactorize.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 w= Variable (1);
CFList factors;
if (!GF && alpha == w) // we are in F_p
{
CFList factors;
bool extension= true;
int p= getCharacteristic();
if (p < 7)
{
if (p == 2)
setCharacteristic (getCharacteristic(), 6, 'Z');
else if (p == 3)
setCharacteristic (getCharacteristic(), 4, 'Z');
else if (p == 5)
setCharacteristic (getCharacteristic(), 3, 'Z');
ExtensionInfo info= ExtensionInfo (extension);
A= A.mapinto();
factors= multiFactorize (A, info);
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 if (p >= 7 && p*p < (1<<16)) // pass to GF if possible
{
setCharacteristic (getCharacteristic(), 2, 'Z');
ExtensionInfo info= ExtensionInfo (extension);
A= A.mapinto();
factors= multiFactorize (A, info);
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, w);
Variable v= rootOf (mipo);
ExtensionInfo info= ExtensionInfo (v);
factors= multiFactorize (A, info);
prune (v);
}
return factors;
}
else if (!GF && (alpha != w)) // we are in F_p(\alpha)
{
if (k == 1) // need factorization over F_p
{
int extDeg= degree (getMipo (alpha));
extDeg++;
CanonicalForm mipo= randomIrredpoly (extDeg, w);
Variable v= rootOf (mipo);
ExtensionInfo info= ExtensionInfo (v);
factors= multiFactorize (A, info);
prune (v);
}
else
{
if (beta == w)
{
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 info= ExtensionInfo (v, alpha, imPrimElem, primElem);
factors= multiFactorize (bufA, info);
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 info= ExtensionInfo (v, beta, imPrimElem, delta);
factors= multiFactorize (bufA, info);
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 (pow ((double) p, (double) 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 info= ExtensionInfo (extension);
factors= multiFactorize (A.mapinto(), info);
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 info= ExtensionInfo (v, extension);
factors= multiFactorize (A, info);
prune (vBuf);
}
}
else // need factorization over GF (p^k)
{
if (pow ((double) p, (double) 2*extensionDeg) < (1<<16))
// pass to GF(p^2k)
{
setCharacteristic (p, 2*extensionDeg, 'Z');
ExtensionInfo info= ExtensionInfo (k, cGFName, extension);
factors= multiFactorize (GFMapUp (A, extensionDeg), info);
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, v1, primFail);
if (primFail)
; //ERROR
else
imPrimElem= mapPrimElem (primElem, v1, v2);
CFList source, dest;
CanonicalForm bufA= mapUp (A, v1, v2, primElem, imPrimElem,
source, dest);
ExtensionInfo info= ExtensionInfo (v2, v1, imPrimElem, primElem);
factors= multiFactorize (bufA, info);
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
chooseExtension
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:421
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
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
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
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
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Definition facFqFactorize.cc:2929
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
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
gf_mipo
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56

## extFactorRecombination()

CFList extFactorRecombination | ( | const CFList & | factors,
|  | const CanonicalForm & | F,
|  | const CFList & | M,
|  | const ExtensionInfo & | info,
|  | const CFList & | evaluation )

Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations.

Returns
  extFactorRecombination returns a list of factors of F, whose shift to zero is reversed.

See also
  factorRecombination()

Parameters

  [in] | factors | list of lifted factors that are monic wrt Variable (1)
  [in] | F | poly to be factored
  [in] | M | a list of powers of Variables
  [in] | info | info about extension
  [in] | evaluation | evaluation point

Definition at line 216 of file facFqFactorize.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
CFList source, dest;
if (factors.length() == 1)
{
CanonicalForm buf= reverseShift (F, evaluation);
return CFList (mapDown (buf, info, source, dest));
}
if (factors.length() < 1)
return CFList();
int degMipoBeta= 1;
if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
CFList T, S;
T= factors;
int s= 1;
CFList result;
CanonicalForm buf;
buf= F;
Variable x= Variable (1);
CanonicalForm g, LCBuf= LC (buf, x);
CanonicalForm buf2, quot;
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
bool noSubset= false;
CFArray TT;
TT= copy (factors);
bool recombination= false;
bool trueFactor= false;
while (T.length() >= 2*s)
{
while (noSubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombination)
{
T.insert (LCBuf);
g= prodMod (T, M);
T.removeFirst();
result.append (g/myContent (g));
g= reverseShift (g, evaluation);
g /= Lc (g);
appendTestMapDown (result, g, info, source, dest);
return result;
}
else
{
buf= reverseShift (buf, evaluation);
return CFList (buf);
}
}
S= subset (v, s, TT, noSubset);
if (noSubset) break;
S.insert (LCBuf);
g= prodMod (S, M);
S.removeFirst();
g /= myContent (g);
if (fdivides (g, buf, quot))
{
buf2= reverseShift (g, evaluation);
buf2 /= Lc (buf2);
if (!k && beta == x)
{
if (degree (buf2, alpha) < degMipoBeta)
{
appendTestMapDown (result, buf2, info, source, dest);
buf= quot;
LCBuf= LC (buf, x);
recombination= true;
trueFactor= true;
}
}
else
{
if (!isInExtension (buf2, gamma, k, delta, source, dest))
{
appendTestMapDown (result, buf2, info, source, dest);
buf /= g;
LCBuf= LC (buf, x);
recombination= true;
trueFactor= true;
}
}
if (trueFactor)
{
T= Difference (T, S);
if (T.length() < 2*s || T.length() == s)
{
buf= reverseShift (buf, evaluation);
buf /= Lc (buf);
appendTestMapDown (result, buf, info, source, dest);
delete [] v;
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)
{
buf= reverseShift (buf, evaluation);
appendTestMapDown (result, buf, info, source, dest);
delete [] v;
return result;
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
noSubset= false;
}
if (T.length() < 2*s)
{
buf= reverseShift (F, evaluation);
appendMapDown (result, buf, info, source, dest);
}
delete [] v;
return result;
}
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
s
const CanonicalForm int s
Definition facAbsFact.cc:51
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition facFqBivarUtil.cc:373
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
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
buf2
CanonicalForm buf2
Definition facFqBivar.cc:76
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

## extLiftBoundAdaption()

int extLiftBoundAdaption | ( | const CanonicalForm & | F,
|  | const CFList & | factors,
|  | bool & | success,
|  | const ExtensionInfo & | info,
|  | const CFList & | eval,
|  | const int | deg,
|  | const CFList & | MOD,
|  | const int | bound )

Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted.

Returns
  liftBoundAdaption returns an adapted lift bound.

See also
  earlyFactorDetect(), earlyFactorDetection()

Parameters

  [in] | F | a poly
  [in] | factors | list of list of lifted factors that are monic wrt
  [in,out] | success | indicates that no further lifting is necessary
  [in] | info | info about extension
  [in] | eval | evaluation point
  [in] | deg | stage of Hensel lifting
  [in] | MOD | a list of powers of Variables
  [in] | bound | initial lift bound

Definition at line 514 of file facFqFactorize.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
int adaptedLiftBound= 0;
CanonicalForm buf= F;
Variable y= F.mvar();
Variable x= Variable (1);
CanonicalForm LCBuf= LC (buf, x);
CanonicalForm g, gg, quot;
CFList M= MOD;
M.append (power (y, deg));
adaptedLiftBound= 0;
int d= bound;
int e= 0;
int nBuf;
int degMipoBeta= 1;
if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
CFList source, dest;
for (CFListIterator i= factors; i.hasItem(); i++)
{
g= mulMod (i.getItem(), LCBuf, M);
g /= myContent (g);
if (fdivides (g, buf, quot))
{
gg= reverseShift (g, eval);
gg /= Lc (gg);
if (!k && beta == x)
{
if (degree (gg, alpha) < degMipoBeta)
{
buf= quot;
nBuf= degree (g, y) + degree (LC (g, x), y);
d -= nBuf;
e= tmax (e, nBuf);
LCBuf= LC (buf, x);
}
}
else
{
if (!isInExtension (gg, gamma, k, delta, source, dest))
{
buf= quot;
nBuf= degree (g, y) + degree (LC (g, x), y);
d -= nBuf;
e= tmax (e, nBuf);
LCBuf= LC (buf, x);
}
}
}
}
adaptedLiftBound= d;
if (adaptedLiftBound < deg)
{
if (adaptedLiftBound < degree (F) + 1)
{
if (d == 1)
{
if (e + 1 > deg)
{
adaptedLiftBound= deg;
success= false;
}
else
{
success= true;
if (e + 1 < degree (F) + 1)
adaptedLiftBound= deg;
else
adaptedLiftBound= e + 1;
}
}
else
{
success= true;
adaptedLiftBound= deg;
}
}
else
{
success= true;
}
}
return adaptedLiftBound;
}

## extNonMonicFactorRecombination()

CFList extNonMonicFactorRecombination | ( | const CFList & | factors,
|  | const CanonicalForm & | F,
|  | const ExtensionInfo & | info )

Definition at line 2421 of file facFqFactorize.cc.

{
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
int k= info.getGFDegree();
CFList source, dest;
int degMipoBeta= 1;
if (!k && beta != Variable(1))
degMipoBeta= degree (getMipo (beta));
CFList T, S;
T= factors;
int s= 1;
CFList result;
CanonicalForm quot, buf= F;
CanonicalForm g;
CanonicalForm buf2;
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
bool noSubset= false;
CFArray TT;
TT= copy (factors);
bool recombination= false;
bool trueFactor= false;
while (T.length() >= 2*s)
{
while (noSubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombination)
{
g= prod (T);
T.removeFirst();
g /= myContent (g);
g /= Lc (g);
appendTestMapDown (result, g, info, source, dest);
return result;
}
else
return CFList (buf/myContent(buf));
}
S= subset (v, s, TT, noSubset);
if (noSubset) break;
g= prod (S);
g /= myContent (g);
if (fdivides (g, buf, quot))
{
buf2= g;
buf2 /= Lc (buf2);
if (!k && beta.level() == 1)
{
if (degree (buf2, alpha) < degMipoBeta)
{
appendTestMapDown (result, buf2, info, source, dest);
buf= quot;
recombination= true;
trueFactor= true;
}
}
else
{
if (!isInExtension (buf2, gamma, k, delta, source, dest))
{
appendTestMapDown (result, buf2, info, source, dest);
buf= quot;
recombination= true;
trueFactor= true;
}
}
if (trueFactor)
{
T= Difference (T, S);
if (T.length() < 2*s || T.length() == s)
{
delete [] v;
buf /= myContent (buf);
buf /= Lc (buf);
appendTestMapDown (result, buf, info, source, dest);
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;
buf /= myContent (buf);
buf /= Lc (buf);
appendTestMapDown (result, buf, info, source, dest);
return result;
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
noSubset= false;
}
if (T.length() < 2*s)
{
buf= F/myContent (F);
buf /= Lc (buf);
appendMapDown (result, buf, info, source, dest);
}
delete [] v;
return result;
}

## factorizationWRTDifferentSecondVars()

void factorizationWRTDifferentSecondVars | ( | const CanonicalForm & | A,
|  | CFList *& | Aeval,
|  | const ExtensionInfo & | info,
|  | int & | minFactorsLength,
|  | bool & | irred )

Definition at line 2184 of file facFqFactorize.cc.

{
Variable x= Variable (1);
minFactorsLength= 0;
irred= false;
CFList factors;
Variable v;
for (int j= 0; j < A.level() - 2; j++)
{
if (!Aeval[j].isEmpty())
{
v= Variable (Aeval[j].getFirst().level());
if (CFFactory::gettype() == GaloisFieldDomain)
factors= GFBiSqrfFactorize (Aeval[j].getFirst());
else if (info.getAlpha().level() == 1)
factors= FpBiSqrfFactorize (Aeval[j].getFirst());
else
factors= FqBiSqrfFactorize (Aeval[j].getFirst(), info.getAlpha());
factors.removeFirst();
if (minFactorsLength == 0)
minFactorsLength= factors.length();
else
minFactorsLength= tmin (minFactorsLength, factors.length());
if (factors.length() == 1)
{
irred= true;
return;
}
sortList (factors, x);
Aeval [j]= factors;
}
}
}
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition facFactorize.h:33
irred
CFList int bool & irred
[in,out] Is A irreducible?
Definition facFactorize.h:34
FqBiSqrfFactorize
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:156
FpBiSqrfFactorize
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:141
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition facFqBivar.h:172
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition facHensel.cc:449

## factorRecombination()

CFList factorRecombination | ( | const CanonicalForm & | F,
|  | const CFList & | factors,
|  | const CFList & | M )

Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.

Returns
  factorRecombination returns a list of factors of F

See also
  extFactorRecombination()

Parameters

  [in] | F | poly to be factored
  [in] | factors | list of lifted factors that are monic wrt Variable (1)
  [in] | M | a list of powers of Variables

Definition at line 361 of file facFqFactorize.cc.

{
if (factors.length() == 1)
return CFList(F);
if (factors.length() < 1)
return CFList();
CFList T, S;
T= factors;
int s= 1;
CFList result;
CanonicalForm LCBuf= LC (F, Variable (1));
CanonicalForm g, buf= F;
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
bool noSubset= false;
CFArray TT;
TT= copy (factors);
Variable y= F.level() - 1;
bool recombination= false;
CanonicalForm h, quot;
while (T.length() >= 2*s)
{
while (noSubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombination)
{
T.insert (LC (buf));
g= prodMod (T, M);
result.append (g/myContent (g));
return result;
}
else
return CFList (F);
}
S= subset (v, s, TT, noSubset);
if (noSubset) break;
S.insert (LCBuf);
g= prodMod (S, M);
S.removeFirst();
g /= myContent (g);
if (fdivides (g, buf, quot))
{
recombination= true;
result.append (g);
buf= quot;
LCBuf= LC (buf, Variable(1));
T= Difference (T, S);
if (T.length() < 2*s || T.length() == s)
{
result.append (buf);
delete [] v;
return result;
}
TT= copy (T);
indexUpdate (v, s, T.length(), noSubset);
if (noSubset) break;
}
}
s++;
if (T.length() < 2*s || T.length() == s)
{
result.append (buf);
delete [] v;
return result;
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
noSubset= false;
}
if (T.length() < 2*s)
result.append (F);
delete [] v;
return result;
}
h
STATIC_VAR Poly * h
Definition janet.cc:971

## gcdFreeBasis()

void gcdFreeBasis | ( | CFFList & | factors1,
|  | CFFList & | factors2 )

gcd free basis of two lists of factors

Parameters

  [in,out] | factors1 | list of factors, returns gcd free factors
  [in,out] | factors2 | list of factors, returns gcd free factors

Definition at line 1269 of file facFqFactorize.cc.

{
CanonicalForm g;
int k= factors1.length();
int l= factors2.length();
int n= 0;
int m;
CFFListIterator j;
for (CFFListIterator i= factors1; (n < k && i.hasItem()); i++, n++)
{
m= 0;
for (j= factors2; (m < l && j.hasItem()); j++, m++)
{
g= gcd (i.getItem().factor(), j.getItem().factor());
if (degree (g,1) > 0)
{
j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
i.getItem()= CFFactor (i.getItem().factor()/g, i.getItem().exp());
factors1.append (CFFactor (g, i.getItem().exp()));
factors2.append (CFFactor (g, j.getItem().exp()));
}
}
}
}
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
m
int m
Definition cfEzgcd.cc:128

## getLeadingCoeffs()

void getLeadingCoeffs | ( | const CanonicalForm & | A,
|  | CFList *& | Aeval )

extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables

Parameters

  [in] | A | some poly
  [in,out] | Aeval | array of bivariate factors, returns the leading coefficients of these factors

Definition at line 2233 of file facFqFactorize.cc.

{
CFListIterator iter;
CFList LCs;
for (int j= 0; j < A.level() - 2; j++)
{
if (!Aeval[j].isEmpty())
{
LCs= CFList();
for (iter= Aeval[j]; iter.hasItem(); iter++)
LCs.append (LC (iter.getItem(), 1));
//normalize (LCs);
Aeval[j]= LCs;
}
}
}

## henselLiftAndEarly()

CFList henselLiftAndEarly | ( | CanonicalForm & | A,
|  | CFList & | MOD,
|  | int *& | liftBounds,
|  | bool & | earlySuccess,
|  | CFList & | earlyFactors,
|  | const CFList & | Aeval,
|  | const CFList & | biFactors,
|  | const CFList & | evaluation,
|  | const ExtensionInfo & | info )

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
  earlyFactorDetectn(), extEarlyFactorDetect()

Parameters

  [in,out] | A | poly to be factored, returns poly divided by detected factors, in case of success
  [in,out] | MOD | a list of powers of Variables
  [in,out] | liftBounds | initial lift bounds, returns adapted lift bounds
  [in,out] | earlySuccess | indicating success
  [in,out] | earlyFactors | early factors
  [in] | Aeval | A successively evaluated at elements of evaluation
  [in] | biFactors | bivariate factors
  [in] | evaluation | evaluation point
  [in] | info | info about extension

Definition at line 985 of file facFqFactorize.cc.

{
bool extension= info.isInExtension();
CFList bufFactors= biFactors;
bufFactors.insert (LC (Aeval.getFirst(), 1));
sortList (bufFactors, Variable (1));
CFList diophant;
CFArray Pi;
int smallFactorDeg= 11; //tunable parameter
CFList result;
int adaptedLiftBound= 0;
int liftBound= liftBounds[1];
earlySuccess= false;
CFList earlyReconstFactors;
CFListIterator j= Aeval;
j++;
CanonicalForm buf= j.getItem();
CFMatrix Mat= CFMatrix (liftBound, bufFactors.length() - 1);
MOD= CFList (power (Variable (2), liftBounds[0]));
if (smallFactorDeg >= liftBound)
{
result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
}
else if (smallFactorDeg >= degree (buf) + 1)
{
liftBounds[1]= degree (buf) + 1;
result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
if (Aeval.length() == 2)
{
if (!extension)
earlyFactors= earlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
degree (buf) + 1, MOD, liftBound);
else
earlyFactors= extEarlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
info, evaluation, degree
(buf) + 1, MOD, liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
degree (buf) + 1, MOD, liftBound);
else
adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
evaluation, degree (buf) + 1,
MOD, liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
liftBounds[1]= adaptedLiftBound;
liftBound= adaptedLiftBound;
henselLiftResume (buf, result, degree (buf) + 1, liftBound,
Pi, diophant, Mat, MOD);
}
else
liftBounds[1]= adaptedLiftBound;
}
else if (smallFactorDeg < degree (buf) + 1)
{
liftBounds[1]= smallFactorDeg;
result= henselLift23 (Aeval, bufFactors, liftBounds, diophant, Pi, Mat);
if (Aeval.length() == 2)
{
if (!extension)
earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
earlySuccess, smallFactorDeg, MOD,
liftBound);
else
earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
earlySuccess, info, evaluation,
smallFactorDeg, MOD, liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
smallFactorDeg, MOD, liftBound);
else
adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess, info,
evaluation, smallFactorDeg, MOD,
liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
henselLiftResume (buf, result, smallFactorDeg, degree (buf) + 1,
Pi, diophant, Mat, MOD);
if (Aeval.length() == 2)
{
if (!extension)
earlyFactors= earlyFactorDetect (buf, result, adaptedLiftBound,
earlySuccess, degree (buf) + 1,
MOD, liftBound);
else
earlyFactors= extEarlyFactorDetect (buf, result, adaptedLiftBound,
earlySuccess, info, evaluation,
degree (buf) + 1, MOD,
liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption (buf, result, earlySuccess,
degree (buf) + 1, MOD,liftBound);
else
adaptedLiftBound= extLiftBoundAdaption (buf, result, earlySuccess,
info, evaluation,
degree (buf) + 1, MOD,
liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
liftBounds[1]= adaptedLiftBound;
liftBound= adaptedLiftBound;
henselLiftResume (buf, result, degree (buf) + 1, liftBound,
Pi, diophant, Mat, MOD);
}
else
liftBounds[1]= adaptedLiftBound;
}
else
liftBounds[1]= adaptedLiftBound;
}
MOD.append (power (Variable (3), liftBounds[1]));
if (Aeval.length() > 2)
{
CFListIterator j= Aeval;
j++;
CFList bufEval;
bufEval.append (j.getItem());
j++;
int liftBoundsLength= Aeval.getLast().level() - 1;
for (int i= 2; i <= liftBoundsLength && j.hasItem(); i++, j++)
{
earlySuccess= false;
result.insert (LC (bufEval.getFirst(), 1));
bufEval.append (j.getItem());
liftBound= liftBounds[i];
Mat= CFMatrix (liftBounds[i], result.length() - 1);
buf= j.getItem();
if (smallFactorDeg >= liftBound)
result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
liftBounds[i - 1], liftBounds[i]);
else if (smallFactorDeg >= degree (buf) + 1)
{
result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
liftBounds[i - 1], degree (buf) + 1);
if (Aeval.length() == i + 1)
{
if (!extension)
earlyFactors= earlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
degree (buf) + 1, MOD, liftBound);
else
earlyFactors= extEarlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
info, evaluation, degree (buf) + 1, MOD, liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption
(buf, result, earlySuccess, degree (buf)
+ 1, MOD, liftBound);
else
adaptedLiftBound= extLiftBoundAdaption
(buf, result, earlySuccess, info, evaluation,
degree (buf) + 1, MOD, liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
liftBounds[i]= adaptedLiftBound;
liftBound= adaptedLiftBound;
henselLiftResume (buf, result, degree (buf) + 1, liftBound,
Pi, diophant, Mat, MOD);
}
else
{
liftBounds[i]= adaptedLiftBound;
}
}
else if (smallFactorDeg < degree (buf) + 1)
{
result= henselLift (bufEval, result, MOD, diophant, Pi, Mat,
liftBounds[i - 1], smallFactorDeg);
if (Aeval.length() == i + 1)
{
if (!extension)
earlyFactors= earlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
smallFactorDeg, MOD, liftBound);
else
earlyFactors= extEarlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
info, evaluation, smallFactorDeg, MOD, liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption
(buf, result, earlySuccess,
smallFactorDeg, MOD, liftBound);
else
adaptedLiftBound= extLiftBoundAdaption
(buf, result, earlySuccess, info, evaluation,
smallFactorDeg, MOD, liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
henselLiftResume (buf, result, smallFactorDeg,
degree (buf) + 1, Pi, diophant, Mat, MOD);
if (Aeval.length() == i + 1)
{
if (!extension)
earlyFactors= earlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
degree (buf) + 1, MOD, liftBound);
else
earlyFactors= extEarlyFactorDetect
(buf, result, adaptedLiftBound, earlySuccess,
info, evaluation, degree (buf) + 1, MOD,
liftBound);
}
else
{
if (!extension)
adaptedLiftBound= liftBoundAdaption
(buf, result, earlySuccess, degree
(buf) + 1, MOD, liftBound);
else
adaptedLiftBound= extLiftBoundAdaption
(buf, result, earlySuccess, info, evaluation,
degree (buf) + 1, MOD, liftBound);
}
if (!earlySuccess)
{
result.insert (LC (buf, 1));
liftBounds[i]= adaptedLiftBound;
liftBound= adaptedLiftBound;
henselLiftResume (buf, result, degree (buf) + 1, liftBound,
Pi, diophant, Mat, MOD);
}
else
liftBounds[i]= adaptedLiftBound;
}
else
liftBounds[i]= adaptedLiftBound;
}
MOD.append (power (Variable (i + 2), liftBounds[i]));
bufEval.removeFirst();
}
bufFactors= result;
}
else
bufFactors= result;
if (earlySuccess)
A= buf;
return result;
}
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
liftBoundAdaption
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
Definition facFqFactorize.cc:448
extEarlyFactorDetect
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqFactorize.cc:665
extLiftBoundAdaption
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
Definition facFqFactorize.cc:514
earlyFactorDetect
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqFactorize.cc:612
henselLift23
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition facHensel.cc:1785
henselLift
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition facHensel.cc:1852
henselLiftResume
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition facHensel.cc:1827

## LCHeuristic()

void LCHeuristic | ( | CanonicalForm & | A,
|  | const CanonicalForm & | LCmultiplier,
|  | CFList & | biFactors,
|  | CFList *& | leadingCoeffs,
|  | const CFList * | oldAeval,
|  | int | lengthAeval,
|  | const CFList & | evaluation,
|  | const CFList & | oldBiFactors )

heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors

Parameters

  [in,out] | A | a poly
  [in,out] | LCmultiplier | divisor of LC (A,1)
  [in,out] | biFactors | bivariate factors
  [in,out] | leadingCoeffs | leading coeffs
  [in] | oldAeval | bivariate factors wrt. different second vars
  [in] | lengthAeval | length of oldAeval
  [in] | evaluation | evaluation point
  [in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them

Definition at line 2615 of file facFqFactorize.cc.

{
CFListIterator iter, iter2;
int index;
Variable xx;
CFList vars1;
CFFList sqrfMultiplier= sqrFree (LCmultiplier);
if (sqrfMultiplier.getFirst().factor().inCoeffDomain())
sqrfMultiplier.removeFirst();
sqrfMultiplier= sortCFFListByNumOfVars (sqrfMultiplier);
xx= Variable (2);
for (iter= oldBiFactors; iter.hasItem(); iter++)
vars1.append (power (xx, degree (LC (iter.getItem(),1), xx)));
for (int i= 0; i < lengthAeval; i++)
{
if (oldAeval[i].isEmpty())
continue;
xx= oldAeval[i].getFirst().mvar();
iter2= vars1;
for (iter= oldAeval[i]; iter.hasItem(); iter++, iter2++)
iter2.getItem() *= power (xx, degree (LC (iter.getItem(),1), xx));
}
CanonicalForm tmp, quot1, quot2, quot3;
iter2= vars1;
for (iter= leadingCoeffs[lengthAeval-1]; iter.hasItem(); iter++, iter2++)
{
tmp= iter.getItem()/LCmultiplier;
for (int i=1; i <= tmp.level(); i++)
{
if (degree (tmp,i) > 0 && (degree (iter2.getItem(),i) > degree (tmp,i)))
iter2.getItem() /= power (Variable (i), degree (tmp,i));
}
}
int multi;
for (CFFListIterator ii= sqrfMultiplier; ii.hasItem(); ii++)
{
multi= 0;
for (iter= vars1; iter.hasItem(); iter++)
{
tmp= iter.getItem();
while (fdivides (myGetVars (ii.getItem().factor()), tmp))
{
multi++;
tmp /= myGetVars (ii.getItem().factor());
}
}
if (multi == ii.getItem().exp())
{
index= 1;
for (iter= vars1; iter.hasItem(); iter++, index++)
{
while (fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
{
int index2= 1;
for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();iter2++,
index2++)
{
if (index2 == index)
continue;
else
{
tmp= ii.getItem().factor();
if (fdivides (tmp, iter2.getItem(), quot1))
{
CFListIterator iter3= evaluation;
for (int jj= A.level(); jj > 2; jj--, iter3++)
tmp= tmp (iter3.getItem(), jj);
if (!tmp.inCoeffDomain())
{
int index3= 1;
for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
{
if (index3 == index2)
{
if (fdivides (tmp, iter3.getItem(), quot2))
{
if (fdivides (ii.getItem().factor(), A, quot3))
{
A = quot3;
iter2.getItem() = quot2;
iter3.getItem() = quot3;
iter3.getItem() /= Lc (iter3.getItem());
break;
}
}
}
}
}
}
}
}
iter.getItem() /= getVars (ii.getItem().factor());
}
}
}
else
{
index= 1;
for (iter= vars1; iter.hasItem(); iter++, index++)
{
if (!fdivides (myGetVars (ii.getItem().factor()), iter.getItem()))
{
int index2= 1;
for (iter2= leadingCoeffs[lengthAeval-1];iter2.hasItem();iter2++,
index2++)
{
if (index2 == index)
{
tmp= power (ii.getItem().factor(), ii.getItem().exp());
if (fdivides (tmp, A, quot1))
{
if (fdivides (tmp, iter2.getItem()))
{
CFListIterator iter3= evaluation;
for (int jj= A.level(); jj > 2; jj--, iter3++)
tmp= tmp (iter3.getItem(), jj);
if (!tmp.inCoeffDomain())
{
int index3= 1;
for (iter3= biFactors; iter3.hasItem(); iter3++, index3++)
{
if (index3 == index2)
{
if (fdivides (tmp, iter3.getItem(), quot3))
{
A = quot1;
iter2.getItem() = quot2;
iter3.getItem() = quot3;
iter3.getItem() /= Lc (iter3.getItem());
break;
}
}
}
}
}
}
}
}
}
}
}
}
}
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f ).
Definition cf_ops.cc:350
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
sortCFFListByNumOfVars
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
Definition facFqFactorizeUtil.cc:186
myGetVars
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
Definition facFqFactorizeUtil.cc:168
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592

## LCHeuristic2()

void LCHeuristic2 | ( | const CanonicalForm & | LCmultiplier,
|  | const CFList & | factors,
|  | CFList & | leadingCoeffs,
|  | CFList & | contents,
|  | CFList & | LCs,
|  | bool & | foundTrueMultiplier )

heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content

Parameters

  [in] | LCmultiplier | divisor of LC (A,1)
  [in] | factors | result of LucksWangSparseHeuristic
  [in,out] | leadingCoeffs | leading coeffs
  [in,out] | contents | content of factors
  [in,out] | LCs | LC of factors divided by content of factors
  [in,out] | foundTrueMultiplier | success?

Definition at line 2779 of file facFqFactorize.cc.

{
CanonicalForm cont;
int index= 1;
CFListIterator iter2;
for (CFListIterator iter= factors; iter.hasItem(); iter++, index++)
{
cont= content (iter.getItem(), 1);
cont= gcd (cont, LCmultiplier);
contents.append (cont);
if (cont.inCoeffDomain()) // trivial content->LCmultiplier needs to go there
{
foundTrueMultiplier= true;
int index2= 1;
for (iter2= leadingCoeffs; iter2.hasItem(); iter2++, index2++)
{
if (index2 == index)
continue;
iter2.getItem() /= LCmultiplier;
}
break;
}
else
LCs.append (LC (iter.getItem()/cont, 1));
}
}

## LCHeuristic3()

void LCHeuristic3 | ( | const CanonicalForm & | LCmultiplier,
|  | const CFList & | factors,
|  | const CFList & | oldBiFactors,
|  | const CFList & | contents,
|  | const CFList * | oldAeval,
|  | CanonicalForm & | A,
|  | CFList *& | leadingCoeffs,
|  | int | lengthAeval,
|  | bool & | foundMultiplier )

heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic.

Parameters

  [in] | LCmultiplier | divisor of LC (A,1)
  [in] | factors | result of LucksWangSparseHeuristic
  [in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them
  [in] | contents | content of factors
  [in] | oldAeval | bivariate factors wrt. different second vars
  [in,out] | A | poly
  [in,out] | leadingCoeffs | leading coeffs
  [in] | lengthAeval | length of oldAeval
  [in,out] | foundMultiplier | success?

Definition at line 2809 of file facFqFactorize.cc.

{
int index= 1;
CFListIterator iter, iter2= factors;
for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
{
if (fdivides (iter.getItem(), LCmultiplier))
{
if ((LCmultiplier/iter.getItem()).inCoeffDomain() &&
!isOnlyLeadingCoeff(iter2.getItem())) //content divides LCmultiplier completely and factor consists of more terms than just the leading coeff
{
Variable xx= Variable (2);
CanonicalForm vars;
vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
xx));
for (int i= 0; i < lengthAeval; i++)
{
if (oldAeval[i].isEmpty())
continue;
xx= oldAeval[i].getFirst().mvar();
vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
xx));
}
if (vars.level() <= 2)
{
int index2= 1;
for (CFListIterator iter3= leadingCoeffs[lengthAeval-1];
iter3.hasItem(); iter3++, index2++)
{
if (index2 == index)
{
iter3.getItem() /= LCmultiplier;
break;
}
}
A /= LCmultiplier;
foundMultiplier= true;
iter.getItem()= 1;
}
}
}
}
}
isOnlyLeadingCoeff
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
Definition facFqFactorizeUtil.cc:162

## LCHeuristic4()

void LCHeuristic4 | ( | const CFList & | oldBiFactors,
|  | const CFList * | oldAeval,
|  | const CFList & | contents,
|  | const CFList & | factors,
|  | const CanonicalForm & | testVars,
|  | int | lengthAeval,
|  | CFList *& | leadingCoeffs,
|  | CanonicalForm & | A,
|  | CanonicalForm & | LCmultiplier,
|  | bool & | foundMultiplier )

heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful.

Parameters

  [in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them
  [in] | oldAeval | bivariate factors wrt. different second vars
  [in] | contents | content of factors
  [in] | factors | result of LucksWangSparseHeuristic
  [in] | testVars | product of second vars that occur among oldAeval
  [in] | lengthAeval | length of oldAeval
  [in,out] | leadingCoeffs | leading coeffs
  [in,out] | A | poly
  [in,out] | LCmultiplier | divisor of LC (A,1)
  [in] | foundMultiplier | success?

Definition at line 2857 of file facFqFactorize.cc.

{
int index=1;
CFListIterator iter, iter2= factors;
for (iter= contents; iter.hasItem(); iter++, iter2++, index++)
{
if (!iter.getItem().isOne() &&
fdivides (iter.getItem(), LCmultiplier))
{
if (!isOnlyLeadingCoeff (iter2.getItem())) // factor is more than just leading coeff
{
int index2= 1;
for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
iter2++, index2++)
{
if (index2 == index)
{
iter2.getItem() /= iter.getItem();
foundMultiplier= true;
break;
}
}
A /= iter.getItem();
LCmultiplier /= iter.getItem();
iter.getItem()= 1;
}
else if (fdivides (getVars (LCmultiplier), testVars))//factor consists of just leading coeff
{
Variable xx= Variable (2);
CanonicalForm vars;
vars= power (xx, degree (LC (getItem(oldBiFactors, index),1),
xx));
for (int i= 0; i < lengthAeval; i++)
{
if (oldAeval[i].isEmpty())
continue;
xx= oldAeval[i].getFirst().mvar();
vars *= power (xx, degree (LC (getItem(oldAeval[i], index),1),
xx));
}
if (myGetVars(content(getItem(leadingCoeffs[lengthAeval-1],index),1))
/myGetVars (LCmultiplier) == vars)
{
int index2= 1;
for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
iter2++, index2++)
{
if (index2 == index)
{
iter2.getItem() /= LCmultiplier;
foundMultiplier= true;
break;
}
}
A /= LCmultiplier;
iter.getItem()= 1;
}
}
}
}
}

## LCHeuristicCheck()

void LCHeuristicCheck | ( | const CFList & | LCs,
|  | const CFList & | contents,
|  | CanonicalForm & | A,
|  | const CanonicalForm & | oldA,
|  | CFList & | leadingCoeffs,
|  | bool & | foundTrueMultiplier )

checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true

Parameters

  [in] | LCs | leading coeffs computed
  [in] | contents | content of factors
  [in,out] | A | oldA*LCmultiplier^m
  [in] | oldA | some poly
  [in,out] | leadingCoeffs | leading coefficients
  [in,out] | foundTrueMultiplier | success?

Definition at line 2763 of file facFqFactorize.cc.

{
CanonicalForm pLCs= prod (LCs);
if (fdivides (pLCs, LC (oldA,1)) && (LC(oldA,1)/pLCs).inCoeffDomain()) // check if the product of the lead coeffs of the primitive factors equals the lead coeff of the old A
{
A= oldA;
CFListIterator iter2= leadingCoeffs;
for (CFListIterator iter= contents; iter.hasItem(); iter++, iter2++)
iter2.getItem() /= iter.getItem();
foundTrueMultiplier= true;
}
}

## lcmContent()

CanonicalForm lcmContent | ( | const CanonicalForm & | A,
|  | CFList & | contentAi )

compute the LCM of the contents of A wrt to each variable occuring in A.

Returns
  lcmContent returns the LCM of the contents of A wrt to each variable occuring in A.

Parameters

  [in] | A | a compressed multivariate poly
  [in,out] | contentAi | an empty list, returns a list of the contents of A wrt to each variable occuring in A starting from A.mvar().

Definition at line 966 of file facFqFactorize.cc.

{
int i= A.level();
CanonicalForm buf= A;
contentAi.append (content (buf, i));
buf /= contentAi.getLast();
contentAi.append (content (buf, i - 1));
CanonicalForm result= lcm (contentAi.getFirst(), contentAi.getLast());
for (i= i - 2; i > 0; i--)
{
contentAi.append (content (buf, i));
buf /= contentAi.getLast();
result= lcm (result, contentAi.getLast());
}
return result;
}
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:709

## liftBoundAdaption()

int liftBoundAdaption | ( | const CanonicalForm & | F,
|  | const CFList & | factors,
|  | bool & | success,
|  | const int | deg,
|  | const CFList & | MOD,
|  | const int | bound )

Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.

Returns
  liftBoundAdaption returns an adapted lift bound.

See also
  earlyFactorDetect(), earlyFactorDetection()

Parameters

  [in] | F | a poly
  [in] | factors | list of list of lifted factors that are monic wrt Variable (1)
  [in,out] | success | indicates that no further lifting is necessary
  [in] | deg | stage of Hensel lifting
  [in] | MOD | a list of powers of Variables
  [in] | bound | initial lift bound

Definition at line 448 of file facFqFactorize.cc.

{
int adaptedLiftBound= 0;
CanonicalForm buf= F;
Variable y= F.mvar();
Variable x= Variable (1);
CanonicalForm LCBuf= LC (buf, x);
CanonicalForm g, quot;
CFList M= MOD;
M.append (power (y, deg));
int d= bound;
int e= 0;
int nBuf;
for (CFListIterator i= factors; i.hasItem(); i++)
{
g= mulMod (i.getItem(), LCBuf, M);
g /= myContent (g);
if (fdivides (g, buf, quot))
{
nBuf= degree (g, y) + degree (LC (g, 1), y);
d -= nBuf;
e= tmax (e, nBuf);
buf= quot;
LCBuf= LC (buf, x);
}
}
adaptedLiftBound= d;
if (adaptedLiftBound < deg)
{
if (adaptedLiftBound < degree (F) + 1)
{
if (d == 1)
{
if (e + 1 > deg)
{
adaptedLiftBound= deg;
success= false;
}
else
{
success= true;
if (e + 1 < degree (F) + 1)
adaptedLiftBound= deg;
else
adaptedLiftBound= e + 1;
}
}
else
{
success= true;
adaptedLiftBound= deg;
}
}
else
{
success= true;
}
}
return adaptedLiftBound;
}

## listGCD()

CanonicalForm listGCD | ( | const CFList & | L | ) |

inline static

Definition at line 75 of file facFqFactorize.cc.

{
if (L.length() == 0)
return 0;
if (L.length() == 1)
return L.getFirst();
if (L.length() == 2)
return gcd (L.getFirst(), L.getLast());
else
{
CFList lHi, lLo;
CanonicalForm resultHi, resultLo;
int length= L.length()/2;
int j= 0;
for (CFListIterator i= L; j < length; i++, j++)
lHi.append (i.getItem());
lLo= Difference (L, lHi);
resultHi= listGCD (lHi);
resultLo= listGCD (lLo);
if (resultHi.isOne() || resultLo.isOne())
return 1;
return gcd (resultHi, resultLo);
}
}
listGCD
static CanonicalForm listGCD(const CFList &L)
Definition facFqFactorize.cc:75

## multiFactorize()

CFList multiFactorize | ( | const CanonicalForm & | F,
|  | const ExtensionInfo & | info )

Definition at line 2929 of file facFqFactorize.cc.

{
if (F.inCoeffDomain())
return CFList (F);
TIMING_START (fac_fq_preprocess_and_content);
// compress and find main Variable
CFMap N;
TIMING_START (fac_fq_compress)
CanonicalForm A= myCompress (F, N);
TIMING_END_AND_PRINT (fac_fq_compress, "time to compress poly over Fq: ")
A /= Lc (A); // make monic
Variable alpha= info.getAlpha();
Variable beta= info.getBeta();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
bool extension= info.isInExtension();
bool GF= (CFFactory::gettype() == GaloisFieldDomain);
//univariate case
if (F.isUnivariate())
{
if (extension == false)
return uniFactorizer (F, alpha, GF);
else
{
CFList source, dest;
A= mapDown (F, info, source, dest);
return uniFactorizer (A, beta, GF);
}
}
//bivariate case
if (A.level() == 2)
{
CFList buf= biSqrfFactorizeHelper (F, info);
if (buf.getFirst().inCoeffDomain())
buf.removeFirst();
return buf;
}
Variable x= Variable (1);
Variable y= Variable (2);
// remove content
TIMING_START (fac_fq_content);
CFList contentAi;
CanonicalForm lcmCont= lcmContent (A, contentAi);
A /= lcmCont;
TIMING_END_AND_PRINT (fac_fq_content, "time to extract content over Fq: ");
// trivial after content removal
CFList contentAFactors;
if (A.inCoeffDomain())
{
for (CFListIterator i= contentAi; i.hasItem(); i++)
{
if (i.getItem().inCoeffDomain())
continue;
else
{
lcmCont /= i.getItem();
contentAFactors=
Union (multiFactorize (lcmCont, info),
multiFactorize (i.getItem(), info));
break;
}
}
decompress (contentAFactors, N);
if (!extension)
normalize (contentAFactors);
return contentAFactors;
}
// factorize content
TIMING_START (fac_fq_content);
contentAFactors= multiFactorize (lcmCont, info);
TIMING_END_AND_PRINT (fac_fq_content, "time to factor content over Fq: ");
// univariate after content removal
CFList factors;
if (A.isUnivariate ())
{
factors= uniFactorizer (A, alpha, GF);
append (factors, contentAFactors);
decompress (factors, N);
return factors;
}
// check main variable
TIMING_START (fac_fq_check_mainvar);
int swapLevel= 0;
CanonicalForm derivZ;
CanonicalForm gcdDerivZ;
CanonicalForm bufA= A;
Variable z;
for (int i= 1; i <= A.level(); i++)
{
z= Variable (i);
derivZ= deriv (bufA, z);
if (derivZ.isZero())
{
if (i == 1)
swapLevel= 1;
else
continue;
}
else
{
gcdDerivZ= gcd (bufA, derivZ);
if (degree (gcdDerivZ) > 0 && !derivZ.isZero())
{
CanonicalForm g= bufA/gcdDerivZ;
CFList factorsG=
Union (multiFactorize (g, info),
multiFactorize (gcdDerivZ, info));
appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
if (!extension)
normalize (factorsG);
return factorsG;
}
else
{
if (swapLevel == 1)
{
swapLevel= i;
bufA= swapvar (A, x, z);
}
A= bufA;
break;
}
}
}
TIMING_END_AND_PRINT (fac_fq_check_mainvar,
"time to check main var over Fq: ");
TIMING_END_AND_PRINT (fac_fq_preprocess_and_content,
"time to preprocess poly and extract content over Fq: ");
CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
bool fail= false;
int swapLevel2= 0;
//int level;
int factorNums= 3;
CFList biFactors, bufBiFactors;
CanonicalForm evalPoly;
int lift, bufLift, lengthAeval2= A.level()-2;
double logarithm= (double) ilog2 (totaldegree (A));
logarithm /= log2exp;
logarithm= ceil (logarithm);
if (factorNums < (int) logarithm)
factorNums= (int) logarithm;
CFList* bufAeval2= new CFList [lengthAeval2];
CFList* Aeval2= new CFList [lengthAeval2];
int counter;
int differentSecondVar= 0;
// several bivariate factorizations
TIMING_START (fac_fq_bifactor_total);
for (int i= 0; i < factorNums; i++)
{
counter= 0;
bufA= A;
bufAeval= CFList();
TIMING_START (fac_fq_evaluation);
bufEvaluation= evalPoints (bufA, bufAeval, alpha, list, GF, fail);
TIMING_END_AND_PRINT (fac_fq_evaluation,
"time to find evaluation point over Fq: ");
evalPoly= 0;
if (fail && (i == 0))
{
/*if (!swapLevel) //uncomment to reenable search for new main variable
level= 2;
else
level= swapLevel + 1;*/
//CanonicalForm g;
//swapLevel2= newMainVariableSearch (A, Aeval, evaluation, alpha, level, g);
/*if (!swapLevel2) // need to pass to an extension
{*/
factors= extFactorize (A, info);
appendSwapDecompress (factors, contentAFactors, N, swapLevel, x);
normalize (factors);
delete [] bufAeval2;
delete [] Aeval2;
return factors;
/*}
else
{
if (swapLevel2 == -1)
{
CFList factorsG=
Union (multiFactorize (g, info),
multiFactorize (A/g, info));
appendSwapDecompress (factorsG, contentAFactors, N, swapLevel, x);
if (!extension)
normalize (factorsG);
delete [] bufAeval2;
delete [] Aeval2;
return factorsG;
}
fail= false;
bufAeval= Aeval;
bufA= A;
bufEvaluation= evaluation;
}*/ //end uncomment
}
else if (fail && (i > 0))
break;
TIMING_START (fac_fq_evaluation);
evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
TIMING_END_AND_PRINT (fac_fq_evaluation,
"time for evaluation wrt diff second vars over Fq: ");
for (int j= 0; j < lengthAeval2; j++)
{
if (!bufAeval2[j].isEmpty())
counter++;
}
bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
TIMING_START (fac_fq_bi_factorizer);
if (!GF && alpha.level() == 1)
bufBiFactors= FpBiSqrfFactorize (bufAeval.getFirst());
else if (GF)
bufBiFactors= GFBiSqrfFactorize (bufAeval.getFirst());
else
bufBiFactors= FqBiSqrfFactorize (bufAeval.getFirst(), alpha);
TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
"time for bivariate factorization: ");
bufBiFactors.removeFirst();
if (bufBiFactors.length() == 1)
{
if (extension)
{
CFList source, dest;
A= mapDown (A, info, source, dest);
}
factors.append (A);
appendSwapDecompress (factors, contentAFactors, N, swapLevel,
swapLevel2, x);
if (!extension)
normalize (factors);
delete [] bufAeval2;
delete [] Aeval2;
return factors;
}
if (i == 0)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
biFactors= bufBiFactors;
lift= bufLift;
for (int j= 0; j < lengthAeval2; j++)
Aeval2 [j]= bufAeval2 [j];
differentSecondVar= counter;
}
else
{
if (bufBiFactors.length() < biFactors.length() ||
((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
counter > differentSecondVar)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
biFactors= bufBiFactors;
lift= bufLift;
for (int j= 0; j < lengthAeval2; j++)
Aeval2 [j]= bufAeval2 [j];
differentSecondVar= counter;
}
}
int k= 0;
for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
evalPoly += j.getItem()*power (x, k);
list.append (evalPoly);
}
delete [] bufAeval2;
sortList (biFactors, x);
int minFactorsLength;
bool irred= false;
TIMING_START (fac_fq_bi_factorizer);
factorizationWRTDifferentSecondVars (A, Aeval2, info, minFactorsLength,irred);
TIMING_END_AND_PRINT (fac_fq_bi_factorizer,
"time for bivariate factorization wrt diff second vars over Fq: ");
TIMING_END_AND_PRINT (fac_fq_bifactor_total,
"total time for eval and bivar factors over Fq: ");
if (irred)
{
if (extension)
{
CFList source, dest;
A= mapDown (A, info, source, dest);
}
factors.append (A);
appendSwapDecompress (factors, contentAFactors, N, swapLevel,
swapLevel2, x);
if (!extension)
normalize (factors);
delete [] Aeval2;
return factors;
}
if (minFactorsLength == 0)
minFactorsLength= biFactors.length();
else if (biFactors.length() > minFactorsLength)
refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
minFactorsLength= tmin (minFactorsLength, biFactors.length());
CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
minFactorsLength= tmin (minFactorsLength, biFactors.length());
if (minFactorsLength == 1)
{
if (extension)
{
CFList source, dest;
A= mapDown (A, info, source, dest);
}
factors.append (A);
appendSwapDecompress (factors, contentAFactors, N, swapLevel,
swapLevel2, x);
if (!extension)
normalize (factors);
delete [] Aeval2;
return factors;
}
if (differentSecondVar == lengthAeval2)
{
bool zeroOccured= false;
for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
{
if (iter.getItem().isZero())
{
zeroOccured= true;
break;
}
}
if (!zeroOccured)
{
factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
minFactorsLength);
if (factors.length() == biFactors.length())
{
if (extension)
factors= extNonMonicFactorRecombination (factors, A, info);
appendSwapDecompress (factors, contentAFactors, N, swapLevel,
swapLevel2, x);
if (!extension)
normalize (factors);
delete [] Aeval2;
return factors;
}
else
factors= CFList();
//TODO case where factors.length() > 0
}
}
CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this
for (int i= 0; i < lengthAeval2; i++)
oldAeval[i]= Aeval2[i];
getLeadingCoeffs (A, Aeval2);
CFList biFactorsLCs;
for (CFListIterator i= biFactors; i.hasItem(); i++)
biFactorsLCs.append (LC (i.getItem(), 1));
Variable v;
TIMING_START (fac_fq_precompute_leadcoeff);
CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, alpha,
evaluation, Aeval2, lengthAeval2, v);
if (v.level() != 1)
changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
uniFactors, v);
CanonicalForm oldA= A;
CFList oldBiFactors= biFactors;
CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
leadingCoeffs.removeFirst();
if (!LCmultiplierIsConst)
distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
//prepare leading coefficients
CFList* leadingCoeffs2= new CFList [lengthAeval2];
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
biFactors, evaluation);
CFListIterator iter;
CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
bufBiFactors= biFactors;
bufA= A;
CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
if (!LCmultiplierIsConst)
{
testVars= Variable (2);
for (int i= 0; i < lengthAeval2; i++)
{
if (!oldAeval[i].isEmpty())
testVars *= oldAeval[i].getFirst().mvar();
}
}
TIMING_END_AND_PRINT(fac_fq_precompute_leadcoeff,
"time to precompute LC over Fq: ");
TIMING_START (fac_fq_luckswang);
CFList bufFactors= CFList();
bool LCheuristic= false;
if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
factors))
{
int check= biFactors.length();
int * index= new int [factors.length()];
CFList oldFactors= factors;
factors= recoverFactors (A, factors, index);
if (check == factors.length())
{
if (extension)
factors= extNonMonicFactorRecombination (factors, bufA, info);
if (v.level() != 1)
{
for (iter= factors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), v, y);
}
appendSwapDecompress (factors, contentAFactors, N, swapLevel,
swapLevel2, x);
if (!extension)
normalize (factors);
delete [] index;
delete [] Aeval2;
TIMING_END_AND_PRINT (fac_fq_luckswang,
"time for successful LucksWang over Fq: ");
return factors;
}
else if (factors.length() > 0)
{
int oneCount= 0;
CFList l;
for (int i= 0; i < check; i++)
{
if (index[i] == 1)
{
iter=biFactors;
for (int j=1; j <= i-oneCount; j++)
iter++;
iter.remove (1);
for (int j= 0; j < lengthAeval2; j++)
{
l= leadingCoeffs2[j];
iter= l;
for (int k=1; k <= i-oneCount; k++)
iter++;
iter.remove (1);
leadingCoeffs2[j]=l;
}
oneCount++;
}
}
bufFactors= factors;
factors= CFList();
}
else if (!LCmultiplierIsConst && factors.length() == 0)
{
LCheuristic= true;
factors= oldFactors;
CFList contents, LCs;
bool foundTrueMultiplier= false;
LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
contents, LCs, foundTrueMultiplier);
if (foundTrueMultiplier)
{
A= oldA;
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
leadingCoeffs, biFactors, evaluation);
}
else
{
bool foundMultiplier= false;
LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
A, leadingCoeffs2, lengthAeval2, foundMultiplier);
// coming from above: divide out more LCmultiplier if possible
if (foundMultiplier)
{
foundMultiplier= false;
LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
lengthAeval2, leadingCoeffs2, A, LCmultiplier,
foundMultiplier);
}
else
{
LCHeuristicCheck (LCs, contents, A, oldA,
leadingCoeffs2[lengthAeval2-1], foundMultiplier);
if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
{
LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
lengthAeval2, evaluation, oldBiFactors);
}
}
// patch everything together again
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
biFactors, evaluation);
}
factors= CFList();
if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
{
LCheuristic= false;
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
LCmultiplier= bufLCmultiplier;
}
}
else
factors= CFList();
delete [] index;
}
TIMING_END_AND_PRINT (fac_fq_luckswang, "time for LucksWang over Fq: ");
TIMING_START (fac_fq_lcheuristic);
if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
&& fdivides (getVars (LCmultiplier), testVars))
{
LCheuristic= true;
LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
lengthAeval2, evaluation, oldBiFactors);
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
biFactors, evaluation);
if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
{
LCheuristic= false;
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
LCmultiplier= bufLCmultiplier;
}
}
TIMING_END_AND_PRINT (fac_fq_lcheuristic, "time for Lc heuristic over Fq: ");
tryAgainWithoutHeu:
TIMING_START (fac_fq_shift_to_zero);
A= shift2Zero (A, Aeval, evaluation);
for (iter= biFactors; iter.hasItem(); iter++)
iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
for (int i= 0; i < lengthAeval2-1; i++)
leadingCoeffs2[i]= CFList();
for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
{
iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
for (int i= A.level() - 4; i > -1; i--)
{
if (i + 1 == lengthAeval2-1)
leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
else
leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
}
}
TIMING_END_AND_PRINT (fac_fq_shift_to_zero,
"time to shift evaluation point to zero: ");
CFArray Pi;
CFList diophant;
int* liftBounds= new int [A.level() - 1];
int liftBoundsLength= A.level() - 1;
for (int i= 0; i < liftBoundsLength; i++)
liftBounds [i]= degree (A, i + 2) + 1;
Aeval.removeFirst();
bool noOneToOne= false;
TIMING_START (fac_fq_hensel_lift);
factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
Pi, liftBounds, liftBoundsLength, noOneToOne);
TIMING_END_AND_PRINT (fac_fq_hensel_lift,
"time for non monic hensel lifting over Fq: ");
if (!noOneToOne)
{
int check= factors.length();
A= oldA;
TIMING_START (fac_fq_recover_factors);
factors= recoverFactors (A, factors, evaluation);
TIMING_END_AND_PRINT (fac_fq_recover_factors,
"time to recover factors over Fq: ");
if (check != factors.length())
noOneToOne= true;
else
factors= Union (factors, bufFactors);
if (extension && !noOneToOne)
factors= extNonMonicFactorRecombination (factors, A, info);
}
if (noOneToOne)
{
if (!LCmultiplierIsConst && LCheuristic)
{
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
delete [] liftBounds;
LCheuristic= false;
goto tryAgainWithoutHeu;
//something probably went wrong in the heuristic
}
A= shift2Zero (oldA, Aeval, evaluation);
biFactors= oldBiFactors;
for (iter= biFactors; iter.hasItem(); iter++)
iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
CanonicalForm LCA= LC (Aeval.getFirst(), 1);
CanonicalForm yToLift= power (y, lift);
CFListIterator i= biFactors;
lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
i++;
for (; i.hasItem(); i++)
lift= tmax (lift,
degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1);
lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
i= biFactors;
yToLift= power (y, lift);
CanonicalForm dummy;
for (; i.hasItem(); i++)
{
LCA= LC (i.getItem(), 1);
extgcd (LCA, yToLift, LCA, dummy);
i.getItem()= mod (i.getItem()*LCA, yToLift);
}
liftBoundsLength= F.level() - 1;
liftBounds= liftingBounds (A, lift);
CFList MOD;
bool earlySuccess;
CFList earlyFactors, liftedFactors;
TIMING_START (fac_fq_hensel_lift);
liftedFactors= henselLiftAndEarly
(A, MOD, liftBounds, earlySuccess, earlyFactors,
Aeval, biFactors, evaluation, info);
TIMING_END_AND_PRINT (fac_fq_hensel_lift,
"time for hensel lifting over Fq: ");
if (!extension)
{
TIMING_START (fac_fq_factor_recombination);
factors= factorRecombination (A, liftedFactors, MOD);
TIMING_END_AND_PRINT (fac_fq_factor_recombination,
"time for factor recombination: ");
}
else
{
TIMING_START (fac_fq_factor_recombination);
factors= extFactorRecombination (liftedFactors, A, MOD, info, evaluation);
TIMING_END_AND_PRINT (fac_fq_factor_recombination,
"time for factor recombination: ");
}
if (earlySuccess)
factors= Union (factors, earlyFactors);
if (!extension)
{
for (CFListIterator i= factors; i.hasItem(); i++)
{
int kk= Aeval.getLast().level();
for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
{
if (i.getItem().level() < kk)
continue;
i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
}
}
}
}
if (v.level() != 1)
{
for (CFListIterator iter= factors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), v, y);
}
swap (factors, swapLevel, swapLevel2, x);
append (factors, contentAFactors);
decompress (factors, N);
if (!extension)
normalize (factors);
delete[] liftBounds;
return factors;
}
swap
#define swap(_i, _j)
ilog2
int ilog2(const CanonicalForm &a)
Definition canonicalform.h:352
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
log2exp
static const double log2exp
Definition cfEzgcd.cc:45
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition cfNewtonPolygon.cc:853
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition cfUnivarGcd.cc:174
CFFactory
Definition cf_factory.h:24
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a).
Definition facFactorize.cc:198
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
getLast
else L getLast()(0
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
biSqrfFactorizeHelper
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition facFqBivar.h:55
recoverFactors
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
Definition facFqFactorizeUtil.cc:238
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition facFqFactorizeUtil.cc:131
liftingBounds
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
Definition facFqFactorizeUtil.cc:118
factorRecombination
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
Definition facFqFactorize.cc:361
precomputeLeadingCoeff
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
Definition facFqFactorize.cc:1479
LCHeuristicCheck
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
Definition facFqFactorize.cc:2763
distributeLCmultiplier
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
Definition facFqFactorize.cc:2591
evaluationWRTDifferentSecondVars
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
Definition facFqFactorize.cc:1966
prepareLeadingCoeffs
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
Definition facFqFactorize.cc:2382
extFactorRecombination
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field....
Definition facFqFactorize.cc:216
LCHeuristic4
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
Definition facFqFactorize.cc:2857
myCompress
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
Definition facFqFactorize.cc:134
changeSecondVariable
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
Definition facFqFactorize.cc:2544
factorizationWRTDifferentSecondVars
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, const ExtensionInfo &info, int &minFactorsLength, bool &irred)
Definition facFqFactorize.cc:2184
sortByUniFactors
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
Definition facFqFactorize.cc:2251
lcmContent
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
Definition facFqFactorize.cc:966
getLeadingCoeffs
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
Definition facFqFactorize.cc:2233
extFactorize
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
multivariate factorization over an extension of the initial field
Definition facFqFactorize.cc:3661
extNonMonicFactorRecombination
CFList extNonMonicFactorRecombination(const CFList &factors, const CanonicalForm &F, const ExtensionInfo &info)
Definition facFqFactorize.cc:2421
LCHeuristic3
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
Definition facFqFactorize.cc:2809
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
Definition facFqFactorize.cc:985
LCHeuristic
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
Definition facFqFactorize.cc:2615
refineBiFactors
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
Definition facFqFactorize.cc:2335
LCHeuristic2
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
Definition facFqFactorize.cc:2779
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition facFqFactorize.cc:2321
evalPoints
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
Definition facFqFactorize.cc:751
nonMonicHenselLift
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition facHensel.cc:2856
LucksWangSparseHeuristic
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Definition facSparseHensel.cc:26
sparseHeuristic
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
Definition facSparseHensel.cc:160
if
if(!FE_OPT_NO_SHELL_FLAG)
Definition fehelp.cc:1000
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
check
VAR int check
Definition libparse.cc:1106
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition lift.cc:26
amp::ceil
const signed long ceil(const ampf< Precision > &x)
Definition amp.h:788
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

## myCompress()

CanonicalForm myCompress | ( | const CanonicalForm & | F,
|  | CFMap & | N )

compress a polynomial s.t. and no gaps between the variables occur

Returns
  a compressed poly with the above properties

Parameters

  [in] | F | a poly
  [in,out] | N | a map to decompress

Definition at line 134 of file facFqFactorize.cc.

{
int n= F.level();
int * degsf= NEW_ARRAY(int,n + 1);
int ** swap= new int* [n + 1];
for (int i= 0; i <= n; i++)
{
degsf[i]= 0;
swap [i]= new int [3];
swap [i] [0]= 0;
swap [i] [1]= 0;
swap [i] [2]= 0;
}
int i= 1;
n= 1;
degsf= degrees (F, degsf);
CanonicalForm result= F;
while ( i <= F.level() )
{
while( degsf[i] == 0 ) i++;
swap[n][0]= i;
swap[n][1]= size (LC (F,i));
swap[n][2]= degsf [i];
if (i != n)
result= swapvar (result, Variable (n), Variable(i));
n++; i++;
}
int buf1, buf2, buf3;
n--;
for (i= 1; i < n; i++)
{
for (int j= 1; j < n - i + 1; j++)
{
if (swap[j][1] > swap[j + 1][1])
{
buf1= swap [j + 1] [0];
buf2= swap [j + 1] [1];
buf3= swap [j + 1] [2];
swap[j + 1] [0]= swap[j] [0];
swap[j + 1] [1]= swap[j] [1];
swap[j + 1] [2]= swap[j] [2];
swap[j][0]= buf1;
swap[j][1]= buf2;
swap[j][2]= buf3;
result= swapvar (result, Variable (j + 1), Variable (j));
}
else if (swap[j][1] == swap[j + 1][1] && swap[j][2] < swap[j + 1][2])
{
buf1= swap [j + 1] [0];
buf2= swap [j + 1] [1];
buf3= swap [j + 1] [2];
swap[j + 1] [0]= swap[j] [0];
swap[j + 1] [1]= swap[j] [1];
swap[j + 1] [2]= swap[j] [2];
swap[j][0]= buf1;
swap[j][1]= buf2;
swap[j][2]= buf3;
result= swapvar (result, Variable (j + 1), Variable (j));
}
}
}
for (i= n; i > 0; i--)
{
if (i != swap[i] [0])
N.newpair (Variable (i), Variable (swap[i] [0]));
}
for (i= F.level(); i >=0 ; i--)
delete [] swap[i];
delete [] swap;
DELETE_ARRAY(degsf);
return result;
}
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
degsf
int * degsf
Definition cfEzgcd.cc:59
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
buf1
CanonicalForm buf1
Definition facFqBivar.cc:76

## myContent() [1/2]

CanonicalForm myContent | ( | const CanonicalForm & | F | ) |

inline static

Definition at line 59 of file facFqFactorize.cc.

{
Variable x= Variable (1);
CanonicalForm G= swapvar (F, F.mvar(), x);
CFList L;
for (CFIterator i= G; i.hasTerms(); i++)
L.append (i.coeff());
if (L.length() == 2)
return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
if (L.length() == 1)
return LC (F, x);
return swapvar (listGCD (L), F.mvar(), x);
}
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## myContent() [2/2]

CanonicalForm myContent | ( | const CanonicalForm & | F,
|  | const Variable & | x )

inline static

Definition at line 102 of file facFqFactorize.cc.

{
if (degree (F, x) <= 0)
return 1;
CanonicalForm G= F;
bool swap= false;
if (x != F.mvar())
{
swap= true;
G= swapvar (F, x, F.mvar());
}
CFList L;
Variable alpha;
for (CFIterator i= G; i.hasTerms(); i++)
L.append (i.coeff());
if (L.length() == 2)
{
if (swap)
return swapvar (gcd (L.getFirst(), L.getLast()), F.mvar(), x);
else
return gcd (L.getFirst(), L.getLast());
}
if (L.length() == 1)
{
return LC (F, x);
}
if (swap)
return swapvar (listGCD (L), F.mvar(), x);
else
return listGCD (L);
}

## newMainVariableSearch()

int newMainVariableSearch | ( | CanonicalForm & | A,
|  | CFList & | Aeval,
|  | CFList & | evaluation,
|  | const Variable & | alpha,
|  | const int | lev,
|  | CanonicalForm & | g )

inline static

Definition at line 925 of file facFqFactorize.cc.

{
Variable x= Variable (1);
CanonicalForm derivI, buf;
bool GF= (CFFactory::gettype() == GaloisFieldDomain);
int swapLevel= 0;
CFList list;
bool fail= false;
buf= A;
Aeval= CFList();
evaluation= CFList();
for (int i= lev; i <= A.level(); i++)
{
derivI= deriv (buf, Variable (i));
if (!derivI.isZero())
{
g= gcd (buf, derivI);
if (degree (g) > 0)
return -1;
buf= swapvar (buf, x, Variable (i));
Aeval= CFList();
evaluation= CFList();
fail= false;
evaluation= evalPoints (buf, Aeval, alpha, list, GF, fail);
if (!fail)
{
A= buf;
swapLevel= i;
break;
}
else
buf= A;
}
}
return swapLevel;
}

## precomputeLeadingCoeff()

CFList precomputeLeadingCoeff | ( | const CanonicalForm & | LCF,
|  | const CFList & | LCFFactors,
|  | const Variable & | alpha,
|  | const CFList & | evaluation,
|  | CFList *& | differentSecondVarLCs,
|  | int | lSecondVarLCs,
|  | Variable & | y )

computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.

Returns
  see above

Parameters

  [in] | LCF | a multivariate poly
  [in] | LCFFactors | a list of univariate factors of LCF of level 2
  [in] | alpha | algebraic var.
  [in] | evaluation | an evaluation point having lSecondVarLCs+1 components
  [in] | differentSecondVarLCs | LCs of factors of f wrt different second variables
  [in] | lSecondVarLCs | length of the above
  [in,out] | y | if y.level() is not 1 on output the second variable has been changed to y

Definition at line 1479 of file facFqFactorize.cc.

{
y= Variable (1);
if (LCF.inCoeffDomain())
{
CFList result;
for (int i= 1; i <= LCFFactors.length() + 1; i++)
result.append (1);
return result;
}
CFMap N, M;
CFArray dummy= CFArray (2);
dummy [0]= LCF;
dummy [1]= Variable (2);
compress (dummy, M, N);
CanonicalForm F= M (LCF);
if (LCF.isUnivariate())
{
CFList result;
int LCFLevel= LCF.level();
bool found= false;
if (LCFLevel == 2)
{
//bivariate leading coefficients are already the true leading coefficients
result= LCFFactors;
found= true;
}
else
{
CFListIterator j;
for (int i= 0; i < lSecondVarLCs; i++)
{
for (j= differentSecondVarLCs[i]; j.hasItem(); j++)
{
if (j.getItem().level() == LCFLevel)
{
found= true;
break;
}
}
if (found)
{
result= differentSecondVarLCs [i];
break;
}
}
if (!found)
result= LCFFactors;
}
if (found)
result.insert (Lc (LCF));
else
result.insert (LCF);
return result;
}
CFList factors= LCFFactors;
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem()= M (i.getItem());
CanonicalForm sqrfPartF;
CFFList * bufSqrfFactors= new CFFList [factors.length()];
CFList evalSqrfPartF, bufFactors;
CFArray evalPoint= CFArray (evaluation.length() - 1);
CFArray buf= CFArray (evaluation.length());
CFArray swap= CFArray (evaluation.length());
CFListIterator iter= evaluation;
CanonicalForm vars=getVars (LCF)*Variable (2);
for (int i= evaluation.length() +1; i > 1; i--, iter++)
{
buf[i-2]=iter.getItem();
if (degree (vars, i) > 0)
swap[M(Variable (i)).level()-1]=buf[i-2];
}
buf= swap;
for (int i= 0; i < evaluation.length() - 1; i++)
evalPoint[i]= buf[i+1];
int pass= testFactors (F, factors, alpha, sqrfPartF,
bufFactors, bufSqrfFactors, evalSqrfPartF, evalPoint);
bool foundDifferent= false;
Variable z, x= y;
int j= 0;
if (!pass)
{
int lev= 0;
// LCF is non-constant here
CFList bufBufFactors;
CanonicalForm bufF;
for (int i= 0; i < lSecondVarLCs; i++)
{
if (!differentSecondVarLCs [i].isEmpty())
{
bool allConstant= true;
for (iter= differentSecondVarLCs[i]; iter.hasItem(); iter++)
{
if (!iter.getItem().inCoeffDomain())
{
allConstant= false;
y= Variable (iter.getItem().level());
lev= M(y).level();
}
}
if (allConstant)
continue;
bufFactors= differentSecondVarLCs [i];
for (iter= bufFactors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), x, y);
bufF= F;
z= Variable (lev);
bufF= swapvar (bufF, x, z);
bufBufFactors= bufFactors;
evalPoint= CFArray (evaluation.length() - 1);
for (int k= 1; k < evaluation.length(); k++)
{
if (N (Variable (k+1)).level() != y.level())
evalPoint[k-1]= buf[k];
else
evalPoint[k-1]= buf[0];
}
pass= testFactors (bufF, bufBufFactors, alpha, sqrfPartF, bufFactors,
bufSqrfFactors, evalSqrfPartF, evalPoint);
if (pass)
{
foundDifferent= true;
F= bufF;
CFList l= factors;
for (iter= l; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), x, y);
differentSecondVarLCs [i]= l;
j= i;
break;
}
if (!pass && i == lSecondVarLCs - 1)
{
CFList result;
result.append (LCF);
for (int j= 1; j <= factors.length(); j++)
result.append (1);
result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
y= Variable (1);
delete [] bufSqrfFactors;
return result;
}
}
}
}
if (!pass)
{
CFList result;
result.append (LCF);
for (int j= 1; j <= factors.length(); j++)
result.append (1);
result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
y= Variable (1);
delete [] bufSqrfFactors;
return result;
}
else
factors= bufFactors;
bufFactors= factors;
CFMap MM, NN;
dummy [0]= sqrfPartF;
dummy [1]= 1;
compress (dummy, MM, NN);
sqrfPartF= MM (sqrfPartF);
CanonicalForm varsSqrfPartF= getVars (sqrfPartF);
for (CFListIterator iter= factors; iter.hasItem(); iter++)
iter.getItem()= MM (iter.getItem());
CFList evaluation2;
for (int i= 2; i <= varsSqrfPartF.level(); i++)
evaluation2.insert (evalPoint[NN (Variable (i)).level()-2]);
CFList interMedResult;
CanonicalForm oldSqrfPartF= sqrfPartF;
sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
if (factors.length() > 1)
{
CanonicalForm LC1= LC (oldSqrfPartF, 1);
CFList leadingCoeffs;
for (int i= 0; i < factors.length(); i++)
leadingCoeffs.append (LC1);
CFList LC1eval= evaluateAtEval (LC1, evaluation2, 2);
CFList oldFactors= factors;
for (CFListIterator i= oldFactors; i.hasItem(); i++)
i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
bool success= false;
CanonicalForm oldSqrfPartFPowLC= oldSqrfPartF*power(LC1,factors.length()-1);
CFList heuResult;
if (size (oldSqrfPartFPowLC)/getNumVars (oldSqrfPartFPowLC) < 500 &&
LucksWangSparseHeuristic (oldSqrfPartFPowLC,
oldFactors, 2, leadingCoeffs, heuResult))
{
interMedResult= recoverFactors (oldSqrfPartF, heuResult);
if (oldFactors.length() == interMedResult.length())
success= true;
}
if (!success)
{
LC1= LC (evalSqrfPartF.getFirst(), 1);
CFArray leadingCoeffs= CFArray (factors.length());
for (int i= 0; i < factors.length(); i++)
leadingCoeffs[i]= LC1;
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem() *= LC1 (0,2)/Lc (i.getItem());
factors.insert (1);
CanonicalForm
newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
int liftBound= degree (newSqrfPartF,2) + 1;
CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
CFArray Pi;
CFList diophant;
nonMonicHenselLift12 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
leadingCoeffs, false);
if (sqrfPartF.level() > 2)
{
int* liftBounds= new int [sqrfPartF.level() - 1];
bool noOneToOne= false;
CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
LC1= LC (evalSqrfPartF.getLast(), 1);
CFList LCs;
for (int i= 0; i < factors.length(); i++)
LCs.append (LC1);
leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
for (int i= sqrfPartF.level() - 1; i > 2; i--)
{
for (CFListIterator j= LCs; j.hasItem(); j++)
j.getItem()= j.getItem() (0, i + 1);
leadingCoeffs2 [i - 3]= LCs;
}
sqrfPartF *= power (LC1, factors.length()-1);
int liftBoundsLength= sqrfPartF.level() - 1;
for (int i= 0; i < liftBoundsLength; i++)
liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
evalSqrfPartF= evaluateAtZero (sqrfPartF);
evalSqrfPartF.removeFirst();
factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
delete [] leadingCoeffs2;
delete [] liftBounds;
}
for (CFListIterator iter= factors; iter.hasItem(); iter++)
iter.getItem()= reverseShift (iter.getItem(), evaluation2);
interMedResult=
recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2),
factors);
}
}
else
{
CanonicalForm contF=content (oldSqrfPartF,1);
factors= CFList (oldSqrfPartF/contF);
interMedResult= recoverFactors (oldSqrfPartF, factors);
}
for (CFListIterator iter= interMedResult; iter.hasItem(); iter++)
iter.getItem()= NN (iter.getItem());
CFList result;
CFFListIterator k;
for (int i= 0; i < LCFFactors.length(); i++)
{
CanonicalForm tmp= 1;
for (k= bufSqrfFactors[i]; k.hasItem(); k++)
{
int pos= findItem (bufFactors, k.getItem().factor());
if (pos)
tmp *= power (getItem (interMedResult, pos), k.getItem().exp());
}
result.append (tmp);
}
for (CFListIterator i= result; i.hasItem(); i++)
{
F /= i.getItem();
if (foundDifferent)
i.getItem()= swapvar (i.getItem(), x, z);
i.getItem()= N (i.getItem());
}
if (foundDifferent)
{
CFList l= differentSecondVarLCs [j];
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), y, z);
differentSecondVarLCs [j]= l;
F= swapvar (F, x, z);
}
result.insert (N (F));
result= distributeContent (result, differentSecondVarLCs, lSecondVarLCs);
if (!result.getFirst().inCoeffDomain())
{
// prepare input for recursion
if (foundDifferent)
{
for (CFListIterator i= result; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), Variable (2), y);
CFList l= differentSecondVarLCs [j];
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), y, z);
differentSecondVarLCs [j]= l;
}
F= result.getFirst();
int level= 0;
if (foundDifferent)
{
level= y.level() - 2;
for (int i= y.level(); i > 1; i--)
{
if (degree (F,i) > 0)
{
if (y.level() == 3)
level= 0;
else
level= i-3;
}
}
}
lcretry:
if (lSecondVarLCs - level > 0)
{
CFList evaluation2= evaluation;
int j= lSecondVarLCs+2;
CanonicalForm swap;
CFListIterator i;
for (i= evaluation2; i.hasItem(); i++, j--)
{
if (j==y.level())
{
swap= i.getItem();
i.getItem()= evaluation2.getLast();
evaluation2.removeLast();
evaluation2.append (swap);
}
}
CFList newLCs= differentSecondVarLCs[level];
if (newLCs.isEmpty())
{
if (degree (F, level+3) > 0)
{
delete [] bufSqrfFactors;
return result; //TODO handle this case
}
level=level+1;
goto lcretry;
}
i= newLCs;
CFListIterator iter= result;
iter++;
CanonicalForm quot;
for (;iter.hasItem(); iter++, i++)
{
swap= iter.getItem();
if (degree (swap, level+3) > 0)
{
int count= evaluation.length()+1;
for (CFListIterator iter2= evaluation2; iter2.hasItem(); iter2++,
count--)
{
if (count != level+3)
swap= swap (iter2.getItem(), count);
}
if (fdivides (swap, i.getItem(), quot))
i.getItem()= quot;
}
}
CFList * differentSecondVarLCs2= new CFList [lSecondVarLCs - level - 1];
for (int j= level+1; j < lSecondVarLCs; j++)
{
if (degree (F, j+3) > 0)
{
if (!differentSecondVarLCs[j].isEmpty())
{
differentSecondVarLCs2[j - level - 1]= differentSecondVarLCs[j];
i= differentSecondVarLCs2[j-level - 1];
iter=result;
iter++;
for (;iter.hasItem(); iter++, i++)
{
swap= iter.getItem();
if (degree (swap, j+3) > 0)
{
int count= evaluation.length()+1;
for (CFListIterator iter2= evaluation2; iter2.hasItem();iter2++,
count--)
{
if (count != j+3)
swap= swap (iter2.getItem(), count);
}
if (fdivides (swap, i.getItem(), quot))
i.getItem()= quot;
}
}
}
}
}
for (int j= 0; j < level+1; j++)
evaluation2.removeLast();
Variable dummyvar= Variable (1);
CanonicalForm newLCF= result.getFirst();
newLCF=swapvar (newLCF, Variable (2), Variable (level+3));
for (i=newLCs; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
for (int j= 1; j < lSecondVarLCs-level;j++)
{
for (i= differentSecondVarLCs2[j-1]; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), Variable (2+j),
Variable (level+3+j));
newLCF= swapvar (newLCF, Variable (2+j), Variable (level+3+j));
}
CFList recursiveResult=
precomputeLeadingCoeff (newLCF, newLCs, alpha, evaluation2,
differentSecondVarLCs2, lSecondVarLCs - level - 1,
dummyvar);
if (dummyvar.level() != 1)
{
for (i= recursiveResult; i.hasItem(); i++)
i.getItem()= swapvar (i.getItem(), Variable (2), dummyvar);
}
for (i= recursiveResult; i.hasItem(); i++)
{
for (int j= lSecondVarLCs-level-1; j > 0; j--)
i.getItem()=swapvar (i.getItem(), Variable (2+j),
Variable (level+3+j));
i.getItem()= swapvar (i.getItem(), Variable (2), Variable (level+3));
}
if (recursiveResult.getFirst() == result.getFirst())
{
delete [] bufSqrfFactors;
delete [] differentSecondVarLCs2;
return result;
}
else
{
iter=recursiveResult;
i= result;
i.getItem()= iter.getItem();
i++;
iter++;
for (; i.hasItem(); i++, iter++)
i.getItem() *= iter.getItem();
delete [] differentSecondVarLCs2;
}
}
}
else
y= Variable (1);
delete [] bufSqrfFactors;
return result;
}
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
List::removeLast
void removeLast()
Definition ftmpl_list.cc:317
Variable::level
int level() const
Definition factory.h:143
found
bool found
Definition facFactorize.cc:55
evaluateAtZero
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
Definition facFqFactorizeUtil.cc:193
evaluateAtEval
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
Definition facFqFactorizeUtil.cc:206
testFactors
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
Definition facFqFactorize.cc:1385
distributeContent
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
Definition facFqFactorize.cc:1295
nonMonicHenselLift12
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
Definition facHensel.cc:2154
count
int status int void size_t count
Definition si_signals.h:69

## prepareLeadingCoeffs()

void prepareLeadingCoeffs | ( | CFList *& | LCs,
|  | CanonicalForm & | A,
|  | CFList & | Aeval,
|  | int | n,
|  | const CFList & | leadingCoeffs,
|  | const CFList & | biFactors,
|  | const CFList & | evaluation )

normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly

Parameters

  [in,out] | LCs |
  [in,out] | A |
  [in,out] | Aeval |
  [in] | n | level of poly to be factored
  [in] | leadingCoeffs | precomputed leading coeffs
  [in] | biFactors | bivariate factors
  [in] | evaluation | evaluation point

Definition at line 2382 of file facFqFactorize.cc.

{
CFList l= leadingCoeffs;
LCs [n-3]= l;
CFListIterator j;
CFListIterator iter= evaluation;
for (int i= n - 1; i > 2; i--, iter++)
{
for (j= l; j.hasItem(); j++)
j.getItem()= j.getItem() (iter.getItem(), i + 1);
LCs [i - 3]= l;
}
l= LCs [0];
for (CFListIterator i= l; i.hasItem(); i++)
i.getItem()= i.getItem() (iter.getItem(), 3);
CFListIterator ii= biFactors;
CFList normalizeFactor;
for (CFListIterator i= l; i.hasItem(); i++, ii++)
normalizeFactor.append (Lc (LC (ii.getItem(), 1))/Lc (i.getItem()));
for (int i= 0; i < n-2; i++)
{
ii= normalizeFactor;
for (j= LCs [i]; j.hasItem(); j++, ii++)
j.getItem() *= ii.getItem();
}
Aeval= evaluateAtEval (A, evaluation, 2);
CanonicalForm hh= 1/Lc (Aeval.getFirst());
for (iter= Aeval; iter.hasItem(); iter++)
iter.getItem() *= hh;
A *= hh;
}

## prodEval()

CanonicalForm prodEval | ( | const CFList & | l,
|  | const CanonicalForm & | evalPoint,
|  | const Variable & | v )

inline static

Definition at line 2012 of file facFqFactorize.cc.

{
CanonicalForm result= 1;
for (CFListIterator i= l; i.hasItem(); i++)
result *= i.getItem() (evalPoint, v);
return result;
}

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

Parameters

  [in] | factors1 | list of bivariate factors
  [in] | factors2 | list univariate factors
  [in] | s | algorithm starts checking subsets of size s
  [in] | thres | threshold for the size of subsets which are checked
  [in] | evalPoint | evaluation point
  [in] | x | second variable of bivariate factors

Definition at line 2114 of file facFqFactorize.cc.

{
CFList T, S;
T= factors1;
CFList result;
CanonicalForm buf;
int * v= new int [T.length()];
for (int i= 0; i < T.length(); i++)
v[i]= 0;
bool nosubset= false;
CFArray TT;
TT= copy (factors1);
int recombinations= 0;
while (T.length() >= 2*s && s <= thres)
{
while (nosubset == false)
{
if (T.length() == s)
{
delete [] v;
if (recombinations == factors2.length() - 1)
result.append (prod (T));
else
result= Union (result, T);
return result;
}
S= subset (v, s, TT, nosubset);
if (nosubset) break;
buf= prodEval (S, evalPoint, x);
buf /= Lc (buf);
if (find (factors2, buf))
{
recombinations++;
T= Difference (T, S);
result.append (prod (S));
TT= copy (T);
indexUpdate (v, s, T.length(), nosubset);
if (nosubset) break;
}
}
s++;
if (T.length() < 2*s || T.length() == s)
{
if (recombinations == factors2.length() - 1)
result.append (prod (T));
else
result= Union (result, T);
delete [] v;
return result;
}
for (int i= 0; i < T.length(); i++)
v[i]= 0;
nosubset= false;
}
delete [] v;
if (T.length() < 2*s)
{
result= Union (result, T);
return result;
}
return result;
}
prodEval
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
Definition facFqFactorize.cc:2012

## refineBiFactors()

void refineBiFactors | ( | const CanonicalForm & | A,
|  | CFList & | biFactors,
|  | CFList *const & | Aeval,
|  | const CFList & | evaluation,
|  | int | minFactorsLength )

refine a bivariate factorization of A with l factors to one with minFactorsLength if possible

Parameters

  [in] | A | some poly
  [in,out] | biFactors | list of bivariate to be refined, returns refined factors
  [in] | Aeval | list of bivariate factorizations of A wrt different second variables
  [in] | evaluation | the evaluation point
  [in] | minFactorsLength | the minimal number of factors

Definition at line 2335 of file facFqFactorize.cc.

{
CFListIterator iter, iter2;
CanonicalForm evalPoint;
int i;
Variable v;
Variable y= Variable (2);
CFList list;
bool leaveLoop= false;
for (int j= 0; j < A.level() - 2; j++)
{
if (Aeval[j].length() == minFactorsLength)
{
i= A.level();
for (iter= evaluation; iter.hasItem(); iter++, i--)
{
for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
{
if (i == iter2.getItem().level())
{
evalPoint= iter.getItem();
leaveLoop= true;
break;
}
}
if (leaveLoop)
{
leaveLoop= false;
break;
}
}
v= Variable (i);
list= buildUniFactors (Aeval[j], evalPoint, v);
biFactors= recombination (biFactors, list, 1,
biFactors.length() - list.length() + 1,
evaluation.getLast(), y);
return;
}
}
}

## sortByUniFactors()

void sortByUniFactors | ( | CFList *& | Aeval,
|  | int | AevalLength,
|  | CFList & | uniFactors,
|  | CFList & | biFactors,
|  | const CFList & | evaluation )

sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary

Parameters

  [in,out] | Aeval | array of bivariate factors
  [in] | AevalLength | length of Aeval
  [in,out] | uniFactors | univariate factors
  [in,out] | biFactors | bivariate factors
  [in] | evaluation | evaluation point

Definition at line 2251 of file facFqFactorize.cc.

{
CanonicalForm evalPoint;
int i;
CFListIterator iter, iter2;
Variable v;
CFList LCs, buf;
CFArray l;
int pos, index, checklength;
bool leaveLoop=false;
recurse:
for (int j= 0; j < AevalLength; j++)
{
if (!Aeval[j].isEmpty())
{
i= evaluation.length() + 1;
for (iter= evaluation; iter.hasItem(); iter++, i--)
{
for (iter2= Aeval[j]; iter2.hasItem(); iter2++)
{
if (i == iter2.getItem().level())
{
evalPoint= iter.getItem();
leaveLoop= true;
break;
}
}
if (leaveLoop)
{
leaveLoop= false;
break;
}
}
v= Variable (i);
if (Aeval[j].length() > uniFactors.length())
Aeval[j]= recombination (Aeval[j], uniFactors, 1,
Aeval[j].length() - uniFactors.length() + 1,
evalPoint, v);
checklength= biFactors.length();
Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
if (checklength > biFactors.length())
{
uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
Variable (2));
goto recurse;
}
buf= buildUniFactors (Aeval[j], evalPoint, v);
l= CFArray (uniFactors.length());
index= 1;
for (iter= buf; iter.hasItem(); iter++, index++)
{
pos= findItem (uniFactors, iter.getItem());
if (pos)
l[pos-1]= getItem (Aeval[j], index);
}
buf= conv (l);
Aeval [j]= buf;
buf= buildUniFactors (Aeval[j], evalPoint, v);
}
}
}
checkOneToOne
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
Definition facFqFactorize.cc:2046
conv
CFList conv(const CFArray &A)
Definition facFqFactorize.cc:2224

## testFactors()

int testFactors | ( | const CanonicalForm & | G,
|  | const CFList & | uniFactors,
|  | const Variable & | alpha,
|  | CanonicalForm & | sqrfPartF,
|  | CFList & | factors,
|  | CFFList *& | bufSqrfFactors,
|  | CFList & | evalSqrfPartF,
|  | const CFArray & | evalPoint )

Definition at line 1385 of file facFqFactorize.cc.

{
CanonicalForm F= G;
CFFList sqrfFactorization;
if (getCharacteristic() > 0)
sqrfFactorization= squarefreeFactorization (F, alpha);
else
sqrfFactorization= sqrFree (F);
sqrfPartF= 1;
for (CFFListIterator i= sqrfFactorization; i.hasItem(); i++)
sqrfPartF *= i.getItem().factor();
evalSqrfPartF= evaluateAtEval (sqrfPartF, evalPoint);
CanonicalForm test= evalSqrfPartF.getFirst() (evalPoint[0], 2);
if (degree (test) != degree (sqrfPartF, 1) || test.inCoeffDomain())
return 0;
CFFList sqrfFactors;
CanonicalForm tmp;
CFList tmp2;
int k= 0;
factors= uniFactors;
CFFListIterator iter;
for (CFListIterator i= factors; i.hasItem(); i++, k++)
{
tmp= 1;
if (getCharacteristic() > 0)
sqrfFactors= squarefreeFactorization (i.getItem(), alpha);
else
sqrfFactors= sqrFree (i.getItem());
for (iter= sqrfFactors; iter.hasItem(); iter++)
{
tmp2.append (iter.getItem().factor());
tmp *= iter.getItem().factor();
}
i.getItem()= tmp/Lc(tmp);
bufSqrfFactors [k]= sqrfFactors;
}
for (int i= 0; i < factors.length() - 1; i++)
{
for (k= i + 1; k < factors.length(); k++)
{
gcdFreeBasis (bufSqrfFactors [i], bufSqrfFactors[k]);
}
}
factors= CFList();
for (int i= 0; i < uniFactors.length(); i++)
{
if (i == 0)
{
for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
{
if (iter.getItem().factor().inCoeffDomain())
continue;
iter.getItem()= CFFactor (iter.getItem().factor()/
Lc (iter.getItem().factor()),
iter.getItem().exp());
factors.append (iter.getItem().factor());
}
}
else
{
for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
{
if (iter.getItem().factor().inCoeffDomain())
continue;
iter.getItem()= CFFactor (iter.getItem().factor()/
Lc (iter.getItem().factor()),
iter.getItem().exp());
if (!find (factors, iter.getItem().factor()))
factors.append (iter.getItem().factor());
}
}
}
test= prod (factors);
tmp= evalSqrfPartF.getFirst() (evalPoint[0],2);
if (test/Lc (test) != tmp/Lc (tmp))
return 0;
else
return 1;
}
test
CanonicalForm test
Definition cfModGcd.cc:4104
gcdFreeBasis
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
Definition facFqFactorize.cc:1269
squarefreeFactorization
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
Definition facFqSquarefree.cc:181

## TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT | ( | fac_fq_bi_factorizer |  | ) | const &