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. More...
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. More...
void	henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, bool sort=true)
	Hensel lift from univariate to bivariate. More...
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 More...
CFList	henselLift23 (const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
	Hensel lifting from bivariate to trivariate. More...
void	henselLiftResume (const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
	resume Hensel lifting. More...
CFList	henselLift (const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
	Hensel lifting. More...
CFList	henselLift (const CFList &eval, const CFList &factors, int *l, int lLength, bool sort=true)
	Hensel lifting from bivariate to multivariate. More...
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. More...
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 More...
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. More...

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;
}

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;
}

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);
}

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();
}

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;
}

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 2940 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;
}

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;
}

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 2697 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;
}

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;
  }
}