MultivariateLifting(E, OV, R, P)¶

mlift.spad line 1 [edit on github]

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 -> Union(SparseUnivariatePolynomial R -> Union(List SparseUnivariatePolynomial R, failed), 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