![]() |
My Project
debian-1:4.1.1-p2+ds-4build2
|
#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... | |
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
Definition in file facHensel.h.
CFList henselLift | ( | const CFList & | eval, |
const CFList & | factors, | ||
int * | l, | ||
int | lLength, | ||
bool | sort = true |
||
) |
Hensel lifting from bivariate to multivariate.
[in] | eval | [in] 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 | [in] bivariate factors, including leading coefficient |
[in] | l | [in] lifting bounds |
[in] | lLength | [in] length of l |
[in] | sort | [in] sort factors by degree in Variable(1) |
Definition at line 1760 of file facHensel.cc.
CFList henselLift | ( | const CFList & | F, |
const CFList & | factors, | ||
const CFList & | MOD, | ||
CFList & | diophant, | ||
CFArray & | Pi, | ||
CFMatrix & | M, | ||
int | lOld, | ||
int | lNew | ||
) |
Hensel lifting.
[in] | F | [in] two compressed, multivariate polys F and G |
[in] | factors | [in] monic multivariate factors including leading coefficient as first element. |
[in] | MOD | [in] a list of powers of Variables of level higher than 1 |
[in,out] | diophant | [in,out] result of multiRecDiophantine() |
[in,out] | Pi | [in,out] stores intermediate results |
[in,out] | M | [in,out] stores intermediate results |
[in] | lOld | [in] lifting precision of F.mvar() |
[in] | lNew | [in] lifting precision of G.mvar() |
Definition at line 1719 of file facHensel.cc.
void henselLift12 | ( | const CanonicalForm & | F, |
CFList & | factors, | ||
int | l, | ||
CFArray & | Pi, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
bool | sort = true |
||
) |
Hensel lift from univariate to bivariate.
[in] | F | [in] compressed, bivariate poly |
[in,out] | factors | [in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient |
[in] | l | [in] lifting precision |
[in,out] | Pi | [in,out] stores intermediate results |
[in,out] | diophant | [in,out] result of diophantine() |
[in,out] | M | [in,out] stores intermediate results |
[in] | sort | [in] sort factors by degree in Variable(1) |
Definition at line 1206 of file facHensel.cc.
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.
[in] | F | [in] compressed, bivariate poly |
[in,out] | factors | [in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient |
[in] | l | [in] lifting precision |
[in,out] | Pi | [in,out] stores intermediate results |
[in,out] | diophant | [in,out] result of diophantine() |
[in,out] | M | [in,out] stores intermediate results |
[in] | b | [in] coeff bound |
[in] | sort | [in] sort factors by degree in Variable(1) |
Definition at line 1148 of file facHensel.cc.
CFList henselLift23 | ( | const CFList & | eval, |
const CFList & | factors, | ||
int * | l, | ||
CFList & | diophant, | ||
CFArray & | Pi, | ||
CFMatrix & | M | ||
) |
Hensel lifting from bivariate to trivariate.
[in] | eval | [in] contains compressed, bivariate as first element and trivariate one as second element |
[in] | factors | [in] monic bivariate factors, including leading coefficient as first element. |
[in] | l | [in] l[0]: precision of bivariate lifting, l[1] as above |
[in,out] | diophant | [in,out] returns the result of biDiophantine() |
[in,out] | Pi | [in,out] stores intermediate results |
[in,out] | M | [in,out] stores intermediate results |
Definition at line 1653 of file facHensel.cc.
void henselLiftResume | ( | const CanonicalForm & | F, |
CFList & | factors, | ||
int | start, | ||
int | end, | ||
CFArray & | Pi, | ||
const CFList & | diophant, | ||
CFMatrix & | M, | ||
const CFList & | MOD | ||
) |
resume Hensel lifting.
[in] | F | [in] compressed, multivariate poly |
[in,out] | 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] | start | [in] starting precision |
[in] | end | [in] end precision |
[in,out] | Pi | [in,out] stores intermediate results |
[in] | diophant | [in] result of multiRecDiophantine() |
[in,out] | M | [in, out] stores intermediate results |
[in] | MOD | [in] a list of powers of Variables of level higher than 1 |
Definition at line 1694 of file facHensel.cc.
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
[in] | F | [in] compressed, bivariate poly |
[in,out] | 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] | start | [in] starting precision |
[in] | end | [in] end precision |
[in,out] | Pi | [in,out] stores intermediate results |
[in] | diophant | [in] result of diophantine |
[in,out] | M | [in,out] stores intermediate results |
[in] | b | [in] coeff bound |
Definition at line 1214 of file facHensel.cc.
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.
[in] | eval | [in] 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 | [in] a list of bivariate factors |
[in] | LCs | [in] leading coefficients, evaluated in the same way as eval |
[in,out] | diophant | [in, out] solution of univariate diophantine equation |
[in,out] | Pi | [in, out] buffer intermediate results |
[in] | liftBound | [in] lifting bounds |
[in] | length | [in] length of lifting bounds |
[in,out] | noOneToOne | [in, out] check for one to one correspondence |
Definition at line 2792 of file facHensel.cc.
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.
[in] | F | [in] a bivariate poly |
[in,out] | factors | [in, out] a list of univariate polys lifted factors |
[in] | l | [in] lift bound |
[in,out] | Pi | [in, out] stores intermediate results |
[in,out] | diophant | [in, out] result of diophantine |
[in,out] | M | [in, out] stores intermediate results |
[in] | LCs | [in] leading coefficients |
[in] | sort | [in] if true factors are sorted by their degree |
Definition at line 2018 of file facHensel.cc.
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
[in] | eval | [in] 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 | [in] bivariate factors |
[in] | l | [in] lift bounds |
[in] | lLength | [in] length of l |
[in] | sort | [in] if true factors are sorted by their degree in Variable(1) |
[in] | LCs1 | [in] a list of evaluated LC of first factor |
[in] | LCs2 | [in] a list of evaluated LC of second factor |
[in] | Pi | [in] intermediate result |
[in] | diophant | [in] result of diophantine |
[in,out] | noOneToOne | [in,out] check for one to one correspondence |
Definition at line 2555 of file facHensel.cc.
sort a list of polynomials by their degree in x.
[in,out] | list | [in, out] list of polys, sorted list |
[in] | x | [in] some Variable |
Definition at line 441 of file facHensel.cc.