Module convolution 

Functions that calculate $(+, \times)$ convolution.

Given two non-empty sequences $a_0, a_1, \ldots, a_{N - 1}$ and $b_0, b_1, \ldots, b_{M - 1}$, they calculate the sequence $c$ of length $N + M - 1$ defined by

\[ c_i = \sum_ {j = 0}^i a_j b_{i - j} \]

Major changes from the original ACL

• Separated the overloaded convolution into convolution<_> and convolution_raw<_, _>.
• Renamed convolution_ll to convolution_i64.

Functions

convolution

Calculates the $(+, \times)$ convolution in $\mathbb{Z}/p\mathbb{Z}$.

convolution_i64

Calculates the $(+, \times)$ convolution in i64.

convolution_raw

Calculates the $(+, \times)$ convolution in $\mathbb{Z}/p\mathbb{Z}$.