# MultivariateLifting(E, OV, R, P)ΒΆ

- E: OrderedAbelianMonoidSup
- OV: OrderedSet
- R: IntegralDomain
- P: PolynomialCategory(R, E, OV)

This package provides the functions for the multivariate “lifting”, using an algorithm of Paul Wang. This package will work for every euclidean domain `R`

which has property `F`

, i.e. there exists a factor operation in `R[x]`

.

- corrPoly: (SparseUnivariatePolynomial P, List OV, List R, List NonNegativeInteger, List SparseUnivariatePolynomial P, SparseUnivariatePolynomial R -> Union(List SparseUnivariatePolynomial R, failed)) -> Union(List SparseUnivariatePolynomial P, failed)
`corrPoly(u, lv, lr, ln, lu, bsolv)`

solves polynomial equation system u/f = sum(ai/lu(`i`

)) where`f`

is product of`lu`

(`i`

) and deg(`ai`

) < deg(`lu`

(`i`

)) using modular method. corrPoly returns “failed” if there are no solution.`lv`

is list of variables,`lr`

is list of corresponding evaluation points, bsolv is solver over`R`

specialized for modular images of`lu`

.

- lifting: (SparseUnivariatePolynomial P, List OV, List SparseUnivariatePolynomial R, List R, List P, List NonNegativeInteger, List SparseUnivariatePolynomial R -> SparseUnivariatePolynomial R -> Union(List SparseUnivariatePolynomial R, failed)) -> Union(List SparseUnivariatePolynomial P, failed)
`lifting(u, lv, lu, lr, lp, ln, gen_solv)`

lifts univariate factorization, returning recovered factors or “failed” in case of bad reduction.`u`

is multivariate polynomial to factor,`lu`

is list of univariate factors,`lv`

is list of variables,`ln`

is list of degrees corresponding to variables,`lr`

is list of evaluation points,`lp`

is list of leading coefficients of factors if known, empty otherwise, gen_solv delivers solver for polynomial equations

- lifting: (SparseUnivariatePolynomial P, List OV, List SparseUnivariatePolynomial R, List R, List P, List NonNegativeInteger, R) -> Union(List SparseUnivariatePolynomial P, failed) if R has EuclideanDomain
`lifting(u, lv, lu, lr, lp, ln, r)`

is lifting(`u`

,`lv`

,`lu`

,`lr`

,`lp`

,`ln`

, solv(`r`

)) where solv(`r`

) is solver using reduction modulo`r`

and lifting. Memberes of`lu`

must be relatively prime modulo`r`