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(v1, v2, n) copies first n elements of v2 into n first positions in v1.
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(v) is degree of v treated as polynomial
Polynomial differentiation.
Polynomial differentiation.
Polynomial division.
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(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(a, lo, computes hi, p)gcd of elements a(lo), a(lo+1), ..., a(hi).
gcd(v1, v2, p) computes monic gcd of v1 and v2 modulo p.
lcm(a, lo, computes hi, p)lcm of elements a(lo), a(lo+1), ..., a(hi).
Polynomial multiplication.
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(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(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(v) converts vector of coefficients to a polynomial
pow(u, n, d, p) returns u^n truncated after degree d, except if n=1, in which case u itself is returned
Polynomial remainder
resultant(v1, v2, p) computes resultant of v1 and v2 modulo p.
to_mod_pa(s, p) reduces coefficients of polynomial s modulo prime p and converts the result to vector
truncated_mul_add(x, y, z, d, p) adds to z the product x*y truncated after degree d.
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_multiplication(x, y, d, p) computes x*y truncated after degree d.
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(v1, c1, v2, c2, n, delta, p) replaces first n + 1 entries of v1 by corresponding entries of c1*v1+c2*x^delta*v2 mod p.