 |
My Project
UNKNOWN_GIT_VERSION
|
This file implements functions to lift factors via Hensel lifting.
More...
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "cfGcdAlgExt.h"
#include "facHensel.h"
#include "facMul.h"
#include "fac_util.h"
#include "cf_algorithm.h"
#include "cf_primes.h"
#include "facBivar.h"
#include "cfNTLzzpEXGCD.h"
#include "cfUnivarGcd.h"
#include <NTL/lzz_pEX.h>
#include "NTLconvert.h"
#include "FLINTconvert.h"
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (diotime) TIMING_DEFINE_PRINT(product1) TIMING_DEFINE_PRINT(product2) TIMING_DEFINE_PRINT(hensel23) TIMING_DEFINE_PRINT(hensel) static CFList productsFLINT(const CFList &factors |
|
| nmod_poly_init (FLINTmipo, getCharacteristic()) |
|
| convertFacCF2nmod_poly_t (FLINTmipo, M) |
|
| fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z") |
|
| for (CFListIterator i=factors;i.hasItem();i++, j++) |
|
| fq_nmod_poly_init (prod, fq_con) |
|
| for (j=0;j< factors.length();j++) |
|
| nmod_poly_clear (FLINTmipo) |
|
| fq_nmod_poly_clear (prod, fq_con) |
|
| fq_nmod_ctx_clear (fq_con) |
|
static void | tryDiophantine (CFList &result, const CanonicalForm &F, const CFList &factors, const CanonicalForm &M, bool &fail) |
|
static CFList | mapinto (const CFList &L) |
|
static int | mod (const CFList &L, const CanonicalForm &p) |
|
static void | chineseRemainder (const CFList &x1, const CanonicalForm &q1, const CFList &x2, const CanonicalForm &q2, CFList &xnew, CanonicalForm &qnew) |
|
static CFList | Farey (const CFList &L, const CanonicalForm &q) |
|
static CFList | replacevar (const CFList &L, const Variable &a, const Variable &b) |
|
CFList | modularDiophant (const CanonicalForm &f, const CFList &factors, const CanonicalForm &M) |
|
void | sortList (CFList &list, const Variable &x) |
| sort a list of polynomials by their degree in x. More...
|
|
CFList | diophantine (const CanonicalForm &F, const CFList &factors) |
|
CFList | diophantineHensel (const CanonicalForm &F, const CFList &factors, const modpk &b) |
|
CFList | diophantineHenselQa (const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha) |
| solve mod over by p-adic lifting More...
|
|
CFList | diophantineQa (const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha) |
| solve mod over by first computing mod and if no zero divisor occurred compute it mod More...
|
|
CFList | diophantine (const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b) |
|
void | henselStep12 (const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b) |
|
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. More...
|
|
void | henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, bool sort) |
| 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) |
| 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 | biDiophantine (const CanonicalForm &F, const CFList &factors, int d) |
|
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) |
|
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) |
| Hensel lifting from bivariate to multivariate. More...
|
|
void | nonMonicHenselStep12 (const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &) |
|
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 | diophantine (const CFList &recResult, const CFList &factors, const CFList &products, const CFList &M, const CanonicalForm &E, bool &bad) |
| solve mod M, products contains More...
|
|
void | nonMonicHenselStep (const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, const CFList &products, int j, const CFList &MOD, bool &noOneToOne) |
|
CanonicalForm | replaceLC (const CanonicalForm &F, const CanonicalForm &c) |
|
CFList | nonMonicHenselLift232 (const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, 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 | 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 &bad) |
| two factor Hensel lifting from bivariate to multivariate, factors need not to be monic More...
|
|
CFList | nonMonicHenselLift23 (const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad) |
|
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 | 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 implements functions to lift factors via Hensel lifting.
ABSTRACT: Hensel lifting is 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.cc.
◆ biDiophantine()
Definition at line 1239 of file facHensel.cc.
1252 i.getItem()=
mod (
i.getItem(),
y);
1263 bufFactors [
k]=
i.getItem();
1273 for (
int l= 0;
l < factors.
length();
l++)
1288 e -=
i.getItem()*
j.getItem();
1296 for (
int i= 1;
i < d;
i++)
1308 for (;
j.hasItem();
j++,
k++,
l++, ii++)
1310 g= coeffE*
j.getItem();
1311 if (
degree (bufFactors[ii],
y) <= 0)
1312 g=
mod (
g, bufFactors[ii]);
1314 g=
mod (
g, bufFactors[ii][0]);
1317 DEBOUTLN (cerr,
"mod (e, power (y, i + 1))= " <<
◆ chineseRemainder()
◆ convertFacCF2nmod_poly_t()
convertFacCF2nmod_poly_t |
( |
FLINTmipo |
, |
|
|
M |
|
|
) |
| |
◆ diophantine() [1/3]
◆ diophantine() [2/3]
◆ diophantine() [3/3]
solve
mod M, products contains
Definition at line 2098 of file facHensel.cc.
2109 ASSERT (
E.isUnivariate() ||
E.inCoeffDomain(),
2110 "constant or univariate poly expected");
2111 ASSERT (
i.getItem().isUnivariate() ||
i.getItem().inCoeffDomain(),
2112 "constant or univariate poly expected");
2113 ASSERT (
j.getItem().isUnivariate() ||
j.getItem().inCoeffDomain(),
2114 "constant or univariate poly expected");
2121 CFList bufFactors= factors;
2123 i.getItem()=
mod (
i.getItem(),
y);
2124 CFList bufProducts= products;
2126 i.getItem()=
mod (
i.getItem(),
y);
2139 e -=
j.getItem()*
i.getItem();
2144 for (
int i= 1;
i < d;
i++)
2153 recDiophantine=
diophantine (recResult, bufFactors, bufProducts,
buf,
2158 for (
j= recDiophantine;
j.hasItem();
j++,
k++,
l++)
2160 k.getItem() +=
j.getItem()*
power (
y,
i);
2161 e -=
l.getItem()*(
j.getItem()*
power (
y,
i));
◆ diophantineHensel()
Definition at line 472 of file facHensel.cc.
479 recResult=
mapinto (recResult);
487 bufFactors[
k]=
i.getItem() (0);
489 bufFactors [
k]=
i.getItem();
495 for (
int l= 0;
l < factors.
length();
l++)
501 tmp=
mulNTL (tmp, bufFactors[
l]);
514 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
522 recResult=
mapinto (recResult);
528 for (
int i= 1;
i < d;
i++)
530 coeffE=
div (e, modulus);
541 for (;
j.hasItem();
j++,
k++,
l++, ii++)
544 g=
modNTL (coeffE, bufFactors[ii]);
548 k.getItem() +=
g.mapinto()*modulus;
549 e -=
mulNTL (
g.mapinto(), b2 (
l.getItem()), b2)*modulus;
◆ diophantineHenselQa()
solve
mod
over
by p-adic lifting
Definition at line 564 of file facHensel.cc.
573 bool mipoHasDen=
false;
587 modMipo /=
lc (modMipo);
599 if (bb.
getk() >
b.getk() )
b=bb;
606 recResult=
mapinto (recResult);
615 bufFactors[
k]=
i.getItem() (0);
617 bufFactors [
k]=
i.getItem();
624 for (
int l= 0;
l < factors.
length();
l++)
629 tmp=
mulNTL (tmp, bufFactors[
l]);
652 modMipo /=
lc (modMipo);
659 bufFactors [
k]= bufFactors[
k].mapinto();
666 for (;
j.hasItem();
j++)
672 j.getItem()=
b(
j.getItem()*
b.inverse(
lc(
j.getItem())));
680 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
701 recResult=
mapinto (recResult);
712 for (
int i= 1;
i < d;
i++)
714 coeffE=
div (e, modulus);
737 for (;
j.hasItem();
j++,
k++,
l++, ii++)
740 g=
modNTL (coeffE, bufFactors[ii]);
749 b2 (
l.getItem()), b2)*modulus;
757 b2 (
l.getItem()), b2)*modulus;
◆ diophantineQa()
solve
mod
over
by first computing mod
and if no zero divisor occurred compute it mod
Definition at line 776 of file facHensel.cc.
785 bool mipoHasDen=
false;
799 modMipo /=
lc (modMipo);
811 if (bb.
getk() >
b.getk() )
b=bb;
836 CFList bufFactors= factors;
840 for (;
i.hasItem();
i++)
858 ZZ_pE::init (NTLmipo);
859 ZZ_pEX NTLS, NTLT, NTLbuf3;
862 XGCD (NTLbuf3, NTLS, NTLT, NTLbuf1, NTLbuf2);
867 for (;
i.hasItem();
i++)
879 j.getItem()=
modNTL (
j.getItem(),
k.getItem(),
b);
◆ Farey()
◆ for() [1/2]
Definition at line 107 of file facHensel.cc.
109 if (
i.getItem().inCoeffDomain())
◆ for() [2/2]
Definition at line 124 of file facHensel.cc.
128 for (
int i= 0;
i < factors.length();
i++,
k++)
◆ fq_nmod_ctx_clear()
◆ fq_nmod_ctx_init_modulus()
fq_nmod_ctx_init_modulus |
( |
fq_con |
, |
|
|
FLINTmipo |
, |
|
|
"Z" |
|
|
) |
| |
◆ fq_nmod_poly_clear()
◆ fq_nmod_poly_init()
◆ henselLift() [1/2]
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 1760 of file facHensel.cc.
1774 for (
int i= 0;
i < 2;
i++)
1782 for (
int i= 2;
i < lLength &&
j.hasItem();
i++,
j++)
◆ henselLift() [2/2]
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 1719 of file facHensel.cc.
1730 bufFactors[
k]=
i.getItem();
1740 Pi [0]=
mod (Pi[0], xToLOld);
1745 for (;
i.hasItem();
i++,
k++)
1747 Pi [
k]=
mod (Pi [
k], xToLOld);
1748 M (1,
k + 1)= Pi [
k];
1751 for (
int d= 1; d < lNew; d++)
◆ henselLift12() [1/2]
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 1206 of file facHensel.cc.
◆ henselLift12() [2/2]
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 1148 of file facHensel.cc.
1164 bool hasAlgVar2=
false;
1175 DEBOUTLN (cerr,
"diophant= " << diophant);
1182 for (;
j.hasItem();
j++,
i++)
1185 M (1,
i + 1)= Pi [
i];
1192 bufFactors[
i]=
mod (
k.getItem(), F.
mvar());
1194 bufFactors[
i]=
k.getItem();
1196 for (
i= 1;
i <
l;
i++)
1201 k.getItem()= bufFactors[
i];
◆ henselLift23()
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 1653 of file facHensel.cc.
1658 int liftBoundBivar=
l[
k];
1667 buf.insert (
LC (
j.getItem(), 1));
1669 bufFactors[
k]=
i.getItem();
1679 for (;
i.hasItem();
i++,
k++)
1681 Pi [
k]=
mulMod (Pi [
k - 1],
i.getItem(), MOD);
1682 M (1,
k + 1)= Pi [
k];
1685 for (
int d= 1; d <
l[1]; d++)
◆ henselLiftResume()
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 1694 of file facHensel.cc.
1704 bufFactors[
i]=
mod (
k.getItem(), xToStart);
1706 bufFactors[
i]=
k.getItem();
1708 for (
i= start;
i < end;
i++)
1709 henselStep (F, factors, bufFactors, diophant,
M, Pi,
i, MOD);
1713 k.getItem()= bufFactors [
i];
◆ henselLiftResume12()
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 1214 of file facHensel.cc.
1224 bufFactors[
i]=
mod (
k.getItem(), xToStart);
1226 bufFactors[
i]=
k.getItem();
1228 for (
i= start;
i < end;
i++)
1233 k.getItem()= bufFactors [
i];
◆ henselStep()
Definition at line 1428 of file facHensel.cc.
1441 for (
int i= 0;
i < factors.
length();
i++)
1450 test2=
mod (test2, MOD);
1451 DEBOUTLN (cerr,
"test in henselStep= " << test2);
1458 for (
int i= 0;
i < factors.
length();
i++)
1463 test *= bufFactors[
i];
1468 DEBOUTLN (cerr,
"test in henselStep= " << test2);
1472 E= F[
j] - Pi [factors.
length() - 2] [
j];
1487 divrem (
E, bufFactors[
k] [0], dummy, rest1, MOD);
1492 divrem (
E, bufFactors[
k], dummy, rest1, MOD);
1502 bufFactors[
k] += xToJ*
buf[
k];
1505 int degBuf0=
degree (bufFactors[0],
x);
1506 int degBuf1=
degree (bufFactors[1],
x);
1507 if (degBuf0 > 0 && degBuf1 > 0)
1508 M (
j + 1, 1)=
mulMod (bufFactors[0] [
j], bufFactors[1] [
j], MOD);
1511 if (degBuf0 > 0 && degBuf1 > 0)
1512 uIZeroJ=
mulMod ((bufFactors[0] [0] + bufFactors[0] [
j]),
1513 (bufFactors[1] [0] +
buf[1]), MOD) -
M(1, 1) -
M(
j + 1, 1);
1514 else if (degBuf0 > 0)
1515 uIZeroJ=
mulMod (bufFactors[0] [
j], bufFactors[1], MOD);
1516 else if (degBuf1 > 0)
1517 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD);
1520 Pi [0] += xToJ*uIZeroJ;
1523 for (
k= 0;
k < factors.
length() - 1;
k++)
1526 one= bufFactors [0];
1527 two= bufFactors [1];
1528 if (degBuf0 > 0 && degBuf1 > 0)
1530 for (
k= 1;
k <= (
j+1)/2;
k++)
1538 (bufFactors[1] [
k] + two.
coeff()), MOD) -
M (
k + 1, 1) -
1546 bufFactors[1] [
k], MOD) -
M (
k + 1, 1);
1551 tmp[0] +=
mulMod (bufFactors[0] [
k], (bufFactors[1] [
k] +
1552 two.
coeff()), MOD) -
M (
k + 1, 1);
1558 tmp[0] +=
M (
k + 1, 1);
1562 Pi [0] += tmp[0]*xToJ*F.
mvar();
1566 for (
int l= 1;
l < factors.
length() - 1;
l++)
1569 degBuf=
degree (bufFactors[
l + 1],
x);
1570 if (degPi > 0 && degBuf > 0)
1571 M (
j + 1,
l + 1)=
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j], MOD);
1574 if (degPi > 0 && degBuf > 0)
1575 Pi [
l] += xToJ*(
mulMod ((Pi [
l - 1] [0] + Pi [
l - 1] [
j]),
1576 (bufFactors[
l + 1] [0] +
buf[
l + 1]), MOD) -
M (
j + 1,
l +1)-
1579 Pi [
l] += xToJ*(
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1], MOD));
1580 else if (degBuf > 0)
1585 if (degPi > 0 && degBuf > 0)
1587 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1] [0], MOD);
1588 uIZeroJ +=
mulMod (Pi [
l - 1] [0],
buf [
l + 1], MOD);
1591 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1], MOD);
1592 else if (degBuf > 0)
1594 uIZeroJ=
mulMod (uIZeroJ, bufFactors [
l + 1] [0], MOD);
1597 Pi[
l] += xToJ*uIZeroJ;
1599 one= bufFactors [
l + 1];
1603 if (degBuf > 0 && degPi > 0)
1614 if (degBuf > 0 && degPi > 0)
1616 for (
k= 1;
k <= (
j+1)/2;
k++)
1624 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1) -
1625 M (
j -
k + 2,
l + 1);
1632 Pi[
l - 1] [
k], MOD) -
M (
k + 1,
l + 1);
1637 tmp[
l] +=
mulMod (bufFactors[
l + 1] [
k],
1638 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1);
1643 tmp[
l] +=
M (
k + 1,
l + 1);
1646 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
◆ henselStep12()
Definition at line 945 of file facHensel.cc.
975 remainder=
modNTL (
E, bufFactors[
k] [0],
b);
990 bufFactors[
k] += xToJ*
buf[
k];
992 bufFactors[
k]=
b(bufFactors[
k]);
996 int degBuf0=
degree (bufFactors[0],
x);
997 int degBuf1=
degree (bufFactors[1],
x);
998 if (degBuf0 > 0 && degBuf1 > 0)
999 M (
j + 1, 1)=
mulNTL (bufFactors[0] [
j], bufFactors[1] [
j],
b);
1002 if (degBuf0 > 0 && degBuf1 > 0)
1003 uIZeroJ=
mulNTL ((bufFactors[0] [0] + bufFactors[0] [
j]),
1004 (bufFactors[1] [0] +
buf[1]),
b) -
M(1, 1) -
M(
j + 1, 1);
1005 else if (degBuf0 > 0)
1006 uIZeroJ=
mulNTL (bufFactors[0] [
j], bufFactors[1],
b);
1007 else if (degBuf1 > 0)
1012 uIZeroJ=
b (uIZeroJ);
1013 Pi [0] += xToJ*uIZeroJ;
1018 for (
k= 0;
k < factors.
length() - 1;
k++)
1021 one= bufFactors [0];
1022 two= bufFactors [1];
1023 if (degBuf0 > 0 && degBuf1 > 0)
1025 for (
k= 1;
k <= (
j+1)/2;
k++)
1032 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), (bufFactors[1][
k]+
1033 two.
coeff()),
b) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
1039 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), bufFactors[1][
k],
b)
1045 tmp[0] +=
mulNTL (bufFactors[0][
k], (bufFactors[1][
k]+two.
coeff()),
b)
1052 tmp[0] +=
M (
k + 1, 1);
1058 Pi [0] += tmp[0]*xToJ*F.
mvar();
1062 for (
int l= 1;
l < factors.
length() - 1;
l++)
1065 degBuf=
degree (bufFactors[
l + 1],
x);
1066 if (degPi > 0 && degBuf > 0)
1067 M (
j + 1,
l + 1)=
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j],
b);
1070 if (degPi > 0 && degBuf > 0)
1071 Pi [
l] += xToJ*(
mulNTL (Pi [
l - 1] [0] + Pi [
l - 1] [
j],
1072 bufFactors[
l + 1] [0] +
buf[
l + 1],
b) -
M (
j + 1,
l +1) -
1075 Pi [
l] += xToJ*(
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1],
b));
1076 else if (degBuf > 0)
1081 if (degPi > 0 && degBuf > 0)
1083 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1] [0],
b);
1087 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1],
b);
1088 else if (degBuf > 0)
1090 uIZeroJ=
mulNTL (uIZeroJ, bufFactors [
l + 1] [0],
b);
1093 Pi[
l] += xToJ*uIZeroJ;
1095 one= bufFactors [
l + 1];
1099 if (degBuf > 0 && degPi > 0)
1110 if (degBuf > 0 && degPi > 0)
1112 for (
k= 1;
k <= (
j+1)/2;
k++)
1138 tmp[
l] +=
M (
k + 1,
l + 1);
1143 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
◆ mapinto()
◆ mod()
◆ modularDiophant()
Definition at line 290 of file facHensel.cc.
300 i.getItem() /=
Lc (
i.getItem());
339 while (
i >= 0 &&
mod( leadingCoeffs,
p ) == 0)
345 ASSERT (
i >= 0,
"ran out of primes");
349 modMipo /=
lc (modMipo);
369 p, newResult, newQ );
384 if (
j.getItem() !=
k.getItem())
409 i.getItem() *=
Lc (
j.getItem())*denf;
416 i.getItem() *= denFirst;
◆ multiRecDiophantine()
Definition at line 1339 of file facHensel.cc.
1352 bufFactors [
k]=
i.getItem();
1364 for (
int l= 0;
l < factors.
length();
l++)
1378 e -=
mulMod (
i.getItem(),
j.getItem(),
M);
1386 for (
int i= 1;
i < d;
i++)
1399 for (;
j.hasItem();
j++,
k++,
l++, ii++)
1402 if (
degree (bufFactors[ii],
y) <= 0)
1406 divrem (
g, bufFactors[ii][0], dummy,
g,
M);
1421 DEBOUTLN (cerr,
"test in multiRecDiophantine= " <<
test);
◆ nmod_poly_clear()
nmod_poly_clear |
( |
FLINTmipo |
| ) |
|
◆ nmod_poly_init()
◆ nonMonicHenselLift() [1/2]
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 2792 of file facHensel.cc.
2797 CFList bufDiophant= diophant;
2806 liftBound[1], liftBound[0], noOneToOne);
2817 for (
int i= 0;
i < 2;
i++)
2825 for (
int i= 2;
i <=
length &&
j.hasItem();
i++,
j++,
k++)
2831 liftBound[
i-1], liftBound[
i], MOD, noOneToOne);
◆ nonMonicHenselLift() [2/2]
Definition at line 2709 of file facHensel.cc.
2725 Pi [0]=
mod (Pi[0], xToLOld);
2728 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2729 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2730 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2731 else if (
degree (bufFactors[0],
y) > 0)
2732 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2733 else if (
degree (bufFactors[1],
y) > 0)
2734 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2736 for (
int i= 1;
i < Pi.
size();
i++)
2738 Pi [
i]=
mod (Pi [
i], xToLOld);
2739 M (1,
i + 1)= Pi [
i];
2742 Pi [
i] += (
mulMod (Pi[
i-1] [1], bufFactors[
i+1] [0], MOD) +
2743 mulMod (Pi[
i-1] [0], bufFactors [
i+1] [1], MOD))*
y;
2745 Pi [
i] +=
mulMod (Pi[
i-1] [1], bufFactors[
i+1], MOD)*
y;
2746 else if (
degree (bufFactors[
i+1],
y) > 0)
2747 Pi [
i] +=
mulMod (Pi[
i-1], bufFactors[
i+1] [1], MOD)*
y;
2754 for (
int i= 0;
i < bufFactors.
size();
i++)
2758 if (!
fdivides (bufFactors[
i] [0], bufF, quot))
2767 if (!
fdivides (bufFactors[
i], bufF, quot))
2777 for (
int d= 1; d < lNew; d++)
2780 products, d, MOD, noOneToOne);
◆ nonMonicHenselLift12()
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 2018 of file facHensel.cc.
2025 CFList bufFactors2= factors;
2028 DEBOUTLN (cerr,
"diophant= " << diophant);
2036 if (
degree (bufFactors[0],
x) > 0 &&
degree (bufFactors [1],
x) > 0)
2038 M (1, 1)=
mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
2039 Pi [0]=
M (1, 1) + (
mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
2040 mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*
x;
2042 else if (
degree (bufFactors[0],
x) > 0)
2044 M (1, 1)=
mulNTL (bufFactors [0] [0], bufFactors[1]);
2046 mulNTL (bufFactors [0] [1], bufFactors[1])*
x;
2048 else if (
degree (bufFactors[1],
x) > 0)
2050 M (1, 1)=
mulNTL (bufFactors [0], bufFactors[1] [0]);
2052 mulNTL (bufFactors [0], bufFactors[1] [1])*
x;
2056 M (1, 1)=
mulNTL (bufFactors [0], bufFactors[1]);
2060 for (
i= 1;
i < Pi.
size();
i++)
2064 M (1,
i+1)=
mulNTL (Pi[
i-1] [0], bufFactors[
i+1] [0]);
2065 Pi [
i]=
M (1,
i+1) + (
mulNTL (Pi[
i-1] [1], bufFactors[
i+1] [0]) +
2066 mulNTL (Pi[
i-1] [0], bufFactors [
i+1] [1]))*
x;
2070 M (1,
i+1)=
mulNTL (Pi[
i-1] [0], bufFactors [
i+1]);
2071 Pi [
i]=
M(1,
i+1) +
mulNTL (Pi[
i-1] [1], bufFactors[
i+1])*
x;
2073 else if (
degree (bufFactors[
i+1],
x) > 0)
2075 M (1,
i+1)=
mulNTL (Pi[
i-1], bufFactors [
i+1] [0]);
2076 Pi [
i]=
M (1,
i+1) +
mulNTL (Pi[
i-1], bufFactors[
i+1] [1])*
x;
2080 M (1,
i+1)=
mulNTL (Pi [
i-1], bufFactors [
i+1]);
2085 for (
i= 1;
i <
l;
i++)
2089 for (
i= 0;
i < bufFactors.
size();
i++)
2090 factors.
append (bufFactors[
i]);
◆ nonMonicHenselLift2() [1/2]
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] | bad | check for one to one correspondence |
Definition at line 2555 of file facHensel.cc.
2559 CFList bufDiophant= diophant;
2573 for (
int i= 0;
i < 2;
i++)
2585 bufLCs2.
append (jjj.getItem());
2588 for (
int i= 2;
i < lLength &&
j.hasItem();
i++,
j++, jj++, jjj++)
2591 bufLCs1.
append (jj.getItem());
2592 bufLCs2.
append (jjj.getItem());
2595 l[
i - 1],
l[
i], bufLCs1, bufLCs2,
bad);
◆ nonMonicHenselLift2() [2/2]
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 at line 2492 of file facHensel.cc.
2505 Pi [0]=
mod (Pi[0], xToLOld);
2508 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2509 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2510 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2511 else if (
degree (bufFactors[0],
y) > 0)
2512 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2513 else if (
degree (bufFactors[1],
y) > 0)
2514 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2518 for (
int i= 0;
i < bufFactors.
size();
i++)
2540 for (
int d= 1; d < lNew; d++)
◆ nonMonicHenselLift23()
Definition at line 2607 of file facHensel.cc.
2611 CFList bufFactors2= factors;
2615 i.getItem()=
mod (
i.getItem(),
y);
2618 bufF=
mod (bufF,
y);
2638 if (
degree (bufFactors[0],
v) > 0 &&
degree (bufFactors [1],
v) > 0)
2640 M (1, 1)=
mulMod2 (bufFactors [0] [0], bufFactors[1] [0], yToL);
2641 Pi [0]=
M (1,1) + (
mulMod2 (bufFactors [0] [1], bufFactors[1] [0], yToL) +
2642 mulMod2 (bufFactors [0] [0], bufFactors [1] [1], yToL))*
v;
2644 else if (
degree (bufFactors[0],
v) > 0)
2646 M (1,1)=
mulMod2 (bufFactors [0] [0], bufFactors [1], yToL);
2647 Pi [0]=
M(1,1) +
mulMod2 (bufFactors [0] [1], bufFactors[1], yToL)*
v;
2649 else if (
degree (bufFactors[1],
v) > 0)
2651 M (1,1)=
mulMod2 (bufFactors [0], bufFactors [1] [0], yToL);
2652 Pi [0]=
M (1,1) +
mulMod2 (bufFactors [0], bufFactors[1] [1], yToL)*
v;
2656 M (1,1)=
mulMod2 (bufFactors [0], bufFactors [1], yToL);
2660 for (
i= 1;
i < Pi.
size();
i++)
2664 M (1,
i+1)=
mulMod2 (Pi[
i-1] [0], bufFactors[
i+1] [0], yToL);
2665 Pi [
i]=
M (1,
i+1) + (
mulMod2 (Pi[
i-1] [1], bufFactors[
i+1] [0], yToL) +
2666 mulMod2 (Pi[
i-1] [0], bufFactors [
i+1] [1], yToL))*
v;
2670 M (1,
i+1)=
mulMod2 (Pi[
i-1] [0], bufFactors [
i+1], yToL);
2671 Pi [
i]=
M(1,
i+1) +
mulMod2 (Pi[
i-1] [1], bufFactors[
i+1], yToL)*
v;
2673 else if (
degree (bufFactors[
i+1],
v) > 0)
2675 M (1,
i+1)=
mulMod2 (Pi[
i-1], bufFactors [
i+1] [0], yToL);
2676 Pi [
i]=
M (1,
i+1) +
mulMod2 (Pi[
i-1], bufFactors[
i+1] [1], yToL)*
v;
2680 M (1,
i+1)=
mulMod2 (Pi [
i-1], bufFactors [
i+1], yToL);
2689 products.
append (bufF/
k.getItem());
2694 for (
int d= 1; d < liftBound; d++)
◆ nonMonicHenselLift232()
Definition at line 2429 of file facHensel.cc.
2435 int liftBoundBivar=
l[
k];
2458 Pi[0]=
mod (Pi[0],
power (
v, liftBoundBivar));
2460 if (
degree (bufFactors[0],
y) > 0 &&
degree (bufFactors [1],
y) > 0)
2461 Pi [0] += (
mulMod (bufFactors [0] [1], bufFactors[1] [0], MOD) +
2462 mulMod (bufFactors [0] [0], bufFactors [1] [1], MOD))*
y;
2463 else if (
degree (bufFactors[0],
y) > 0)
2464 Pi [0] +=
mulMod (bufFactors [0] [1], bufFactors[1], MOD)*
y;
2465 else if (
degree (bufFactors[1],
y) > 0)
2466 Pi [0] +=
mulMod (bufFactors [0], bufFactors[1] [1], MOD)*
y;
2469 for (
int i= 0;
i < bufFactors.
size();
i++)
2477 for (
int d= 1; d <
l[1]; d++)
◆ nonMonicHenselStep()
Definition at line 2176 of file facHensel.cc.
2188 for (
int i= 0;
i < factors.
length();
i++)
2193 test *= bufFactors[
i];
2198 DEBOUTLN (cerr,
"test in nonMonicHenselStep= " << test2);
2202 E= F[
j] - Pi [factors.
length() - 2] [
j];
2219 buf[
k]=
i.getItem();
2220 bufFactors[
k] += xToJ*
i.getItem();
2226 int degBuf0=
degree (bufFactors[0],
x);
2227 int degBuf1=
degree (bufFactors[1],
x);
2228 if (degBuf0 > 0 && degBuf1 > 0)
2230 M (
j + 1, 1)=
mulMod (bufFactors[0] [
j], bufFactors[1] [
j], MOD);
2231 if (
j + 2 <=
M.rows())
2232 M (
j + 2, 1)=
mulMod (bufFactors[0] [
j + 1], bufFactors[1] [
j + 1], MOD);
2238 if (degBuf0 > 0 && degBuf1 > 0)
2239 uIZeroJ=
mulMod (bufFactors[0] [0],
buf[1], MOD) +
2240 mulMod (bufFactors[1] [0],
buf[0], MOD);
2241 else if (degBuf0 > 0)
2242 uIZeroJ=
mulMod (
buf[0], bufFactors[1], MOD) +
2244 else if (degBuf1 > 0)
2245 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD) +
2248 uIZeroJ=
mulMod (bufFactors[0],
buf[1], MOD) +
2250 Pi [0] += xToJ*uIZeroJ;
2253 for (
k= 0;
k < factors.
length() - 1;
k++)
2256 one= bufFactors [0];
2257 two= bufFactors [1];
2258 if (degBuf0 > 0 && degBuf1 > 0)
2262 for (
k= 1;
k <= (
j+1)/2;
k++)
2270 (bufFactors[1] [
k] + two.
coeff()), MOD) -
M (
k + 1, 1) -
2278 bufFactors[1] [
k], MOD) -
M (
k + 1, 1);
2283 tmp[0] +=
mulMod (bufFactors[0] [
k], (bufFactors[1] [
k] +
2284 two.
coeff()), MOD) -
M (
k + 1, 1);
2290 tmp[0] +=
M (
k + 1, 1);
2295 if (degBuf0 >=
j + 1 && degBuf1 >=
j + 1)
2297 if (
j + 2 <=
M.rows())
2298 tmp [0] +=
mulMod ((bufFactors [0] [
j + 1]+ bufFactors [0] [0]),
2299 (bufFactors [1] [
j + 1] + bufFactors [1] [0]), MOD)
2300 -
M(1,1) -
M (
j + 2,1);
2302 else if (degBuf0 >=
j + 1)
2305 tmp[0] +=
mulMod (bufFactors [0] [
j+1], bufFactors [1] [0], MOD);
2307 tmp[0] +=
mulMod (bufFactors [0] [
j+1], bufFactors [1], MOD);
2309 else if (degBuf1 >=
j + 1)
2312 tmp[0] +=
mulMod (bufFactors [0] [0], bufFactors [1] [
j + 1], MOD);
2314 tmp[0] +=
mulMod (bufFactors [0], bufFactors [1] [
j + 1], MOD);
2316 Pi [0] += tmp[0]*xToJ*F.
mvar();
2320 for (
int l= 1;
l < factors.
length() - 1;
l++)
2323 degBuf=
degree (bufFactors[
l + 1],
x);
2324 if (degPi > 0 && degBuf > 0)
2326 M (
j + 1,
l + 1)=
mulMod (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j], MOD);
2327 if (
j + 2 <=
M.rows())
2328 M (
j + 2,
l + 1)=
mulMod (Pi [
l - 1] [
j + 1], bufFactors[
l + 1] [
j + 1],
2332 M (
j + 1,
l + 1)= 0;
2334 if (degPi > 0 && degBuf > 0)
2335 uIZeroJ=
mulMod (Pi[
l - 1] [0],
buf[
l + 1], MOD) +
2336 mulMod (uIZeroJ, bufFactors[
l + 1] [0], MOD);
2338 uIZeroJ=
mulMod (uIZeroJ, bufFactors[
l + 1], MOD) +
2340 else if (degBuf > 0)
2342 mulMod (uIZeroJ, bufFactors[
l + 1][0], MOD);
2345 mulMod (uIZeroJ, bufFactors[
l + 1], MOD);
2347 Pi [
l] += xToJ*uIZeroJ;
2349 one= bufFactors [
l + 1];
2351 if (degBuf > 0 && degPi > 0)
2355 for (
k= 1;
k <= (
j+1)/2;
k++)
2363 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1) -
2364 M (
j -
k + 2,
l + 1);
2371 Pi[
l - 1] [
k], MOD) -
M (
k + 1,
l + 1);
2376 tmp[
l] +=
mulMod (bufFactors[
l + 1] [
k],
2377 (Pi[
l - 1] [
k] + two.
coeff()), MOD) -
M (
k + 1,
l + 1);
2382 tmp[
l] +=
M (
k + 1,
l + 1);
2386 if (degPi >=
j + 1 && degBuf >=
j + 1)
2388 if (
j + 2 <=
M.rows())
2389 tmp [
l] +=
mulMod ((Pi [
l - 1] [
j + 1]+ Pi [
l - 1] [0]),
2390 (bufFactors [
l + 1] [
j + 1] + bufFactors [
l + 1] [0])
2391 , MOD) -
M(1,
l+1) -
M (
j + 2,
l+1);
2393 else if (degPi >=
j + 1)
2396 tmp[
l] +=
mulMod (Pi [
l - 1] [
j+1], bufFactors [
l + 1] [0], MOD);
2398 tmp[
l] +=
mulMod (Pi [
l - 1] [
j+1], bufFactors [
l + 1], MOD);
2400 else if (degBuf >=
j + 1)
2403 tmp[
l] +=
mulMod (Pi [
l - 1] [0], bufFactors [
l + 1] [
j + 1], MOD);
2405 tmp[
l] +=
mulMod (Pi [
l - 1], bufFactors [
l + 1] [
j + 1], MOD);
2408 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
◆ nonMonicHenselStep12()
Definition at line 1797 of file facHensel.cc.
1807 E= F[
j] - Pi [factors.
length() - 2] [
j];
1819 remainder=
modNTL (
E, bufFactors[
k] [0]);
1821 remainder=
modNTL (
E, bufFactors[
k]);
1830 bufFactors[
k] += xToJ*
buf[
k];
1833 int degBuf0=
degree (bufFactors[0],
x);
1834 int degBuf1=
degree (bufFactors[1],
x);
1835 if (degBuf0 > 0 && degBuf1 > 0)
1837 M (
j + 1, 1)=
mulNTL (bufFactors[0] [
j], bufFactors[1] [
j]);
1838 if (
j + 2 <=
M.rows())
1839 M (
j + 2, 1)=
mulNTL (bufFactors[0] [
j + 1], bufFactors[1] [
j + 1]);
1845 if (degBuf0 > 0 && degBuf1 > 0)
1846 uIZeroJ=
mulNTL(bufFactors[0][0],
buf[1]) +
1848 else if (degBuf0 > 0)
1849 uIZeroJ=
mulNTL (
buf[0], bufFactors[1]) +
1851 else if (degBuf1 > 0)
1852 uIZeroJ=
mulNTL (bufFactors[0],
buf[1]) +
1855 uIZeroJ=
mulNTL (bufFactors[0],
buf[1]) +
1858 Pi [0] += xToJ*uIZeroJ;
1861 for (
k= 0;
k < factors.
length() - 1;
k++)
1864 one= bufFactors [0];
1865 two= bufFactors [1];
1866 if (degBuf0 > 0 && degBuf1 > 0)
1870 for (
k= 1;
k <= (
j+1)/2;
k++)
1877 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()),(bufFactors[1][
k] +
1878 two.
coeff())) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
1884 tmp[0] +=
mulNTL ((bufFactors[0][
k]+one.
coeff()), bufFactors[1] [
k]) -
1890 tmp[0] +=
mulNTL (bufFactors[0][
k],(bufFactors[1][
k] + two.
coeff())) -
1896 tmp[0] +=
M (
k + 1, 1);
1900 if (degBuf0 >=
j + 1 && degBuf1 >=
j + 1)
1902 if (
j + 2 <=
M.rows())
1903 tmp [0] +=
mulNTL ((bufFactors [0] [
j + 1]+ bufFactors [0] [0]),
1904 (bufFactors [1] [
j + 1] + bufFactors [1] [0]))
1905 -
M(1,1) -
M (
j + 2,1);
1907 else if (degBuf0 >=
j + 1)
1910 tmp[0] +=
mulNTL (bufFactors [0] [
j+1], bufFactors [1] [0]);
1912 tmp[0] +=
mulNTL (bufFactors [0] [
j+1], bufFactors [1]);
1914 else if (degBuf1 >=
j + 1)
1917 tmp[0] +=
mulNTL (bufFactors [0] [0], bufFactors [1] [
j + 1]);
1919 tmp[0] +=
mulNTL (bufFactors [0], bufFactors [1] [
j + 1]);
1922 Pi [0] += tmp[0]*xToJ*F.
mvar();
1925 for (
int l= 1;
l < factors.
length() - 1;
l++)
1928 degBuf=
degree (bufFactors[
l + 1],
x);
1929 if (degPi > 0 && degBuf > 0)
1931 M (
j + 1,
l + 1)=
mulNTL (Pi [
l - 1] [
j], bufFactors[
l + 1] [
j]);
1932 if (
j + 2 <=
M.rows())
1933 M (
j + 2,
l + 1)=
mulNTL (Pi [
l - 1][
j + 1], bufFactors[
l + 1] [
j + 1]);
1936 M (
j + 1,
l + 1)= 0;
1938 if (degPi > 0 && degBuf > 0)
1940 mulNTL (uIZeroJ, bufFactors[
l+1] [0]);
1942 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1]) +
1944 else if (degBuf > 0)
1945 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1][0]) +
1948 uIZeroJ=
mulNTL (uIZeroJ, bufFactors[
l + 1]) +
1951 Pi [
l] += xToJ*uIZeroJ;
1953 one= bufFactors [
l + 1];
1955 if (degBuf > 0 && degPi > 0)
1959 for (
k= 1;
k <= (
j+1)/2;
k++)
1967 (Pi[
l - 1] [
k] + two.
coeff())) -
M (
k + 1,
l + 1) -
1968 M (
j -
k + 2,
l + 1);
1975 Pi[
l - 1] [
k]) -
M (
k + 1,
l + 1);
1980 tmp[
l] +=
mulNTL (bufFactors[
l + 1] [
k],
1981 (Pi[
l - 1] [
k] + two.
coeff())) -
M (
k + 1,
l + 1);
1986 tmp[
l] +=
M (
k + 1,
l + 1);
1990 if (degPi >=
j + 1 && degBuf >=
j + 1)
1992 if (
j + 2 <=
M.rows())
1993 tmp [
l] +=
mulNTL ((Pi [
l - 1] [
j + 1]+ Pi [
l - 1] [0]),
1994 (bufFactors [
l + 1] [
j + 1] + bufFactors [
l + 1] [0])
1995 ) -
M(1,
l+1) -
M (
j + 2,
l+1);
1997 else if (degPi >=
j + 1)
2000 tmp[
l] +=
mulNTL (Pi [
l - 1] [
j+1], bufFactors [
l + 1] [0]);
2002 tmp[
l] +=
mulNTL (Pi [
l - 1] [
j+1], bufFactors [
l + 1]);
2004 else if (degBuf >=
j + 1)
2007 tmp[
l] +=
mulNTL (Pi [
l - 1] [0], bufFactors [
l + 1] [
j + 1]);
2009 tmp[
l] +=
mulNTL (Pi [
l - 1], bufFactors [
l + 1] [
j + 1]);
2012 Pi[
l] += tmp[
l]*xToJ*F.
mvar();
◆ replaceLC()
◆ replacevar()
◆ sortList()
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 441 of file facHensel.cc.
456 m.getItem()=
j.getItem();
459 j.getItem()=
m.getItem();
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
diotime |
| ) |
const & |
◆ tryDiophantine()
Definition at line 148 of file facHensel.cc.
153 CFList bufFactors= factors;
163 for (;
i.hasItem();
i++)
168 i.getItem()=
reduce (
i.getItem()*inv,
M);
170 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
171 bufFactors= productsFLINT (bufFactors,
M);
173 bufFactors= productsNTL (bufFactors,
M);
190 zz_pE::init (NTLMipo);
191 zz_pEX NTLbuf1, NTLbuf2, NTLbuf3, NTLS, NTLT;
194 tryNTLXGCD (NTLbuf3, NTLS, NTLT, NTLbuf1, NTLbuf2, fail);
208 for (;
i.hasItem();
i++)
212 tryNTLXGCD (NTLbuf3, NTLS, NTLT, NTLbuf3, NTLbuf1, fail);
219 tryExtgcd (buf3,
buf1,
M, buf3, S,
T, fail);
227 j.getItem()=
mod (
j.getItem(),
k.getItem());
◆ buf
◆ fq_con
◆ prod
◆ result
◆ vec
fq_nmod_poly_init(prod, fq_con)
static int mod(const CFList &L, const CanonicalForm &p)
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)
static const int SW_RATIONAL
set to 1 for computations over Q
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
void henselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b)
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
class to iterate through CanonicalForm's
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList const Variable & y
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
static void henselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFList &MOD)
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
static BOOLEAN length(leftv result, leftv arg)
REvaluation E(1, terms.length(), IntRandom(25))
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm replaceLC(const CanonicalForm &F, const CanonicalForm &c)
int cf_getBigPrime(int i)
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CFList diophantineHensel(const CanonicalForm &F, const CFList &factors, const modpk &b)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
CFList nonMonicHenselLift232(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, bool &bad)
CanonicalForm convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT poly over Fq to a CanonicalForm with alg. variable alpha and polynomial variabl...
void nonMonicHenselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, const CFList &products, int j, const CFList &MOD, bool &noOneToOne)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
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),...
#define ASSERT(expression, message)
TIMING_START(fac_alg_resultant)
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.
CF_NO_INLINE int exp() const
get the current exponent
static void tryDiophantine(CFList &result, const CanonicalForm &F, const CFList &factors, const CanonicalForm &M, bool &fail)
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
CanonicalForm divNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z,...
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
CanonicalForm modNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a),...
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
void sort(CFArray &A, int l=0)
quick sort A
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
class to do operations mod p^k for int's p and k
static CFList Farey(const CFList &L, const CanonicalForm &q)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CFList diophantine(const CanonicalForm &F, const CFList &factors)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void setReduce(const Variable &alpha, bool reduce)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
CFList diophantineQa(const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha)
solve mod over by first computing mod and if no zero divisor occurred compute it mod
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
CFList modularDiophant(const CanonicalForm &f, const CFList &factors, const CanonicalForm &M)
void tryNTLXGCD(zz_pEX &d, zz_pEX &s, zz_pEX &t, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the extended GCD d=s*a+t*b, fail is set to true if a zero divisor is encountered
int hasAlgVar(const CanonicalForm &f, const Variable &v)
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)
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
const Variable & v
< [in] a sqrfree bivariate poly
const CanonicalForm int s
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
int status int void size_t count
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
static CFList mapinto(const CFList &L)
static void chineseRemainder(const CFList &x1, const CanonicalForm &q1, const CFList &x2, const CanonicalForm &q2, CFList &xnew, CanonicalForm &qnew)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.