# Revisiting Fast Fourier multiplication algorithms on quotient rings

Ramiro Martínez Paz Morillo
Universitat Politècnica de Catalunya e-mail<EMAIL_ADDRESS>0000-0003-0496-6462 0000-0002-0063-2716

(2023
April)

###### Abstract

This work formalizes efficient Fast Fourier-based multiplication algorithms
for polynomials in quotient rings such as
$\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>$, with $n$ a power of $2$ and $m$ a
non necessarily prime integer. We also present a meticulous study on the
necessary and/or sufficient conditions required for the applicability of these
multiplication algorithms. This paper allows us to unify the different
approaches to the problem of efficiently computing the product of two
polynomials in these quotient rings.

Keywords: Fast Fourier Transform, polynomial quotient ring, multiplication
algorithm, ideal lattice

##  1 Introduction

Constructing efficient multiplication algorithms for polynomials with
coefficients in a ring $R$ has been an extensive research area. Given two
polynomials $g(x),\allowbreak h(x)\in R[x]$ of degree bounded by $n$,
$g(x)=\sum_{i=0}^{n-1}g_{i}x^{i}$ and $h(x)=\sum_{i=0}^{n-1}h_{i}x^{i}$,
computing its product in a naïve way (known as the schoolbook multiplication
algorithm),

$(g\cdot h)(x)=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\left(g_{i}\cdot
h_{j}\right)x^{i+j},$

requires a quadratic number, $n^{2}$, of multiplications of elements from the
ring $R$.

$\begin{array}[]{r<{x^6} c r<{x^5} c r<{x^4} c r<{x^3} c r<{x^2} c r<{x} c
r}\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{6}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{5}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{4}&&g_{3}x^{3}&+&g_{2}x^{2}&+&g_{1}&+&g_{0}\\\
\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{6}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{5}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{4}&\times&h_{3}x^{3}&+&h_{2}x^{2}&+&h_{1}&+&h_{0}\\\
\hline\cr\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{6}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{5}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{4}&&g_{3}\cdot
h_{0}x^{3}&+&g_{2}\cdot h_{0}x^{2}&+&g_{1}\cdot h_{0}&+&g_{0}\cdot h_{0}\\\
\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{6}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{5}&&g_{3}\cdot
h_{1}x^{4}&+&g_{2}\cdot h_{1}x^{3}&+&g_{1}\cdot h_{1}x^{2}&+&g_{0}\cdot
h_{1}&&\\\
\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{6}&&g_{3}\cdot
h_{2}x^{5}&+&g_{2}\cdot h_{2}x^{4}&+&g_{1}\cdot h_{2}x^{3}&+&g_{0}\cdot
h_{2}x^{2}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}&&\\\
g_{3}\cdot h_{3}x^{6}&+&g_{2}\cdot h_{3}x^{5}&+&g_{1}\cdot
h_{3}x^{4}&+&g_{0}\cdot
h_{3}x^{3}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}x^{2}&&\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}&&\\\
\hline\cr\textstyle\sum\limits_{\scalebox{0.4}{i+j=6}}g_{i}h_{j}x^{6}&+&\textstyle\sum\limits_{\scalebox{0.4}{i+j=5}}g_{i}h_{j}x^{5}&+&\textstyle\sum\limits_{\scalebox{0.4}{i+j=4}}g_{i}h_{j}x^{4}&+&\textstyle\sum\limits_{\scalebox{0.4}{i+j=3}}g_{i}h_{j}x^{3}&+&\textstyle\sum\limits_{\scalebox{0.4}{i+j=2}}g_{i}h_{j}x^{2}&+&\textstyle\sum\limits_{\scalebox{0.4}{i+j=1}}g_{i}h_{j}&+&g_{0}h_{0}\end{array}$

If we now want to work in a ring $R[x]/\left<f(x)\right>$ the schoolbook
multiplication algorithm would perform the same amount of operations taking
into account that at the end we should perform a reduction.

For the particular cases $f(x)=x^{n}\pm 1$ it is clear that the algorithm
performs the same number of operations, as we just need to multiply by $\mp 1$
all $i$-coefficients from $n$ to $2n-2$ and add them to their corresponding
$i-n$ column.

The goal of this work is to formalize and unify some concepts used to build
more efficient multiplication algorithms focusing on the ring
$R[x]=\mathbb{Z}_{m}[x]$ and then on its quotient
$\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$, with $n$ a power of $2$ and $m$ non
necessarily prime (although sometimes we would also consider $x^{n}-1$ or in
general $x^{n}-a$).

We choose to study optimizations for this particular ring as it is widely used
by cryptographic constructions that base their security on ideal lattices
[10], that can be identified with ideals in
$\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$.

Most of the literature usually deals with this matter by providing a set of
recipes that can be applied for some specific particular rings (considering
whether $m$ is prime or not or how does $x^{n}-a$ split), without specifying
if the imposed conditions in these recipes are necessary or only sufficient.
This lack of detail might make more difficult the applicability of such
recipes. Through this article we instead analyze what are the fundamental
properties that allow us to obtain a computational speedup from a
comprehensive and mathematical point of view, so that the reader can apprehend
these techniques and distinguish intrinsic properties from superfluous
conventions.

Therefore, the analysis presented in this paper will help the reader to avoid
confusions when using multiplication algorithms for polynomials in quotient
rings $\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$.

Many of the ideas developed in this article are folklore when working on other
rings such as $\mathbb{C}[x]$ or $\mathbb{Z}_{q}[x]$ with $q$ a prime
satisfying certain conditions, but an exhaustive analysis might be very
helpful to analyze when these ideas can be, completely or partially,
generalized to our ring of interest and why the required conditions for the
underlying ring are indeed necessary or just sufficient.

###  1.1 Related works

####  1.1.1 Karatsuba multiplication algorithm

The first subquadratic multiplication algorithm was designed by Karatsuba in
[8], with a cost of $\mathcal{O}\left(n^{\log{3}}\right)$ derived from a
clever divide an conquer strategy. We include it here as our approach uses
Karatsuba’s algorithm as a subroutine.

Let $g(x)$ and $h(x)$ be two polynomials of degree strictly smaller than $n$
(a power of two). We can split these polynomials into upper and lower degree
polynomials as $g(x)=g_{U}(x)x^{n/2}+g_{L}(x)$ and
$h(x)=h_{U}(x)x^{n/2}+h_{L}(x)$ where $g_{L},g_{U},h_{L},h_{U}$ have all
degree smaller than $n/2$.

A naïve computation would be

$\displaystyle g(x)\cdot h(x)$
$\displaystyle=(g_{U}(x)x^{n/2}+g_{L}(x))(h_{U}(x)x^{n/2}+h_{L}(x))$
$\displaystyle=\left(g_{U}(x)\cdot h_{U}(x)\right)x^{n}$
$\displaystyle\phantom{{}={}}+\left(g_{U}(x)\cdot h_{L}(x)+g_{L}(x)\cdot
h_{U}(x)\right)x^{n/2}$ $\displaystyle\phantom{{}={}}+g_{L}(x)\cdot h_{L}(x).$

That way we divide the full multiplication into four multiplications of
polynomials of size $n/2$. One can see however that this does not improve the
efficiency of the computation. Let $T(n)$ be the number of operations required
for computing the product using this method. The recurrence obtained,
$T(n)=4T(n/2)+\mathcal{O}\left(n\right)$, implies (via the Master Theorem for
divide-and-conquer recurrences [3]) that $T(n)=\mathcal{O}\left(n^{2}\right)$.

Karatsuba’s gifted idea was to notice that the crossed terms can be obtained
from the other terms and a single multiplication of $n/2$-polynomials. That
is, we can write the term $\left(g_{U}(x)\cdot h_{L}(x)+g_{L}(x)\cdot
h_{U}(x)\right)$ as

$(g_{L}(x)+g_{U}(x))(h_{L}(x)+h_{U}(x))-\left(g_{U}(x)\cdot
h_{U}(x)\right)-\left(g_{L}(x)\cdot h_{L}(x)\right).$

Input: Two polynomials $g(x)$ and $h(x)$ of degree bounded by $n$

Result: Product of $g(x)\cdot h(x)$

1 if  _n = 1_ then return _$g\cdot h$_ ;

Split $g(x)$ and $h(x)$ into $g_{L}(x),g_{U}(x),h_{L}(x),h_{U}(x)$.

2 $a(x)\coloneqq\textsc{Karatsuba}(g_{U}(x),h_{U}(x))$

3 $b(x)\coloneqq\textsc{Karatsuba}(g_{L}(x),h_{L}(x))$

4 $c(x)\coloneqq\textsc{Karatsuba}(g_{L}(x)+g_{U}(x),h_{L}(x)+h_{U}(x))$

5 return _$a(x)x^{n}+(c(x)-a(x)-b(x))x^{n/2}+b(x)$_

Algorithm 1 Karatsuba

Notice how the recurrence now computes only $3$ products of half size and a
linear amount of operations ($T(n)=3T(n/2)+\mathcal{O}\left(n\right)$)
providing the desired sublinear running time of
$T(n)=\mathcal{O}\left(n^{\log{3}}\right)$ (solving the recurrence with the
Master Theorem for divide-and-conquer recurrences [3]).

####  1.1.2 Karatsuba multiplication algorithm $\mod f(x)$

However notice this is not the most natural way of writing this recursion when
working $\mod x^{n}\pm 1$ as all recursive calls work the same way but the
last one, where a reduction has to be performed.

Alternatively we can split $g(x)=g_{1}(x^{2})x+g_{0}(x^{2})$, with $g_{0}$
containing the even coefficients and $g_{1}$ containing the odd ones. This
allows us to think of $g(x)\in R[x]$ of degree smaller than $n$ as
$g(x,y)=g_{0}(y)+g_{1}(y)x\in R[x,y]$ of $x$-degree $1$ and $y$-degree smaller
than $n/2$. It is called _Dual Karatsuba_ and the idea remains the same:

$\displaystyle g(x)\cdot h(x)$
$\displaystyle=(g_{1}(x^{2})x+g_{0}(x^{2}))(h_{1}(x^{2})x+h_{0}(x^{2}))$
$\displaystyle=\left(g_{1}(x^{2})\cdot h_{1}(x^{2})\right)x^{2}$
$\displaystyle\phantom{{}={}}+\left(g_{1}(x^{2})\cdot
h_{0}(x^{2})+g_{0}(x^{2})\cdot h_{1}(x^{2})\right)x$
$\displaystyle\phantom{{}={}}+g_{0}(x^{2})\cdot h_{0}(x^{2})$

And analogously as we did before we can write the second term with only one
additional multiplication. $\left(g_{1}(x^{2})\cdot
h_{0}(x^{2})+g_{0}(x^{2})\cdot h_{1}(x^{2})\right)$ is:

$\left(\left(g_{1}(x^{2})+g_{0}(x^{2})\right)\cdot\left(h_{1}(x^{2})+h_{0}(x^{2})\right)-g_{1}(x^{2})\cdot
h_{1}(x^{2})-g_{0}(x^{2})\cdot h_{0}(x^{2})\right).$

Input: Two polynomials $g(x)$ and $h(x)$ of degree bounded by $n$

Result: Product of $g(x)\cdot h(x)$

if  _n = 1_ then return _$g\cdot h$_ ;

Split $g(x)$ and $h(x)$ into $g_{0}(x),g_{1}(x),h_{0}(x),h_{1}(x)$.

$a(y)\coloneqq\textsc{Karatsuba}(g_{1}(y),h_{1}(y))$

$b(y)\coloneqq\textsc{Karatsuba}(g_{0}(y),h_{0}(y))$

$c(y)\coloneqq\textsc{Karatsuba}(g_{0}(y)+g_{1}(y),h_{0}(y)+h_{1}(y))$

return _$a(x^{2})x^{2}+(c(x^{2})-a(x^{2})-b(x^{2}))x+b(x^{2})\pmod{x^{n}\pm
1}$_

Algorithm 2 Karatsuba $\pmod{x^{n}\pm 1}$

Now the reduction modulo $x^{n}\pm 1$ works at each level of the recursive
algorithm, as $\widehat{g}(y)\cdot\widehat{h}(y)\pmod{y^{n/2}\pm 1}$ is
equivalent to $\widehat{g}(x^{2})\cdot\widehat{h}(x^{2})\pmod{x^{n}\pm 1}$
once we change variables again. We obtain no computational advantage, but it
allows us to understand it from a different perspective.

Notice $g_{0}(y)+g_{1}(y)\equiv g(x,y)\mod x-1$ and $g_{0}(y)\equiv g(x,y)\mod
x$. These ideas are considered in [4] in order to see all these tools as part
of the same framework.

####  1.1.3 Faster multiplication algorithms

Even faster algorithms can be obtained from more clever recurrences, mapping
the polynomials into a different domain in a recursive way (recursively
computing two transforms of half the size
$T(n)=2T(n/2)+\mathcal{O}\left(n\right)$) where they can be efficiently
multiplied in linear time, so that the final computational complexity is
$\mathcal{O}\left(n\log n\right)$. Through this work we are going to focus and
systematically explore the ones derived from the Fast Fourier Transform (FFT)
paradigm, that is going to be extensively described in the following sections.
This approach is usually referred as Number Theoretic Transformation (NTT)
when working with finite fields.

The main idea of the FFT recurrence is attributed to Gauss and was fully
developed by Cooley and Tukey in its seminal work [6] considering the ring of
complex numbers.

Many variants have been developed since then, generalizing [6] to non-power of
two bounded degree polynomials or providing additional tricks and
interpretations from which we benefit, such as [7]. An extensive and
magnificently well documented survey can be found in [4].

Most of the work has focused on the particular case of multiplications in
$\mathbb{Z}_{q}[x]/\left<x^{n}+1\right>$ when $q$ is prime and $x^{n}+1$ fully
splits in linear factors. That has been studied for a while, both from a
software [9] and hardware [14] point of view.

We are particularly interested in the ideas presented in [12], as they
specifically discuss multiplications of polynomials in
$\mathbb{Z}_{q}[x]/\left<x^{n}+1\right>$ when $x^{n}+1$ does not fully split
in linear factors (a situation that happens in some lattice-based
cryptographic schemes such as some commitment schemes [2]) and the standard
FFT can only be partially applied. However [12] only considers the case with a
prime $q$ and briefly describes the procedure.

This technique of partially applying an FFT is sometimes called incomplete NTT
[5] and usually interpreted like a Chinese Remainder Transform (CRT), as in
[11] doing Fast Chinese remaindering [17].

However, most of the literature only provides some sufficient conditions that
allow some particular implementation or specific abstraction of a fast
multiplication algorithm that are not directly generalizable. In spite of that
we present a more general framework for multiplications in
$\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$ that would allow the reader to
comprehend why some folklore assumptions are indeed necessary and why some
others are not, from a mathematically rigorous, yet accessible for readers not
familiarized with algebraic constructions, point of view.

###  1.2 Notation and conventions

Since our goal is to work in $R[x]/\left<f(x)\right>$, with $f$ a monic
polynomial, we choose as a representative for $g(x)\in R[x]/\left<f(x)\right>$
its remainder when divided by $f(x)$, denoted by $g(x)\nonscript\mskip-4.0mu
plus -2.0mu minus -4.0mu\mkern 5.0mu\mathbin{\operator@font rem}\penalty
900\mkern 5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0muf(x)$.

We denote vectors by lower-case bold-faced roman letters and use $\log$ for
the binary logarithm.

We borrow most of our notation from [4], and present some new definitions
through sections 3 and 4, that we believe are of independent interest.

##  2 Pointwise product

The main idea behind any Fast Fourier Transform multiplication technique is to
compute the product of two polynomials via the pointwise product of their
evaluations on certain points of the ring $R$.

It is straightforward by the definition of the product of polynomials that
given a point $x_{0}\in R$ the evaluation of the product is equal to the
product of the evaluations $(g\cdot h)(x_{0})=g(x_{0})\cdot h(x_{0})$.

This way if we compute enough evaluations (we denote this transform as $T$)
then we could perform a pointwise product (denoted by $\odot$) of the
evaluations and then interpolate back ($T^{-1}$) the polynomial.

$\begin{array}[]{*{7}{c}}{(R[x])}^{2}&\xrightarrow{\odot\circ
T}&R^{k}&\xrightarrow{T^{-1}}&R[x]\\\
(g(x),h(x))&\mapsto&\begin{pmatrix}g(x_{0})\\\ g(x_{1})\\\ \vdots\\\
g(x_{k-1})\end{pmatrix}\odot\begin{pmatrix}h(x_{0})\\\ h(x_{1})\\\ \vdots\\\
h(x_{k-1})\end{pmatrix}&\mapsto&(g\cdot h)(x)\end{array}$

In the following sections we will explore what possibilities do we have for
$R$, $k$ and $x_{0},x_{1},\dots,\allowbreak x_{k-1}$ so that $T^{-1}$ is well
defined and both $T$ and $T^{-1}$ are efficiently computable. We are going to
characterize the necessary and sufficient conditions the evaluation points
have to satisfy to be able to perform these operations.

###  2.1 General invertibility of $T$

To deal with the invertibility of transform $T$ when applied to polynomials of
degree bounded by $n$ we notice it is a linear mapping and characterize it by
its associated matrix

$V=\begin{pmatrix}1&x_{0}&{x_{0}}^{2}&\cdots&{x_{0}}^{n-1}\\\
1&x_{1}&{x_{1}}^{2}&\cdots&{x_{1}}^{n-1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&x_{k-1}&{x_{k-1}}^{2}&\cdots&{x_{k-1}}^{n-1}\\\ \end{pmatrix}.$

This special matrix is known as a Vandermonde matrix. If we choose $k=n$ we
have a square Vandermonde matrix and we can discuss its invertibility.

Since we are working with a general commutative ring with unity $R$, a matrix
is invertible if and only if its determinant is invertible [16]. The
determinant of a Vandermonde matrix is easy to compute and has the form

$\det(V)=\prod_{0\leq i<j<n}(x_{j}-x_{i}).$

Now if $R$ is a field it is just sufficient to choose $n$ different evaluation
points $x_{0},\dots,x_{n-1}$.

If $R$ is just a commutative ring it is a necessary and sufficient condition
to choose points such that their differences are invertible in $R$.

######  Condition 1 (Points with invertible differences).

We say a set of points satisfies Condition 1 if the difference of every pair
is invertible in $R$.

######  Remark 1.

Choosing $n$ evaluation points with invertible differences in $R$ is a
necessary and sufficient condition for the transform $T$ to be invertible.

Notice how we are talking about transforming and anti-transforming polynomials
of a certain degree. Given two polynomials $g(x)$ and $h(x)$ of degrees $n$
and $n^{\prime}$, since we want to recover the polynomial $g(x)\cdot h(x)$, we
would have to think them as polynomials of degree smaller or equal than
$n+n^{\prime}$ and use $(n+n^{\prime}+1)\times(n+n^{\prime}+1)$ Vandermonde
matrices.

###  2.2 Pointwise product of evaluations modulo $f(x)$

Given $a\in R$111 One can see that in the special cases $a=\pm 1$ we have that
the product in $R[x]/\left<x^{n}-1\right>$ and $R[x]/\left<x^{n}+1\right>$ is
usually described in the literature as a cyclic/anti-cyclic convolution
(denoted by $\ast$).  $\displaystyle(g\cdot h)(x)\pod{{\operator@font
rem}\mkern 6.0mux^{n}-1}$ $\displaystyle=g(x)\cdot h(x)\pod{{\operator@font
rem}\mkern 6.0mux^{n}-1}$
$\displaystyle=\left(\sum_{i=0}^{n-1}g_{i}x^{i}\right)\left(\sum_{j=0}^{n-1}h_{j}x^{j}\right)\pod{{\operator@font
rem}\mkern 6.0mux^{n}-1}$
$\displaystyle=\sum_{k=0}^{n-1}\left(\sum_{\begin{subarray}{c}i,j\\\ i+j\equiv
k\\\ \mod{n}\end{subarray}}g_{i}\cdot h_{j}\right)x^{k}$ $\displaystyle=(g\ast
h)(x)$ This intuition might be of independent interest as a convolution
product in the regular domain is a pointwise product in the transformed
domain.  we can always consider polynomials in $R[x]/\left<x^{n}-a\right>$ as
polynomials in $R[x]$ with degree strictly bounded by $n$ (using the canonical
representative $\operator@font rem$), compute, as we said before, their
product as a polynomial in $R[x]$ with degree strictly bounded by $2n$ via a
$2n$-transform and then applying $\allowbreak\mkern 12.0mu{\operator@font
rem}\,\,x^{n}-a$ again to obtain the representative with degree smaller than
$n$.

The main issue we face when trying to use the pointwise product of evaluations
technique to compute the product of two polynomials modulo $f(x)$ is that
evaluation is not well defined in general as it depends on the representative
we choose from the class of equivalence modulo $f(x)$.

In general, for an arbitrary $x_{0}$, it is not the same to compute
$(g(x)\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus
-4.0muf(x))(x_{0})\cdot(h(x)\nonscript\mskip-4.0mu plus -2.0mu minus
-4.0mu\mkern 5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0muf(x))(x_{0})$ than
$(g(x)\cdot h(x)\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0muf(x))(x_{0})$.

For this reason we have to choose specific points where evaluation is
compatible with congruence classes. If $\alpha$ is such that for any two
equivalent polynomials $g(x)\equiv\widehat{g}(x)\pmod{f(x)}$ we obtain
$g(\alpha)=\widehat{g}(\alpha)$ then we necessarily have $f(\alpha)=0$ and
$\alpha$ has to be a root of $f(x)$.

Let $\alpha$ be a root of $f(x)$. Then $g(x)\equiv\widehat{g}(x)\pmod{f(x)}$
implies $g(\alpha)=\widehat{g}(\alpha)$ and therefore

$(g(x)\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus
-4.0muf(x))(\alpha)\cdot(h(x)\nonscript\mskip-4.0mu plus -2.0mu minus
-4.0mu\mkern 5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0muf(x))(\alpha)=(g(x)\cdot
h(x)\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0muf(x))(\alpha).$

In conclusion, for the particular case with $f(x)=x^{n}-a$, where $a\in R$,
$\alpha$ has to be an $n$/̄th root of $a$. By choosing
$\alpha_{0},\dots,\alpha_{n-1}$ different $n$/̄th roots of $a$ with invertible
differences we would be able to directly recover $g(x)\cdot
h(x)\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu\mkern
5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mu{x^{n}-a}$ from the
pointwise product of their evaluations in $\alpha_{0},\dots,\alpha_{n-1}$.

This reduces the number of computations needed, since only $n$ evaluation
points are required and no further reduction is needed to obtain the canonical
representative.

######  Condition 2 (Roots of $f(x)$ as points).

We say a set of points in $R$ for a polynomial in $R[x]/\left<f(x)\right>$
satisfies Condition 2 if they are roots of $f(x)$.

######  Remark 2.

Choosing $n$/̄th roots of $a$ as evaluation points is a necessary and
sufficient condition for the evaluations of polynomials in
$R[x]/\left<x^{n}-a\right>$ to be well defined.

So far conditions 1 and 2 are necessary and sufficient conditions to use
pointwise product of evaluations as a technique to compute the product of two
polynomials in $R[x]/\left<x^{n}-a\right>$. The next step is to study when can
this be computed efficiently.

##  3 Efficient transforms

In this section we are going to define efficient transform and anti-transform
protocols from a theoretical and asymptotical point of view. Additional
implementation tricks or approaches (for example, whether the recurrences are
solved in an iterative or recursive way) could have an important impact to
save up space or computations but are out of the scope of this article.

###  3.1 Efficient evaluation of $T$

Once we have seen the requirements for the pointwise product of evaluations to
work under each possible concerned circumstances we have to discus how to
efficiently apply them.

Computing each of the $n$ evaluations individually would require
$\mathcal{O}\left(n\right)$ operations, for a total of
$\mathcal{O}\left(n^{2}\right)$. The Fast Fourier approach outperforms that
computing the $n$ evaluations at the same time by means of a divide-and-
conquer recursive strategy.

If we call $x_{i}$ to one of the evaluation points and we decompose the
polynomial $g(x)$ into two polynomials $g_{0}(x)$ and $g_{1}(x)$ of half the
size with even and odd coefficients respectively, as in Dual Karatsuba, we can
write

$g(x_{i})=g_{0}(x_{i}^{2})+x_{i}\cdot g_{1}(x_{i}^{2}).$

With this recursion we reduce a single polynomial evaluation of degree bounded
by $n$ to two polynomial evaluations of degree bounded by $n/2$, a product in
$R$ and an addition in $R$. Directly doing this would not save us any cost, as
it would still take $\mathcal{O}\left(n\right)$ per evaluation.

The main idea is to choose the evaluation points
$\\{x_{0},x_{1},\dots,x_{n-1}\\}$ so that the set containing their squares
$\\{y\;|\;y={x_{i}}^{2}\\}$ contains only $n/2$ elements (therefore we could
reuse the evaluations of $g_{0}$ and $g_{1}$ on the squares). We would like
that to be true recursively so we introduce the following definition, already
satisfying Condition 2.

######  Definition 1 (Twofold set of $n$/̄th roots).

An indexed set $\alpha_{0},\dots,\alpha_{n-1}\in R$ (properly reindexed if
required) of $n$/̄th roots of an element $a\in R$, with $n$ a power of 2, is
said to be a _twofold set of $n$/̄th roots_ if $i\equiv
j\pmod{2^{{\log(n)}-k}}$ implies ${\alpha_{i}}^{2^{k}}={\alpha_{j}}^{2^{k}}$
for $k$ from $0$ to $\log(n)$.

We can visually represent it as a full binary tree like in Figure 1. Observe
the evaluation points, leafs in the tree, appear in _bit-reversed order_.

$a$$\alpha_{\,0}$$\alpha_{\,00}$$\alpha_{\,000}$$\alpha_{\,100}$$\alpha_{\,10}$$\alpha_{\,010}$$\alpha_{\,110}$$\alpha_{\,1}$$\alpha_{\,01}$$\alpha_{\,001}$$\alpha_{\,101}$$\alpha_{\,11}$$\alpha_{\,011}$$\alpha_{\,111}$
Figure 1: Twofold set of $8$/̄th roots

######  Remark 3.

Given $\alpha_{0},\dots,\alpha_{n-1}$ a twofold set of $n$/̄th roots of $a\in
R$ then the set $\\{{\alpha_{0}}^{2},\dots,\allowbreak{\alpha_{n/2-1}}^{2}\\}$
is a twofold set of $n/2$/̄th roots of $a$.

Choosing as evaluation points a twofold set of roots
$\alpha_{0},\dots,\alpha_{n-1}$ we have that for every $0\leq i<n/2$ the
equality ${\alpha_{i}}^{2}={\alpha_{i+n/2}}^{2}$ holds and we can write

$\displaystyle g(\alpha_{i})$
$\displaystyle=g_{0}({\alpha_{i}}^{2})+\phantom{{}^{{}+n/2}}\alpha_{i}\cdot
g_{1}({\alpha_{i}}^{2})$ $\displaystyle g(\alpha_{i+n/2})$
$\displaystyle=g_{0}({\alpha_{i}}^{2})+\alpha_{i+n/2}\cdot
g_{1}({\alpha_{i}}^{2}).$

We can use it to present our first general description of a Fast Fourier
Transform (FFT) Algorithm 3.

Input: A polynomial $g(x)$ of degree bounded by $n$ and a twofold set
$\alpha_{0},\dots,\alpha_{n-1}$ of $n$/̄th roots of $a$

Result: Evaluations of $g(x)$ at $\alpha_{0},\dots,\alpha_{n-1}$

1 if  _n = 1_ then return _$g$_ ;

Split $g(x)$ into $g_{0}(x)$ and $g_{1}(x)$.

2
$\bm{y}_{0}\coloneqq\textsc{FFT}(g_{0}(x),{\alpha_{0}}^{2},\dots,{\alpha_{n/2-1}}^{2})$

3
$\bm{y}_{1}\coloneqq\textsc{FFT}(g_{1}(x),{\alpha_{0}}^{2},\dots,{\alpha_{n/2-1}}^{2})$

4 return
_$\bm{y}_{0}+\bm{y}_{1}\odot(\alpha_{0},\dots,\alpha_{n/2-1})||\bm{y}_{0}+\bm{y}_{1}\odot(\alpha_{n/2},\dots,\alpha_{n-1})$_

Algorithm 3 FFT

Analyzing its computational cost now we find that computing the $n$-FFT takes
as much time as computing two $n/2$-FFT plus a linear amount of products and
additions in $R$ ($T(n)=2T(n/2)+\mathcal{O}\left(n\right)$). Using again [3]
we end up with a total cost $\mathcal{O}\left(n\log{n}\right)$. Observe that
now this is the total cost of the transform and not per evaluation as it was
the case before.

######  Condition 3 (Twofold set of roots).

We say a set of points satisfies Condition 3 if it is a twofold set.

######  Remark 4.

Choosing the evaluation points as a twofold set of $n$/̄th roots of $a\in R$
is a sufficient condition for the existence of an efficient FFT.

Observe that, by definition, Condition 3 implies Condition 2. However we
prefer to treat it separately as it is sufficient for an efficient
implementation but unnecessary for a general pointwise product method.

We are going to use the following notation. For any $i\in\\{0,1,\dots,n-1\\}$
let $\overline{\imath}=i+n/2\nonscript\mskip-4.0mu plus -2.0mu minus
-4.0mu\mkern 5.0mu\mathbin{\operator@font rem}\penalty 900\mkern
5.0mu\nonscript\mskip-4.0mu plus -2.0mu minus -4.0mun$. Analogously with $j$
and $\overline{\jmath}$.

###  3.2 Efficient evaluation of $T^{-1}$

In order to obtain an efficient multiplication algorithm we need not only an
efficient transform algorithm but also an efficient anti-transform algorithm.

Notice beforehand that, the same way we saw in Remark 3 that Condition 3 is
preserved when squaring the evaluation points we should check if the same
holds with Condition 1. To do so we first require the following Lemma 1.

######  Lemma 1.

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a twofold set of $n$/̄th roots of $a$
with invertible differences.

Then $\alpha_{\overline{\imath}}=-\alpha_{i}$.

###### Proof.

Since the set satisfies Condition 3 we know
${\alpha_{i}}^{2}={\alpha_{\overline{\imath}}}^{2}$. That is

$0={\alpha_{i}}^{2}-{\alpha_{\overline{\imath}}}^{2}=(\alpha_{i}-\alpha_{\overline{\imath}})(\alpha_{i}+\alpha_{\overline{\imath}}).$

Using that the elements have invertible differences we obtain
$\alpha_{i}+\alpha_{\overline{\imath}}=0$. ∎

######  Proposition 2 (Squares of a set satisfying Conditions 2, 3 and 1 also
satisfy Conditions 2, 3 and 1).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a twofold set of $n$/̄th roots of $a$
with invertible differences.

Then the set ${\alpha_{0}}^{2},\dots,{\alpha_{n/2-1}}^{2}$ is a twofold set of
$n/2$/̄th roots of $a$ with invertible differences.

###### Proof.

From the definition of a twofold set it directly follows that the set of
squares ${\alpha_{0}}^{2},\dots,\allowbreak{\alpha_{n/2-1}}^{2}$ is a twofold
set of $n/2$/̄th roots of $a$.

We only need to check if the differences among the squares are still
invertible.

${\alpha_{i}}^{2}-{\alpha_{j}}^{2}=(\alpha_{i}-\alpha_{j})(\alpha_{i}+\alpha_{j})=(\alpha_{i}-\alpha_{j})(\alpha_{i}-\alpha_{\overline{\jmath}}).$

Using Lemma 1 we have seen the differences among the squares are products of
differences among original elements, invertible by hypothesis, implying the
squares also satisfy the conditions. ∎

After these preliminaries one can define the anti-transform from a
constructive point of view by reversing the transform algorithm or
explicitating the inverse of the transform matrix. However, to get a deeper
insight we are going to describe it using the language of Lagrange
interpolation.

Given an indexed set of points ${\\{\alpha_{i}\\}}_{i=0}^{n-1}$ with
invertible differences and the evaluations of a polynomial in such points
${\\{g(\alpha_{i})\\}}_{i=0}^{n-1}$ we can recover the original polynomial
$g(x)$ using Lagrange polynomials $l_{i}^{{\\{\alpha_{j}\\}}_{j=0}^{n-1}}(x)$
as

$g(x)=\sum_{i=0}^{n-1}g(\alpha_{i})l_{i}^{{\\{\alpha_{j}\\}}_{j=0}^{n-1}}(x),\quad
l_{i}^{{\\{\alpha_{j}\\}}_{j=0}^{n-1}}(x)=\prod_{\begin{subarray}{c}j=0\\\
j\neq i\end{subarray}}^{n-1}\frac{x-\alpha_{j}}{\alpha_{i}-\alpha_{j}}.$

The key point is to observe that, due to the particular requirements of our
set of evaluation points, that is Conditions 1, 2 and 3, our Lagrange
polynomials factorize in a special way.

Using Lemma 1 we can see how the Lagrange polynomial splits.

$\displaystyle l_{i}^{{\\{\alpha_{j}\\}}_{j=0}^{n-1}}(x)$
$\displaystyle=\prod_{\begin{subarray}{c}j=0\\\ j\neq
i\end{subarray}}^{n-1}\frac{x-\alpha_{j}}{\alpha_{i}-\alpha_{j}}$
$\displaystyle=\frac{x-\alpha_{\overline{\imath}}}{\alpha_{i}-\alpha_{\overline{\imath}}}\prod_{\begin{subarray}{c}j=0\\\
j\not\equiv i\\\
\pmod{n/2}\end{subarray}}^{n/2-1}\left(\frac{x-\alpha_{j}}{\alpha_{i}-\alpha_{j}}\right)\left(\frac{x-\alpha_{\overline{\jmath}}}{\alpha_{i}-\alpha_{\overline{\jmath}}}\right)$
$\displaystyle=\frac{x-\alpha_{\overline{\imath}}}{\alpha_{i}-\alpha_{\overline{\imath}}}\prod_{\begin{subarray}{c}j=0\\\
j\not\equiv i\\\
\pmod{n/2}\end{subarray}}^{n/2-1}\frac{x^{2}-{\alpha_{j}}^{2}}{{\alpha_{i}}^{2}-{\alpha_{j}}^{2}}$
$\displaystyle=l_{i}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)l_{i\allowbreak\mkern
12.0mu{\operator@font
rem}\,\,n/2}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x^{2}).$

It is crucial to note that with a twofold set
$l_{\overline{\imath}\allowbreak\mkern 12.0mu{\operator@font
rem}\,\,n/2}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x)=l_{i\allowbreak\mkern
12.0mu{\operator@font
rem}\,\,n/2}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x)$.

Then we can write

$\displaystyle g(x)$
$\displaystyle=\sum_{i=0}^{n-1}g(\alpha_{i})l_{i}^{{\\{\alpha_{j}\\}}_{j=0}^{n-1}}(x)$
$\displaystyle=\sum_{i=0}^{n-1}g(\alpha_{i})l_{i}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)l_{i\allowbreak\mkern
12.0mu{\operator@font
rem}\,\,n/2}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x)$
$\displaystyle=\sum_{i=0}^{n/2-1}\left(g(\alpha_{i})l_{i}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)+g(\alpha_{\overline{\imath}})l_{\overline{\imath}}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)\right)l_{i}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x^{2}).$

Once we have this decomposition the advantage of this language is that it
allows us to interpret it. We were considering $g(x)$ as
$g_{0}(x^{2})+xg_{1}(x^{2})$. Polynomials
$l_{i}^{{\\{{\alpha_{j}}^{2}\\}}_{j=0}^{n/2-1}}(x)$ would help us interpolate
$g_{0}(x)$ and $g_{1}(x)$ if we had their images
$\\{g_{0}({\alpha_{i}}^{2})\\}$ and $\\{g_{1}({\alpha_{i}}^{2})\\}$. However
the images we have are $\\{g(\alpha_{i})\\}$. But then
$l_{i}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)$ and
$l_{\overline{\imath}}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)$ are
precisely the polynomials that interpolate
$g_{0}({\alpha_{i}}^{2})+xg_{1}({\alpha_{i}}^{2})$ (a polynomial of degree $1$
that has the desired evaluations as coefficients) from $g(\alpha_{i})$ and
$g(\alpha_{\overline{\imath}})$.

As we are going to use it later lets explicitate

$g(\alpha_{i})l_{i}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)+g(\alpha_{\overline{\imath}})l_{\overline{\imath}}^{\\{\alpha_{i},\alpha_{\overline{\imath}}\\}}(x)=\alpha_{i}\left(\frac{g(\alpha_{i})+g(\alpha_{\overline{\imath}})}{\alpha_{i}-\alpha_{\overline{\imath}}}\right)+x\left(\frac{g(\alpha_{i})-g(\alpha_{\overline{\imath}})}{\alpha_{i}-\alpha_{\overline{\imath}}}\right).$

This can be used to build an efficient interpolation algorithm. From the $n$
evaluations of a polynomial $g$ of degree bounded by $n$ at points
${\\{\alpha_{i}\\}}_{i=0}^{n-1}$ we can recover the evaluations of polynomials
$g_{0}$ and $g_{1}$ at points ${\\{{\alpha_{i}}^{2}\\}}_{i=0}^{n/2-1}$ (this
is done with interpolations of polynomials of degree bounded by $2$, so each
requires a constant time and we need a total of $\mathcal{O}(n)$ operations).
Then we use them to interpolate $g_{0}$ and $g_{1}$, each of them polynomials
of degree bounded by $n/2$ belonging to $R[x]/\left<x^{n/2}-a\right>$. That is
$T(n)=2T(n/2)+\mathcal{O}(n)$, and we end up again achieving
$T(n)=\mathcal{O}\left(n\log{n}\right)$.

Input: A vector of evaluations $\bm{y}$ of size $n$ and a twofold set
$\alpha_{0},\dots,\alpha_{n-1}$ of $n$/̄th roots of $a$ with invertible
differences

Result: Coefficients of a polynomial $g(x)$ interpolating $\bm{y}$ at
$\alpha_{0},\dots,\alpha_{n-1}$

1 if  _n = 1_ then return _$y$_ ;

2 for  _$i\leftarrow 0$ to __ $n/2-1$_ do

$\bm{y}_{0}[i]\coloneqq\alpha_{i}\left(\frac{\bm{y}[i]+\bm{y}[i+n/2]}{\alpha_{i}-\alpha_{i+n/2}}\right)$

$\bm{y}_{1}[i]\coloneqq\left(\frac{\bm{y}[i]-\bm{y}[i+n/2]}{\alpha_{i}-\alpha_{i+n/2}}\right)$

end for

3
$g_{0}(x)\coloneqq\textsc{IFFT}(\bm{y}_{0},{\alpha_{0}}^{2},\dots,{\alpha_{n/2-1}}^{2})$

4
$g_{1}(x)\coloneqq\textsc{IFFT}(\bm{y}_{1},{\alpha_{0}}^{2},\dots,{\alpha_{n/2-1}}^{2})$

5 return _$g_{0}(x^{2})+xg_{1}(x^{2})$_

Algorithm 4 IFFT

###  3.3 Efficient multiplication algorithm in $R[x]/\left<x^{n}-a\right>$

Combining both Algorithms 3 and 4 we describe in Algorithm 5 an efficient
multiplication algorithm in $R[x]/\left<x^{n}-a\right>$.

Input: Two polynomials $g(x)$, $h(x)$ of degree bounded by $n$

Auxiliary: A twofold set $\alpha_{0},\dots,\alpha_{n-1}$ of $n$/̄th roots of
$a$ with invertible differences

Result: The product $(g\cdot h)(x)$ of $g(x)$ and $h(x)$ in
$R[x]/\left<x^{n}-a\right>$

1 $\bm{g}\coloneqq\textsc{FFT}(g(x),\alpha_{0},\dots,\alpha_{n-1})$

2 $\bm{h}\coloneqq\textsc{FFT}(h(x),\alpha_{0},\dots,\alpha_{n-1})$

3 $\bm{f}\coloneqq\bm{g}\odot\bm{h}$

4 $f(x)\coloneqq\textsc{IFFT}(\bm{f},\alpha_{0},\dots,\alpha_{n-1})$

return _$f(x)$_

Algorithm 5 Efficient FFT Multiplication

Thereby our work is to study the existence of sets of evaluation points
satisfying Conditions 3, 1 and 2 and how to find them in our desired $R$.

##  4 Characterization of suitable sets of evaluation points in the ring
$\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>$

In this section we focus on $\mathbb{Z}_{m}$ and study the relations among the
given conditions to see that these are precisely the required notions and
provide necessary and sufficient conditions for the existence of proper
evaluation sets.

We can start certifying that Conditions 3, 2 and 1 are indeed independent in
general.

######  Proposition 3 (Condition 3 does not imply Condition 1 in
$\mathbb{Z}_{m}$ if $m$ is not a power of a prime).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a twofold set of $n$/̄th roots of $a$
in $\mathbb{Z}_{m}$, where $m$ is not a power of a prime. There is a twofold
set of $n$/̄th roots of $a$ in $\mathbb{Z}_{m}$ without invertible
differences.

###### Proof.

Decomposing $m=pq$ with $p$ and $q$ coprime proper factors we can always
construct another twofold set defining
$\alpha^{\prime}_{i}\equiv\alpha_{i}\pmod{p}$ but
$\alpha^{\prime}_{i}\equiv\alpha_{0}\pmod{q}$. It would be a twofold set but
none of their differences would be invertible. ∎

When the modulus is a power of a prime ${p^{e}}$ invertibility comes from
being different modulo $p$, which is not implied in general by being different
modulo $p^{e}$. We have first to further characterize $n$/̄th roots in
$\mathbb{Z}_{p^{e}}$ when $p$ is prime to address this particular case.

######  Theorem 4 (Hensel’s lemma as in Theorem 2.23 from [13]).

Suppose that $f(x)$ is a polynomial with integral coefficients. If
$f(x_{0})\equiv 0\pmod{p^{e}}$ and $f^{\prime}(x_{0})\not\equiv 0\pmod{p}$,
then there is a unique $t\pmod{p}$ such that $f(x_{0}+tp^{e})\equiv
0\pmod{p^{e+1}}$.

In our case we are particularly interested in $f(x)=x^{n}-a$, with $n$ a power
of $2$, so $f^{\prime}(x)=nx^{n-1}$. Since our solutions are $n$/̄th roots of
$a$ (when considered modulo $p^{e}$ and therefore also modulo $p$)
$n{x_{0}}^{n-1}\not\equiv 0\pmod{p}$ as long as $p\neq 2$ and $a\neq 0$.

######  Corollary 5.

There is a one to one correspondence of $n$/̄th roots in $\mathbb{Z}_{p^{e}}$
and in $\mathbb{Z}_{p}$, where $p$ is an odd prime.

###### Proof.

On the one hand we can see each root in $\mathbb{Z}_{p^{e}}$ as a root in
$\mathbb{Z}_{p}$ by applying $\pod{{\operator@font rem}\mkern 6.0mup}$.

On the other hand one just needs to apply Theorem 4 iteratively $e-1$ times
from $\mathbb{Z}_{p}$ to $\mathbb{Z}_{p^{e}}$. ∎

In particular this implies the order, as elements of the group, is preserved
given that powers of a root are uniquely lifted to powers of the lifted root.

######  Remark 5.

We omit here the case $p=2$ as in the following sections we are going to see
that other conditions forbid this particular case.

######  Proposition 6 (Condition 2 implies Condition 1 in $\mathbb{Z}_{m}$ if
$m$ is a power of an odd prime).

Let $m=p^{e}$, with $p$ an odd prime, and let $\alpha_{0},\dots,\alpha_{n-1}$
be $n$ different $n$/̄th roots of $a$ in $\mathbb{Z}_{p^{e}}$. Then
$\alpha_{i}-\alpha_{j}$ is invertible in $\mathbb{Z}_{p^{e}}$ for all $i\neq
j$.

###### Proof.

Every $\alpha_{i}$ is a root of $f(x)=x^{n}-a$ when considered modulo $p$. By
the previous corollary we have $\alpha_{i}\not\equiv\alpha_{j}\pmod{p^{e}}$
implies $\alpha_{i}\not\equiv\alpha_{j}\pmod{p}$. Therefore
$\gcd(\alpha_{i}-\alpha_{j},p)=1$ as we wanted. ∎

######  Proposition 7 (Condition 3 implies Condition 1 in $\mathbb{Z}_{m}$ if
$m$ is a power of an odd prime).

Let $m=p^{e}$, with $p$ an odd prime, and let $\alpha_{0},\dots,\alpha_{n-1}$
be a twofold set of $n$/̄th roots of $a$ in $\mathbb{Z}_{p^{e}}$. Then
$\alpha_{i}-\alpha_{j}$ is invertible in $\mathbb{Z}_{p^{e}}$ for all $i\neq
j$.

###### Proof.

Condition 3 implies Condition 2 and Condition 2 implies Condition 1. ∎

Working with an arbitrary modulus $m$, that has $m={p_{1}}^{e_{1}}\dots
p_{k}^{e_{k}}$ as its prime decomposition, we can completely determine any
$d\in\mathbb{Z}_{m}$, via the Chinese Remainder Theorem (CRT), from $d_{(i)}$
such that

$\displaystyle d_{(1)}$ $\displaystyle\equiv d\pmod{{p_{1}}^{e_{1}}}$
$\displaystyle d_{(2)}$ $\displaystyle\equiv d\pmod{{p_{2}}^{e_{2}}}$
$\displaystyle\mathmakebox[width("{}\equiv{}")][c]{\vdots}$ $\displaystyle
d_{(k)}$ $\displaystyle\equiv d\pmod{{p_{k}}^{e_{k}}}.$

Using this representation we can prove the following theorem.

######  Theorem 8 (Conditions 2 and 1 hold if and only if Condition 2 holds
modulo every ${p_{j}}^{e_{j}}$).

Let $\alpha_{0},\dots,\alpha_{n-1}\in\mathbb{Z}_{m}$ be a set of different
$n$/̄th roots of $a\in\mathbb{Z}_{m}$, and let $m={p_{1}}^{e_{1}}\dots
p_{k}^{e_{k}}$ be the prime decomposition of an odd module $m$.

The differences among these elements are invertible modulo $m$ if and only if
all the elements are still different when considered modulo any of the
${p_{j}}^{e_{j}}$.

###### Proof.

Follows the same ideas as the previous propositions, since an element is
invertible if and only if it is invertible modulo all the coprime factors of a
factorization of its modulus and we have seen (Corollary 5) that such roots
are different modulo ${p_{j}}^{e_{j}}$ if and only if they are different
modulo $p_{j}$, and therefore have invertible differences. ∎

The same way we can see how other implications are not true in general either.

######  Proposition 9 (Conditions 1 and 2 do not imply Condition 3 in
$\mathbb{Z}_{m}$ if $m$ is not a power of a prime).

Not every $n$/̄set of $n$/̄th roots of $a\in\mathbb{Z}_{m}$ with invertible
differences is a twofold set of $n$/̄th roots. It is not the case in general,
not even for roots of unity.

###### Proof.

Consider the following set of $4$/̄th roots of unity in $\mathbb{Z}_{65}$:

$\displaystyle 12^{4}$ $\displaystyle\equiv 1$ $\displaystyle\pmod{65}$
$\displaystyle\qquad\qquad\qquad\qquad 12^{2}$ $\displaystyle\equiv 14$
$\displaystyle\pmod{65}$ $\displaystyle 14^{4}$ $\displaystyle\equiv 1$
$\displaystyle\pmod{65}$ $\displaystyle 14^{2}$ $\displaystyle\equiv 1$
$\displaystyle\pmod{65}$ $\displaystyle 18^{4}$ $\displaystyle\equiv 1$
$\displaystyle\pmod{65}$ $\displaystyle 18^{2}$ $\displaystyle\equiv 64$
$\displaystyle\pmod{65}$ $\displaystyle 21^{4}$ $\displaystyle\equiv 1$
$\displaystyle\pmod{65}$ $\displaystyle 21^{2}$ $\displaystyle\equiv 51$
$\displaystyle\pmod{65}$

And their set of differences is $\\{2,3,4,6,7,9\\}$, all of them invertible
elements modulo $65$. ∎

Observe that the evaluation points from the example are indeed, after some
reorderings, a twofold set of $n$/̄th roots of unity in $\mathbb{Z}_{5}$ and
in $\mathbb{Z}_{13}$, but the _reorderings_ are different.

$\displaystyle 12^{2}$ $\displaystyle\equiv 18^{2}$ $\displaystyle\pmod{5}$
$\displaystyle\qquad\qquad\qquad\qquad 12^{2}$ $\displaystyle\equiv 14^{2}$
$\displaystyle\pmod{13}$ $\displaystyle 14^{2}$ $\displaystyle\equiv 21^{2}$
$\displaystyle\pmod{5}$ $\displaystyle 18^{2}$ $\displaystyle\equiv 21^{2}$
$\displaystyle\pmod{13}$

Once again the proposition does hold if we work modulo a power of an odd
prime. To prove it we require a couple of lemmas that show the important role
of roots of unity and allow us to focus on them with the goal of better
understanding these orderings.

######  Lemma 10 (Conditions 2 and 1 imply the evaluation points are
invertible).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be different $n$/̄th roots of $a$ in
$\mathbb{Z}_{m}$ such that $\alpha_{i}-\alpha_{j}$ is invertible in
$\mathbb{Z}_{m}$ for all $i\neq j$. Then $\alpha_{i}$ is invertible in
$\mathbb{Z}_{m}$ for all $i$.

###### Proof.

Choose two indices $i$ and $j$ and let $d$ be a square-free common divisor of
$\alpha_{i}$ and $m$. Since ${\alpha_{i}}^{n}\equiv a\pmod{m}$ and
${\alpha_{j}}^{n}\equiv a\pmod{m}$ we have that
$m|{\alpha_{i}}^{n}-{\alpha_{j}}^{n}$, implying that $d|\alpha_{j}$ (here we
have to use that $d$ is square free). We would finally get
$d|\alpha_{i}-\alpha_{j}$ but we know $\gcd(\alpha_{i}-\alpha_{j},m)=1$ and
therefore $d=1$, proving $\gcd(\alpha_{i},m)=1$ for all $i$. ∎

######  Remark 6.

If roots of $a$ are invertible it directly follows that $a$ itself has to be
invertible. We will impose it when required since this argument implies it is
a necessary condition for the existence of the inverse transform $T^{-1}$.

######  Lemma 11 (Roots of $a$ and roots of $1$).

Let $a\in\mathbb{Z}_{m}$. The following two statements are equivalent:

  1. (i)

The set $\alpha_{0},\dots,\alpha_{n-1}\in\mathbb{Z}_{m}$ satisfies Conditions
2 and 1.

  2. (ii)

The set $\alpha_{0},\dots,\alpha_{n-1}\in\mathbb{Z}_{m}$ can be constructed
from an invertible $n$/̄th root of $a$, lets denote it $\alpha$, and $n$
different $n$/̄th roots of unity $\omega_{0},\dots,\omega_{n-1}$ with
invertible differences in $\mathbb{Z}_{m}$ such that
$\alpha_{i}=\alpha\omega_{i}$.

###### Proof.

Lets prove both implications:

  * •

(i)$\implies$(ii)

Let $\alpha_{0},\dots,\alpha_{n-1}$ be the roots satisfying the conditions.

We can define $\alpha=\alpha_{0}$ (invertible by Lemma 10) and
$\omega_{i}=\alpha_{i}\cdot{\alpha_{0}}^{-1}$. We can check $\omega_{i}$ are
roots of unity and their differences are invertible

${(\omega_{i}-\omega_{j})}^{-1}={\left(\frac{\alpha_{i}}{\alpha_{0}}-\frac{\alpha_{j}}{\alpha_{0}}\right)}^{-1}=\alpha_{0}\cdot{(\alpha_{i}-\alpha_{j})}^{-1}.$

  * •

(ii)$\implies$(i)

Let $\alpha,\omega_{0},\dots,\omega_{n-1}$ be a set of roots satisfying the
conditions.

Define now $\alpha_{i}=\alpha\cdot\omega_{i}$. Again by construction all
$\alpha_{i}$ are $n$/̄th roots of $a$ and their differences are invertible
since

${(\alpha_{i}-\alpha_{j})}^{-1}={(\alpha\cdot\omega_{i}-\alpha\cdot\omega_{j})}^{-1}=\alpha^{-1}{(\omega_{i}-\omega_{j})}^{-1}.$

∎

This motivates the definition of a sufficient condition that, as we are going
to see, will be necessary when $m$ is a power of an odd prime.

######  Definition 2 ($(\alpha,\omega)$/̄set).

Let $\alpha$ be any $n$/̄th root of an invertible $a\in R$ and $\omega$ an
$n$/̄th root of unity in $R$ of order $n$ whose powers have invertible
differences. Then the set defined as $\alpha_{i}=\alpha\omega^{i}$ is said to
be an _$(\alpha,\omega)$ /̄set_.

######  Condition 4 ($(\alpha,\omega)$/̄set).

We say a set of evaluation points satisfies Condition 4 if (after some
reordering) it is an $(\alpha,\omega)$/̄set for some $\alpha,\omega\in R$.

######  Remark 7.

Let $m={p_{1}}^{e_{1}}\dots p_{k}^{e_{k}}$ be the prime decomposition of the
module $m$. An $n$/̄th root of unity $\omega\in\mathbb{Z}_{m}$ can be
determined from $\omega_{(i)}\equiv\omega\pmod{p_{i}^{e_{i}}}$ and the order
of $\omega$ is just the least common multiple of the orders of $\omega_{(i)}$
in $\mathbb{Z}_{p_{i}^{e_{i}}}$. Since we choose $n$ to be a power of $2$ and
all the orders of each $\omega_{(i)}$ divide $n$ the least common multiple is
just going to be the maximum of the orders. Then, for $\omega$ to be an
$n$/̄th root of unity of order $n$ it is only necessary that one of these
$\omega_{(j)}$ has order $n$. However as we also need to impose invertibility
of the differences of its powers then every $\omega_{(i)}$ has to have order
$n$.

######  Proposition 12 (Condition 4 implies Conditions 3, 2 and 1).

An $(\alpha,\omega)$/̄set in $\mathbb{Z}_{m}$ is a twofold set of $n$/̄th
roots of $a$ with invertible differences.

###### Proof.

Let $\alpha_{i}=\alpha\omega^{i}$ and let
$m={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\dots p_{k}^{e_{k}}$ be the prime
decomposition of $m$.

We can start checking Condition 1. From the proof of Lemma 11 we know an
$(\alpha,\omega)$/̄set of $n$/̄th roots satisfies Condition 1 if $\alpha$ is
invertible and $\omega^{i}-\omega^{j}$ are invertible too.

Since $a$ is invertible in $\mathbb{Z}_{m}$ then $\alpha$ as an $n$/̄th root
of $a$ has to be invertible too. Otherwise if $\alpha\equiv 0\pmod{p_{j}}$ for
some $j$ then $a\equiv 0\pmod{p_{j}}$ for the same $j$ and it would not be
invertible either, contradicting the statement.

The second condition is ensured from the definition. Then every difference is
invertible modulo $m$.

Condition 2 follows from the construction of an $(\alpha,\omega)$/̄set.

Then for Condition 3 let $i\equiv j\pmod{2^{{\log(n)}-k}}$ and, without loss
of generality, assume $i\geq j$ and therefore $i=j+c\cdot 2^{{\log(n)}-k}$ for
some non-negative integer $c$. Then

$\alpha_{i}^{2^{k}}={(\alpha_{0}\omega^{i})}^{2^{k}}=\alpha_{0}^{2^{k}}\omega^{(j+c\cdot
2^{{\log(n)}-k})\cdot 2^{k}}=\alpha_{0}^{2^{k}}\omega^{j\cdot 2^{k}+c\cdot
n}={(\alpha_{0}\omega^{j})}^{2^{k}}=\alpha_{j}^{2^{k}}.$

∎

This condition is quite convenient, for example it allows us to explicitly
describe the transform from its Vandermonde matrix, as we mentioned before, in
a compact way as ${(V)}_{i\,j}={(\alpha\omega^{i})}^{j}$ and
${(V^{-1})}_{i\,j}=\frac{1}{n}{(\alpha^{-1}\omega^{-j})}^{i}$. Notice that the
inverse matrix looks like $1/n$ times the transpose of the evaluation matrix
of an $(\alpha^{-1},\omega^{-1})$/̄set. If we were working in
$\mathbb{Z}_{m}[x]/\left<x^{n}-1\right>$ with $\alpha=1$ the transpose would
be irrelevant as the matrix would be symmetric and the same efficient
recursive evaluation techniques from the direct transform would work directly
for its inverse.

However even if Condition 4 implies Conditions 3, 2 and 1 the converse is not
true in general. Besides that we can see it holds for some particular cases,
when $m$ is a power of a prime.

######  Proposition 13 (Conditions 1 and 2 do imply Condition 4 in
$\mathbb{Z}_{m}$ if $m$ is a power of an odd prime).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a set of $n$/̄th roots of $a$ with
invertible differences in $\mathbb{Z}_{p^{e}}$, with $p$ an odd prime. This is
(except reordering) an $(\alpha,\omega)$/̄set of $n$/̄th roots of $a$ in
$\mathbb{Z}_{p^{e}}$.

###### Proof.

From Lemma 11 we deduce the existence of an invertible $\alpha$ and
$\omega_{0},\dots,\allowbreak\omega_{n-1}$ with invertible differences such
that $\alpha_{i}=\alpha\cdot\omega_{i}$.

As $\mathbb{Z}_{p}$ is a field its multiplicative group is a cyclic group of
order $p-1$. Then the set of $n$/̄th roots of unity in $\mathbb{Z}_{p}$ is
also a group, and as a subgroup of a cyclic group it is also cyclic.

It is also known that $x^{n}-1$ has at most $n$ solutions modulo $p$ (Theorem
2.6 from [13]), therefore the $n$ roots $\omega_{i}\pod{{\operator@font
rem}\mkern 6.0mup}$ (all different since $\alpha\omega_{i}\pod{{\operator@font
rem}\mkern 6.0mup}$ are lifted to different points in $\mathbb{Z}_{p^{e}}$)
form the whole cyclic group of roots of unity and in consequence are generated
by one of them.

As there is a one to one correspondence among $n$/̄th roots in
$\mathbb{Z}_{p}$ and in $\mathbb{Z}_{p^{e}}$ the original
$\omega_{i}\in\mathbb{Z}_{p^{e}}$ are generated too by one $\omega$ of order
$n$. That is, there exists a permutation $\pi$ such that
$\omega_{\pi(i)}=\omega^{i}$.

After this reordering defined by $\pi$ the set
$\alpha_{\pi(0)},\alpha_{\pi(1)},\dots,\alpha_{\pi(n-1)}$ is an
$(\alpha,\omega)$/̄set. ∎

######  Proposition 14 (Conditions 1 and 2 do imply Condition 3 in
$\mathbb{Z}_{m}$ if $m$ is a power of an odd prime).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a set of $n$/̄th roots of $a$ with
invertible differences in $\mathbb{Z}_{p^{e}}$, with $p$ an odd prime. This is
(except reordering) a twofold/̄set of $n$/̄th roots of $a$ in
$\mathbb{Z}_{p^{e}}$.

###### Proof.

Direct as we know by Proposition 13 that Conditions 1 and 2 imply Condition 4
in $\mathbb{Z}_{m}$ if $m$ is a power of an odd prime and Condition 4 always
implies Condition 3, as seen in Proposition 12. ∎

This new condition seems the right choice, and the FFT is usually introduced
from constructions equivalent to this definition, but we should study first if
restricting to this particular set of evaluation points reduces the options
for computing an FFT multiplication when $m$ is not a power of an odd prime.

Once again Conditions 1 and 2 being true modulo every ${p_{j}}^{e_{j}}$ should
imply that Condition 4 holds modulo every ${p_{j}}^{e_{j}}$, but the
permutations might be different.

There are cases where these permutations allow Condition 3 to be true while
Condition 4 is not.

######  Theorem 15 (Conditions 1, 2 and 3 do not imply Condition 4 in general,
but imply the existence of a set satisfying Condition 4).

Let $\alpha_{0},\dots,\alpha_{n-1}$ be a twofold set of $n$/̄th roots of $a$
with invertible differences in $\mathbb{Z}_{m}$, where $m$ is odd and not a
power of a prime and $n$ is a power of two greater than $2^{2}$. Then $a$ has
an inverse in $\mathbb{Z}_{m}$, there is both a twofold set
$\alpha^{\prime}_{0},\dots,\alpha^{\prime}_{n-1}$ of $n$/̄th roots of $a$ in
$\mathbb{Z}_{m}$ with invertible differences not satisfying Condition 4 and a
set $\alpha^{\prime\prime}_{i}=\alpha\omega^{i}$ where $\alpha$ is an $n$/̄th
root of $a$ and $\omega$ is a root of unity of order $n$ with all its powers
having invertible differences, that is, an $(\alpha,\omega)$/̄set.

###### Proof.

Following Lemma 10 we get $a$ is invertible.

Let $m={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\dots p_{k}^{e_{k}}$ be the prime
decomposition of $m$.

There is a unique (except reordering) twofold set of $n$/̄th roots of $a$ with
invertible differences in $\mathbb{Z}_{{p_{j}}^{e_{j}}}$. This is the case
since the values of each of the roots of $a$ modulo ${p_{j}}^{e_{j}}$ are
completely determined, being the unique elements lifted to
$\mathbb{Z}_{{p_{j}}^{e_{j}}}$ from the unique $n$ roots of $a$ in
$\mathbb{Z}_{p_{j}}$. By Proposition 13 it satisfies Condition 4. The only
thing we could choose is the respective order they have.

This order is irrelevant in $\mathbb{Z}_{{p_{j}}^{e_{j}}}$ but becomes
important when considering $\mathbb{Z}_{m}$ as once we fix an order modulo
${p_{1}}^{e_{1}}$ the different respective orders for the remaining
${p_{j}}^{e_{j}}$ would produce different elements in $\mathbb{Z}_{m}$.

From the twofold set definition we got a tree structure in Figure 1 and a
specific notation for the points (a bit decomposition of the index). The
twofold structure is only preserved by the tree structure, so the only
possible reorderings are those that come from swapping left and right children
of a node. That is, choosing $b_{i-1}\dots b_{0}$ (an internal node), and
mapping $\alpha_{b_{{\log(n)}-1}\dots b_{i}\dots b_{0}}$ to
$\alpha_{b_{{\log(n)}-1}\dots\overline{b_{i}}\dots b_{0}}$ for all
$b_{{\log(n)}-1},\dots,b_{i+1}$ still preserves this structure.

For example, choosing nodes $\alpha_{1}$ and $\alpha_{10}$ we obtain a
different ordering like in Figure 2.

$a$$\alpha_{\,0}$$\alpha_{\,00}$$\alpha_{\,000}$$\alpha_{\,100}$$\alpha_{\,10}$$\alpha_{\,110}$$\alpha_{\,010}$$\alpha_{\,1}$$\alpha_{\,11}$$\alpha_{\,011}$$\alpha_{\,111}$$\alpha_{\,01}$$\alpha_{\,001}$$\alpha_{\,101}$
Figure 2: Twofold set of $8$/̄th roots swapping left and right descendants of
$\alpha_{1}$ and $\alpha_{10}$

This means that given a twofold set there are exactly $2^{n-1}$ possible
reorderings (since the tree has exactly $n-1$ inner nodes and we can swap or
not each of them).

When odd $m$ is not a power of a prime once we fix the order of the roots
modulo ${p_{1}}^{e_{1}}$ each possible reordering of the roots modulo
${p_{j}}^{e_{j}}$ for the remaining $j$ produces a new twofold set with
invertible differences, for a total of $2^{(k-1)(n-1)}$ possibilities.

On the other hand we can count the number of $(\alpha,\omega)$/̄sets. To do so
it is important to notice that $(\alpha,\omega)$ and a different pair
$(\beta,\xi)$ can generate the same set (just in a different order). If that
is the case let $\pi\in\mathfrak{S}_{n}$ be the permutation such that
$\beta_{i}=\alpha_{\pi(i)}$. Let $c=\pi(0)$, then
$\beta=\beta_{0}=\alpha_{\pi(0)}=\alpha\omega^{c}$. Let $d=\pi(1)-\pi(0)$,
then
$\xi=\beta_{1}/\beta_{0}=\alpha_{\pi(1)}/\alpha_{\pi(0)}=(\alpha\omega^{\pi(1)})/(\alpha\omega^{\pi(0)})=\omega^{\pi(1)-\pi(0)}=\omega^{d}$.

This allows us to completely characterize permutation $\pi$ as

$\beta_{i}=\beta\xi^{i}=\alpha\omega^{c}{(\omega^{d})}^{i}=\alpha\omega^{c+di}=\alpha_{c+di}.$

For $\pi$ to be a permutation $d$ has to be invertible modulo $n$ so it has to
be odd.

That is everything required as any pair of $c\in\mathbb{Z}_{n}$ and odd
$d\in\mathbb{Z}_{n}$ would produce a new set of generators
$(\alpha\omega^{c},\omega^{d})$ for the same set. That is, each
$(\alpha,\omega)$/̄set with invertible differences can be constructed from
$n^{2}/2$ different pairs of roots of $a$ and $1$ (we have $n$ options for $c$
and $n/2$ options for $d$).

Then, from the existence of a twofold set with invertible differences and
previous propositions we know there are $n$ possible $\alpha_{(j)}$ roots of
$a$ in $\mathbb{Z}_{{p_{j}}^{e_{j}}}$ and $n/2$ possible $\omega_{(j)}$ roots
of unity in $\mathbb{Z}_{{p_{j}}^{e_{j}}}$ of order $n$ that when combined via
the CRT would define an $(\alpha^{\prime\prime},\omega^{\prime\prime})$/̄set
with invertible differences. That is a total of $n^{2k}/2^{k}$ pairs of
generators, and since every set is defined by $n^{2}/2$ pairs we would have
$n^{2(k-1)}/2^{(k-1)}$ unique sets.

However, if $n>2^{2}$ then $2^{(k-1)(n-1)}>n^{2(k-1)}/2^{(k-1)}$ and therefore
some of the $2^{(k-1)(n-1)}$ sets ${\\{\alpha^{\prime}_{i}\\}}_{i}$ satisfying
Conditions 1, 2 and 3 would not satisfy Condition 4.

∎

This important theorem ensures that, even if Condition 4 is not necessary to
design an efficient FFT multiplication algorithm, as it is sometimes
indirectly taken for granted in the literature, we can safely assume it when
working in $\mathbb{Z}_{m}[x]$ as it adds no additional restrictions on $m$ to
the necessary Conditions 1, 2 and 3. Only having done this analysis we can
safely use $(\alpha,\omega)$/̄sets when convenient without loosing any
generality.

###  4.1 Existence and construction of suitable roots in $\mathbb{Z}_{m}$

Once we have established the necessary conditions for the transform to be
useful to efficiently compute the product of two polynomials modulo $x^{n}-a$
we are left with the task of studying whether such points exist in our desired
ring and how to find them.

As we have seen in Theorem 15 the existence of suitable points satisfying
Conditions 2, 1 and 3 implies the existence of an $(\alpha,\omega)$/̄set
satisfying Condition 4. For convenience we are going to characterize when such
set of points exists and how to find it.

######  Remark 8.

When $R=\mathbb{C}$ we just have to choose $\omega=e^{\frac{i2\pi}{n}}$ and
$\alpha=\sqrt[n]{a}$ (for example $\alpha=1$ if $a=1$ or
$\alpha=e^{\frac{i\pi}{n}}$ if $a=-1$). This choice is the standard Fourier
Transform and it is usually introduced directly in the literature.

Now we can consider the case $R=\mathbb{Z}_{m}$.

On the one hand finding a primitive $n$/̄th root of unity $\omega$ in
$\mathbb{Z}_{m}$, that is, an $n$/̄th root of unity of order $n$, such that
all its powers have invertible differences implies finding a primitive $n$/̄th
root of unity $\omega_{(i)}$ in every $\mathbb{Z}_{{p_{i}}^{e_{i}}}$ and then
reconstruct $\omega$ using the CRT.

That way we have reduced the problem of finding a primitive $n$/̄th root of
unity in $\mathbb{Z}_{m}$ for an arbitrary $m$ to finding a primitive $n$/̄th
root of unity in $\mathbb{Z}_{p^{e}}$.

The proof of Theorem 4 in [13] explicitly tells us how to lift a solution
$x_{e}$ modulo $p^{e}$ to a solution $x_{e+1}$ modulo $p^{e+1}$. It can be
computed recursively using $x_{e+1}\equiv
x_{e}-f(x_{e})\overline{f^{\prime}(x_{1})}\pmod{p^{e+1}}$ where
$\overline{f^{\prime}(x_{1})}$ is the inverse of $f^{\prime}(x_{1})$ when
considering it in $\mathbb{Z}_{p}$. Recall $f(x)$ was $x^{n}-a$ and therefore
$f^{\prime}(x)=nx^{n-1}$.

The only step of this computation that is not immediate is to compute
$\overline{f^{\prime}(x_{1})}$. Since we are sure $f^{\prime}(x_{1})$ is not
$0$ modulo $p$ we can use the Extended Euclidean algorithm to compute integers
$r$ and $s$ so that $f^{\prime}(x_{1})r+ps=\gcd(f^{\prime}(x_{1}),p)=1$ and
$r$ would be the desired $\overline{f^{\prime}(x_{1})}$.

We finally want to analyze under which conditions on $p$ and $n$ do primitive
$n$/̄th roots of unity exist in $\mathbb{Z}_{p}$ and how to find them. We
obtain necessary conditions from Fermat’s Little Theorem 16.

######  Theorem 16 (Fermat’s Little Theorem as in Theorem 2.7 from [13]).

Let $p$ be a prime. If $p\not|x_{0}$ then

${x_{0}}^{p-1}\equiv 1\pmod{p}.$

######  Corollary 17.

If $\mathbb{Z}_{p}$ contains an $n$/̄th root of unity of order $n$ then
$n|p-1$.

###### Proof.

Let $x_{0}$ be an $n$/̄th root of unity of order $n$ in $\mathbb{Z}_{p}$. By
Theorem 16 we have ${x_{0}}^{p-1}\equiv 1\pmod{p}$ and therefore its order
divides $p-1$, that is, $n|p-1$ or $p=kn+1$ for an integer $k$. ∎

######  Remark 9.

Taking advantage of this condition, in the particular case $f(x)=x^{n}\pm 1$,
the calculation of $\overline{f^{\prime}(x_{1})}$, with $x_{1}$ an $n$/̄th
root of $\mp 1$ modulo $p$, can now be computed explicitly as
$\overline{f^{\prime}(x_{1})}=\pm x_{1}(p-1)/n$, as can be easily checked
computing $\overline{f^{\prime}(x_{1})}\cdot f^{\prime}(x_{1})$ and getting
$(\pm x_{1}(p-1)/n)(n{x_{1}}^{n-1})\equiv 1\pmod{p}$.

######  Remark 10.

This necessary condition rules out all the additional considerations we were
having about $n\not\equiv 0\pmod{p_{i}}$, for example ensuring $m$ has to be
odd. Observe that in Algorithm 4 we have to compute a quotient with
$\alpha_{i}-\alpha_{\overline{\imath}}$, that is, $2\alpha_{i}$ in the
denominator. Requesting Conditions 2, 1 and 3 always implies that twice the
unity of the ring has to be invertible (via Lemmas 1 and 10).

######  Corollary 18.

$\mathbb{Z}_{p}$ contains $n$/̄th roots of unity of order $n$ if and only if
$n|p-1$.

###### Proof.

We have already seen one implication, lets consider now $\mathbb{Z}_{p}$ with
$n|p-1$. We know the multiplicative group $\mathbb{Z}_{p}^{*}$ is cyclic. Take
a generator $g$, it has order $p-1$ and since $n|p-1$ we can choose
$\omega=g^{(p-1)/n}$ and by construction it would be an $n$/̄th root of unity
of order $n$. ∎

######  Remark 11.

Notice that, by Dirichlet’s theorem on arithmetic progressions, there are
infinitely many primes of this form.

Now we can start computing $\alpha\pmod{p_{j}}$ and $\omega\pmod{p_{j}}$.
Choosing $u_{j}$ a quadratic nonresidue in $\mathbb{Z}_{p_{j}}$ we can let
$\omega_{(j)}\equiv u_{j}^{(p_{j}-1)/n}\in\mathbb{Z}_{p_{j}}$ and then lift it
to $\mathbb{Z}_{{p_{j}}^{e_{j}}}$ using again the constructive proof of
Theorem 4.

Notice first that there is no known deterministic polynomial-time algorithm
able to find a quadratic nonresidue (see [1]) however checking if a uniformly
random element from $\mathbb{Z}^{*}_{p_{j}}$ is a quadratic nonresidue can be
done computing the Legendre symbol
$\left(\frac{u_{j}}{p_{j}}\right)\equiv{u_{j}}^{(p_{j}-1)/2}$, as it is $-1$
if and only if it is a quadratic nonresidue modulo $p$ (see Theorem 3.1 from
[13]), and has a success probability of almost one half.

On the one hand we know $n|p_{j}-1$ is a condition for the existence of
appropriate roots, so $\omega_{(j)}={u_{j}}^{(p_{j}-1)/n}$ is well defined.
Its $n$/̄th power is ${\omega_{(j)}}^{n}={u_{j}}^{p_{j}-1}=1$ (once again by
Theorem 16).

The only thing we have left is to check all its powers have invertible
differences. If it was not the case then $\omega_{(j)}$ would have order $k$
with $k<n$. This cannot be possible because since we already know
${\omega_{(j)}}^{n}=1$ then it would imply $k|n$, and if $k$ was a power of
$2$ strictly smaller than $n$ we would get a contradiction as, by
construction,
$-1=u_{j}^{(p_{j}-1)/2}={\omega_{(j)}}^{n/2}={\left({\omega_{(j)}}^{k}\right)}^{n/(2k)}=1^{n/(2k)}=1$.

This ensures our final $\omega$ meets the required conditions.

For computing $\alpha$ we might have different approaches. If $a=1$ the
trivial solution $\alpha=1$ works perfectly fine for our purposes. If $a=-1$
we can follow an analogous procedure, noticing that as $n$/̄th roots of $-1$
are $2n$/̄th roots of $1$ the condition is now that $2n|p_{j}-1$, and let
$\alpha_{(j)}\equiv{u_{j}}^{(p_{j}-1)/2n}\pmod{p_{j}}$, once again lifting
them and computing the final $\alpha$ from its CRT representation.

If $a\neq\pm 1$ then our alternative would be to make use of the
Tonelli–Shanks Algorithm [15].

Input: An odd prime $p$, a quadratic residue $a\in\mathbb{Z}_{p}$ and a
nonresidue $u\in\mathbb{Z}_{p}$

Result: An element $\alpha\in\mathbb{Z}_{p}$ square root of $a$

1 Let $v$ and $s$ be such that $p-1=v2^{s}$ and $v$ is odd.

2 Let

$\begin{aligned} k&\leftarrow s\\\ c&\leftarrow u^{v}\\\ t&\leftarrow a^{v}\\\
r&\leftarrow a^{\frac{v+1}{2}}\end{aligned}$

3 while  _$t\neq 0\land t\neq 1$_ do

Find least $i$, $0<i<k$, such that $t^{2^{i}}=1$

Let $d\leftarrow c^{2^{k-i-1}}$ and set

$\begin{aligned} k&\leftarrow i\\\ c&\leftarrow d^{2}\\\ t&\leftarrow
td^{2}\\\ r&\leftarrow rd\end{aligned}$

end while

4if  _$t=0$_ then

return _$\alpha=0$_

end if

5if  _$t=1$_ then

return _$\alpha=r$_

end if

Algorithm 6 Tonelli–Shanks ([15])

This algorithm allows us to compute a square root of a quadratic residue in
$\mathbb{Z}_{p}$. Note this algorithm uses again as an auxiliary element a
quadratic nonresidue. Iteratively applying it we can use
${\alpha_{(j)}}^{n/2^{i}}\pmod{p_{j}}$ the $2^{i}$/̄th root of $a$ to compute
its square root ${\alpha_{(j)}}^{n/2^{i+1}}$, until we finally reach
$\alpha_{(j)}$, from which we can recover $\alpha$.

Coming back again to the case $x^{n}+1$, we describe every step to compute
$(\alpha,\omega)$ in Algorithm 7.

Input: A power of two $n$ and a modulus $m$ (with known factorization)

Result: Suitable $(\alpha,\omega)$ roots of $-1$ and $1$

Let $m={p_{1}}^{e_{1}}\dots p_{k}^{e_{k}}$ be the prime decomposition of $m$.

1 Ensure $2n|p_{j}-1$ for every prime and abort otherwise.

for  _$j\leftarrow 1$ to __ $k$_ do

2 /* obtain a quadratic nonresidue in $\mathbb{Z}_{p_{j}}$ */

$tests=\mathsf{False}$;

// whether a candidate is a nonresidue

while  _not __ $tests$_ do

$u_{j}\xleftarrow{R}\mathbb{Z}_{p_{j}}$;

// choose a nonresidue candidate

if  _$u_{j}^{(p_{j}-1)/2}\equiv-1\pmod{p_{j}}$_ then

$tests=\mathsf{True}$;

// it is a nonresidue

end if

end while

3 /* compute $\alpha$ and $\omega\pmod{{p_{j}}^{e_{j}}}$ */

$\alpha_{(j)}=u_{j}^{(p-1)/2n}$;

// compute $\alpha\pmod{p_{j}}$

$\omega_{(j)}=u_{j}^{(p-1)/n}$;

// compute $\omega\pmod{p_{j}}$

$c,aux=\textsc{ExtEuclides}(n\alpha_{(j)}^{2n-1},p_{j})$;

// compute $\overline{f^{\prime}(\alpha_{(j)})}$

$d,aux=\textsc{ExtEuclides}(n\omega_{(j)}^{n-1},p_{j})$;

// compute $\overline{f^{\prime}(\omega_{(j)})}$

for  _$e\leftarrow 2$ to __ $e_{j}$_ do // apply Hensel Lemma

$\alpha_{(j)}\leftarrow\alpha_{(j)}-(\alpha_{(j)}^{n}+1)c\allowbreak\mkern
12.0mu{\operator@font rem}\,\,{p_{j}}^{e}$;

// lift from ${{p_{j}}^{e-1}}$ to ${{p_{j}}^{e}}$

$\omega_{(j)}\leftarrow\omega_{(j)}-(\omega_{(j)}^{n}-1)d\allowbreak\mkern
12.0mu{\operator@font rem}\,\,{p_{j}}^{e}$;

// lift from ${{p_{j}}^{e-1}}$ to ${{p_{j}}^{e}}$

end for

end for

4 Reconstruct $\alpha$ from $(\alpha_{(1)},\dots,\alpha_{(k)})$;

// via the CRT

5 Reconstruct $\omega$ from $(\omega_{(1)},\dots,\omega_{(k)})$;

// via the CRT

return _$(\alpha,\omega)$_

Algorithm 7 Computation of $\alpha$ and $\omega$

##  5 FFT Generalizations

As we have seen in Section 4 we only have suitable evaluation points in the
ring $\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$ if $m={p_{1}}^{e_{1}}\dots
p_{k}^{e_{k}}$ is such that every $p_{i}\equiv 1\pmod{2n}$.

These congruences are deeply related to the factorization of $x^{n}+1$
(irreducible in $\mathbb{Z}[x]$) when considered modulo $m$. It has been
described in [12] where Theorem 19 is presented.

######  Theorem 19 (Corollary 1.2 in [12]).

Let $n\geq d>1$ be powers of $2$ and $p\equiv 2d+1\pmod{4d}$ be a prime. Then
the polynomial $x^{n}+1$ factors as

$x^{n}+1\equiv\prod_{j=0}^{d-1}\left(x^{n/d}-\alpha_{j}\right)\pmod{p}$

for distinct $\alpha_{j}\in\mathbb{Z}_{p}^{*}$, where $x^{n/d}-\alpha_{j}$ are
irreducible in $\mathbb{Z}_{p}[x]$.

Theorem 19 can also be generalized to a not necessarily prime modulus $m$
taking advantage of the results discussed in the previous sections.

######  Theorem 20 (Generalization of Theorem 19 to a not necessarily prime
modulus $m$).

Let $n\geq d>1$ be powers of $2$, $m={p_{1}}^{e_{1}}\dots p_{k}^{e_{k}}$ the
prime decomposition of $m$ such that $p_{i}\equiv 2d+1\pmod{4d}$. Then the
polynomial $x^{n}+1$ factors as

$x^{n}+1\equiv\prod_{j=0}^{d-1}\left(x^{n/d}-\alpha_{j}\right)\pmod{m}$

for distinct $\alpha_{j}\in\mathbb{Z}_{m}^{*}$.

###### Proof.

Notice first $p_{i}\equiv 2d+1\pmod{4d}$ implies $p_{i}\equiv 1\pmod{2d}$,
therefore by the results discussed in Section 4.1 we know there exists a
twofold set of $d$/̄th roots of $-1$ with invertible differences
$\alpha_{0},\dots,\alpha_{d-1}$. From Lemma 10 we know each
$\alpha_{i}\in\mathbb{Z}_{m}^{\ast}$. We also know from Lemma 1 that

$\prod_{j=0}^{d-1}\left(x^{n/d}-\alpha_{j}\right)\equiv\prod_{j=0}^{d/2-1}\left(x^{n/d}-\alpha_{j}\right)\left(x^{n/d}-\alpha_{\overline{\jmath}}\right)\equiv\prod_{j=0}^{d/2-1}\left(x^{2n/d}-{\alpha_{j}}^{2}\right).$

Given that squares preserve the initial properties (as seen in
LABEL:{prop:squaring}) iteratively applying the same idea we finally get
$\displaystyle\prod_{j=0}^{d-1}\left(x^{n/d}-\alpha_{j}\right)\equiv
x^{n}+1\pmod{m}$ as desired. ∎

This implies that, under the necessary conditions for an FFT multiplication
algorithm, $x^{n}+1$ fully splits in linear factors when considered modulo
$m$. However sometimes this is not the case and we are enforced to use modulus
that specifically require $x^{n}+1$ to split in a smaller number of factors.

That is the case of some cryptographic constructions that use Theorem 19 from
[12] (or similar versions) to guarantee the invertibility of particular
subsets of elements in $\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$.

The condition $p_{i}\equiv 2d+1\pmod{4d}$ implies that there are $d$/̄th roots
of $-1$ in $\mathbb{Z}_{m}$, but no $2d$/̄th roots of $-1$. Therefore if $d<n$
no suitable evaluation points exist.

However having only $d$/̄th roots of $-1$ does not prevent us from finding a
reasonably efficient multiplication algorithm. We cannot complete the
recursion strategy but we still can partially use it.

To do so we just need to apply a technique called $n/d$/̄degree _striding_ (as
described in [4]), mapping our polynomials to a more convenient ring, defining
an auxiliary new variable $y=x^{n/d}$. We can always consider
$R[x]/\left<x^{n}+1\right>$ as a subring of
$R[x,y]/\left<x^{n/d}-y,x^{n}+1\right>$, and observe we can also describe this
second ring as $R[x][y]/\left<x^{n/d}-y,y^{d}+1\right>$.

With this simple change of variables we can now represent our original
polynomial as a polynomial in $y$ with $y$/̄degree bounded by $d$ that has as
coefficients polynomials in $R[x]$ of $x$/̄degree bounded by $n/d$. As a
polynomial in $y$ it satisfies all required conditions as we are only
considering modulus $y^{d}+1$ and the new ring $R^{\prime}=R[x]$ does contain
$d$ evaluation points $\alpha_{0},\dots,\alpha_{d-1}$ satisfying Conditions 2,
1 and 3.

With these $d$/̄th roots of $-1$ we can efficiently use $g(x,y)$ and $h(x,y)$
to compute evaluations $\\{g(x,\alpha_{i})\\}$ and $\\{h(x,\alpha_{i})\\}$, do
a pointwise product in $R[x]$ (using an auxiliary multiplication algorithm,
such as (Dual) Karatsuba) and invert the transform to recover the product
$(g\cdot h)(x,y)$ that directly gives us the desired solution substituting
again $y$ with $x^{n/d}$.

Observe that, the same way we have to choose an $\alpha$ that is a $d$/̄th
root of $-1$ to make the evaluation compatible with the quotient
$\left<y^{d}+1\right>$ the other quotient $\left<x^{n/d}-y\right>$ implies
that when computing the evaluation of the variable $y$ at $\alpha$ we obtain
as a result a polynomial in $R[x]/\left<x^{n/d}-\alpha\right>$ and therefore
is only defined modulo $x^{n/d}-\alpha$. This is an artifact of the technique
due to the additional variable introduced that has no impact in the process
but helps us keep these $x$-polynomials bounded when computing their products.

The running time for both the transform and the anti-transform is now
$\mathcal{O}\left(n\log{d}\right)$ and the $d$ products of polynomials of
degree $n/d$ that require each $\mathcal{O}\left({(n/d)}^{\log{3}}\right)$ for
a total of $\mathcal{O}\left(n\log{d}+d{(n/d)}^{\log{3}}\right)$.

From an abstract point of view we could directly apply Algorithm 5, as it was
described for a general ring $R$ and therefore we could use it just taking
into account to which ring each element belongs. However, for the sake of
readability, we explicitate this generalization in Algorithm 8.

Input: Two polynomials $g(x)$, $h(x)$ of degree bounded by $n$

Auxiliary: A twofold set $\alpha_{0},\dots,\alpha_{d-1}$ of $d$/̄th roots of
$-1$ with invertible differences

Result: The product $(g\cdot h)(x)$ of $g(x)$ and $h(x)$ in
$\mathbb{Z}_{m}[x]/\left<x^{n}+1\right>$

1 $\widehat{g}(y)\coloneqq g(x)\allowbreak\mkern 12.0mu{\operator@font
rem}\,\,x^{n/d}-y$ ;

// polynomial in $\left(\mathbb{Z}_{m}[x]\right)[y]$

2 $\widehat{h}(y)\coloneqq h(x)\allowbreak\mkern 12.0mu{\operator@font
rem}\,\,x^{n/d}-y$ ;

// polynomial in $\left(\mathbb{Z}_{m}[x]\right)[y]$

3 $\bm{g}\coloneqq\textsc{FFT}(\widehat{g}(y),\alpha_{0},\dots,\alpha_{d-1})$
;

// vector of polynomials in $\mathbb{Z}_{m}[x]$

4 $\bm{h}\coloneqq\textsc{FFT}(\widehat{h}(y),\alpha_{0},\dots,\alpha_{d-1})$
;

// vector of polynomials in $\mathbb{Z}_{m}[x]$

Define $\bm{f}$ a vector of polynomials in $\mathbb{Z}_{m}[x]$ of size $d$.

5 for  _$i\leftarrow 0$ to __ $d-1$_ do

$\bm{f}[i]\coloneqq\textsc{Karatsuba}(\bm{g}[i],\bm{h}[i])\allowbreak\mkern
12.0mu{\operator@font rem}\,\,x^{n/d}-\alpha_{i}$

end for

6 $\widehat{f}(y)\coloneqq\textsc{IFFT}(\bm{f},\alpha_{0},\dots,\alpha_{d-1})$

7 $f(x)\coloneqq\widehat{f}(y)\allowbreak\mkern 12.0mu{\operator@font
rem}\,\,y-x^{n/d}$

return _$f(x)$_

Algorithm 8 Generalized Efficient FFT Multiplication

###  5.1 Fast Chinese Remaindering

As we mentioned in the introduction, this particular issue of partially
splitting rings, where we cannot directly apply the original full FFT to the
initial polynomials, has been studied in [12] for rings with prime modulus
from a different point of view, considering FFT-like algorithms for
efficiently applying the Chinese Reminder Theorem [11, 17].

The main idea of these CRT approaches is to consider evaluations at
$\alpha_{i}$ as representatives for $g(x)\pmod{x-\alpha_{i}}$, sufficient for
determining $g(x)$ via the CRT since
$x^{n}+1\equiv\prod_{j=0}^{n-1}\left(x-\alpha_{j}\right)\pmod{m}$ (as we know
from LABEL:, 19 and 20). The same kind of recursions apply, as both
$g(x)\pmod{x-\alpha_{i}}$ and $g(x)\pmod{x-\alpha_{\overline{\imath}}}$ can be
computed from $g(x)\pmod{x^{2}-{\alpha_{i}}^{2}}$ (in an equivalent manner to
what we saw in Section 3).

Given an twofold set $\alpha_{0},\dots,\alpha_{d-1}$ of $d$/̄th roots of $-1$
what we do in Algorithm 8 is precisely computing the reminders
$\pod{{\operator@font rem}\mkern 6.0mux^{n/d}-\alpha_{i}}$ that determine the
original polynomials via the CRT.

However we believe our presentation is still more direct and informative,
since the generalization to a not necessarily prime modulus in a partially
splitting ring, not explored in [12], comes completely for free, while an
interpretation using the Chinese Reminder Theorem would technically require a
much more involved analysis when the ring is not a Principal Ideal Domain, or
not even a Unique Factorization Domain, as in order to verify the hypothesis
of the theorem one should check whether some ideals are comaximal in order to
ensure that every mapping is indeed an isomorphism, and some conditions (as
the requirement for $m$ to be odd) would only appear as artifacts of the
construction.

Recall the evaluation $g(\alpha)$ of any polynomial in $\alpha$ is equivalent
to computing its remainder after dividing by $x-\alpha$ (this is known as the
Polynomial Remainder Theorem).

All the evaluations at each of the $\alpha_{i}$ are just
$g(\alpha_{i})=g(x)\pod{{\operator@font rem}\mkern 6.0mux-\alpha_{i}}$. We can
see the vector whose components are these evaluations as the CRT
representation of the polynomial. Pointwise multiplication of these vectors of
evaluations for two polynomials $g(x)$ and $h(x)$ is just a multiplication in
the CRT domain and the interpolation consists of recovering the polynomial
coefficients from the CRT representations.

It seems just like a different interpretation of the same idea. It allows the
same analysis as the CRT representation over a set of factors can be computed
even if $x^{n}-a$ does not fully split.

The important point is that this argument works even if $d\neq n$, and we
could use it to represent any polynomial with $d$ remainders
$\pod{{\operator@font rem}\mkern 6.0mux^{n/d}-\alpha_{i}}$, compute the
pointwise products among polynomials of degree bounded by $n/d$ and then
recover back the product polynomial modulo ${x^{n}-a}$.

######  Theorem 21 (CRT for $\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>$).

Let $x^{n}-a=\prod_{i=0}^{d-1}(x^{n/d}-\alpha_{i})$ where
${\\{\alpha_{i}\\}}_{i}$ are a twofold set of $d$/̄th roots of $a$ with
differences invertible in $\mathbb{Z}_{m}$, then
$\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>\cong\mathbb{Z}_{m}[x]/\left<x^{n/d}-\alpha_{0}\right>\times\cdots\times\mathbb{Z}_{m}[x]/\left<x^{n/d}-\alpha_{d-1}\right>$.

###### Proof.

For convenience we are going to label the $d$ roots as
$\alpha_{b_{\log(d)-1}\dots b_{0}}$ as we did in Figure 1.

From an argument analogous to Theorem 20 we know that we can write
$x^{n/{2^{k}}}-\alpha_{b_{k-1}\dots
b_{0}}=(x^{n/{2^{k+1}}}-\alpha_{0b_{k-1}\dots
b_{0}})(x^{n/{2^{k+1}}}-\alpha_{1b_{k-1}\dots b_{0}})$.

We have to prove that
$\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k}}-\alpha_{b_{k-1}\dots b_{0}}\right>$
is isomorphic to

$\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\times\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots
b_{0}}\right>.$

We can define a map from $\mathbb{Z}_{m}[x]$ to

$\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\times\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots
b_{0}}\right>$

by computing $\operator@font rem$, and the kernel would be

$\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\bigcap\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}\right>.$

That is, the map is also well defined from

$\mathbb{Z}_{m}[x]\Big{/}\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\bigcap\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}\right>.$

So far this discussion has been completely general. However for this
particular polynomials we have

$\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>+\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots
b_{0}}\right>\cong\mathbb{Z}_{m}[x].$

This is the case since

$(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})-(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}})=\alpha_{1b_{k-1}\dots
b_{0}}-\alpha_{0b_{k-1}\dots b_{0}}$

which is invertible in $\mathbb{Z}_{m}$ (as every difference of roots is
invertible), implying

$1\in\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>+\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}\right>.$

We can explicitly write this saying there are two polynomials $g(x)$ and
$h(x)$ such that

$(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})g(x)+(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}})h(x)=1.$

On the one hand this implies that the map is surjective. From the previous
identity we know any pair of polynomials $(a(x),b(x))$ has a preimage
$b(x)g(x)(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})+a(x)h(x)(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}})$.

On the other hand this implies

$\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\bigcap\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots
b_{0}}\right>=\left<x^{n/2^{k}}-\alpha_{b_{k-1}\dots b_{0}}\right>.$

The right-hand side is directly a subset of the left-hand side. To see the
other inclusion we can check that for any

$a(x)\in\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}}\right>\bigcap\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}\right>,$

that is, there are polynomials $b(x)$ and $c(x)$ such that

$a(x)=b(x)(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})=c(x)(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}),$

it is also true that

$\displaystyle a(x)$ $\displaystyle=a(x)\cdot 1$
$\displaystyle=a(x)(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})g(x)+a(x)(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}})h(x)$
$\displaystyle=c(x)(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots
b_{0}})(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots b_{0}})g(x)$
$\displaystyle\mathrel{\phantom{=}}+b(x)(x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots
b_{0}})(x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}})h(x)$
$\displaystyle=(c(x)g(x)+b(x)h(x))(x^{n/2^{k}}-\alpha_{b_{k-1}\dots b_{0}})$

and therefore $a(x)\in\left<x^{n/2^{k}}-\alpha_{b_{k-1}\dots b_{0}}\right>$.

Summing up the desired mapping is an isomorphism.

The main issue here is that CRT is usually defined for principal ideal domains
or at least unique factorization domains. If it is not the case, such as with
our construction, we have to specifically check these additional properties,
such as $\left<x^{n/2^{k+1}}-\alpha_{0b_{k-1}\dots b_{0}}\right>$ and
$\left<x^{n/2^{k+1}}-\alpha_{1b_{k-1}\dots b_{0}}\right>$ being comaximal. ∎

The task we have is defined as follows. We have a polynomial
$g(x)\in\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>$ and a twofold set
$\\{\alpha_{b_{\log(d)-1}b_{\log(d)-2}\dots b_{0}}\\}$ of $d$/̄th roots of $a$
with invertible differences.

Our goal is to compute all $g_{b_{\log(d)-1}\dots
b_{0}}(x)=g(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/d}-\alpha_{b_{\log(d)-1}\dots b_{0}}}$.

To do so we start computing $g_{0}(x)=g(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2}-\alpha_{0}}$ and $g_{1}(x)=g(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2}-\alpha_{1}}$. This requires $\mathcal{O}\left(n\right)$
operations.

Then we notice $g_{0b_{0}}(x)=g(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/4}-\alpha_{0b_{0}}}=g_{b_{0}}(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/4}-\alpha_{0b_{0}}}$ and $g_{1b_{0}}(x)=g(x)\pod{{\operator@font
rem}\mkern 6.0mux^{n/4}-\alpha_{1b_{0}}}=g_{b_{0}}(x)\pod{{\operator@font
rem}\mkern 6.0mux^{n/4}-\alpha_{1b_{0}}}$.

In general we can recursively compute $g_{b_{i}b_{i-1}\dots
b_{0}}(x)=g(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2^{i+1}}-\alpha_{b_{i}b_{i-1}\dots b_{0}}}=g_{b_{i-1}\dots
b_{0}}(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2^{i+1}}-\alpha_{b_{i}b_{i-1}\dots b_{0}}}$. Therefore at this
$i$/̄th level computing each remainder takes $\mathcal{O}\left(n/2^{i}\right)$
operations and has to be done $\mathcal{O}\left(2^{i}\right)$ times, for a
total cost of $\mathcal{O}\left(n\right)$.

Observe computing $g_{b_{i-1}\dots b_{0}}(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2^{i+1}}-\alpha_{0b_{i-1}\dots b_{0}}}$ is done taking the lower
coefficients of $g_{b_{i-1}\dots b_{0}}(x)$ and adding the higher coefficients
multiplied by $\alpha_{0b_{i-1}\dots b_{0}}$.

The same way, since $\alpha_{1b_{i-1}\dots b_{0}}=-\alpha_{0b_{i-1}\dots
b_{0}}$ we have that $g_{b_{i-1}\dots b_{0}}(x)\pod{{\operator@font rem}\mkern
6.0mux^{n/2^{i+1}}-\alpha_{1b_{i-1}\dots b_{0}}}$ is computed taking the lower
coefficients of $g_{b_{i-1}\dots b_{0}}(x)$ and subtracting the higher
coefficients multiplied by $\alpha_{0b_{i-1}\dots b_{0}}$.

Notice the multiplications are the same (and could be reused) and the only
difference is that we add or subtract depending on the case.

The number of levels is $\log(d)$ and we end up with
$\mathcal{O}\left(n\log(d)\right)$ operations to compute the CRT
representation of $g(x)$ taking modulus over the $d$ different polynomials of
degree $n/d$.

Input: A polynomial $g(x)$ of degree bounded by $n$ and a twofold set
$\alpha_{0},\dots,\alpha_{d-1}$ of $d$/̄th roots of $a$ with invertible
differences

Result: Remainders of $g(x)$ when divided by
$x^{n/d}-\alpha_{0},\dots,x^{n/d}-\alpha_{d-1}$

if  _$r=1$_ then return _$g$_ ;

r $\\{g_{b_{\log(d)-2}\dots
b_{0}}\\}\coloneqq\textsc{FFT}(g,{\alpha_{0}}^{2},\dots,{\alpha_{d/2-1}}^{2})$

for  _$b_{\log(d)-2}\dots b_{0}\leftarrow{\\{0,1\\}}^{\log(d)-1}$_ do

Split $g_{b_{\log(d)-2}\dots b_{0}}$ into $g_{b_{\log(d)-2}\dots b_{0}}^{L}$
and $g_{b_{\log(d)-2}\dots b_{0}}^{H}$

$g_{0b_{\log(d)-2}\dots b_{0}}\coloneqq g_{b_{\log(d)-2}\dots
b_{0}}^{L}+g_{b_{\log(d)-2}\dots b_{0}}^{H}\cdot\alpha_{0b_{\log(d)-2}\dots
b_{0}}$

$g_{1b_{\log(d)-2}\dots b_{0}}\coloneqq g_{b_{\log(d)-2}\dots
b_{0}}^{L}-g_{b_{\log(d)-2}\dots b_{0}}^{H}\cdot\alpha_{0b_{\log(d)-2}\dots
b_{0}}$

end for

return _$\\{g_{b_{\log(d)-1}b_{\log(d)-2}\dots b_{0}}\\}$_

Algorithm 9 FFT (CRT)

At this point we could use Karatsuba’s algorithm to multiply them, that is, a
cost of $\mathcal{O}\left(d{(n/d)}^{\log_{2}(3)}\right)$.

Then we have to invert this operations. To do so we could follow the same
ideas inverting the operations at each level. To recover the lower part of
$g_{b_{i-1}\dots b_{0}}(x)$ we add $g_{0b_{i-1}\dots
b_{0}}(x)+g_{1b_{i-1}\dots b_{0}}(x)$ and divide by two (that is, multiply
each coefficient by $2^{-1}$). To recover the upper part we now subtract them
computing $g_{0b_{i-1}\dots b_{0}}(x)-g_{1b_{i-1}\dots b_{0}}(x)$ and multiply
each coefficient by $2^{-1}{(\alpha_{0b_{i-1}\dots b_{0}})}^{-1}$. The cost of
this operations is again $\mathcal{O}\left(n\log(d)\right)$.

As we have to divide by $2$ at each level one could just skip this step and
divide by $d$ at the end.

Input: A CRT representation $g_{0}\dots g_{d-1}$ of a polynomial $g(x)$ of
degree bounded by $n$, and a twofold set $\alpha_{0},\dots,\alpha_{d-1}$ of
$d$/̄th roots of $a$ with invertible differences

Result: The polynomial $g(x)$

if  _$r=2$_ then return
_$2^{-1}\left((g_{0}+g_{1})+x^{n/2}(g_{0}+g_{1})\cdot{\alpha_{0}}^{-1}\right)$_
;

for  _$b_{\log(d)-2}\dots b_{0}\leftarrow{\\{0,1\\}}^{\log(d)-1}$_ do

$\begin{aligned} &g_{b_{\log(d)-2}\dots b_{0}}\coloneqq
2^{-1}(g_{0b_{\log(d)-2}\dots b_{0}}+g_{1b_{\log(d)-2}\dots b_{0}})+\\\
&\mathrel{\phantom{\coloneqq}}x^{n/2}2^{-1}(g_{0b_{\log(d)-2}\dots
b_{0}}-g_{1b_{\log(d)-2}\dots b_{0}})\cdot{\alpha_{0b_{\log(d)-2}\dots
b_{0}}}^{-1}\end{aligned}$

end for

return _${\textsc{IFFT}}(\\{g_{b_{\log(d)-2}\dots
b_{0}}\\},{\alpha_{0}}^{2},\dots,{\alpha_{d/2-1}}^{2})$_

Algorithm 10 IFFT (CRT)

This alternative interpretation has then same properties and can also be used
to design the same efficient multiplication algorithms. We however believe the
previous presentation was more insightful.

##  6 Results and Discussion

The main result can be summarized in the following way, in order to design an
efficient multiplication algorithm in $\mathbb{Z}_{m}[x]/\left<x^{n}-a\right>$
via an FFT the necessary and sufficient condition is to have a set of $n$
different $n$/̄th roots of $a$ (Condition 2, so that multiplication is
compatible with congruence classes) with invertible differences (Condition 1,
so that the inverse transform is defined) such that its recursive squares are
equal two by two (Condition 3, so that the computation can be efficiently done
recursively).

This characterization is similar but not equivalent to the usual
characterization with roots of unity (Condition 4), which is sufficient but
not necessary. We have proven however that, as Theorem 15 states, restricting
to sets satisfying Condition 4 does not decrease the applicability of these
efficient multiplication algorithms as these $(\alpha,\omega)$/̄sets exist if
and only if the necessary and sufficient sets satisfying Conditions 2, 1 and 3
exist.

As intermediate result we have also proven that these properties are indeed
independent in the general case, and we do believe that this analysis might
help to clarify whether some considerations and conditions usually stated in
the folklore are fundamental considerations about the algebraic structure or
just conventions for a particular instantiation on a particular setting (as it
is the case with roots of unity).

This framework is also a general introduction to FFT/̄multiplication from a
rigorous mathematical point of view while still keeping it readable for an
audience not familiarized with more advanced algebraic considerations.

For example our analysis directly generalizes, as we have seen in Section 5,
to a ring where $x^{n}-a$ does not fully split and $\mathbb{Z}_{m}$ is not a
field, while alternative interpretations are much more delicate to work with.

Acknowledgments. This work is partially supported by the European Union
PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant
780701) and the Spanish Ministry of Economy and Competitiveness, through
Project MTM2016-77213-R.

## References

  * [1] Eric Bach and Jeffrey Outlaw Shallit.  Algorithmic number theory.  Foundations of computing. MIT Press, Cambridge, MA, 1996.
  * [2] Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner, and Chris Peikert.  More efficient commitments from structured lattice assumptions.  In Dario Catalano and Roberto De Prisco, editors, SCN 18, volume 11035 of LNCS, pages 368–385, Amalfi, Italy, September 5–7, 2018\. Springer, Heidelberg, Germany.  doi:10.1007/978-3-319-98113-0_20.
  * [3] Jon Louis Bentley, Dorothea Haken, and James B. Saxe.  A general method for solving divide-and-conquer recurrences.  SIGACT News, 12(3):36––44, September 1980.  doi:10.1145/1008861.1008865.
  * [4] Daniel J Bernstein.  Multidigit multiplication for mathematicians.  https://cr.yp.to/papers/m3.pdf.
  * [5] Chi-Ming Marvin Chung, Vincent Hwang, Matthias J. Kannwischer, Gregor Seiler, Cheng-Jhih Shih, and Bo-Yin Yang.  NTT multiplication for NTT-unfriendly rings.  IACR TCHES, 2021(2):159–188, 2021.  doi:10.46586/tches.v2021.i2.159-188.
  * [6] James W. Cooley and John W. Tukey.  An algorithm for the machine calculation of complex fourier series.  Mathematics of computation, 19(90):297–301, 1965.  doi:10.2307/2003354.
  * [7] Charles M. Fiduccia.  Polynomial evaluation via the division algorithm the fast fourier transform revisited.  In Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC ’72, pages 88––93, New York, NY, USA, 1972. Association for Computing Machinery.  doi:10.1145/800152.804900.
  * [8] Anatolii Karatsuba.  Multiplication of multidigit numbers on automata.  In Soviet physics doklady, volume 7, pages 595–596, 1963.
  * [9] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen.  SWIFFT: A modest proposal for FFT hashing.  In Kaisa Nyberg, editor, FSE 2008, volume 5086 of LNCS, pages 54–72, Lausanne, Switzerland, February 10–13, 2008. Springer, Heidelberg, Germany.  doi:10.1007/978-3-540-71039-4_4.
  * [10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  On ideal lattices and learning with errors over rings.  In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23, French Riviera, May 30 – June 3, 2010. Springer, Heidelberg, Germany.  doi:10.1007/978-3-642-13190-5_1.
  * [11] Vadim Lyubashevsky, Chris Peikert, and Oded Regev.  A toolkit for ring-LWE cryptography.  In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 35–54, Athens, Greece, May 26–30, 2013. Springer, Heidelberg, Germany.  doi:10.1007/978-3-642-38348-9_3.
  * [12] Vadim Lyubashevsky and Gregor Seiler.  Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs.  In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 204–224, Tel Aviv, Israel, April 29 – May 3, 2018. Springer, Heidelberg, Germany.  doi:10.1007/978-3-319-78381-9_8.
  * [13] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery.  An Introduction to the theory of numbers.  John Wiley, 5th ed. edition, 1991.
  * [14] Thomas Pöppelmann and Tim Güneysu.  Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware.  In Alejandro Hevia and Gregory Neven, editors, LATINCRYPT 2012, volume 7533 of LNCS, pages 139–158, Santiago, Chile, October 7–10, 2012\. Springer, Heidelberg, Germany.  doi:10.1007/978-3-642-33481-8_8.
  * [15] Daniel Shanks.  Five number-theoretic algorithms.  In Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), pages 51–70, 1973.
  * [16] Gilbert Strang.  Introduction to linear algebra.  Cambridge Press, Wellesley, 5th ed. edition, 2016.
  * [17] Joachim von zur Gathen and Jürgen Gerhard.  Modern Computer Algebra.  Cambridge University Press, 3 edition, 2013.  doi:10.1017/CBO9781139856065.