U32VectorPolynomialOperations

u32vec.spad line 403 [edit on github]

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.