DFT for something similar to convolution I have the following problem:
Let $x$, $y$ be finite real valued sequences defined on $0, \ldots, N-1$ and let $g$ be a non negative integer.

Define:

$$z_n=\sum_{k=0}^n x_{n-k}y_k, \quad \text{also on $0, \ldots, N-1$.}$$

Note that the sum is from $0$ to $n$, not $N-1$. In addition, the DFT of $y$ is known in closed form.


Is there a way to write $z$ as some cyclic convolution, so that with the help of the convolution theorem $z$ can be calculated in $N \log N$ instead of $N^2$?


I tried following the convolution theorem proof but I get stuck:

\begin{align}
z_n&amp;=\sum_{k=0}^nx_{n-k}y_k= \sum_{k=0}^{N-1}x_{n-k}\cdot \theta (n-k)\cdot y_k\\
\Rightarrow \tilde{z_q}&amp;=\sum_{n=0}^{N-1}\sum_{k=0}^{N-1} x_{n-k}\cdot \theta (n-k)\cdot y_k e^{-2\pi iqn/N}\\
&amp;=\sum_{n=0}^{N-1}\sum_{k=0}^{N-1} x_{n-k}\cdot \theta (n-k)e^{-2\pi iq(n-k)/N}\cdot y_k e^{-2\pi iqk/N}\\
&amp;=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n=0}^{N-1} x_{n-k}\cdot \theta (n-k)e^{-2\pi iq(n-k)/N}\\
&amp;=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n'=-k}^{N-1-k} x_{n'}\cdot \theta (n')e^{-2\pi iqn'/N}\\
&amp;=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n'=0}^{N-1-k} x_{n'}e^{-2\pi iqn'/N}=?????\\
\end{align}

The problem is that the second sum depends on $k$ so the double sum doesn't factor to the product of DFTs.

What am I missing?
You might be looking for the convolution property of the DFT. If $z[n] = x[n] * y[n]$, where $*$ represents circular convolution, then $Z[k] = X[k] Y[k]$, where $Z[k]$ is the DFT of $z[n]$ and so on. 

This property is used in fast convolution techniques like overlap-save to implement convolution in $O(N \log N)$ time instead of the $O(n^2)$ time required by direct implementation of the convolution sum.