My Project
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]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 1894 of file facHensel.cc.

1896{
1897 CFList diophant;
1898 CFList buf= factors;
1899 buf.insert (LC (eval.getFirst(), 1));
1900 if (sort)
1901 sortList (buf, Variable (1));
1902 CFArray Pi;
1903 CFMatrix M= CFMatrix (l[1], factors.length());
1904 CFList result= henselLift23 (eval, buf, l, diophant, Pi, M);
1905 if (eval.length() == 2)
1906 return result;
1907 CFList MOD;
1908 for (int i= 0; i < 2; i++)
1909 MOD.append (power (Variable (i + 2), l[i]));
1911 j++;
1912 CFList bufEval;
1913 bufEval.append (j.getItem());
1914 j++;
1915
1916 for (int i= 2; i < lLength && j.hasItem(); i++, j++)
1917 {
1918 result.insert (LC (bufEval.getFirst(), 1));
1919 bufEval.append (j.getItem());
1920 M= CFMatrix (l[i], factors.length());
1921 result= henselLift (bufEval, result, MOD, diophant, Pi, M, l[i - 1], l[i]);
1922 MOD.append (power (Variable (i + 2), l[i]));
1923 bufEval.removeFirst();
1924 }
1925 return result;
1926}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Array< CanonicalForm > CFArray
Matrix< CanonicalForm > CFMatrix
ListIterator< CanonicalForm > CFListIterator
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
int l
Definition cfEzgcd.cc:100
int i
Definition cfEzgcd.cc:132
static void sort(int **points, int sizePoints)
T getFirst() const
void removeFirst()
int length() const
void append(const T &)
factory's class for variables
Definition factory.h:127
return result
CFList & eval
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.
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition facHensel.cc:449
int status int void * buf
Definition si_signals.h:69
#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]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
diophant[in,out] result of multiRecDiophantine()
Pi[in,out] stores intermediate results
M[in,out] stores intermediate results
[in]lOldlifting precision of F.mvar()
[in]lNewlifting precision of G.mvar()

Definition at line 1852 of file facHensel.cc.

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

◆ 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
factors[in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]llifting precision
Pi[in,out] stores intermediate results
diophant[in,out] result of diophantine()
M[in,out] stores intermediate results
[in]sortsort factors by degree in Variable(1)

Definition at line 1334 of file facHensel.cc.

1336{
1337 modpk dummy= modpk();
1338 henselLift12 (F, factors, l, Pi, diophant, M, dummy, sort);
1339}
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.

◆ 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
factors[in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]llifting precision
Pi[in,out] stores intermediate results
diophant[in,out] result of diophantine()
M[in,out] stores intermediate results
[in]bcoeff bound
[in]sortsort factors by degree in Variable(1)

Definition at line 1274 of file facHensel.cc.

1276{
1277 if (sort)
1278 sortList (factors, Variable (1));
1279 Pi= CFArray (factors.length() - 1);
1280 CFListIterator j= factors;
1281 diophant= diophantine (F[0], F, factors, b);
1282 CanonicalForm bufF= F;
1283 if (getCharacteristic() == 0 && b.getp() != 0)
1284 {
1285 Variable v;
1286 bool hasAlgVar= hasFirstAlgVar (F, v);
1287 for (CFListIterator i= factors; i.hasItem() && !hasAlgVar; i++)
1288 hasAlgVar= hasFirstAlgVar (i.getItem(), v);
1289 Variable w;
1290 bool hasAlgVar2= false;
1291 for (CFListIterator i= diophant; i.hasItem() && !hasAlgVar2; i++)
1292 hasAlgVar2= hasFirstAlgVar (i.getItem(), w);
1293 if (hasAlgVar && hasAlgVar2 && v!=w)
1294 {
1295 bufF= replacevar (bufF, v, w);
1296 for (CFListIterator i= factors; i.hasItem(); i++)
1297 i.getItem()= replacevar (i.getItem(), v, w);
1298 }
1299 }
1300
1301 DEBOUTLN (cerr, "diophant= " << diophant);
1302 j++;
1303 Pi [0]= mulNTL (j.getItem(), mod (factors.getFirst(), F.mvar()), b);
1304 M (1, 1)= Pi [0];
1305 int i= 1;
1306 if (j.hasItem())
1307 j++;
1308 for (; j.hasItem(); j++, i++)
1309 {
1310 Pi [i]= mulNTL (Pi [i - 1], j.getItem(), b);
1311 M (1, i + 1)= Pi [i];
1312 }
1313 CFArray bufFactors= CFArray (factors.length());
1314 i= 0;
1315 for (CFListIterator k= factors; k.hasItem(); i++, k++)
1316 {
1317 if (i == 0)
1318 bufFactors[i]= mod (k.getItem(), F.mvar());
1319 else
1320 bufFactors[i]= k.getItem();
1321 }
1322 for (i= 1; i < l; i++)
1323 henselStep12 (bufF, factors, bufFactors, diophant, M, Pi, i, b);
1324
1325 CFListIterator k= factors;
1326 for (i= 0; i < factors.length (); i++, k++)
1327 k.getItem()= bufFactors[i];
1328 factors.removeFirst();
1329}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
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:4111
#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)
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)
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]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
diophant[in,out] returns the result of biDiophantine()
Pi[in,out] stores intermediate results
M[in,out] stores intermediate results

Definition at line 1785 of file facHensel.cc.

1787{
1788 CFList buf= factors;
1789 int k= 0;
1790 int liftBoundBivar= l[k];
1791 diophant= biDiophantine (eval.getFirst(), buf, liftBoundBivar);
1792 CFList MOD;
1793 MOD.append (power (Variable (2), liftBoundBivar));
1794 CFArray bufFactors= CFArray (factors.length());
1795 k= 0;
1797 j++;
1798 buf.removeFirst();
1799 buf.insert (LC (j.getItem(), 1));
1800 for (CFListIterator i= buf; i.hasItem(); i++, k++)
1801 bufFactors[k]= i.getItem();
1802 Pi= CFArray (factors.length() - 1);
1804 i++;
1805 Variable y= j.getItem().mvar();
1806 Pi [0]= mulMod (i.getItem(), mod (buf.getFirst(), y), MOD);
1807 M (1, 1)= Pi [0];
1808 k= 1;
1809 if (i.hasItem())
1810 i++;
1811 for (; i.hasItem(); i++, k++)
1812 {
1813 Pi [k]= mulMod (Pi [k - 1], i.getItem(), MOD);
1814 M (1, k + 1)= Pi [k];
1815 }
1816
1817 for (int d= 1; d < l[1]; d++)
1818 henselStep (j.getItem(), buf, bufFactors, diophant, M, Pi, d, MOD);
1819 CFList result;
1820 for (k= 1; k < factors.length(); k++)
1821 result.append (bufFactors[k]);
1822 return result;
1823}
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
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]Fcompressed, multivariate poly
factors[in,out] monic 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
Pi[in,out] stores intermediate results
[in]diophantresult of multiRecDiophantine()
M[in, out] stores intermediate results
[in]MODa list of powers of Variables of level higher than 1

Definition at line 1827 of file facHensel.cc.

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

◆ 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
factors[in,out] monic 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
Pi[in,out] stores intermediate results
[in]diophantresult of diophantine
M[in,out] stores intermediate results
[in]bcoeff bound

Definition at line 1343 of file facHensel.cc.

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

◆ 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
diophant[in, out] solution of univariate diophantine equation
Pi[in, out] buffer intermediate results
[in]liftBoundlifting bounds
[in]lengthlength of lifting bounds
noOneToOne[in, out] check for one to one correspondence

Definition at line 2941 of file facHensel.cc.

2945{
2946 CFList bufDiophant= diophant;
2947 CFList buf= factors;
2948 CFArray bufPi= Pi;
2949 CFMatrix M= CFMatrix (liftBound[1], factors.length() - 1);
2950 int k= 0;
2951
2952 TIMING_START (hensel23);
2953 CFList result=
2954 nonMonicHenselLift23 (eval.getFirst(), factors, LCs [0], diophant, bufPi,
2955 liftBound[1], liftBound[0], noOneToOne);
2956 TIMING_END_AND_PRINT (hensel23, "time for 23: ");
2957
2958 if (noOneToOne)
2959 return CFList();
2960
2961 if (eval.length() == 1)
2962 return result;
2963
2964 k++;
2965 CFList MOD;
2966 for (int i= 0; i < 2; i++)
2967 MOD.append (power (Variable (i + 2), liftBound[i]));
2968
2970 CFList bufEval;
2971 bufEval.append (j.getItem());
2972 j++;
2973
2974 for (int i= 2; i <= length && j.hasItem(); i++, j++, k++)
2975 {
2976 bufEval.append (j.getItem());
2977 M= CFMatrix (liftBound[i], factors.length() - 1);
2978 TIMING_START (hensel);
2979 result= nonMonicHenselLift (bufEval, result, LCs [i-1], diophant, bufPi, M,
2980 liftBound[i-1], liftBound[i], MOD, noOneToOne);
2981 TIMING_END_AND_PRINT (hensel, "time for further hensel: ");
2982 if (noOneToOne)
2983 return result;
2984 MOD.append (power (Variable (i + 2), liftBound[i]));
2985 bufEval.removeFirst();
2986 }
2987
2988 return result;
2989}
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)
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
#define TIMING_START(t)
Definition timing.h:92
#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]Fa bivariate poly
factors[in, out] a list of univariate polys lifted factors
[in]llift bound
Pi[in, out] stores intermediate results
diophant[in, out] result of diophantine
M[in, out] stores intermediate results
[in]LCsleading coefficients
[in]sortif true factors are sorted by their degree

Definition at line 2154 of file facHensel.cc.

2157{
2158 if (sort)
2159 sortList (factors, Variable (1));
2160 Pi= CFArray (factors.length() - 2);
2161 CFList bufFactors2= factors;
2162 bufFactors2.removeFirst();
2163 diophant= diophantine (F[0], bufFactors2);
2164 DEBOUTLN (cerr, "diophant= " << diophant);
2165
2166 CFArray bufFactors= CFArray (bufFactors2.length());
2167 int i= 0;
2168 for (CFListIterator k= bufFactors2; k.hasItem(); i++, k++)
2169 bufFactors[i]= replaceLc (k.getItem(), LCs [i]);
2170
2171 Variable x= F.mvar();
2172 if (degree (bufFactors[0], x) > 0 && degree (bufFactors [1], x) > 0)
2173 {
2174 M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
2175 Pi [0]= M (1, 1) + (mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
2176 mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*x;
2177 }
2178 else if (degree (bufFactors[0], x) > 0)
2179 {
2180 M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1]);
2181 Pi [0]= M (1, 1) +
2182 mulNTL (bufFactors [0] [1], bufFactors[1])*x;
2183 }
2184 else if (degree (bufFactors[1], x) > 0)
2185 {
2186 M (1, 1)= mulNTL (bufFactors [0], bufFactors[1] [0]);
2187 Pi [0]= M (1, 1) +
2188 mulNTL (bufFactors [0], bufFactors[1] [1])*x;
2189 }
2190 else
2191 {
2192 M (1, 1)= mulNTL (bufFactors [0], bufFactors[1]);
2193 Pi [0]= M (1, 1);
2194 }
2195
2196 for (i= 1; i < Pi.size(); i++)
2197 {
2198 if (degree (Pi[i-1], x) > 0 && degree (bufFactors [i+1], x) > 0)
2199 {
2200 M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors[i+1] [0]);
2201 Pi [i]= M (1,i+1) + (mulNTL (Pi[i-1] [1], bufFactors[i+1] [0]) +
2202 mulNTL (Pi[i-1] [0], bufFactors [i+1] [1]))*x;
2203 }
2204 else if (degree (Pi[i-1], x) > 0)
2205 {
2206 M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors [i+1]);
2207 Pi [i]= M(1,i+1) + mulNTL (Pi[i-1] [1], bufFactors[i+1])*x;
2208 }
2209 else if (degree (bufFactors[i+1], x) > 0)
2210 {
2211 M (1,i+1)= mulNTL (Pi[i-1], bufFactors [i+1] [0]);
2212 Pi [i]= M (1,i+1) + mulNTL (Pi[i-1], bufFactors[i+1] [1])*x;
2213 }
2214 else
2215 {
2216 M (1,i+1)= mulNTL (Pi [i-1], bufFactors [i+1]);
2217 Pi [i]= M (1,i+1);
2218 }
2219 }
2220
2221 for (i= 1; i < l; i++)
2222 nonMonicHenselStep12 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs);
2223
2224 factors= CFList();
2225 for (i= 0; i < bufFactors.size(); i++)
2226 factors.append (bufFactors[i]);
2227 return;
2228}
int degree(const CanonicalForm &f)
int size() const
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
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
noOneToOne[in,out] check for one to one correspondence

Definition at line 2698 of file facHensel.cc.

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

◆ sortList()

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

sort a list of polynomials by their degree in x.

Parameters
list[in, out] list 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