Recall the Fourier Transform (FT):
$\displaystyle F(k) = {1 \over 2 \pi } \int f(x)\ e^{-i k x}\ dx$
The Inverse Fourier Transform (IFT) is:
$\displaystyle f(t) = \int F(k)\ e^{i k t}\ dk$
You will see some variants of this, all equivalent:
$\begin{array}{ll}
F(k) = \int f(x)\ e^{-i k x}\ dx
&
f(t) = {1 \over 2 \pi } \int F(k)\ e^{i k t}\ dk \qquad \text{(most common form)}
\\ \\
F(k) = {1 \over \sqrt{2 \pi} } \int f(x)\ e^{-i k x}\ dx
&
f(t) = {1 \over \sqrt{2 \pi} } \int F(k)\ e^{i k t}\ dk
\\ \\
F(\omega) = \int f(x)\ e^{- i 2 \pi \omega x}\ dx
&
f(t) = {\omega \over 2 \pi } \int F(\omega)\ e^{i 2 \pi \omega t}\ d\omega \qquad \text{(for frequency $\omega$)}
\end{array}$
We'll first see how the convolution operation appears in the frequency domain.
$(f \ast g)(t) = \displaystyle \int f(u)\ g(t-u)\ du$
Below, $\mathscr{F}$ denotes the Fourier Transform. We use
$F$ to as a short form for $\mathscr{F}(f)$ and use $G$ as a short
form for $\mathscr{F}(g)$.
The Fourier Transform of $(f \ast g)(t)$ is:
$\begin{array}{rcl}
\mathscr{F}(\ (f \ast g)(t)\ )(k)
& = & \displaystyle \int_t\ \left[\ (f \ast g)(t) \right]\ e^{-i k t}\ dt \\
& = & \displaystyle \int_t\ \left[\ \int_u f(u)\ g(t-u)\ du\ \right]\ e^{-i k t}\ dt \\
& = & \displaystyle \int_u\ f(u) \left[\ \int_t g(t-u)\ e^{-i k t}\ dt\ \right]\ du \\
& & \Big\downarrow\ \text{substitute}\ \tau = t-u \\
& = & \displaystyle \int_u\ f(u) \left[\ \int_\tau g(\tau)\ e^{-i k (\tau+u)}\ d\tau\ \right]\ du \\
& = & \displaystyle \int_u\ f(u) \left[\ \int_\tau g(\tau)\ e^{-i k \tau}\ e^{-i k u}\ d\tau\ \right]\ du \\
& = & \displaystyle \int_u\ f(u) \left[\ G(k)\ e^{-i k u} \right]\ du \\
& = & \displaystyle G(k)\ \int_u\ f(u)\ e^{-i k u}\ du \\
& = & \displaystyle G(k)\ F(k)
\end{array}$
In other words, convolution in the
spatial domain is the same as multiplication in the frequency
domain:
$\mathscr{F}( f \ast g ) = \mathscr{F}(f) \times \mathscr{F}(g)$
It's much cheaper to do a convolution by
moving into the frequency domain, performing a multiplication,
then moving back to the spatial domain, as follows:
$$\begin{array}{ccc}
\displaystyle f, g & \quad \overset{\mathscr{F}}{\longrightarrow} \quad & \mathscr{F}(f), \mathscr{F}(g) \\
\\
\displaystyle \Big\downarrow \ast & & \Big\downarrow \times \\
\\
\displaystyle f \ast g & \quad \overset{\mathscr{F}^{-1}}{\longleftarrow} \quad & \mathscr{F}(f) \times \mathscr{F}(g) \\
\end{array}$$
The $\mathscr{F}$ and $\mathscr{F}^{-1}$ operations can be done
in $\cal{O}(n \log n)$ time on a function sampled at $n$
locations and the multiplication ($\times$) takes $\cal{O}(n)$
time. Much slower is straight convolution, which takes
$\cal{O}(n^2)$ time.
Going the other way, we can also show that convolution in the
frequency domain is the same as multiplication in the spatial
domain:
$\mathscr{F}( f \times g ) = \mathscr{F}(f) \ast \mathscr{F}(g)$