# 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`

.