INTRODUCTION

Fast algorithms for calculating the Fourier transform arose in connection with the problems of speeding up the processing and transmission of information, but they turned out to be very useful in connection with the creation of more efficient algorithms for multiplying large natural numbers and polynomial, which is an important problem in the theory of algorithms, number theory, and algebra. If the length (the number of digits in the positional notation) of the multiplied numbers does not exceed \(N\), then the generally accepted algorithm for column multiplication of two integers requires \(\mathcal{O}(N^{2})\) arithmetic operations with digits of the multiplied numbers. In 1962 A. A. Karatsuba [1, 2] proposed a recursive integer multiplication algorithm containing \(\mathcal{O}(N^{\text{log}_{2}3})\) arithmetic operations with numbers. In 1965, J. W. Cooley and J. W. Tukey published in [3] a fast algorithm for calculating the complex Fourier transform, and although this work did not talk about the multiplication of integers, all subsequent speed-ups of the multiplication algorithms were associated with the use of various versions of the fast Fourier transform. These two works were of a breakthrough nature and gave rise to a large line of research on fast algorithms. A detailed review of the development of multiplication algorithms can be found in the comprehensive work by S. B. Gashkov and I. S. Sergeev [4]. Here we will only mention the main achievements.

The next step forward was made in 1971 by A. Schönhage and F. Strassen [5], who presented two algorithms for multiplying integers. The performance of the fastest of them was estimated by the value of \(\mathcal{O}(N\log N\cdot 2^{O(\log^{*}N)})\) arithmetic operations. Subsequently, M. Fürer [6] found an algorithm for multiplying natural numbers that works with complex numbers and has a complexity of \(\mathcal{O}(N\log N\cdot 2^{O(\log^{*}N)})\) operations, where \(\log^{*}N\) is some function (iterated logarithm) that grows slower than any iteration of the logarithm. In 2008, in [7], an algorithm of the same complexity as that of Fürer was proposed, but using instead of the field \(\mathbb{C}\) some ring with a finite number of elements. Finally, in 2019, D. Harvey and J. van der Hoeven in work [8] published an algorithm for multiplying integers with a complexity of \(O(N\ln N)\) arithmetic operations. The existence of such an algorithm was predicted in [5]. Fast algorithms for multiplying integers have stimulated our research in this area, in particular, motivated the preparation of this article.

FOURIER TRANSFORM

Let \(\mathcal{R}\) be a commutative ring with unity; \(g\) is an element of the multiplicative group of this ring having the order \(n=2^{s}\), \(s\geqslant 2,\) and satisfying the equality \(g^{2^{s-1}}+1=0\). Such elements do not always exist. For example, there is no such element in the ring \(\mathbb{Z}_{9}=\mathbb{Z}/9\mathbb{Z}\). And in the ring \(\mathbb{Z}_{17}\) we have \(2^{2^{2}}+1=0\) and \(3^{2^{3}}+1=0\). In what follows we will assume that in the ring \(\mathcal{R}\) such an element \(g\)—we will call it the basic or primary unit—exists and, moreover, 2 is an invertible element of this ring.

Let \({\mathbf{a}}=(a_{0},a_{1},\ldots,a_{n-1})\in\mathcal{R}^{n}\) be a row vector with coordinates from the ring \(\mathcal{R}\). We define the polynomial \(A(x)=\sum_{i=0}^{n-1}a_{i}x^{i}\in\mathcal{R}[x]\). The Fourier transform \(\mathcal{F}(\mathbf{a})\) of the vector \(\mathbf{a}\) is called the vector

$${\mathbf{b}}=(A(1),A(g),A(g^{2}),\ldots,A(g^{n-1}))\in\mathcal{R}^{n}.$$

It is easy to see that, using the Gorner scheme, the vector \(\mathcal{F}({\mathbf{a}})\) can be calculated in \(O(n^{2})\) arithmetic operations. The following algorithm for fast calculation of the Fourier transform finds the vector \(\mathcal{F}({\mathbf{a}})\) significantly faster, namely in \(O(n\log n)\) arithmetic operations.

Let \(v\) be a nonnegative integer. Let us represent it in binary notation \(v=2^{s-1}v_{1}+\ldots+2v_{s-1}+v_{s}\), i.e., the digits \(v_{j}\) are 0 or 1 here. In what follows, we will denote by the symbol \(v^{*}\) the integer \(v^{*}=2^{s-1}v_{s}+\ldots+2v_{2}+v_{1}\). So, for \(s=3\) we have

$$0^{*}=0,\quad 1^{*}=4,\quad 2^{*}=2,\quad 3^{*}=6,\quad 4^{*}=1,\quad 5^{*}=5,\quad 6^{*}=3,\quad 7^{*}=7.$$

Algorithm 1. Input: the vector \({\mathbf{a}}=(a_{0},a_{1},\ldots,a_{2^{s}-1})\in\mathcal{R}^{n}\) ; the basic unit \(g\) of the ring \(\mathcal{R}\), having the order \(n=2^{s}\); and the precomputed sequence \(g_{u}=g^{2^{s-u}}\), \(g_{u-1}=g_{u}^{2}\), \(0\leqslant u\leqslant s\).

Output: the vector \(\mathcal{F}(\mathbf{a})\).

We construct a sequence of vectors \({\mathbf{a}_{u}}=(a_{u,0},a_{u,1},\ldots,a_{u,2^{s}-1})\in\mathcal{R}^{n}\), \(0\leqslant u\leqslant s\), according to the following rules:

(1) define the vector \({\mathbf{a}_{0}}\) by the equalities \(a_{0,v}=a_{v^{*}}\), \(0\leqslant v<2^{s}\);

(2) for each \(u\), \(0<u\leqslant s\), determine the coordinates \(a_{u,v}\), \(0\leqslant v<2^{s}\) of the vector \({\mathbf{a}_{u}}\) by equalities

$$a_{u,v}=a_{u-1,v}+g^{2^{s-u}v}a_{u-1,v+2^{u-1}}\quad\text{for}\quad 0\leqslant\lambda<2^{u-1};$$
(1)
$$a_{u,v}=a_{u-1,v-2^{u-1}}+g^{2^{s-u}v}a_{u-1,v}\quad\text{for}\quad 2^{u-1}\leqslant\lambda<2^{u},$$
(2)

where \(\lambda\equiv v(\text{mod }{2^{u}})\), \(0\leqslant\lambda<2^{u}\);

(3) put \(\mathcal{F}(\mathbf{a})={\mathbf{a}_{s}}\).

To formulate the following theorem, we define the polynomials

$$A_{u,\lambda}(x)=\sum_{\mu=0}^{2^{u}-1}a_{\lambda+\mu 2^{s-u}}x^{\mu},\quad 0\leqslant u\leqslant s,\,0\leqslant\lambda<2^{s-u}.$$

For \(u=s\), \(0\leqslant\lambda<1\) we find \(\lambda=0\), \(A_{s,0}(x)=A(x).\) In addition, \(A_{0,\lambda}(x)=a_{\lambda},0\leqslant\lambda<2^{s}.\)

The correctness of the algorithm is proved in the following theorem.

Theorem 1. For all indices \(0\leqslant u\leqslant s\), \(0\leqslant v<2^{s}\) the equalities

$$a_{u,v}=A_{u,\tau}(g^{2^{s-u}v}),\quad\text{where}\quad\tau\equiv v^{*}(\text{mod }{2^{s-u}}),\quad 0\leqslant\tau<2^{s-u}.$$

are fulfilled.

Let us first prove the following auxiliary statement.

Lemma 1. 1. If \(0\leqslant\lambda<2^{s-u}\), then \(A_{u-1,\lambda}(x^{2})+xA_{u-1,\lambda+2^{s-u}}(x^{2})=A_{u,\lambda}(x)\).

2. If \(2^{s-u}\leqslant\lambda<2^{s-u+1}\), then \(xA_{u-1,\lambda}(x^{2})+A_{u-1,\lambda-2^{s-u}}(x^{2})=A_{u,\lambda-2^{s-u}}(x)\).

Proof of the lemma. Denote by \(S(x)\) the left part of the first equality. Since for \(0\leqslant\lambda<2^{s-u}\) the equalities \(\lambda+\mu 2^{s-u+1}=\lambda+(2\mu)2^{s-u}\) and \(\lambda+2^{s-u}+\mu 2^{s-u+1}=\lambda+(2\mu+1)2^{s-u}\) are fulfilled,

$$S(x)=A_{u-1,\lambda}(x^{2})+xA_{u-1,\lambda+2^{s-u}}(x^{2})=\sum_{0\leqslant\mu<2^{u-1}}a_{\lambda+(2\mu)2^{s-u}}x^{2\mu}+x\sum_{0\leqslant\mu<2^{u-1}}a_{\lambda+(2\mu+1)2^{s-u}}x^{2\mu}.$$

For the first sum, we put \(\nu=2\mu.\) Then \(0\leqslant 2\mu=\nu<2^{u}\). For the second sum, let \(\nu=2\mu+1.\) Then \(1\leqslant 2\mu+1\leqslant 2^{u}-2+1=2^{u}-1.\)

Therefore, \(S(x)=\sum_{0\leqslant\nu\leqslant 2^{u}-1}a_{\lambda+\nu 2^{s-u}}x^{\nu}=A_{u,\lambda}(x),\) because \(0\leqslant\lambda<2^{s-u}\).

To prove the second statement of the lemma, we put \(\lambda=2^{s-u}+\varkappa\). Then \(0\leqslant\varkappa<2^{s-u}\) and according to the first statement we have

$$xA_{u-1,\lambda}(x^{2})+A_{u-1,\lambda-2^{s-u}}(x^{2})=$$
$$=xA_{u-1,\varkappa+2^{s-u}}(x^{2})+A_{u-1,\varkappa}(x^{2})=A_{u,\varkappa}(x)=A_{u,\lambda-2^{s-u}}(x).$$

Proof of Theorem 1. Let us use the induction on \(u\) from \(u=0\) to \(u=s\).

For \(u=0\) we have \(\tau\equiv v^{*}(\text{mod }{2^{s}})\) and therefore \(\tau=v^{*}\). Further

$$A_{0,v^{*}}(g^{2^{s}v})=A_{0,v^{*}}(1)=a_{v^{*}}=a_{0,v}.$$

Suppose that \(u\geqslant 1\) and for the vector \({\mathbf{a}_{u-1}}\) the statement of the theorem is fulfilled.

Let \(v=\lambda+2^{u}\mu,\tau\equiv v^{*}(\text{mod }{2^{s-u}}),0\leqslant\tau<2^{s-u},\nu\equiv v^{*}(\text{mod }{2^{s-u+1}}),0\leqslant\nu<2^{s-u+1}.\) It is easy to check that for \(v=2^{s-1}v_{1}+\ldots+2v_{s-1}+v_{s},\) where each binary digit \(v_{i}\) is equal to 0 or 1, the comparisons

$$v^{*}\equiv 2^{s-u}v_{s-u+1}+\ldots+v_{1}(\text{mod }{2^{s-u+1}}),\quad v^{*}\equiv 2^{s-u-1}v_{s-u}+\ldots+v_{1}(\text{mod }{2^{s-u}})$$

and

$$\lambda=2^{u-1}v_{s-u+1}+2^{u-2}v_{s-u+2}+\ldots+2v_{s-1}+v_{s}$$

are valid. From the last equality and comparisons, it follows that the case of \(0\leqslant\lambda<2^{u-1}\) occurs if and only if \(v_{s-u+1}=0\), and in this case \(\nu=\tau.\) If \(v_{s-u+1}=1\), then the inequalities \(2^{u-1}\leqslant\lambda<2^{u}\) and the equality \(\nu=\tau+2^{su}\) are fulfilled simultaneously. Let us first analyze the case \(0\leqslant\lambda<2^{u-1}.\) By the inductive assumption, we find

$$a_{u-1,v}=A_{u-1,\tau}(g^{2^{s-u+1}v}),\quad a_{u-1,v+2^{u-1}}=A_{u-1,\tau+2^{s-u}}(g^{2^{s-u+1}v}).$$

The last equality holds due to the fact that \((v+2^{u-1})^{*}=\tau+2^{s-u}.\) In addition, \(g^{2^{s-u+1}(v+2^{u-1})}=g^{2^{s-u+1}v}\). Now, using the first statement of the lemma, we find

$$a_{u,v}=a_{u-1,v}+g^{2^{s-u}v}a_{u-1,v+2^{u-1}}$$
$${}=A_{u-1,\tau}(g^{2^{s-u+1}v})+g^{2^{s-u}v}A_{u-1,\tau+2^{s-u}}(g^{2^{s-u+1}v})=A_{u,\tau}(g^{2^{s-u}v}).$$

The required equality is proved.

Consider the second case \(2^{u-1}\leqslant\lambda<2^{u}.\) As before, we find

$$v^{*}\equiv\tau+2^{s-u}\textrm{mod}{2^{s-u+1}}\quad\text{and}\quad(v-2^{u-1})^{*}\equiv\tau\textrm{mod}{2^{s-u+1}}.$$

Therefore

$$a_{u,v}=a_{u-1,v-2^{u-1}}+g^{2^{s-u}v}a_{u-1,v}=A_{u-1,\tau}(g^{2^{s-u+1}v})$$
$${}+g^{2^{s-u}v}A_{u-1,\tau+2^{s-u}}(g^{2^{s-u+1}v})=A_{u,\tau}(g^{2^{s-u}v}).$$

The equality \(g^{2^{s-u+1}(v-2^{u-1})}=g^{2^{s-u+1}v}\) was used here. Theorem 1 is thus proved. \(\Box\)

For \(u=s\), the number \(\tau\) in Theorem 1 satisfies the inequalities \(0\leqslant\tau<1\) and therefore \(\tau=0.\) Assuming \(u=s\) and \(\tau=0\) in this theorem, we get

$$a_{s,v}=A_{s,\tau}(g^{v})=A_{s,0}(g^{v})=A(g^{v}),\quad 0\leqslant v<2^{s}.$$

The correctness of the algorithm is proved.

The obvious implementation of the described algorithm requires saving the vector \(\mathbf{a}_{u-1}\) until the end of calculating all the coordinates of the vector \(\mathbf{a}_{u}\). But already in the article by Cooley and Tukey [3] it was pointed out that it is possible to organize calculations so that the necessary memory is reduced by half. In other words, we can construct calculations so that the coordinates of the vector \(\mathbf{a}_{u}\) will replace the corresponding coordinates of the vector \(\mathbf{a}_{u-1}\). We will show how to do this in the algorithm described above. To do this, you should calculate the new coordinates not in ascending order \(v\), but choose their order in a slightly more complex way.

Let us represent the number \(v\) in the form

$$v=\lambda+2^{u}\mu,\quad 0\leqslant\lambda<2^{u},\quad 0\leqslant\mu<2^{s-u},$$

and rewrite equalities (1) and (2), leaving the first of them unchanged, and replacing the number \(v\) with \(v+2^{u-1}\) in the second. As a result, the following relations are obtained

$$a_{u,v}=a_{u-1,v}+g^{2^{s-u}v}a_{u-1,v+2^{u-1}},$$
$$a_{u,v+2^{u-1}}=a_{u-1,v}-g^{2^{s-u}v}a_{u-1,v+2^{u-1}},$$

valid for all \(v\) with the condition \(v\equiv\lambda(\text{mod }{2^{u}})\), \(0\leqslant\lambda<2^{u-1}\). The equality

$$g^{2^{s-u}\cdot(v+2^{u-1})}=-g^{2^{s-u}\lambda}.$$

was used here. Moreover, \(g^{2^{s-u}\lambda}=g_{u}^{\lambda}\), so the resulting recurrent equations can be rewritten in the form

$$a_{v}:=a_{v}+g_{u}^{\lambda}a_{v+2^{u-1}},$$
(3)
$$a_{v+2^{u-1}}:=a_{v}-g_{u}^{\lambda}a_{v+2^{u-1}}.$$
(4)

For brevity, we have omitted the indexes indicating the vector number here. On the left in equalities (3) and (4) are the coordinates of the vector \(\mathbf{a}_{u}\), and on the right are the expressions that depend on the same coordinates of the vector \(\mathbf{a}_{u-1}\). The obtained formulas allow us to replace the coordinates with the numbers \(v,v+2^{u-1}\) of the vector \(\mathbf{a}_{u-1}\) with coordinates with the same numbers of the vector \(\mathbf{a}_{u}\). Let us order the pairs \((\mu,\lambda)\), \(0\leqslant\mu<2^{s-u}\), \(0\leqslant\lambda<2^{u-1}\) in lexicographic order, i.e., in ascending order of \(\mu\), and for equal \(\mu\) — in ascending order of \(\lambda\). Performing these calculations in the specified order for all pairs \(v=\lambda+2^{u}\mu,v+2^{u-1}\), we will calculate all the coordinates of the vector \(\mathbf{a}_{u}\). Calculating the next coefficient \(g_{u}^{\lambda}\) will require one multiplication operation in the ring \(\mathcal{R}\), and all calculations require \(2^{s-1}s\) multiplication operations and \(2^{s}s\) addition and subtraction operations, a total of \(3\times 2^{s-1}s\) arithmetic operations.

The following algorithm defines the mapping \(\mathcal{F}^{-1}:\mathcal{R}^{2^{s}}\rightarrow\mathcal{R}^{2^{s}}\), inverse to the Fourier transform \(\mathcal{F}\), i.e., satisfying the equality \(\mathcal{F}^{-1}(\mathcal{F}({\mathbf{a}}))={\mathbf{a}}\) for any vector \({\mathbf{a}}\in\mathcal{R}^{2^{s}}\).

Algorithm 2. Input: the vector \({\mathbf{b}}=(b_{0},b_{1},\ldots,b_{2^{s}-1})\in\mathcal{R}^{n}\); the basic unit \(g\) of the ring \(\mathcal{R}\), having the order \(n=2^{s}\); and the precomputed sequence \(g_{u}=g^{2^{s-u}},\,g_{u-1}=g_{u}^{2}\), \(0\leqslant u\leqslant s\).

Output: the vector \(\mathcal{F}^{-1}(\mathbf{b})\).

We construct a sequence of vectors \({\mathbf{b}_{u}}=(b_{u,0},b_{u,1},\ldots,b_{u,2^{s-1}})\in\mathcal{R}^{2^{s}},0\leqslant u\leqslant s\), according to the following rules:

(1) put \(\mathbf{b}_{0}=\mathbf{b}\);

(2) for each \(u,0\leqslant u<s\), and each \(v,0\leqslant v<2^{s}\), define \(\lambda\), which is the smallest nonnegative remainder of the number \(v\) when divided by \(2^{s-u}\) and we put

$$b_{u+1,v}=\frac{1}{2}(b_{u,v}+b_{u,v+2^{s-u-1}}),\quad\text{or}\quad 0\leqslant\lambda<2^{s-u-1};$$
(5)
$$b_{u+1,v}=\frac{1}{2}g^{-2^{u}v}(b_{u,v}-b_{u,v-2^{s-u-1}}),\quad\text{or}\quad 2^{s-u-1}\leqslant\lambda<2^{s-u}.$$
(6)

This will sequentially find the coordinates of all vectors \({\mathbf{b}}_{u}\), \(0\leqslant u\leqslant s\);

(3) put \({\mathcal{F}^{-1}(\mathbf{b})}=(b_{s,0^{*}},b_{s,1^{*}},\ldots,b_{s,(2^{s}-1)^{*}}).\)

The following statement proves the correctness of Algorithm 2. It uses the notation introduced in Algorithms 1 and 2.

Theorem 2. Let \(\mathbf{a}\) be an arbitrary vector from \(\mathcal{R}^{2^{s}}\) and \({\mathbf{b}}=\mathcal{F}(\mathbf{a})\).

(1) For each index \(u,0\leqslant u\leqslant s\), the equality \({\mathbf{b}_{u}}={\mathbf{a}_{s-u}}\) holds.

(2) The equality \(\mathcal{F}^{-1}(\mathcal{F}({\mathbf{a}}))={\mathbf{a}}\) is valid.

Proof. We prove the first statement by induction on \(u\). Using item 1 from Algorithm 2, the definition of the vector \(\mathbf{b}\) from the condition of Theorem 2, and item 3 from Algorithm 1, we conclude that \({\mathbf{b}}_{0}={\mathbf{b}}={\mathcal{F}(\mathbf{a})}={\mathbf{a}}_{s}\). This proves the first statement of Theorem 2 for \(u=0\). The following is the reasoning in the general case. Let us assume that it is true for some \(u\geqslant 0\).

Let \(v=\lambda+2^{u}\mu\) and \(0\leqslant\lambda<2^{u-1}\). Using the equalities \((1)\) for \(a_{u,v}\) and \((2)\) for \(a_{u,v+2^{u-1}}\), we find

$$a_{u,v}=a_{u-1,v}+g^{2^{s-u}v}a_{u-1,v+2^{u-1}},$$
$$a_{u,v+2^{u-1}}=a_{u-1,v}+g^{2^{s-u}(v+2^{u-1})}a_{u-1,v+2^{u-1}}.$$

Solving this system of equations with respect to \(a_{u-1,v}\), \(a_{u-1,v+2^{u-1}}\), we get

$$a_{u-1,v}=\frac{1}{2}(a_{u,v}+a_{u,v+2^{u-1}}),$$
(7)
$$a_{u-1,v+2^{u-1}}=\frac{1}{2}g^{-2^{s-u}v}(a_{u,v}-a_{u,v+2^{u-1}}).$$
(8)

In the calculations, we used the equality \(g^{2^{s-1}}=-1\), and also the invertibility of the elements \(g\) and \(2\) in the ring \(\mathcal{R}\).

Taking into account equality (5), the induction hypothesis, and equality (7), we have

$$b_{u+1,v}=\frac{1}{2}(b_{u,v}+b_{u,v+2^{s-u-1}})=\frac{1}{2}(a_{s-u,v}+a_{s-u,v+2^{s-u-1}})=a_{s-u-1,v}.$$

In the same way, using (6), the inductive hypothesis, and equality (8), we find

$$b_{u+1,v+2^{s-u-1}}=\frac{1}{2}g^{-2^{u}(v+2^{s-u-1})}(b_{u,v+2^{s-u-1}}-b_{u,v})=\frac{1}{2}g^{-2^{u}v}(b_{u,v}-b_{u,v+2^{s-u-1}})$$
$${}=\frac{1}{2}g^{-2^{u}v}(a_{s-u,v}-a_{s-u,v+2^{s-u-1}})=a_{s-u-1,v+2^{s-u-1}}.$$

The first statement is proved.

Let us prove the second statement. To do this, we will use the first statement and the definition of the vector \(\mathbf{a}_{0}\) from item 1 of Algorithm 1. We have

$${\mathbf{a}}=(a_{0,0^{*}},a_{0,1^{*}},\ldots,a_{0,(2^{s}-1)^{*}})=(b_{s,0^{*}},b_{s,1^{*}},\ldots,b_{s,(2^{s}-1)^{*}})={\mathcal{F}^{-1}}(\mathbf{b}).$$

Theorem 2 is completely proved.

In connection with numerous applications, there is an extensive literature devoted to fast algorithms for computing the Fourier transform. The authors of these publications retain the basic ideas of the original algorithm, but depending on their interests and mathematical background, they focus on diagrams and drawings that explain the operation of the algorithm, try to improve the structure of the algorithm, making its implementation more efficient, and improve the mathematical part of applied algorithms by choosing the ring \(\mathcal{R}\) with useful properties or using multidimensional variants of the Fourier transform.