Open batzor opened 3 weeks ago
Currently, in univariate polynomial-by-polynomial multiplication, it uses the naive approach which takes $O(n^2)$. But if we utilize FFT, it can be reduced to $O(nlogn)$ https://github.com/kroma-network/tachyon/blob/ec92fa45e4a29b552e8380e463bbd3c1144bd91b/tachyon/math/polynomials/univariate/univariate_polynomial_ops.h#L460-L462
Reference: https://www.cs.toronto.edu/~denisp/csc373/docs/tutorial3-adv-writeup.pdf
Currently, in univariate polynomial-by-polynomial multiplication, it uses the naive approach which takes $O(n^2)$. But if we utilize FFT, it can be reduced to $O(nlogn)$ https://github.com/kroma-network/tachyon/blob/ec92fa45e4a29b552e8380e463bbd3c1144bd91b/tachyon/math/polynomials/univariate/univariate_polynomial_ops.h#L460-L462
Reference: https://www.cs.toronto.edu/~denisp/csc373/docs/tutorial3-adv-writeup.pdf