GenExEuclid(R, BP)

geneez.spad line 1 [edit on github]

Author : P.Gianni. January 1990 The equation Af+Bg=h and its generalization to n polynomials is solved for solutions over the R, euclidean domain. A table containing the solutions of Af+Bg=x^k is used. The operations are performed modulus a prime which are in principle big enough, but the solutions are tested and, in case of failure, a hensel lifting process is used to get to the right solutions. It will be used in the factorization of multivariate polynomials over finite field, with R=F[x].

compBound: (BP, List BP) -> NonNegativeInteger

compBound(p, lp) computes a bound for the coefficients of the solution polynomials. Given a polynomial right hand side p, and a list lp of left hand side polynomials. Exported because it depends on the valuation.

reduction: (BP, R) -> BP

reduction(p, prime) reduces the polynomial p modulo prime of R. Note: this function is exported only because it's conditional.

solveid: (BP, R, Vector List BP) -> Union(List BP, failed)

solveid(h, prime, table) computes the coefficients of the extended euclidean algorithm for a list of polynomials whose tablePow is table and with right side h.

tablePow: (NonNegativeInteger, R, List BP) -> Union(Vector List BP, failed)

tablePow(maxdeg, prime, lpol) constructs the table with the coefficients of the Extended Euclidean Algorithm for lpol. Here the right side is x^k, for k less to maxdeg. The operation returns “failed” when the elements are not coprime modulo prime.

testModulus: (R, List BP) -> Boolean

testModulus(p, lp) returns true if the prime p is valid for the list of polynomials lp, i.e. preserves the degree and they remain relatively prime.