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

This file defines functions for Hensel lifting. More...

`#include "cf_assert.h"`
`#include "debug.h"`
`#include "timing.h"`
`#include "canonicalform.h"`
`#include "fac_util.h"`

Go to the source code of this file.

## Functions

void | sortList (CFList &list, const Variable &x)
| sort a list of polynomials by their degree in x.
void | henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort=true)
| Hensel lift from univariate to bivariate.
void | henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, bool sort=true)
| Hensel lift from univariate to bivariate.
void | henselLiftResume12 (const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b=modpk())
| resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)^start and lifts them to precision Variable (2)^end
CFList | henselLift23 (const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
| Hensel lifting from bivariate to trivariate.
void | henselLiftResume (const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
| resume Hensel lifting.
CFList | henselLift (const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
| Hensel lifting.
CFList | henselLift (const CFList &eval, const CFList &factors, int *l, int lLength, bool sort=true)
| Hensel lifting from bivariate to multivariate.
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.
CFList | nonMonicHenselLift2 (const CFList &eval, const CFList &factors, int *l, int lLength, bool sort, const CFList &LCs1, const CFList &LCs2, const CFArray &Pi, const CFList &diophant, bool &noOneToOne)
| two factor Hensel lifting from bivariate to multivariate, factors need not to be monic
CFList | nonMonicHenselLift (const CFList &eval, const CFList &factors, CFList *const &LCs, CFList &diophant, CFArray &Pi, int *liftBound, int length, bool &noOneToOne)
| Hensel lifting of non monic factors, needs correct leading coefficients of factors and a one to one corresponds between bivariate and multivariate factors to succeed.

## Detailed Description

This file defines functions for Hensel lifting.

ABSTRACT: function are used for bi- and multivariate factorization over finite fields. Described in "Efficient Multivariate Factorization over Finite Fields" by L. Bernardin & M. Monagon and "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn

Author
  Martin Lee

Definition in file facHensel.h.

## Function Documentation

## henselLift() [1/2]

CFList henselLift | ( | const CFList & | eval,
|  | const CFList & | factors,
|  | int * | l,
|  | int | lLength,
|  | bool | sort = true )

Hensel lifting from bivariate to multivariate.

Returns
  henselLift returns a list of lifted factors

See also
  henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()

Parameters

  [in] | eval | a list of polynomials the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed bivariate poly.
  [in] | factors | bivariate factors, including leading coefficient
  [in] | l | lifting bounds
  [in] | lLength | length of l
  [in] | sort | sort factors by degree in Variable(1)

Definition at line 1894 of file facHensel.cc.

{
CFList diophant;
CFList buf= factors;
buf.insert (LC (eval.getFirst(), 1));
if (sort)
sortList (buf, Variable (1));
CFArray Pi;
CFMatrix M= CFMatrix (l[1], factors.length());
CFList result= henselLift23 (eval, buf, l, diophant, Pi, M);
if (eval.length() == 2)
return result;
CFList MOD;
for (int i= 0; i < 2; i++)
MOD.append (power (Variable (i + 2), l[i]));
CFListIterator j= eval;
j++;
CFList bufEval;
bufEval.append (j.getItem());
j++;
for (int i= 2; i < lLength && j.hasItem(); i++, j++)
{
result.insert (LC (bufEval.getFirst(), 1));
bufEval.append (j.getItem());
M= CFMatrix (l[i], factors.length());
result= henselLift (bufEval, result, MOD, diophant, Pi, M, l[i - 1], l[i]);
MOD.append (power (Variable (i + 2), l[i]));
bufEval.removeFirst();
}
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
eval
CFList & eval
Definition facFactorize.cc:47
j
int j
Definition facHensel.cc:110
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
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition facHensel.cc:449
buf
int status int void * buf
Definition si_signals.h:69
M
#define M
Definition sirandom.c:25

## henselLift() [2/2]

CFList henselLift | ( | const CFList & | F,
|  | const CFList & | factors,
|  | const CFList & | MOD,
|  | CFList & | diophant,
|  | CFArray & | Pi,
|  | CFMatrix & | M,
|  | int | lOld,
|  | int | lNew )

Hensel lifting.

Returns
  henselLift returns a list of polynomials lifted to precision F.getLast().mvar()^l_new

See also
  henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()

Parameters

  [in] | F | two compressed, multivariate polys F and G
  [in] | factors | monic multivariate factors including leading coefficient as first element.
  [in] | MOD | a list of powers of Variables of level higher than 1
  [in,out] | diophant | result of multiRecDiophantine()
  [in,out] | Pi | stores intermediate results
  [in,out] | M | stores intermediate results
  [in] | lOld | lifting precision of F.mvar()
  [in] | lNew | lifting precision of G.mvar()

Definition at line 1852 of file facHensel.cc.

{
diophant= multiRecDiophantine (F.getFirst(), factors, diophant, MOD, lOld);
int k= 0;
CFArray bufFactors= CFArray (factors.length());
for (CFListIterator i= factors; i.hasItem(); i++, k++)
{
if (k == 0)
bufFactors[k]= LC (F.getLast(), 1);
else
bufFactors[k]= i.getItem();
}
CFList buf= factors;
buf.removeFirst();
buf.insert (LC (F.getLast(), 1));
CFListIterator i= buf;
i++;
Variable y= F.getLast().mvar();
Variable x= F.getFirst().mvar();
CanonicalForm xToLOld= power (x, lOld);
Pi [0]= mod (Pi[0], xToLOld);
M (1, 1)= Pi [0];
k= 1;
if (i.hasItem())
i++;
for (; i.hasItem(); i++, k++)
{
Pi [k]= mod (Pi [k], xToLOld);
M (1, k + 1)= Pi [k];
}
for (int d= 1; d < lNew; d++)
henselStep (F.getLast(), buf, bufFactors, diophant, M, Pi, d, MOD);
CFList result;
for (k= 1; k < factors.length(); k++)
result.append (bufFactors[k]);
return result;
}
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
CanonicalForm
factory's main class
Definition canonicalform.h:86
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
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
mod
static int mod(const CFList &L, const CanonicalForm &p)
Definition facHensel.cc:252
M
const CanonicalForm & M
Definition facHensel.cc:97
multiRecDiophantine
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
Definition facHensel.cc:1470
henselStep
static void henselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFList &MOD)
Definition facHensel.cc:1559

## henselLift12() [1/2]

void henselLift12 | ( | const CanonicalForm & | F,
|  | CFList & | factors,
|  | int | l,
|  | CFArray & | Pi,
|  | CFList & | diophant,
|  | CFMatrix & | M,
|  | bool | sort = true )

Hensel lift from univariate to bivariate.

See also
  henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()

Parameters

  [in] | F | compressed, bivariate poly
  [in,out] | factors | monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
  [in] | l | lifting precision
  [in,out] | Pi | stores intermediate results
  [in,out] | diophant | result of diophantine()
  [in,out] | M | stores intermediate results
  [in] | sort | sort factors by degree in Variable(1)

Definition at line 1334 of file facHensel.cc.

{
modpk dummy= modpk();
henselLift12 (F, factors, l, Pi, diophant, M, dummy, sort);
}
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk
return modpk(p, k)
henselLift12
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
Definition facHensel.cc:1274

## henselLift12() [2/2]

void henselLift12 | ( | const CanonicalForm & | F,
|  | CFList & | factors,
|  | int | l,
|  | CFArray & | Pi,
|  | CFList & | diophant,
|  | CFMatrix & | M,
|  | modpk & | b,
|  | bool | sort = true )

Hensel lift from univariate to bivariate.

See also
  henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()

Parameters

  [in] | F | compressed, bivariate poly
  [in,out] | factors | monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
  [in] | l | lifting precision
  [in,out] | Pi | stores intermediate results
  [in,out] | diophant | result of diophantine()
  [in,out] | M | stores intermediate results
  [in] | b | coeff bound
  [in] | sort | sort factors by degree in Variable(1)

Definition at line 1274 of file facHensel.cc.

{
if (sort)
sortList (factors, Variable (1));
Pi= CFArray (factors.length() - 1);
CFListIterator j= factors;
diophant= diophantine (F[0], F, factors, b);
CanonicalForm bufF= F;
if (getCharacteristic() == 0 && b.getp() != 0)
{
Variable v;
bool hasAlgVar= hasFirstAlgVar (F, v);
for (CFListIterator i= factors; i.hasItem() && !hasAlgVar; i++)
hasAlgVar= hasFirstAlgVar (i.getItem(), v);
Variable w;
bool hasAlgVar2= false;
for (CFListIterator i= diophant; i.hasItem() && !hasAlgVar2; i++)
hasAlgVar2= hasFirstAlgVar (i.getItem(), w);
if (hasAlgVar && hasAlgVar2 && v!=w)
{
bufF= replacevar (bufF, v, w);
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem()= replacevar (i.getItem(), v, w);
}
}
DEBOUTLN (cerr, "diophant= " << diophant);
j++;
Pi [0]= mulNTL (j.getItem(), mod (factors.getFirst(), F.mvar()), b);
M (1, 1)= Pi [0];
int i= 1;
if (j.hasItem())
j++;
for (; j.hasItem(); j++, i++)
{
Pi [i]= mulNTL (Pi [i - 1], j.getItem(), b);
M (1, i + 1)= Pi [i];
}
CFArray bufFactors= CFArray (factors.length());
i= 0;
for (CFListIterator k= factors; k.hasItem(); i++, k++)
{
if (i == 0)
bufFactors[i]= mod (k.getItem(), F.mvar());
else
bufFactors[i]= k.getItem();
}
for (i= 1; i < l; i++)
henselStep12 (bufF, factors, bufFactors, diophant, M, Pi, i, b);
CFListIterator k= factors;
for (i= 0; i < factors.length (); i++, k++)
k.getItem()= bufFactors[i];
factors.removeFirst();
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
b
CanonicalForm b
Definition cfModGcd.cc:4111
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
w
const CanonicalForm & w
Definition facAbsFact.cc:51
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
diophantine
CFList diophantine(const CanonicalForm &F, const CFList &factors)
Definition facHensel.cc:1062
replacevar
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
Definition facHensel.cc:289
henselStep12
void henselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b)
Definition facHensel.cc:1070
mulNTL
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition facMul.cc:417

## henselLift23()

CFList henselLift23 | ( | const CFList & | eval,
|  | const CFList & | factors,
|  | int * | l,
|  | CFList & | diophant,
|  | CFArray & | Pi,
|  | CFMatrix & | M )

Hensel lifting from bivariate to trivariate.

Returns
  henselLift23 returns a list of polynomials lifted to precision Variable (3)^l[1]

See also
  henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()

Parameters

  [in] | eval | contains compressed, bivariate as first element and trivariate one as second element
  [in] | factors | monic bivariate factors, including leading coefficient as first element.
  [in] | l | l[0]: precision of bivariate lifting, l[1] as above
  [in,out] | diophant | returns the result of biDiophantine()
  [in,out] | Pi | stores intermediate results
  [in,out] | M | stores intermediate results

Definition at line 1785 of file facHensel.cc.

{
CFList buf= factors;
int k= 0;
int liftBoundBivar= l[k];
diophant= biDiophantine (eval.getFirst(), buf, liftBoundBivar);
CFList MOD;
MOD.append (power (Variable (2), liftBoundBivar));
CFArray bufFactors= CFArray (factors.length());
k= 0;
CFListIterator j= eval;
j++;
buf.removeFirst();
buf.insert (LC (j.getItem(), 1));
for (CFListIterator i= buf; i.hasItem(); i++, k++)
bufFactors[k]= i.getItem();
Pi= CFArray (factors.length() - 1);
CFListIterator i= buf;
i++;
Variable y= j.getItem().mvar();
Pi [0]= mulMod (i.getItem(), mod (buf.getFirst(), y), MOD);
M (1, 1)= Pi [0];
k= 1;
if (i.hasItem())
i++;
for (; i.hasItem(); i++, k++)
{
Pi [k]= mulMod (Pi [k - 1], i.getItem(), MOD);
M (1, k + 1)= Pi [k];
}
for (int d= 1; d < l[1]; d++)
henselStep (j.getItem(), buf, bufFactors, diophant, M, Pi, d, MOD);
CFList result;
for (k= 1; k < factors.length(); k++)
result.append (bufFactors[k]);
return result;
}
biDiophantine
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
Definition facHensel.cc:1369
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition facMul.cc:3086

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

See also
  henselLift12(), henselLiftResume12(), henselLift23(), henselLift()

Parameters

  [in] | F | compressed, multivariate poly
  [in,out] | factors | monic multivariate factors lifted to precision F.mvar()^start, including leading coefficient as first element. Returns factors lifted to precision F.mvar()^end
  [in] | start | starting precision
  [in] | end | end precision
  [in,out] | Pi | stores intermediate results
  [in] | diophant | result of multiRecDiophantine()
  [in,out] | M | stores intermediate results
  [in] | MOD | a list of powers of Variables of level higher than 1

Definition at line 1827 of file facHensel.cc.

{
CFArray bufFactors= CFArray (factors.length());
int i= 0;
CanonicalForm xToStart= power (F.mvar(), start);
for (CFListIterator k= factors; k.hasItem(); k++, i++)
{
if (i == 0)
bufFactors[i]= mod (k.getItem(), xToStart);
else
bufFactors[i]= k.getItem();
}
for (i= start; i < end; i++)
henselStep (F, factors, bufFactors, diophant, M, Pi, i, MOD);
CFListIterator k= factors;
for (i= 0; i < factors.length(); k++, i++)
k.getItem()= bufFactors [i];
factors.removeFirst();
return;
}

## henselLiftResume12()

void henselLiftResume12 | ( | const CanonicalForm & | F,
|  | CFList & | factors,
|  | int | start,
|  | int | end,
|  | CFArray & | Pi,
|  | const CFList & | diophant,
|  | CFMatrix & | M,
|  | const modpk & | b = modpk() )

resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)^start and lifts them to precision Variable (2)^end

See also
  henselLift12(), henselLift23(), henselLiftResume(), henselLift()

Parameters

  [in] | F | compressed, bivariate poly
  [in,out] | factors | monic factors of F, lifted to precision start, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
  [in] | start | starting precision
  [in] | end | end precision
  [in,out] | Pi | stores intermediate results
  [in] | diophant | result of diophantine
  [in,out] | M | stores intermediate results
  [in] | b | coeff bound

Definition at line 1343 of file facHensel.cc.

{
CFArray bufFactors= CFArray (factors.length());
int i= 0;
CanonicalForm xToStart= power (F.mvar(), start);
for (CFListIterator k= factors; k.hasItem(); k++, i++)
{
if (i == 0)
bufFactors[i]= mod (k.getItem(), xToStart);
else
bufFactors[i]= k.getItem();
}
for (i= start; i < end; i++)
henselStep12 (F, factors, bufFactors, diophant, M, Pi, i, b);
CFListIterator k= factors;
for (i= 0; i < factors.length(); k++, i++)
k.getItem()= bufFactors [i];
factors.removeFirst();
return;
}

## nonMonicHenselLift()

CFList nonMonicHenselLift | ( | const CFList & | eval,
|  | const CFList & | factors,
|  | CFList *const & | LCs,
|  | CFList & | diophant,
|  | CFArray & | Pi,
|  | int * | liftBound,
|  | int | length,
|  | bool & | noOneToOne )

Hensel lifting of non monic factors, needs correct leading coefficients of factors and a one to one corresponds between bivariate and multivariate factors to succeed.

Returns
  nonMonicHenselLift returns a list of lifted factors such that prod (factors) == eval.getLast() if there is a one to one correspondence

Parameters

  [in] | eval | a list of polys the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed poly in 3 variables
  [in] | factors | a list of bivariate factors
  [in] | LCs | leading coefficients, evaluated in the same way as eval
  [in,out] | diophant | solution of univariate diophantine equation
  [in,out] | Pi | buffer intermediate results
  [in] | liftBound | lifting bounds
  [in] | length | length of lifting bounds
  [in,out] | noOneToOne | check for one to one correspondence

Definition at line 2941 of file facHensel.cc.

{
CFList bufDiophant= diophant;
CFList buf= factors;
CFArray bufPi= Pi;
CFMatrix M= CFMatrix (liftBound[1], factors.length() - 1);
int k= 0;
TIMING_START (hensel23);
CFList result=
nonMonicHenselLift23 (eval.getFirst(), factors, LCs [0], diophant, bufPi,
liftBound[1], liftBound[0], noOneToOne);
TIMING_END_AND_PRINT (hensel23, "time for 23: ");
if (noOneToOne)
return CFList();
if (eval.length() == 1)
return result;
k++;
CFList MOD;
for (int i= 0; i < 2; i++)
MOD.append (power (Variable (i + 2), liftBound[i]));
CFListIterator j= eval;
CFList bufEval;
bufEval.append (j.getItem());
j++;
for (int i= 2; i <= length && j.hasItem(); i++, j++, k++)
{
bufEval.append (j.getItem());
M= CFMatrix (liftBound[i], factors.length() - 1);
TIMING_START (hensel);
result= nonMonicHenselLift (bufEval, result, LCs [i-1], diophant, bufPi, M,
liftBound[i-1], liftBound[i], MOD, noOneToOne);
TIMING_END_AND_PRINT (hensel, "time for further hensel: ");
if (noOneToOne)
return result;
MOD.append (power (Variable (i + 2), liftBound[i]));
bufEval.removeFirst();
}
return result;
}
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
nonMonicHenselLift23
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
Definition facHensel.cc:2752
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
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

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

Parameters

  [in] | F | a bivariate poly
  [in,out] | factors | a list of univariate polys lifted factors
  [in] | l | lift bound
  [in,out] | Pi | stores intermediate results
  [in,out] | diophant | result of diophantine
  [in,out] | M | stores intermediate results
  [in] | LCs | leading coefficients
  [in] | sort | if true factors are sorted by their degree

Definition at line 2154 of file facHensel.cc.

{
if (sort)
sortList (factors, Variable (1));
Pi= CFArray (factors.length() - 2);
CFList bufFactors2= factors;
bufFactors2.removeFirst();
diophant= diophantine (F[0], bufFactors2);
DEBOUTLN (cerr, "diophant= " << diophant);
CFArray bufFactors= CFArray (bufFactors2.length());
int i= 0;
for (CFListIterator k= bufFactors2; k.hasItem(); i++, k++)
bufFactors[i]= replaceLc (k.getItem(), LCs [i]);
Variable x= F.mvar();
if (degree (bufFactors[0], x) > 0 && degree (bufFactors [1], x) > 0)
{
M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
Pi [0]= M (1, 1) + (mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*x;
}
else if (degree (bufFactors[0], x) > 0)
{
M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1]);
Pi [0]= M (1, 1) +
mulNTL (bufFactors [0] [1], bufFactors[1])*x;
}
else if (degree (bufFactors[1], x) > 0)
{
M (1, 1)= mulNTL (bufFactors [0], bufFactors[1] [0]);
Pi [0]= M (1, 1) +
mulNTL (bufFactors [0], bufFactors[1] [1])*x;
}
else
{
M (1, 1)= mulNTL (bufFactors [0], bufFactors[1]);
Pi [0]= M (1, 1);
}
for (i= 1; i < Pi.size(); i++)
{
if (degree (Pi[i-1], x) > 0 && degree (bufFactors [i+1], x) > 0)
{
M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors[i+1] [0]);
Pi [i]= M (1,i+1) + (mulNTL (Pi[i-1] [1], bufFactors[i+1] [0]) +
mulNTL (Pi[i-1] [0], bufFactors [i+1] [1]))*x;
}
else if (degree (Pi[i-1], x) > 0)
{
M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors [i+1]);
Pi [i]= M(1,i+1) + mulNTL (Pi[i-1] [1], bufFactors[i+1])*x;
}
else if (degree (bufFactors[i+1], x) > 0)
{
M (1,i+1)= mulNTL (Pi[i-1], bufFactors [i+1] [0]);
Pi [i]= M (1,i+1) + mulNTL (Pi[i-1], bufFactors[i+1] [1])*x;
}
else
{
M (1,i+1)= mulNTL (Pi [i-1], bufFactors [i+1]);
Pi [i]= M (1,i+1);
}
}
for (i= 1; i < l; i++)
nonMonicHenselStep12 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs);
factors= CFList();
for (i= 0; i < bufFactors.size(); i++)
factors.append (bufFactors[i]);
return;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
Array::size
int size() const
Definition ftmpl_array.cc:92
nonMonicHenselStep12
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
Definition facHensel.cc:1932
replaceLc
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition fac_util.cc:90

## nonMonicHenselLift2()

CFList nonMonicHenselLift2 | ( | const CFList & | eval,
|  | const CFList & | factors,
|  | int * | l,
|  | int | lLength,
|  | bool | sort,
|  | const CFList & | LCs1,
|  | const CFList & | LCs2,
|  | const CFArray & | Pi,
|  | const CFList & | diophant,
|  | bool & | noOneToOne )

two factor Hensel lifting from bivariate to multivariate, factors need not to be monic

Returns
  henselLift122 returns a list of lifted factors

Parameters

  [in] | eval | a list of polynomials the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed bivariate poly.
  [in] | factors | bivariate factors
  [in] | l | lift bounds
  [in] | lLength | length of l
  [in] | sort | if true factors are sorted by their degree in Variable(1)
  [in] | LCs1 | a list of evaluated LC of first factor
  [in] | LCs2 | a list of evaluated LC of second factor
  [in] | Pi | intermediate result
  [in] | diophant | result of diophantine
  [in,out] | noOneToOne | check for one to one correspondence

Definition at line 2698 of file facHensel.cc.

{
CFList bufDiophant= diophant;
CFList buf= factors;
if (sort)
sortList (buf, Variable (1));
CFArray bufPi= Pi;
CFMatrix M= CFMatrix (l[1], factors.length());
CFList result=
nonMonicHenselLift232(eval, buf, l, bufDiophant, bufPi, M, LCs1, LCs2, bad);
if (bad)
return CFList();
if (eval.length() == 2)
return result;
CFList MOD;
for (int i= 0; i < 2; i++)
MOD.append (power (Variable (i + 2), l[i]));
CFListIterator j= eval;
j++;
CFList bufEval;
bufEval.append (j.getItem());
j++;
CFListIterator jj= LCs1;
CFListIterator jjj= LCs2;
CFList bufLCs1, bufLCs2;
jj++, jjj++;
bufLCs1.append (jj.getItem());
bufLCs2.append (jjj.getItem());
jj++, jjj++;
for (int i= 2; i < lLength && j.hasItem(); i++, j++, jj++, jjj++)
{
bufEval.append (j.getItem());
bufLCs1.append (jj.getItem());
bufLCs2.append (jjj.getItem());
M= CFMatrix (l[i], factors.length());
result= nonMonicHenselLift2 (bufEval, result, MOD, bufDiophant, bufPi, M,
l[i - 1], l[i], bufLCs1, bufLCs2, bad);
if (bad)
return CFList();
MOD.append (power (Variable (i + 2), l[i]));
bufEval.removeFirst();
bufLCs1.removeFirst();
bufLCs2.removeFirst();
}
return result;
}
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
bad
bool bad
Definition facFactorize.cc:64
nonMonicHenselLift2
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
Definition facHensel.cc:2633
nonMonicHenselLift232
CFList nonMonicHenselLift232(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, bool &bad)
Definition facHensel.cc:2569

## sortList()

void sortList | ( | CFList & | list,
|  | const Variable & | x )

sort a list of polynomials by their degree in x.

Parameters

  [in,out] | list | list of polys, sorted list
  [in] | x | some Variable

Definition at line 449 of file facHensel.cc.

{
int l= 1;
int k= 1;
CanonicalForm buf;
CFListIterator m;
for (CFListIterator i= list; l <= list.length(); i++, l++)
{
for (CFListIterator j= list; k <= list.length() - l; k++)
{
m= j;
m++;
if (degree (j.getItem(), x) > degree (m.getItem(), x))
{
buf= m.getItem();
m.getItem()= j.getItem();
j.getItem()= buf;
j++;
j.getItem()= m.getItem();
}
else
j++;
}
k= 1;
}
}
m
int m
Definition cfEzgcd.cc:128