U32VectorPolynomialOperationsΒΆ

u32vec.spad line 189

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