Kyber/Dilithium中的数论变换
数论变换(NTT)是一种用来快速计算多项式环上多项式乘法的方法，Dilithium和Kyber中都使用了NTT。Dilithium中所使用的多项式环形式为。
两个多项式乘积的对应项系数计算方式如下：
对于乘积的每个系数，都需要做最多次系数乘法；总共有个系数，所以乘法操作的复杂度是。使用NTT优化过后的乘法操作复杂度可以降低为。
中国剩余定理 （CRT）
给出个值，，。其中所有 且互素。中国剩余定理是在说这个值可以唯一地确定整数。因此，如果我们在很多小值上进行操作，就和在对应的大值上进行操作等价。在多项式环上也有类似的结论。
拆分多项式
先以环为例，真正Dilithium所用的和要大很多。
这个环中的多项式乘法需要进行次，可以使用CRT来减少系数乘法的次数。模数，需要找到两个满足:
(；以及与是互素的)
可以使用缩减的多项式和，用两个更小的环来表达原环
例如， 时 :
现在可以用这些一阶多项式来有效地做乘法。对两个小环中的两个小多项式做乘法，每个小环只需4次系数乘法，总共8次，是原来的一半。
可以进一步把环分为两个0阶环。
在这些环中存储一个多项式只需要一个整数。
通过把大多项式分为4个小多项式，可以把乘法操作的次数从16降低为4。如果为多项式的阶，那么这个变换使得所有多项式乘法的复杂度从降低到。
总结一下，要对两个多项式和做乘法得到:
将和分别分解为个阶为0的多项式 对于 ，使用逐点乘积计算 使用中国剩余定理将组合回
拆分Dilithium所用环
Dilithium中所用的环为：
首先要找到两个多项式使得：
由上述推导可知 为第四个本原单位根。我们继续往下拆分，考察这一项：
类似的对于这一项进行拆分可以得到
这里就出现了一个模式：如果在某个多项式中有值的话，在下一层就会以值 和 结束。
记 为第 个本原单位根：
我们可以看到，在第一层：。
在第二层：
换句话说，在第二层我们把多项式分解为：
再经过一层拆分后得到：
记.
不断的分拆多项式直到阶为0的不可约多项式形式，得到：
前向变换
要对一个多项式进行变换，首先拆分成两个多项式 和
首先观察：取的所有高位系数 然后模约简之。因为， 可得 所以为了去掉高位系数，我们用 乘之并且添加到小128位的相应系数上面。结果为：
观察 ：在这种情况下约减多项式有一个正的 项。故在此情况下 。为了模这个多项式进行约减，需要乘上 :
我们可以并行应用这两个公式。对于每个系数，我们只需要与相乘一次，然后分别进行加法和减法，就一口气完成了这两种约减。现在我们拥有两个相邻的多项式，左边的多项式等于 ，右边的为 。上述这个操作被称为“蝴蝶操作”。
接下来就如同上一节所述继续向下约减。继续在左多项式的每一个系数上应用“蝴蝶操作” ，乘以因子。对于右多项式 进行同样的操作, 但因子为 。不断地拆分这些多项式，直到只剩下0阶多项式。
逆变换
正向变换中第一层的一次蝴蝶操作计算如下：
在逆变换中，是要从 和 开始，需要得到。
在完成变换后，我们就可以以“逐点”的方式在多项式上进行所有操作，而且复杂度都为 。为了转化多项式，我们是在 层的树上递归下降, 每一层进行次乘以某个的乘法。于是变换的总复杂度为。