为了在有限域中执行 FFT 算法（即数论变换，Number Theoretic Transform），需要存在 $k$ 次单位根，使得 $k$ 是 2 的幂。

理想情况下，我们需要一个较大的 2 的幂，以便我们能够进行大多项式的乘法。有几种常用的有限域（几乎所有的都有一个朗朗上口的名字）。本文列出了其中比较常见的一些。

简单定义一下，域的特征（characteristic）是我们用来取模的素数，所以在有限域 $\mathbb{F}_q$ 中，$q$ 就是特征。（如果我们考虑有限域扩展，这个定义会有一些细微差别，但我们现在不想深入探讨。就本文而言，$q$ 是一个素数，也是该有限域的特征）。

正如我们在有限循环群基本定理中所看到的，如果子群的阶能整除群的阶，那么该子群就存在。

因此，如果该域是 FFT 友好的，那么必然存在某个 $k$ 使得 $k|(q-1)$ 且 $k$ 是一个较大的 2 的幂。换句话说，$q-1$ 能被一个较大的 2 的幂整除。

这里的列表并不完整——我们仅收录了截至发布时相对知名的有限域。

FFT 友好的有限域列表

Goldilocks 域

Goldilocks 域的特征为 $q=2^{64}-2^{32}+1$，并具有 $2^{32}$ 次单位根。

以下 Python 代码断言该域中存在一个阶为 $2^{32}$ 的乘法子群。

Copy
q = 2**64 - 2**32 + 1
k = 2**32
assert (q - 1) % k == 0

由于该特征小于 64 位，因此在大多数现代硬件（通常为 64 位）上，其元素可以存储在一个单字（word）中。

然而，将两个 64 位数字相乘会临时需要 128 位，这就要求使用额外的寄存器来进行乘法运算。

这一痛点促使人们开始使用仅需 32 位的更小的域。

Baby Bear 域

Baby Bear 域使用的特征为 $2^{31} - 2^{27} + 1$。它具有 $2^{27}$ 次单位根。

Copy
q = 2**31 - 2**27 + 1
k = 2**27
assert (q - 1) % k == 0

“Baby Bear” 这个名字是对 Goldilocks 童话的戏仿，该故事强调了 Baby Bear（小熊）相较于故事主角（Goldilocks）体型较小的特点。

由于该域可以容纳在 32 位中，一台 64 位计算机可以在一个单字内将两个元素相乘。

Teddy Bear 域

Teddy Bear 域使用的特征为 $2^{32}-2^{30}+1$，并具有 $2^{30}$ 次单位根。

Copy
q = 2**32 - 2**30 + 1
k = 2**30
assert (q - 1) % k == 0

与 Baby Bear 域相比，它同样能容纳在 32 位中，但拥有一个大八倍的乘法子群。

Teddy Bear 域由 Ingonyama 在此论文中提出。

Koala Bear 域

Koala Bear 域是另一个特征 $2^{31} - 2^{24} + 1$ 可容纳在 32 位中的域，并具有 $2^{24}$ 次单位根。

Copy
q = 2**31 - 2**24 + 1
k = 2**24
assert (q - 1) % k == 0

BN-128 域

BN-128 域因其支持椭圆曲线配对而被使用，但它也具有相对较大的乘法子群，其阶为 $2^{28}$。

Copy
# curve_order = 21888242871839275222246405745257275088548364400416034343698204186575808495617
from py_ecc.bn128 import curve_order
k = 2**28
assert (curve_order - 1) % k == 0

STARK 域

Starknet 使用的 Cairo VM 具有一个特征为 $2^{251}+17\cdot2^{192}+1$ 的域，并具有一个非常大的 $2^{192}$ 次单位根。

Copy
q = 2**251 + 17*2**192 + 1
k = 2**192
assert (q - 1) % k == 0

BLS12-381

BLS12-381 是另一个配对友好的椭圆曲线，其曲线阶（curve order）具有 $2^{32}$ 次单位根。

Copy
# curve_order = 52435875175126190479447740508185965837690552500527637822603658699938581184513
from py_ecc.bls12_381 import curve_order
k = 2**32
assert (curve_order - 1) % k == 0

库支持

Plonky3 库 提供了针对 Goldilocks、Baby Bear 和 Koala Bear 的库。