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