My Project
Functions
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]evala 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]factorsbivariate factors, including leading coefficient
[in]llifting bounds
[in]lLengthlength of l
[in]sortsort factors by degree in Variable(1)

Definition at line 1892 of file facHensel.cc.

1894 {
1895  CFList diophant;
1896  CFList buf= factors;
1897  buf.insert (LC (eval.getFirst(), 1));
1898  if (sort)
1899  sortList (buf, Variable (1));
1900  CFArray Pi;
1901  CFMatrix M= CFMatrix (l[1], factors.length());
1902  CFList result= henselLift23 (eval, buf, l, diophant, Pi, M);
1903  if (eval.length() == 2)
1904  return result;
1905  CFList MOD;
1906  for (int i= 0; i < 2; i++)
1907  MOD.append (power (Variable (i + 2), l[i]));
1909  j++;
1910  CFList bufEval;
1911  bufEval.append (j.getItem());
1912  j++;
1913 
1914  for (int i= 2; i < lLength && j.hasItem(); i++, j++)
1915  {
1916  result.insert (LC (bufEval.getFirst(), 1));
1917  bufEval.append (j.getItem());
1918  M= CFMatrix (l[i], factors.length());
1919  result= henselLift (bufEval, result, MOD, diophant, Pi, M, l[i - 1], l[i]);
1920  MOD.append (power (Variable (i + 2), l[i]));
1921  bufEval.removeFirst();
1922  }
1923  return result;
1924 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Matrix< CanonicalForm > CFMatrix
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:134
CFList & eval
Definition: facFactorize.cc:47
int j
Definition: facHensel.cc:110
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:1783
fq_nmod_t buf
Definition: facHensel.cc:101
const CanonicalForm & M
Definition: facHensel.cc:97
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:1850
CFList result
Definition: facHensel.cc:126
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449
void sort(CFArray &A, int l=0)
quick sort A

◆ 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]Ftwo compressed, multivariate polys F and G
[in]factorsmonic multivariate factors including leading coefficient as first element.
[in]MODa list of powers of Variables of level higher than 1
[in,out]diophantresult of multiRecDiophantine()
[in,out]Pistores intermediate results
[in,out]Mstores intermediate results
[in]lOldlifting precision of F.mvar()
[in]lNewlifting precision of G.mvar()

Definition at line 1850 of file facHensel.cc.

1852 {
1853  diophant= multiRecDiophantine (F.getFirst(), factors, diophant, MOD, lOld);
1854  int k= 0;
1855  CFArray bufFactors= CFArray (factors.length());
1856  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1857  {
1858  if (k == 0)
1859  bufFactors[k]= LC (F.getLast(), 1);
1860  else
1861  bufFactors[k]= i.getItem();
1862  }
1863  CFList buf= factors;
1864  buf.removeFirst();
1865  buf.insert (LC (F.getLast(), 1));
1866  CFListIterator i= buf;
1867  i++;
1868  Variable y= F.getLast().mvar();
1869  Variable x= F.getFirst().mvar();
1870  CanonicalForm xToLOld= power (x, lOld);
1871  Pi [0]= mod (Pi[0], xToLOld);
1872  M (1, 1)= Pi [0];
1873  k= 1;
1874  if (i.hasItem())
1875  i++;
1876  for (; i.hasItem(); i++, k++)
1877  {
1878  Pi [k]= mod (Pi [k], xToLOld);
1879  M (1, k + 1)= Pi [k];
1880  }
1881 
1882  for (int d= 1; d < lNew; d++)
1883  henselStep (F.getLast(), buf, bufFactors, diophant, M, Pi, d, MOD);
1884  CFList result;
1885  for (k= 1; k < factors.length(); k++)
1886  result.append (bufFactors[k]);
1887  return result;
1888 }
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:99
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
T getLast() const
Definition: ftmpl_list.cc:309
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
Variable x
Definition: facHensel.cc:127
static int mod(const CFList &L, const CanonicalForm &p)
Definition: facHensel.cc:252
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
Definition: facHensel.cc:1468
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:1557

◆ 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]Fcompressed, bivariate poly
[in,out]factorsmonic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]llifting precision
[in,out]Pistores intermediate results
[in,out]diophantresult of diophantine()
[in,out]Mstores intermediate results
[in]sortsort factors by degree in Variable(1)

Definition at line 1332 of file facHensel.cc.

1334 {
1335  modpk dummy= modpk();
1336  henselLift12 (F, factors, l, Pi, diophant, M, dummy, sort);
1337 }
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
return modpk(p, k)
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:1272

◆ 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]Fcompressed, bivariate poly
[in,out]factorsmonic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]llifting precision
[in,out]Pistores intermediate results
[in,out]diophantresult of diophantine()
[in,out]Mstores intermediate results
[in]bcoeff bound
[in]sortsort factors by degree in Variable(1)

Definition at line 1272 of file facHensel.cc.

1274 {
1275  if (sort)
1276  sortList (factors, Variable (1));
1277  Pi= CFArray (factors.length() - 1);
1278  CFListIterator j= factors;
1279  diophant= diophantine (F[0], F, factors, b);
1280  CanonicalForm bufF= F;
1281  if (getCharacteristic() == 0 && b.getp() != 0)
1282  {
1283  Variable v;
1284  bool hasAlgVar= hasFirstAlgVar (F, v);
1285  for (CFListIterator i= factors; i.hasItem() && !hasAlgVar; i++)
1286  hasAlgVar= hasFirstAlgVar (i.getItem(), v);
1287  Variable w;
1288  bool hasAlgVar2= false;
1289  for (CFListIterator i= diophant; i.hasItem() && !hasAlgVar2; i++)
1290  hasAlgVar2= hasFirstAlgVar (i.getItem(), w);
1291  if (hasAlgVar && hasAlgVar2 && v!=w)
1292  {
1293  bufF= replacevar (bufF, v, w);
1294  for (CFListIterator i= factors; i.hasItem(); i++)
1295  i.getItem()= replacevar (i.getItem(), v, w);
1296  }
1297  }
1298 
1299  DEBOUTLN (cerr, "diophant= " << diophant);
1300  j++;
1301  Pi [0]= mulNTL (j.getItem(), mod (factors.getFirst(), F.mvar()), b);
1302  M (1, 1)= Pi [0];
1303  int i= 1;
1304  if (j.hasItem())
1305  j++;
1306  for (; j.hasItem(); j++, i++)
1307  {
1308  Pi [i]= mulNTL (Pi [i - 1], j.getItem(), b);
1309  M (1, i + 1)= Pi [i];
1310  }
1311  CFArray bufFactors= CFArray (factors.length());
1312  i= 0;
1313  for (CFListIterator k= factors; k.hasItem(); i++, k++)
1314  {
1315  if (i == 0)
1316  bufFactors[i]= mod (k.getItem(), F.mvar());
1317  else
1318  bufFactors[i]= k.getItem();
1319  }
1320  for (i= 1; i < l; i++)
1321  henselStep12 (bufF, factors, bufFactors, diophant, M, Pi, i, b);
1322 
1323  CFListIterator k= factors;
1324  for (i= 0; i < factors.length (); i++, k++)
1325  k.getItem()= bufFactors[i];
1326  factors.removeFirst();
1327 }
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
CanonicalForm b
Definition: cfModGcd.cc:4105
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
const CanonicalForm & w
Definition: facAbsFact.cc:51
int hasAlgVar(const CanonicalForm &f, const Variable &v)
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CFList diophantine(const CanonicalForm &F, const CFList &factors)
Definition: facHensel.cc:1060
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
Definition: facHensel.cc:289
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:1068
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:411

◆ 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]evalcontains compressed, bivariate as first element and trivariate one as second element
[in]factorsmonic bivariate factors, including leading coefficient as first element.
[in]ll[0]: precision of bivariate lifting, l[1] as above
[in,out]diophantreturns the result of biDiophantine()
[in,out]Pistores intermediate results
[in,out]Mstores intermediate results

Definition at line 1783 of file facHensel.cc.

1785 {
1786  CFList buf= factors;
1787  int k= 0;
1788  int liftBoundBivar= l[k];
1789  diophant= biDiophantine (eval.getFirst(), buf, liftBoundBivar);
1790  CFList MOD;
1791  MOD.append (power (Variable (2), liftBoundBivar));
1792  CFArray bufFactors= CFArray (factors.length());
1793  k= 0;
1795  j++;
1796  buf.removeFirst();
1797  buf.insert (LC (j.getItem(), 1));
1798  for (CFListIterator i= buf; i.hasItem(); i++, k++)
1799  bufFactors[k]= i.getItem();
1800  Pi= CFArray (factors.length() - 1);
1801  CFListIterator i= buf;
1802  i++;
1803  Variable y= j.getItem().mvar();
1804  Pi [0]= mulMod (i.getItem(), mod (buf.getFirst(), y), MOD);
1805  M (1, 1)= Pi [0];
1806  k= 1;
1807  if (i.hasItem())
1808  i++;
1809  for (; i.hasItem(); i++, k++)
1810  {
1811  Pi [k]= mulMod (Pi [k - 1], i.getItem(), MOD);
1812  M (1, k + 1)= Pi [k];
1813  }
1814 
1815  for (int d= 1; d < l[1]; d++)
1816  henselStep (j.getItem(), buf, bufFactors, diophant, M, Pi, d, MOD);
1817  CFList result;
1818  for (k= 1; k < factors.length(); k++)
1819  result.append (bufFactors[k]);
1820  return result;
1821 }
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
Definition: facHensel.cc:1367
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:3080

◆ 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]Fcompressed, multivariate poly
[in,out]factorsmonic multivariate factors lifted to precision F.mvar()^start, including leading coefficient as first element. Returns factors lifted to precision F.mvar()^end
[in]startstarting precision
[in]endend precision
[in,out]Pistores intermediate results
[in]diophantresult of multiRecDiophantine()
[in,out]Mstores intermediate results
[in]MODa list of powers of Variables of level higher than 1

Definition at line 1825 of file facHensel.cc.

1828 {
1829  CFArray bufFactors= CFArray (factors.length());
1830  int i= 0;
1831  CanonicalForm xToStart= power (F.mvar(), start);
1832  for (CFListIterator k= factors; k.hasItem(); k++, i++)
1833  {
1834  if (i == 0)
1835  bufFactors[i]= mod (k.getItem(), xToStart);
1836  else
1837  bufFactors[i]= k.getItem();
1838  }
1839  for (i= start; i < end; i++)
1840  henselStep (F, factors, bufFactors, diophant, M, Pi, i, MOD);
1841 
1842  CFListIterator k= factors;
1843  for (i= 0; i < factors.length(); k++, i++)
1844  k.getItem()= bufFactors [i];
1845  factors.removeFirst();
1846  return;
1847 }

◆ 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]Fcompressed, bivariate poly
[in,out]factorsmonic factors of F, lifted to precision start, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]startstarting precision
[in]endend precision
[in,out]Pistores intermediate results
[in]diophantresult of diophantine
[in,out]Mstores intermediate results
[in]bcoeff bound

Definition at line 1341 of file facHensel.cc.

1344 {
1345  CFArray bufFactors= CFArray (factors.length());
1346  int i= 0;
1347  CanonicalForm xToStart= power (F.mvar(), start);
1348  for (CFListIterator k= factors; k.hasItem(); k++, i++)
1349  {
1350  if (i == 0)
1351  bufFactors[i]= mod (k.getItem(), xToStart);
1352  else
1353  bufFactors[i]= k.getItem();
1354  }
1355  for (i= start; i < end; i++)
1356  henselStep12 (F, factors, bufFactors, diophant, M, Pi, i, b);
1357 
1358  CFListIterator k= factors;
1359  for (i= 0; i < factors.length(); k++, i++)
1360  k.getItem()= bufFactors [i];
1361  factors.removeFirst();
1362  return;
1363 }

◆ 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]evala 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]factorsa list of bivariate factors
[in]LCsleading coefficients, evaluated in the same way as eval
[in,out]diophantsolution of univariate diophantine equation
[in,out]Pibuffer intermediate results
[in]liftBoundlifting bounds
[in]lengthlength of lifting bounds
[in,out]noOneToOnecheck for one to one correspondence

Definition at line 2938 of file facHensel.cc.

2942 {
2943  CFList bufDiophant= diophant;
2944  CFList buf= factors;
2945  CFArray bufPi= Pi;
2946  CFMatrix M= CFMatrix (liftBound[1], factors.length() - 1);
2947  int k= 0;
2948 
2949  TIMING_START (hensel23);
2950  CFList result=
2951  nonMonicHenselLift23 (eval.getFirst(), factors, LCs [0], diophant, bufPi,
2952  liftBound[1], liftBound[0], noOneToOne);
2953  TIMING_END_AND_PRINT (hensel23, "time for 23: ");
2954 
2955  if (noOneToOne)
2956  return CFList();
2957 
2958  if (eval.length() == 1)
2959  return result;
2960 
2961  k++;
2962  CFList MOD;
2963  for (int i= 0; i < 2; i++)
2964  MOD.append (power (Variable (i + 2), liftBound[i]));
2965 
2967  CFList bufEval;
2968  bufEval.append (j.getItem());
2969  j++;
2970 
2971  for (int i= 2; i <= length && j.hasItem(); i++, j++, k++)
2972  {
2973  bufEval.append (j.getItem());
2974  M= CFMatrix (liftBound[i], factors.length() - 1);
2975  TIMING_START (hensel);
2976  result= nonMonicHenselLift (bufEval, result, LCs [i-1], diophant, bufPi, M,
2977  liftBound[i-1], liftBound[i], MOD, noOneToOne);
2978  TIMING_END_AND_PRINT (hensel, "time for further hensel: ");
2979  if (noOneToOne)
2980  return result;
2981  MOD.append (power (Variable (i + 2), liftBound[i]));
2982  bufEval.removeFirst();
2983  }
2984 
2985  return result;
2986 }
List< CanonicalForm > CFList
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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:2853
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
Definition: facHensel.cc:2749
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257

◆ 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]Fa bivariate poly
[in,out]factorsa list of univariate polys lifted factors
[in]llift bound
[in,out]Pistores intermediate results
[in,out]diophantresult of diophantine
[in,out]Mstores intermediate results
[in]LCsleading coefficients
[in]sortif true factors are sorted by their degree

Definition at line 2152 of file facHensel.cc.

2155 {
2156  if (sort)
2157  sortList (factors, Variable (1));
2158  Pi= CFArray (factors.length() - 2);
2159  CFList bufFactors2= factors;
2160  bufFactors2.removeFirst();
2161  diophant= diophantine (F[0], bufFactors2);
2162  DEBOUTLN (cerr, "diophant= " << diophant);
2163 
2164  CFArray bufFactors= CFArray (bufFactors2.length());
2165  int i= 0;
2166  for (CFListIterator k= bufFactors2; k.hasItem(); i++, k++)
2167  bufFactors[i]= replaceLc (k.getItem(), LCs [i]);
2168 
2169  Variable x= F.mvar();
2170  if (degree (bufFactors[0], x) > 0 && degree (bufFactors [1], x) > 0)
2171  {
2172  M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
2173  Pi [0]= M (1, 1) + (mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
2174  mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*x;
2175  }
2176  else if (degree (bufFactors[0], x) > 0)
2177  {
2178  M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1]);
2179  Pi [0]= M (1, 1) +
2180  mulNTL (bufFactors [0] [1], bufFactors[1])*x;
2181  }
2182  else if (degree (bufFactors[1], x) > 0)
2183  {
2184  M (1, 1)= mulNTL (bufFactors [0], bufFactors[1] [0]);
2185  Pi [0]= M (1, 1) +
2186  mulNTL (bufFactors [0], bufFactors[1] [1])*x;
2187  }
2188  else
2189  {
2190  M (1, 1)= mulNTL (bufFactors [0], bufFactors[1]);
2191  Pi [0]= M (1, 1);
2192  }
2193 
2194  for (i= 1; i < Pi.size(); i++)
2195  {
2196  if (degree (Pi[i-1], x) > 0 && degree (bufFactors [i+1], x) > 0)
2197  {
2198  M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors[i+1] [0]);
2199  Pi [i]= M (1,i+1) + (mulNTL (Pi[i-1] [1], bufFactors[i+1] [0]) +
2200  mulNTL (Pi[i-1] [0], bufFactors [i+1] [1]))*x;
2201  }
2202  else if (degree (Pi[i-1], x) > 0)
2203  {
2204  M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors [i+1]);
2205  Pi [i]= M(1,i+1) + mulNTL (Pi[i-1] [1], bufFactors[i+1])*x;
2206  }
2207  else if (degree (bufFactors[i+1], x) > 0)
2208  {
2209  M (1,i+1)= mulNTL (Pi[i-1], bufFactors [i+1] [0]);
2210  Pi [i]= M (1,i+1) + mulNTL (Pi[i-1], bufFactors[i+1] [1])*x;
2211  }
2212  else
2213  {
2214  M (1,i+1)= mulNTL (Pi [i-1], bufFactors [i+1]);
2215  Pi [i]= M (1,i+1);
2216  }
2217  }
2218 
2219  for (i= 1; i < l; i++)
2220  nonMonicHenselStep12 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs);
2221 
2222  factors= CFList();
2223  for (i= 0; i < bufFactors.size(); i++)
2224  factors.append (bufFactors[i]);
2225  return;
2226 }
int degree(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
Definition: facHensel.cc:1930
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]evala 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]factorsbivariate factors
[in]llift bounds
[in]lLengthlength of l
[in]sortif true factors are sorted by their degree in Variable(1)
[in]LCs1a list of evaluated LC of first factor
[in]LCs2a list of evaluated LC of second factor
[in]Piintermediate result
[in]diophantresult of diophantine
[in,out]noOneToOnecheck for one to one correspondence

Definition at line 2695 of file facHensel.cc.

2698 {
2699  CFList bufDiophant= diophant;
2700  CFList buf= factors;
2701  if (sort)
2702  sortList (buf, Variable (1));
2703  CFArray bufPi= Pi;
2704  CFMatrix M= CFMatrix (l[1], factors.length());
2705  CFList result=
2706  nonMonicHenselLift232(eval, buf, l, bufDiophant, bufPi, M, LCs1, LCs2, bad);
2707  if (bad)
2708  return CFList();
2709 
2710  if (eval.length() == 2)
2711  return result;
2712  CFList MOD;
2713  for (int i= 0; i < 2; i++)
2714  MOD.append (power (Variable (i + 2), l[i]));
2716  j++;
2717  CFList bufEval;
2718  bufEval.append (j.getItem());
2719  j++;
2720  CFListIterator jj= LCs1;
2721  CFListIterator jjj= LCs2;
2722  CFList bufLCs1, bufLCs2;
2723  jj++, jjj++;
2724  bufLCs1.append (jj.getItem());
2725  bufLCs2.append (jjj.getItem());
2726  jj++, jjj++;
2727 
2728  for (int i= 2; i < lLength && j.hasItem(); i++, j++, jj++, jjj++)
2729  {
2730  bufEval.append (j.getItem());
2731  bufLCs1.append (jj.getItem());
2732  bufLCs2.append (jjj.getItem());
2733  M= CFMatrix (l[i], factors.length());
2734  result= nonMonicHenselLift2 (bufEval, result, MOD, bufDiophant, bufPi, M,
2735  l[i - 1], l[i], bufLCs1, bufLCs2, bad);
2736  if (bad)
2737  return CFList();
2738  MOD.append (power (Variable (i + 2), l[i]));
2739  bufEval.removeFirst();
2740  bufLCs1.removeFirst();
2741  bufLCs2.removeFirst();
2742  }
2743  return result;
2744 }
T & getItem() const
Definition: ftmpl_list.cc:431
bool bad
Definition: facFactorize.cc:64
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:2630
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:2566

◆ sortList()

void sortList ( CFList list,
const Variable x 
)

sort a list of polynomials by their degree in x.

Parameters
[in,out]listlist of polys, sorted list
[in]xsome Variable

Definition at line 449 of file facHensel.cc.

450 {
451  int l= 1;
452  int k= 1;
455  for (CFListIterator i= list; l <= list.length(); i++, l++)
456  {
457  for (CFListIterator j= list; k <= list.length() - l; k++)
458  {
459  m= j;
460  m++;
461  if (degree (j.getItem(), x) > degree (m.getItem(), x))
462  {
463  buf= m.getItem();
464  m.getItem()= j.getItem();
465  j.getItem()= buf;
466  j++;
467  j.getItem()= m.getItem();
468  }
469  else
470  j++;
471  }
472  k= 1;
473  }
474 }
int m
Definition: cfEzgcd.cc:128