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: (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.