我们将以一种不同寻常的方式开始本章——NTT 算法其实非常简单，不到 20 行代码就能实现。然而，奇怪的是，使其生效的核心思想并没有一个正式的数学名称。因此，我们将冒昧地为这个我们认为是该算法背后的核心定理起一个（主观上）朗朗上口的名字：
多值函数的像保持定理
为了解释像保持定理，我们将复习最后一个关于单位根的（非常简单的）概念，然后再介绍该定理。
嵌套平方根的 k k k
“k k k a a a a k ≡ 1 a^k\equiv1 a k ≡ 1
a ≡ 1 k a\equiv\sqrt[k]{1} a ≡ k 1
因此，如果 ω \omega ω
1 4 = { 1 , ω , − 1 , − ω } \sqrt[4]{1}=\set{1,\omega,-1,-\omega} 4 1 = { 1 , ω , − 1 , − ω }
现在，如果 ω \omega ω
1 4 = { 1 , ω 2 , ω 4 , ω 6 } \sqrt[4]{1}=\set{1,\omega^2,\omega^4,\omega^6} 4 1 = { 1 , ω 2 , ω 4 , ω 6 }
并且 1 的 8 次根会生成所有的 8 次单位根：
1 8 = { 1 , ω , ω 2 , ω 3 , ω 4 , ω 5 , ω 6 , ω 7 } \sqrt[8]{1}=\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5,\omega^6,\omega^7} 8 1 = { 1 , ω , ω 2 , ω 3 , ω 4 , ω 5 , ω 6 , ω 7 }
这些观察结果仅仅是定义使然。当然，我们并不想直接 计算 1 的平方根。更简单的方法是先找到本原 k k k 1 8 \sqrt[8]{1} 8 1
Copy import galois Fq = 17 k = 8 assert (Fq - 1 ) % k == 0 , "no such subgroup" GF = galois.GF(Fq) pr = GF .primitive_root_of_unity(k) roots = [] for i in range ( 0 ,k): roots.append(pr ** i) print (roots) 我们还可以观察到：
1 4 = 1 \sqrt[4]{1}=\sqrt{\sqrt{1}} 4 1 = 1
1 8 = 1 \sqrt[8]{1}=\sqrt{\sqrt{\sqrt{1}}} 8 1 = 1
1 16 = 1 \sqrt[16]{1}=\sqrt{\sqrt{\sqrt{\sqrt{1}}}} 16 1 = 1
以此类推。正如上面提到的，直接计算 1 k \sqrt[k]{1} k 1
我们可以从 1 开始，通过不断提取平方根来计算 8 次单位根。
对于任意的 k k k
下面是平方根计算的分布推导过程：
1 的平方根是 { 1 , ω k / 2 } \set{1,\omega^{k/2}} { 1 , ω k /2 } ω k / 2 \omega^{k/2} ω k /2
回顾上一章，ω m \omega^m ω m ω m / 2 \omega^{m/2} ω m /2 − ω m / 2 -\omega^{m/2} − ω m /2 m m m
因此，ω k / 2 \omega^{k/2} ω k /2 { ω k / 4 , − ω k / 4 } \set{\omega^{k/4},-\omega^{k/4}} { ω k /4 , − ω k /4 }
还要记住，ω i \omega^i ω i ω i + k / 2 \omega^{i+k/2} ω i + k /2
因此，为了在计算 − ω k / 4 -\omega^{k/4} − ω k /4 ω k / 4 + k / 2 = ω k / 4 + 2 k / 4 = ω 3 k / 4 \omega^{k/4+k/2}=\omega^{k/4+2k/4}=\omega^{3k/4} ω k /4 + k /2 = ω k /4 + 2 k /4 = ω 3 k /4 ω k / 2 \omega^{k/2} ω k /2 { ω k / 4 , ω 3 k / 4 } \set{\omega^{k/4},\omega^{3k/4}} { ω k /4 , ω 3 k /4 }
ω k / 4 \omega^{k/4} ω k /4 ω k / 8 , − ω k / 8 {\omega^{k/8},-\omega^{k/8}} ω k /8 , − ω k /8 ω k / 8 + k / 2 = ω 5 k / 8 \omega^{k/8+k/2}=\omega^{5k/8} ω k /8 + k /2 = ω 5 k /8
至于为什么 ω 3 k / 4 \omega^{3k/4} ω 3 k /4 { ω 3 k / 8 , ω 7 k / 8 } \set{\omega^{3k/8},\omega^{7k/8}} { ω 3 k /8 , ω 7 k /8 }
树的高度是 log 2 n \log_2n log 2 n
通过不断提取 1 的平方根来计算 k k k log 2 ( n ) \log_2(n) log 2 ( n )
概念化树的中间状态
集合
1 \sqrt{\sqrt{\sqrt{1}}} 1
在数学上等价于 8 次单位根。该集合也等价于：
{ 1 , − 1 } \left\{\sqrt{\sqrt{1}},\sqrt{\sqrt{-1}}\right\} { 1 , − 1 }
这也等价于：
{ 1 , − 1 , ω 2 , − ω 2 } \set{\sqrt{1},\sqrt{-1},\sqrt{\omega^2},\sqrt{-\omega^2}} { 1 , − 1 , ω 2 , − ω 2 }
换句话说：
1 = { 1 , − 1 } = { 1 , − 1 , ω 2 , − ω 2 } = { 1 , . . . , ω 7 } \sqrt{\sqrt{\sqrt{1}}}=\left\{\sqrt{\sqrt{1}},\sqrt{\sqrt{-1}}\right\}=\set{\sqrt{1},\sqrt{-1},\sqrt{\omega^2},\sqrt{-\omega^2}}=\set{1,...,\omega^7} 1 = { 1 , − 1 } = { 1 , − 1 , ω 2 , − ω 2 } = { 1 , ... , ω 7 }
快速插曲 —— 多值函数与像
诚然，我们上面所做的观察只是 k k k
函数的像 (Image of a function) —— 如果我们有一组点用于求取函数值，那么求得的结果集合就是像 。例如，如果函数是 f ( x ) = 2 x f(x)=2x f ( x ) = 2 x f f f { 1 , 2 } \set{1,2} { 1 , 2 } { 2 , 4 } \set{2,4} { 2 , 4 } 值域 (range) 一词是指函数可能 输出的值的集合。在我们的语境中，函数的像是指 给定一组输入后实际产生的输出集合。
多值函数 (Multivalued function) —— 对定义域中的单个点可能返回多个求值结果的函数。例如，x \sqrt{x} x x \sqrt{x} x { 1 , − 1 } \set{1, -1} { 1 , − 1 }
注意：多值函数 f ( x ) = x f(x)=\sqrt{x} f ( x ) = x
牢记这些定义，读者应该能够理解以下陈述：
“f ( x ) = x + 1 f(x)=x+1 f ( x ) = x + 1 { 0 , 2 } \set{0,2} { 0 , 2 } { 1 , 3 } \set{1,3} { 1 , 3 }
“多值函数 f ( x ) = x f(x)=\sqrt{x} f ( x ) = x { 1 } \set{1} { 1 } { 1 , − 1 } \set{1,-1} { 1 , − 1 }
现在我们来看一组更有趣的观察结果。
f ( x ) = x f(x)=x f ( x ) = x { 1 , . . . , ω 7 } \set{1,...,\omega^7} { 1 , ... , ω 7 } g ( x ) = x 8 g(x)=\sqrt[8]{x} g ( x ) = 8 x { 1 } \set{1} { 1 } 这一主张只是对上述概念的简单重述，因此我们不再赘述。有趣的部分在于我们如何将此推广到其他函数。
这里的微妙之处在于 g ( x ) g(x) g ( x )
f ( x ) = a x f(x)=ax f ( x ) = a x g ( x ) = a x 4 g(x)=a\sqrt[4]{x} g ( x ) = a 4 x { 1 } \set{1} { 1 } 请记住，1 4 = { 1 , ω , ω 2 , ω 3 } \sqrt[4]{1}=\set{1,\omega,\omega^2,\omega^3} 4 1 = { 1 , ω , ω 2 , ω 3 } a 1 4 = { a , a ω , a ω 2 , a ω 3 } a\sqrt[4]{1}=\set{a,a\omega,a\omega^2,a\omega^3} a 4 1 = { a , aω , a ω 2 , a ω 3 } f f f f ( x ) = a x f(x)=ax f ( x ) = a x
f ( 1 ) = a f(1)=a f ( 1 ) = a f ( ω ) = a ω f(\omega)=a\omega f ( ω ) = aω f ( ω 2 ) = a ω 2 f(\omega^2)=a\omega^2 f ( ω 2 ) = a ω 2 f ( ω 3 ) = a ω 3 f(\omega^3)=a\omega^3 f ( ω 3 ) = a ω 3
读者练习： 设 f ( x ) = a x + c f(x)=ax+c f ( x ) = a x + c f ( x ) f(x) f ( x ) g ( x ) = a x 4 + b g(x)=a\sqrt[4]{x}+b g ( x ) = a 4 x + b { 1 } \set{1} { 1 }
在接下来的章节中，我们将展示如何处理像 f ( x ) = x 2 + x 3 f(x)=x^2+x^3 f ( x ) = x 2 + x 3
f ( x ) = x f(x)=x f ( x ) = x g ( x ) = x g(x)=\sqrt{x} g ( x ) = x { 1 , − 1 } \set{1,-1} { 1 , − 1 } 这个例子与上面的非常相似，只不过我们“瞄准”的定义域不是 { 1 } \set{1} { 1 } { 1 , − 1 } \set{1,-1} { 1 , − 1 }
我们可知：
g ( 1 ) = 1 = { 1 , − 1 } g(1)=\sqrt{1}=\set{1,-1} g ( 1 ) = 1 = { 1 , − 1 } g ( − 1 ) = − 1 = { ω , − ω } g(-1)=\sqrt{-1}=\set{\omega,-\omega} g ( − 1 ) = − 1 = { ω , − ω }
这与对 f f f { 1 , ω , − 1 , − ω } \set{1,\omega,-1,-\omega} { 1 , ω , − 1 , − ω }
综上所述，如果我们将定义域“缩小” r r r f ( x ) f(x) f ( x ) x x x x r \sqrt[r]{x} r x g g g f f f g g g
现在我们将正式定义我们一直在阐述的这个概念：
NTT 的核心定理：多值函数的像保持定理
设 ω \omega ω k k k ⟨ ω ⟩ = { 1 , ω , ω 2 , . . . } \langle\omega\rangle=\set{1,\omega,\omega^2,...} ⟨ ω ⟩ = { 1 , ω , ω 2 , ... } F q \mathbb{F}_q F q k k k
设 k k k
设 f ( x ) f(x) f ( x ) F q \mathbb{F}_q F q r r r k k k
设 g ( x ) g(x) g ( x ) f ( x ) f(x) f ( x ) x x x x r \sqrt[r]{x} r x
设定义域 ⟨ ω ⟩ r \langle\omega\rangle^r ⟨ ω ⟩ r { ω r ∣ ω ∈ ⟨ ω ⟩ } \set{\omega^r|\omega\in \langle\omega\rangle} { ω r ∣ ω ∈ ⟨ ω ⟩ } r = k r=k r = k ⟨ ω ⟩ r = { 1 } \langle\omega\rangle^r=\set{1} ⟨ ω ⟩ r = { 1 }
f f f ⟨ ω ⟩ \langle\omega\rangle ⟨ ω ⟩ g g g ⟨ ω ⟩ r \langle\omega\rangle^r ⟨ ω ⟩ r
读者理解上述定理至关重要，因为它是 Number Theoretic Transform 所依赖的关键概念！
这里有一些例子来巩固这个概念：
f ( x ) = x f(x)=x f ( x ) = x g ( x ) = x g(x)=\sqrt{x} g ( x ) = x f ( x ) = x f(x) =x f ( x ) = x g ( x ) = x g(x)=\sqrt{x} g ( x ) = x f ( x ) = x f(x) =x f ( x ) = x g 1 ( x ) = x g_1(x)=\sqrt{x} g 1 ( x ) = x g 1 ( x ) = x g_1(x)=\sqrt{x} g 1 ( x ) = x g 2 ( x ) = x 4 g_2(x)=\sqrt[4]{x} g 2 ( x ) = 4 x
下一节将展示 f ( x ) f(x) f ( x )
f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b 设 f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b { 1 , ω , ω 2 , ω 3 } \set{1,\omega,\omega^2,\omega^3} { 1 , ω , ω 2 , ω 3 }
设 f 1 f_1 f 1 a x + b a\sqrt{x}+b a x + b { 1 , − 1 } \set{1,-1} { 1 , − 1 } { 1 , − ω 2 } \set{1,-\omega^2} { 1 , − ω 2 }
设 f 2 f_2 f 2 a x 4 + b a\sqrt[4]{x}+b a 4 x + b { 1 } \set{1} { 1 }
f f f f 1 f_1 f 1 f 2 f_2 f 2 { a + b , a ω + b , a ω 2 + b , a ω 3 + b } \set{a+b,a\omega+b,a\omega^2+b,a\omega^3+b} { a + b , aω + b , a ω 2 + b , a ω 3 + b }
与 NTT 的联系
请记住，NTT 的目标是在 O ( n log n ) \mathcal{O}(n\log n) O ( n log n ) k k k f ( x ) f(x) f ( x ) f f f k k k 像 。
你可能已经猜到接下来的方向了。
计算 f ( x ) f(x) f ( x ) k k k g ( x ) g(x) g ( x ) f f f x x x x → x k x\rightarrow\sqrt[k]{x} x → k x { 1 } \set{1} { 1 }
然而，这留下了一个悬而未决的问题：
将 x k \sqrt[k]{x} k x { 1 , . . . , ω k − 1 } \set{1,...,\omega^{k-1}} { 1 , ... , ω k − 1 } 1 k \sqrt[k]{1} k 1 k k k k k k f ( x ) f(x) f ( x ) f ( x ) f(x) f ( x )
在下一章中，我们将展示如何使用平方根展开来计算多值函数，并解释这种方法如何避免冗余计算。
