# U32VectorPolynomialOperationsΒΆ

This is a low-level package which implements operations on vectors treated as univariate modular polynomials. Most operations takes modulus as parameter. Modulus is machine sized prime which should be small enough to avoid overflow in intermediate calculations.

- copy_first: (U32Vector, U32Vector, Integer) -> Void
`copy_first(v1, v2, n)`

copies first`n`

elements of`v2`

into`n`

first positions in`v1`

.

- copy_slice: (U32Vector, U32Vector, Integer, Integer) -> Void
`copy_slice(v1, v2, m, n)`

copies the slice of`v2`

starting at`m`

elements and having`n`

elements into corresponding positions in`v1`

.

- differentiate: (U32Vector, NonNegativeInteger, Integer) -> U32Vector
- Polynomial differentiation.

- eval_at: (U32Vector, Integer, Integer, Integer) -> Integer
`eval_at(v, deg, pt, p)`

treats`v`

as coefficients of polynomial of degree`deg`

and evaluates the polynomial at point`pt`

modulo`p`

- extended_gcd: (U32Vector, U32Vector, Integer) -> List U32Vector
`extended_gcd(v1, v2, p)`

gives [`g`

,`c1`

,`c2`

] such that`g`

is`gcd(v1, v2, p)`

,`g = c1*v1 + c2*v2`

and degree(`c1`

) < max(degree(`v2`

) - degree(`g`

), 0) and degree(`c2`

) < max(degree(`v1`

) - degree(`g`

), 1)

- gcd: (PrimitiveArray U32Vector, Integer, Integer, Integer) -> U32Vector
`gcd(a, lo, hi, p)`

computes`gcd`

of elements a(`lo`

), a(`lo+1`

), ..., a(`hi`

).

- gcd: (U32Vector, U32Vector, Integer) -> U32Vector
`gcd(v1, v2, p)`

computes monic`gcd`

of`v1`

and`v2`

modulo`p`

.

- lcm: (PrimitiveArray U32Vector, Integer, Integer, Integer) -> U32Vector
`lcm(a, lo, hi, p)`

computes`lcm`

of elements a(`lo`

), a(`lo+1`

), ..., a(`hi`

).

- mul_by_binomial: (U32Vector, Integer, Integer) -> Void
`mul_by_binomial(v, pt, p)`

treats`v`

a polynomial and multiplies in place this polynomial by binomial (`x`

+`pt`

). Highest coefficient of product is ignored.

- mul_by_binomial: (U32Vector, Integer, Integer, Integer) -> Void
`mul_by_binomial(v, deg, pt, p)`

treats`v`

as coefficients of polynomial of degree`deg`

and multiplies in place this polynomial by binomial (`x`

+`pt`

). Highest coefficient of product is ignored.

- mul_by_scalar: (U32Vector, Integer, Integer, Integer) -> Void
`mul_by_scalar(v, deg, c, p)`

treats`v`

as coefficients of polynomial of degree`deg`

and multiplies in place this polynomial by scalar`c`

- pa_to_sup: U32Vector -> SparseUnivariatePolynomial Integer
`pa_to_sup(v)`

converts vector of coefficients to a polynomial

- pow: (U32Vector, PositiveInteger, NonNegativeInteger, Integer) -> U32Vector
`pow(u, n, d, p)`

returns u^n truncated after degree`d`

, except if`n=1`

, in which case`u`

itself is returned

- resultant: (U32Vector, U32Vector, Integer) -> Integer
`resultant(v1, v2, p)`

computes resultant of`v1`

and`v2`

modulo`p`

.

- to_mod_pa: (SparseUnivariatePolynomial Integer, Integer) -> U32Vector
`to_mod_pa(s, p)`

reduces coefficients of polynomial`s`

modulo prime`p`

and converts the result to vector

- truncated_mul_add: (U32Vector, U32Vector, U32Vector, Integer, Integer) -> Void
`truncated_mul_add(x, y, z, d, p)`

adds to`z`

the produce x*y truncated after degree`d`

- truncated_multiplication: (U32Vector, U32Vector, Integer, Integer) -> U32Vector
`truncated_multiplication(x, y, d, p)`

computes x*y truncated after degree`d`