Crate subproductdomain_pre_release

Structs

SubproductDomain
A subproduct domain is a domain { u_0, …, u_{n-1} } of scalar values accompanied by a subproduct tree of the polynomial: m = (x - u_0)…(x-u_{n-1}) Once the subproduct tree is constructed, operations over the entire subproduct domain can be done in a fast, recursive way. Unlike other fast algorithms, the subproduct domain may be arbitrary points instead of a multiplicative subgroup of roots of unity of the field
SubproductTree
A subproduct tree of the subproduct domain This type is defined separately from SubproductDomain because the domain u is owned by SubproductDomain, whereas m = (x - u_i)…(x-u_j) is owned by the SubproductTree The subdomain { u_i, …, u_j } is borrowed by SubproductTree for each operation

build_circulant
Build a vector representation of the (n x n) circulant matrix of polynomial f Based on the blog post: https://alinush.github.io/2020/03/19/multiplying-a-vector-by-a-toeplitz-matrix.html
derivative
Compute the derivative of polynomial f
fast_divide_monic
GG Algorithm 9.5 Divide f by g in nearly linear time
fast_multiexp
Compute a fast multiexp of many scalars times the same base Only convenient for when called once with given base; if called more than once, it’s faster to save the generated window table
inverse_mod_xl
Where indicated, algorithms are from Modern Computer Algebra, 3rd edition, by Gathen and Gerhard Abbreviated as GG Let M(n) denote the time to multiply. GG Algorithm 9.3 Computes the inverse of f mod x^l Takes O(M(l)) field arithmetic operations
moduli_from_scalar
poly_from_scalar
rev
GG chapter 9.1 Computes the rev_m(f) function in place rev_m(f) = x^m f(1/x)
toeplitz_mul
Computes the Toeplitz matrix of polynomial times the vector v