背景介绍

Ring-LWE和Modular-LWE问题已经在密码学理论和应用中非常广泛地使用了，而其中最为广泛使用的环，则是环$R_q=\mathbb Z_q[x]/\Phi_m(x)$，因此在这个环上快速进行乘法，成了基于Ring/Modular-LWE的密码算法实现中的效率方面关注的重要问题。

现假设我们有多项式$a,b\in R_q$并且要计算它们相乘后在，如果采用直接在$\mathbb Z[x]$中计算乘积再求模的方式，我们首先得计算出$a\cdot b\in\mathbb Z[x]$，然后再依次模上$\Phi_m(x)$和$q$——这将会造成非常大的开销。幸运的是，我们有一个非常聪明的办法可以避免这个问题，该问题可以避免求多项式模$\Phi_m(x)$这一经常使用的操作，使得整个计算过程极大地加速，再配合上模素数运算的相关算法，可以使得整个运算在很快地时间内完成，极大提高了Ring/Modular-LWE相关算法的效率和实际应用价值。

这个巧妙的办法就是运用称作数论变换$\mathsf{NTT}(\cdot)$的同构，将多项式变换$a,b$均为向量$\hat a,\hat b$，然后计算$\widehat{ab}=\hat a\odot \hat b$，计算完成后，再用逆数论变换$\mathsf{NTT}^{-1}$将$\widehat{ab}$恢复为$a\cdot b$。这里的$\mathsf{NTT}$和$\mathsf{NTT}^{-1}$均为非常简单的操作，而"$\odot$“就是简单地将两个相同长度的向量的对应位乘起来再模$q$以得到一个新的向量，是一个非常简单的操作！以上两个运算使得多项式的乘法可以高效的计算，更进一步如果我们将反复用到一个多项式用作乘数，我们甚至可以让它暂时始终保持数论变换下的形式，来取得更好的计算效率。

下文中，我们将对上述过程进行形式化的描述，并介绍具体的算法，以及算法背后的一些数学知识。

数论变换算法

数论变换算法的形式多种多样，我们采用文章[LN16]中的方式进行介绍，但对记号做一定的修改。选择这个文章中的方式的主要原因一来是因为该文对数论变换的描述非常接近离散傅里叶变换，因此熟悉离散傅里叶变换的读者可以快速明白整个算法的过程；二来该文中的描述足够简洁和清晰，这样想要阅读原文的读者也不会花费大量时间。改变原文的记号的是希望同Ring-LWE的开山之作[LPR12]及其其他相关文章相统一，以能更好地进行理论方面的解释。同时不熟悉傅里叶变化的读者也完全没有必要再去研究它的具体过程，以及它到底有什么用，我们在文章将其当成一个固定的模块来使用，它是数论变换的一个环节，而其逆变换也是数论逆变换的一个环节。

我们考虑最常见的情形，设$m=2^d$是一个2的幂次，并令$n=\phi (m)$, 其中$\phi(\cdot)$是高斯函数，则有$n=2^{d-1}$。在这样的参数下，分圆多项式具有非常简洁的形式$\Phi_m=x^n+1$，模这样的分圆多项式的多项式环也是Ring/Modular-LWE算法中最常选择的环。如果素数$q$的选择也恰好使得$\mathbb Z_q^\times$中有一个阶为$m$的元素$r$，此时数论变换也就派上用场了。现在假设上述参数全部满足，计算环元素$a,b\in\mathbb Z_q[x]/\Phi_m(x)$可以通过数论变换来进行，由于多项式也可以写成由系数组成的向量的形式，对于任意多项式$c=c_0+c_1x+c_2x^2+\cdots+c_{n-1}c^{n-1}\in\mathbb Z_q[x]/\Phi_m(x)$，$\mathbb Z_q^n$中的向量，即$c=(c_0,c_1,\cdots,c_{n-1})$，有了这种对应后，我们不再区分几种变换函数中的参数是多项式还是向量。首先我们假设$\omega=r^2$，并令矩阵

$$ \mathbf A=\left[ \begin{matrix} \omega^0 & \omega^0 & \omega^0 & \cdots & \omega^0 \newline \omega^0 & \omega^1 & \omega^2 & \cdots & \omega^{n-1} \newline \omega^0 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline \omega^0 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{matrix} \right] $$

实际上这个矩阵就是离散傅里叶变换的矩阵，我们记$\mathsf{DFT}(c)=\mathbf {A}c$。这里$\mathsf{DFT}$也可以看作是对多项式的赋值，通过赋给$x$不同的值来形成一个新的多项式，我们有$\mathsf{DFT}(c)=(c(\omega^0),c(\omega^1),\cdots,c(\omega^{n-1}))$。对多项式做傅里叶变换不是我们的终极目的，在这之前，我们还需要另一种变换，我们称之为$R$变换。对一个多项式进行$R$变换，可以表示为$R(a)=(a_0,ra_1,r^2a_2,\cdots,r^{n-1}a_{n-1})$。这个过程也可以用矩阵来表示，即令

$$ \mathbf R=\left[ \begin{matrix} r^0 & & & \newline & r^1 & & \newline & & \ddots & \newline & & & r^{n-1} \end{matrix} \right] $$

则显然有$R(a)=\mathbf Ra$。我们整个数论变换$\mathsf{NTT}(a)$可以表示为$\mathsf{NTT}(a)=\mathsf{DFT}(R(a))=\mathbf{AR}a$。我们固定用$\hat a$表示$a$经过数论变换后的形式，即$\hat a=\mathsf{NTT}(a)$。由于$\mathbf A$和$\mathbf R$均为可逆矩阵，则显然也就是一个同构变换，其逆变换也可以很快地通过$a=\mathsf{NTT}^{-1}(\hat a)=(\mathbf{AR})^{-1}\hat a$来求出。矩阵$\mathbf A$的逆矩阵为

$$ \mathbf A^{-1}=n^{-1}\left[ \begin{matrix} \omega^0 & \omega^0 & \omega^0 & \cdots & \omega^0 \newline \omega^0 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(n-1)} \newline \omega^0 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(n-1)} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline \omega^0 & \omega^{-(n-1)} & \omega^{-2(n-1)} & \cdots & \omega^{-(n-1)^2} \end{matrix} \right] $$ 其中$n^{-1}$表示$n$在$\mathbb Z_q^times$中的逆元。显然矩阵$\mathbf A^{-1}$是对向量的作用是求它的傅里叶逆变换。而$\mathbf R$的可以根据对角矩阵求逆的方式简单求出: $$ \mathbf R^{-1}=\left[ \begin{matrix} r^0 & & & \newline & r^{-1} & & \newline & & \ddots & \newline & & & r^{-(n-1)} \end{matrix} \right] $$ 有了以上的基础操作，整个通过数论变换来求多项式$a,b\in\mathbb Z_q[x]/\Phi_m(x)$在该环中的积可以可以表示为$a\cdot b=\mathsf{NTT}^{-1}(\mathsf{NTT}(a)\odot\mathsf{NTT}(b))$，其中$\odot$就是在前文中提到过的向量逐位乘。除此之外，更加可喜的是，由于$\hat a=\mathbf{AR}a,\hat b=\mathbf{AR}b$，如果用$\oplus$来表示向量的逐位加，那么根据$a+b=a\oplus b$有$\hat a\oplus \hat b=(\mathbf{AR}a)\oplus(\mathbf{AR}b)=\mathbf{AR}(a\oplus b)$，因此$a+b=(\mathbf{AR})^{-1}(\hat a\oplus \hat b)$。也就是说，向量的加法也可以在数论变换的形式下通过逐位相加完成！

还原最初的形式

我们将傅里叶变换用作数论变换中的一个模块，来帮助读者快速理解数论变换的过程，但是要探究它的本质，我们还是要回到最初的形式，即研究复合变换$\mathsf{NTT}(a)=\mathsf{DFT}\circ R (a)$做了什么样的操作。根据矩阵的计算结果，我们有 $$ \mathbf{AR}=\left[ \begin{matrix} r^0& r^1& r^2& \cdots& r^{n-1}\newline r^0& r^3& r^6& \cdots& r^{3( n-1 )}\newline r^0& r^5& r^{10}& \cdots& r^{5( n-1 )}\newline \vdots& \vdots& \vdots& \ddots& \vdots\newline r^0& r^{2n-1}& r^{2( 2n-1 )}& \cdots& r^{( n-1 ) \left( 2n-1 \right)} \end{matrix} \right] $$ 我们可以看出$\mathsf{NTT}(a)=(a(r),a(r^3),\cdots,a(r^{2n-1}))$，其中$r$在$\mathbb Z_q$中的阶为$m=2n$，而$1,3,5,\cdots,2n-1$则正是$\mathbb Z_m^\times$中的元素。这一切究竟是为什么？为什么这样一种奇怪的多项式赋值可以让我们如此简便地对$\mathbb Z_q[x]/\Phi_m(x)$中的元素做运算？要探究背后的原因，一切都还要从“数的故事”说起。

数的故事

数的故事就像神话一样长，我们没有办法从故事的序章开始讲，只好假设绝大部分读者都听过其中很多广为人知的章节，今天我们就讲那些章节之后的故事。如果读者没有听过太多数的故事，那么阅读任何一本初等数论或代数的读物都是不错的选择。

在数的世界中，我们熟悉的有大世界$\mathbb C$，即所有复数的世界；也有小世界$\mathbb Q$，即有理数的世界；甚至还有迷你世界$\mathbb Z$即所有整数的世界。读者都应该知道，在大世界和小世界之间，应该存在其它的世界，例如著名的“次大世界”$\mathbb R$就介于$\mathbb C$和$\mathbb Q$之间，然后大家却经常忽略二者之间的一些“中等世界”。在讲中等世界的故事之前，我们需要对数的大世界了解更多。

代数数

即使是大世界中的数，也要分很多的等级，例如整数是一种非常稀有的数，而有理数则相对要普遍一些，无理数相比有理数来说，又要多得多。但是在无理数和有理数之间，实际上还有一个等级——代数数。代数数，就是可以那些作为有理系数的代数方程（即多项式$p(x)=0$的形式）的解的数，例如$\sqrt 2$，它就是方程$x^2-2=0$的一个解，因此是一个代数数；而$\pi$和$e$就不是那么幸运了，它们不能被表示成任何一个有理系数的代数方程的解，因此不是代数数，这样的数我们也给它们一个名字，称为\textbf{超越数}。

在复数的世界中，有理系数的代数方程的解并不一定是落在实数中的，我们可以将代数数推广到整个复数世界中来，称为复数中所有是某个有理系数的多项式$f(x)\in\mathbb Q[x]$的根的数为代数数（这里需要注意到多项式和代数方程的一一对应关系，以及前者的根就是后者的解）。复数中的代数数最简单的例子就是$i$，由于$i$是$x^2+1$的一个根，因此它是一个代数数。

代数数的故事还没完。一个代数数显然可以是无穷多个有理系数的多项式的根，因为对于任意的$\alpha\in\mathbb Q$而言，多项式$p(x)$和$\alpha p(x)$显然有着相同的根；除此之外，若$\zeta$是多项式$p(x)\in\mathbb Q[x]$的一个根，那么对于任意的$q(x)\in\mathbb Q[x]$，$\zeta$也是$p(x)\cdot q(x)\in\mathbb Q[x]$的一个根，则是由于$p(\zeta)\cdot q(\zeta)=0\cdot q(\zeta)=0$。在以代数数$\zeta$为根的千千万万个有理系数多项式中，实际上有一个就可以代表它们的所有，即那个最高次项的系数是$1$的有理数域中的不可约多项式，我们称这样的多项式为首一不可约多项式，也称其为$\zeta$的最小多项式。也许一些简单的故事主角更能说明问题：

• $x^2+1$是$i$的最小多项式。$x^2+1$的最高次项系数为$1$，满足了“首一”的条件；由于在复数域上，它可以分解为$x^2+1=(x-i)(x+i)$，尚若它能在有理数域上分解，分解的结果应该是同实数域中的分解相同，因此实数域上的分解结果表明$x^2+1$不能在有理数域中分解，因此它是一个不可约多项式，也是$i$的最小多项式。
• $x^3+1$不是$-1$的最小多项式。$x^3+1=(x+1)(x^2-x+1)$是一个可约的多项式。

当然，寻找一个代数数的最小多项式并不是一个简单的问题，需要更多的背景知识，但是我们可以按照例子中，利用一个结论来论证一些多项式是最小多项式。根据多项式分裂的原理，如果一个多项式能够在域$K$上分裂，又能在它的子域$E$上分裂，那么在两个域上分裂的结果应当是相同的。那么显而易见，如果一个多项式$f(x)$在实数域上能分解为系数中含有复数的一次多项式，那它就一定是一个有理数域上的不可约多项式。这是由于$\mathbb Q$是$\mathbb C$的子域，如果$f(x)$在$Q$上分裂，那么其分裂出的多项式应当是系数是有理数，那么它在$\mathcal C$上分裂出的多项式系数也就应当是有理数了，与事实显然是矛盾的。除此之外，所有的代数数也是可以构成一个域的，称为\textbf{代数数域}，证明的方法多种多样，读者不妨自己尝试一下。到此为止，我们找到了一个“中等世界”。

代数数中还有一类很特殊的数，这些数是代数数中的“整数”，它们是那些最小多项式是整系数多项式的代数数，我们称它们为\textbf{代数整数}。根据这个定义$\sqrt 2,i,\frac{\sqrt 2}{2}+\frac{\sqrt 2}{2}i$都是代数整数，因为它们的最小多项式分别是$x^2-2,x^2+1,x^8+1$。可以证明，有理数中的代数整数就是整数，因此我们可以将有理数域和代数数域对应起来，它们各自包含一个“整数环”，代数数域包含的就是代数整数环，而有理数域包含的就是整数环。

域扩张

现在就让我们来看看，其他“中等世界”到底是什么样。如果我们试图向有理数域中添加一个代数数，为了保持域的特征，我们添加一个元素是远远不够的，但是添加进去所有的代数数肯定又是够的，那么就可能有如下两种可能：

• 必须同时添加其他所有的代数数
• 可以只添加一部分代数数

我们用一个简单的例子来说明，第二种说法是对的。我们知道$\sqrt 2$是一个代数数，现在考虑向$\mathbb Q$中添加$\sqrt 2$并向其中尽可能少的添加代数来形成一个新的域$\mathbb Q(\sqrt 2)$。首先根据域的定义，所有形如$a+b\sqrt 2$（以下默认$a,b\in\mathbb Q$）的元素都必须加入$\mathbb Q(\sqrt 2)$。那么加入这些元素够了吗？可以肯定的是，任意两个形如$a+b\sqrt 2$的数的加法、乘法、减法都可以表示成这样的形式，而除法也不难证明。既然除法可以保证，那么$r=a+b\sqrt 2$的乘法逆元也可以通过$1/r$来计算，也就是说，所有$a+b\sqrt 2$的数组成的集合就是我们需要的$\mathbb Q(\sqrt 2)$。$\mathbb Q(\sqrt[3]2)$的形式要更加复杂一些，需要加入所有形如$a+b2^{1/3}+c2^{2/3},a,b,c\in\mathbb Q$的数才行。

如果更加深究一点我们会发现，无论是$\mathbb Q(\sqrt 2)$还是$\mathbb Q(\sqrt[3]2)$，其中的元素都可以用“一串”$\mathbb Q$表示出来，而并不需要一些“外来魔法”。对于任意的代数数$\zeta$这样还是行得通吗？即，我们是否可以将$\mathbb Q(\zeta)$表示成由$\zeta$的次数为基的$\mathbb Q$中的向量？现在我们给代数数定义一个新的属性，叫做它的次数，这个次数也就是它的最小多项式的次数。假设$f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0$是$\zeta$的最小多项式，那么根据$f(\zeta)=0$就有$\zeta^n=-(a_{n-1}\zeta^{n-1}+\cdots+a_1\zeta^1+a_0)$，即$\zeta^n$可以表示为由${1,\zeta,\cdots,\zeta^{n-1}}$为基组成的向量。这个操作对于所有的$\zeta^m$（其中$m$为大于$n$的整数）也可行，只需要反复代入$\zeta^n=-(a_{n-1}\zeta^{n-1}+\cdots+a_1\zeta^1+a_0)$就可以将$\zeta^m$表示成上述形式。实际上，可以验证$\mathbb Q(\zeta)$就可以表示为以${1,\zeta,\cdots,\zeta^{n-1}}$为基的$\mathbb Q$中的向量。

通过这样引入新的元素，将域扩大到一个最小的能包含原先的域和该新元素的域这样的操作，称为域扩张。而在$\mathbb Q$中引入代数数后，扩张后的域可以表示成$\mathbb Q$的向量，这个向量的维数就称为域扩张的次数。显然对于$n$次代数数$\zeta$来说，$\mathbb Q(\zeta)$是一个$\mathbb Q$的$n$次扩张。我们将所有向$\mathbb Q$中引入代数数进行域扩张后得到的域称为\textbf{数域}。

有关域扩张，还有说不完的故事，扩张可以通过不引入代数数，而是引入超越数来进行，或者扩张又可以是针对某个多项式的根来说，又或是在有限域中研究扩张，这些都是精彩的故事。今天让我们关注我们的故事，继续说完数论变换的故事。

分圆多项式和分圆域

现在我们将问题进一步简化，我们只找那些让我们看起来“舒服”一些素多项式作为模多项式。一个天然的选择就是“分圆多项式”。分圆多项式是这样的：对于一个$m$次分圆多项式来说

• 首先找到所有的$m$阶本元根，即$\omega_m^k = e^{\frac{2\pi k}{m}}$

• 计算$\Phi_m(x)=\prod_{i\in\mathbb Z_m^\times}(x-\omega_m^i)$

  分圆多项式始终是一个整系数的多项式。我们将域$Q[\omega_m^{1}]$这样的域都叫做分圆域，显然它同构于$\mathbb Q[x]/\Phi_m(x)$。

当$m=2^d$为某个2的幂次方时，我们有$\Phi_m(x)=x^{m/2}+1$。这里显然对于所有的$\omega_m^i,i\in\mathbb Z_q^\times$来说，$\Phi_m(x)$就是$\zeta_i$的最小多项式。我们稍后就会说，这一的选择会使得我们在计算上有相当大的优势。我

从代数扩张到多项式域

对于一个代数数$\zeta$来说，扩域$\mathbb Q(\zeta)$中的元素可以被表示为$a_{n-1}\zeta^{n-1}+\cdots+a_1x+a_0$的形式，这不得不让人想到多项式。实际上，作映射$\kappa:\zeta\mapsto x$，则$a_{n-1}\zeta^{n-1}+\cdots+a_1\zeta+a_0$就可以表示为$a_{n-1}x^{n-1}+\cdots+a_1x+a_0$，这也就是$\mathbb Q[x]/f(x)$中的多项式！可以确定的一点是，由于$f(x)$是一个$\mathbb Q$不可约中的不可约多项式，$\mathbb Q[x]/f(x)$也就是一个域，并且其元素同$\mathbb Q(\zeta)$的元素是一一对应的，进一步可以检查映射$\kappa$是满足同态关系的，也就是说$\mathbb Q(\zeta)$和$\mathbb Q[x]/f(x)$是同一个域。我们研究Ring/Modular-LWE的时候，本质上是在研究复数中的元素，多项式只是我们看到的外在形式。

扩域中的代数整数

接下来我们考虑的问题中，为了避免问题变得过于复杂，我们限定$\zeta$为代数整数，并分析扩域$\mathbb Q(\zeta)$中的代数整数都是怎样的元素？这里需要注意的是，$\mathbb Q(\zeta)\cong \mathbb Q[x]/f(x)$中的$f(x)$是$\zeta$的最小多项式，是一个整系数多项式。首先由于$\zeta$本身是代数整数，且所有的代数整数构成环，那么所有形如$\sum_{i=0}^{n-1}\mathbb Z\cdot \zeta^i$的数都是代数整数。假设$K=\mathbb Q(\zeta)$中所有的代数整数集合为$R$，由于$\mathbb Q(\zeta)$本身具有加法和乘法封闭性，而所有的代数整数中的元素又在$\mathbb C$中构成环，因此$R$中的数相互做加法和乘法仍然会落在$R$中，$R$也就是$K$的一个子环。我们又可以简单地验证$Z(\zeta)=\sum_{i=0}^{n-1}\mathbb Z\cdot \zeta^i$（注意这里不是域扩张）也是$K$中的一个环，显然有$\mathbb Z(\zeta)\subset R$。

这个包含关系当$\zeta$是$m$次本原根（即$\zeta^m=1$）时可以改写为等号。如果要讲这里的故事，读者需要对环的性质具有充分的了解，我们决定暂时先跳过这一篇章，将它作为日后的谈资，而直奔我们的主题。当$R=\mathbb Z(\zeta)$后，那么，$K$中的代数等式，在先前到模不可约多项式域后，对应也就是那些系数为整数的多项式。到此，我们终于明白，数论变换处理的对象就是那些数域中的代数整数。

中国剩余定理

我们都听过一个很神奇的定理，这个定理来自《孙子算经》中的一个小问题：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”，简而言之就是求一个整数$k$，它满足$k\equiv 3\mod 2, k\equiv 3\mod 5, k\equiv 2\mod 7$。这个问题的答案是多少并不重要，重要的是，任何一个数，都可以分解成这一的形式。我们知道$3,5,7$都可以看作是环$\mathbb Z$的理想，而且，其中任意两个理想都可以生成整个环，例如$(3)+(5)=\mathbb Z$。我们称环$R$的两个理想$I,J$互素，如果$I+J=R$。这个问题实际上是将一个环中的元素写成了它们互素的理想的形式。

例如上文中的题目答案是$23$，首先将$(3)$看作是一个理想，则$23$就应该对应商环$\mathbb Z_3=\mathbb Z/(3)$中的$2+(3)$。而在理想$(5),(7)$对应商环中，则是依次将23表示为$3+(5)\in\mathbb Z_5$和$2+(7)\in\mathbb Z_7$。

上述的过程在环中有一个类似版本，可以将环中的元素分解到一组互素的理想中去。更加精确的说，如果我们找到环$R$中一组两两互数的理想$I_1,\cdots,I_n$且$I=\prod_{i\in[n]}I_i$，那么$R/I$中的元素就可以映射为$\bigoplus_{i\in[n]}(R/I_i)$中的元素。如果$I=R$，那么我们也就可以将$R$中的元素化更最简单的形式。而且这个映射是非常容易做到的，就是商环的自然映射！例如对于$23$来说，环到商环$\mathbb Z_3$的自然映射，就是将$23$映射到$\mathbb Z_3$中$23+(3)$，也就是$\mathbb Z_3$中的2。

分圆域中代数整数环的分解

让我们回到代数整数环的中国剩余定理讨论中来。这里我们将问题进一步简化，我们认定$\zeta=\omega_m^i$，其中$i\in\mathbb Z_m^\times$，由于$\zeta$的最小多项式就是$\Phi_m(x)$，因此$\mathbb Q(\zeta)=\mathbb Q[x]/\Phi_m(x)$。

文中提到的论文

[LN16]: Patrick Longa and Michael Naehrig. Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography. eprint

[LPR12]: Vadim Lyubashevsky and Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors Over Rings. eprint