GenExEuclid(R, BP)¶

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(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(p, prime) reduces the polynomial p modulo prime of R. Note: this function is exported only because it's conditional.
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(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(p, lp) returns true if the the prime p is valid for the list of polynomials lp, i.e. preserves the degree and they remain relatively prime.