Покажем как выполнить дискретное преобразование Фурье за 
действий при 
. В частности, при N = 2n понадобится O(Nlog(N))действий.
Дискретное преобразование Фурье преобразует набор чисел 
в набор чисел 
, такой, что 
, где εn = 1 и 
при 0 < k < n. Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c ε = e2πi / n) и к кольцам вычетов.
Основной шаг алгоритма состоит в сведении задачи для N чисел к задаче для p = N / q числам, где q — делитель N. Пусть мы уже умеем решать задачу для N / q чисел. Применим преобразование Фурье к наборам 
для 
. Покажем теперь, как за O(Np) действий решить исходную задачу. Заметим, что 
. Выражения в скобках нам уже известны — это i(mod p)-тое число после преобразования Фурье j-той группы. Таким образом, для вычисления каждого bi нужно O(q) действий, а для вычисления всех bi — O(Nq) действий, что и требовалось получить.
