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

degree: U32Vector -> Integer

`degree(v)` is degree of `v` treated as polynomial

differentiate: (U32Vector, Integer) -> U32Vector

Polynomial differentiation.

differentiate: (U32Vector, NonNegativeInteger, Integer) -> U32Vector

Polynomial differentiation.

divide!: (U32Vector, U32Vector, U32Vector, Integer) -> Void

Polynomial division.

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: (U32Vector, U32Vector, Integer) -> U32Vector

Polynomial multiplication.

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

remainder!: (U32Vector, U32Vector, Integer) -> Void

Polynomial remainder

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_add2: (U32Vector, U32Vector, U32Vector, Integer, Integer, Integer) -> Void

`truncated_mul_add2(x, y, z, d1, d2, p)` adds to `z` the product x*y and the variable to power `d1` truncated after degree `d`.

truncated_mul_add: (U32Vector, U32Vector, U32Vector, Integer, Integer) -> Void

`truncated_mul_add(x, y, z, d, p)` adds to `z` the product 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`.

vector_add_mul: (U32Vector, U32Vector, Integer, Integer, Integer, Integer) -> Void

`vector_add_mul(v1, v2, m, n, c, p)` sets `v1`(`m`), …, `v1`(`n`) to corresponding extries in `v1` + `c*v2` modulo `p`.

vector_combination: (U32Vector, Integer, U32Vector, Integer, Integer, Integer, Integer) -> Void

`vector_combination(v1, c1, v2, c2, n, delta, p)` replaces first `n` + 1 entires of `v1` by corresponding entries of `c1*v1+c2*x^delta*v2` mod `p`.