译自 halo2 book：background/fields.md

域(field)

许多密码学协议的一个基础组成部分，是被称为 域(field) 的代数结构。域是一些对象（通常是数）的集合，配备两个相关联的二元运算符 $+$ 和 $\times$，使得各种 域公理(field axioms) 成立。实数 $\mathbb{R}$ 就是一个具有不可数多个元素的域的例子。

Halo 使用 有限域(finite field)，它只有有限个元素。有限域可以完全分类如下：

• 如果 $\mathbb{F}$ 是一个有限域，那么对某个整数 $k\ge 1$ 和某个素数 $p$，它包含 $|\mathbb{F}|=p^k$ 个元素；
• 任意两个具有相同元素个数的有限域是同构的。特别地，素域(prime field) ${\mathbb{F}}_p$ 中的所有算术运算，都与整数模 $p$ 的加法和乘法同构，即与 ${\mathbb{Z}}_p$ 中的运算同构。这就是我们常把 $p$ 称为 模(modulus) 的原因。

我们将域写作 ${\mathbb{F}}_q$，其中 $q=p^k$。素数 $p$ 称为它的 特征(characteristic)。在 $k>1$ 的情形下，域 ${\mathbb{F}}_q$ 是域 ${\mathbb{F}}_p$ 的 $k$ 次扩张(extension)。（作个类比，复数 $\mathbb{C}=\mathbb{R}(i)$ 是实数的扩张。）然而在 Halo 中我们不使用扩域(extension field)。每当我们写 ${\mathbb{F}}_p$ 时，指的都是我们所说的 素域(prime field)，它有素数 $p$ 个元素，即 $k=1$。

重要说明：

• 任何域中都有两个特殊元素：$0$，即加法单位元(additive identity)；以及 $1$，即乘法单位元(multiplicative identity)。
• 当域元素以二进制整数形式表示时，其最低有效位(least significant bit)可以被解释为它的"符号(sign)"，以帮助把它与其加法逆元(negation)区分开。这是因为对于某个最低有效位为 $0$ 的非零元素 $a$，我们有 $-a=p-a$ 的最低有效位为 $1$，反之亦然。我们也可以用一个元素是否大于 $(p-1)/2$ 来赋予它一个"符号"。

有限域稍后将用于构造 多项式(polynomial) 和 椭圆曲线(elliptic curve)。椭圆曲线是群(group)的例子，我们接下来讨论群。

群(group)

群比域更简单也更受限；它们只有一个二元运算符 $\cdot$，公理也更少。它们也有一个单位元，我们记作 $1$。

群中任意非零元素 $a$ 都有一个 逆元(inverse) $b=a^{-1}$，它是 唯一 满足 $a\cdot b=1$ 的元素 $b$。

例如，${\mathbb{F}}_p$ 的非零元素的集合构成一个群，其中群运算由域上的乘法给出。

（旁注）加法记法 vs 乘法记法

如果像我们上面那样把 $\cdot$ 写成 $\times$ 或者省略（即把 $a\cdot b$ 写作 $ab$），把单位元写作 $1$，把求逆写作 $a^{-1}$，那么我们说这个群是"用乘法记法书写的"。如果把 $\cdot$ 写成 $+$，把单位元写作 $0$ 或 $\mathcal{O}$，把求逆写作 $-a$，那么我们说它是"用加法记法书写的"。

习惯上，椭圆曲线群用加法记法，而当元素来自有限域时用乘法记法。

使用加法记法时，对于非负的 $k$，我们还写

$$[k]A=\underset{k\text{ times}}{\underbrace{A+A+\cdots +A}}$$

并称之为"标量乘法(scalar multiplication)"；我们也常用大写字母作为表示群元素的变量。使用乘法记法时，我们还写

$$a^k=\underset{k\text{ times}}{\underbrace{a\times a\times \cdots \times a}}$$

并称之为"幂运算(exponentiation)"。无论哪种情形，我们把满足 $[k]g=a$ 或 $g^k=a$ 的标量 $k$ 称为 $a$ 以 $g$ 为底的"离散对数(discrete logarithm)"。我们可以通过求逆把标量扩展到负整数，即 $[-k]A+[k]A=\mathcal{O}$ 或 $a^{-k}\times a^k=1$。

有限群的元素 $a$ 的 阶(order) 定义为使得 $a^k=1$（乘法记法）或 $[k]a=\mathcal{O}$（加法记法）成立的最小正整数 $k$。群的阶 是群中元素的个数。

群总有一个 生成集(generating set)，即这样一个元素集合：我们能（用乘法术语来说）把群中任意元素表示为这些元素的幂的乘积。所以若生成集是 $g_{\mathrm{1..}k}$，我们就能把群中任意元素表示为 $\prod _{i=1}^k{g}_i^{a_i}$。对于给定的群，可以有许多不同的生成集。

如果一个群有一个仅含单个元素（记为 $g$）的（不一定唯一的）生成集，则称它为 循环群(cyclic)。在这种情形下，我们可以说 $g$ 生成该群，并且 $g$ 的阶就是该群的阶。

任意 $n$ 阶有限循环群 $\mathbb{G}$ 都 同构(isomorphic) 于整数模 $n$（记作 $\mathbb{Z}/n\mathbb{Z}$），使得：

• $\mathbb{G}$ 中的运算 $\cdot$ 对应于模 $n$ 加法；
• $\mathbb{G}$ 中的单位元对应于 $0$；
• 某个生成元 $g\in \mathbb{G}$ 对应于 $1$。

给定一个生成元 $g$，这个同构在 $\mathbb{Z}/n\mathbb{Z}\to \mathbb{G}$ 方向上总是易于计算的；它就是 $a\mapsto g^a$（或在加法记法下，$a\mapsto [a]g$）。但在 $\mathbb{G}\to \mathbb{Z}/n\mathbb{Z}$ 方向上一般可能很难计算；当我们讲到 椭圆曲线(elliptic curve) 时会进一步讨论这一点。

如果有限群的阶 $n$ 是素数，那么这个群是循环群，并且每个非单位元都是生成元。

有限域的乘法群(multiplicative group)

我们用记号 ${\mathbb{F}}_p^{\times }$ 表示集合 ${\mathbb{F}}_p-\{0\}$ 上的乘法群（即群运算是 ${\mathbb{F}}_p$ 中的乘法）。

在 ${\mathbb{F}}_p^{\times }$ 中求逆的一个快捷方式是 $a^{-1}=a^{p-2}$。其原因源自 费马小定理(Fermat's little theorem)，该定理指出对任意整数 $a$ 都有 $a^p=a(\mathrm{mod}p)$。如果 $a$ 非零，我们可以把它除两次 $a$，得到 $a^{p-2}=a^{-1}.$

设 $\alpha$ 是 ${\mathbb{F}}_p^{\times }$ 的一个生成元，那么它的阶为 $p-1$（等于 ${\mathbb{F}}_p^{\times }$ 中元素的个数）。因此，对任意元素 $a\in {\mathbb{F}}_p^{\times }$，都存在唯一的整数 $i\in \{\mathrm{0..}p-2\}$ 使得 $a={\alpha }^i$。

注意 $a\times b$（其中 $a,b\in {\mathbb{F}}_p^{\times }$）实际上可以被解释为 ${\alpha }^i\times {\alpha }^j$，其中 $a={\alpha }^i$ 且 $b={\alpha }^j$。事实上，对所有 $0\le i,j<p-1$ 都有 ${\alpha }^i\times {\alpha }^j={\alpha }^{i+j}$ 成立。因此，非零域元素的乘法可以被解释为相对于某个固定生成元 $\alpha$ 的模 $p-1$ 加法。加法只是发生"在指数上"。

这也是看待计算域中逆元为何用 $a^{p-2}$ 的另一种角度：

$$p-2\equiv -1(\mathrm{mod}p-1),$$

所以 $a^{p-2}=a^{-1}$。

蒙哥马利技巧(Montgomery's Trick)

蒙哥马利技巧（以 Peter Montgomery（安息）命名）是一种同时计算多个群逆元的方法。它常用于计算 ${\mathbb{F}}_p^{\times }$ 中的逆元，相对于乘法而言，这些逆元的计算开销相当大。

设想我们需要计算三个非零元素 $a,b,c\in {\mathbb{F}}_p^{\times }$ 的逆元。我们改为先计算乘积 $x=ab$ 和 $y=xc=abc$，然后计算逆元

$$z=y^{p-2}=\frac{1}{abc}.$$

现在我们可以把 $z$ 乘以 $x$ 得到 $\frac{1}{c}$，把 $z$ 乘以 $c$ 得到 $\frac{1}{ab}$，随后再把它乘以 $a,b$ 就能得到它们各自的逆元。

这个技巧可以推广到任意数量的群元素，而只需要做一次求逆。

乘法子群(multiplicative subgroups)

群 $G$（运算为 $\cdot$）的一个 子群(subgroup)，是 $G$ 中这样一个元素子集：它在 $\cdot$ 下也构成一个群。

在上一节中我们说过 $\alpha$ 是 $(p-1)$ 阶乘法群 ${\mathbb{F}}_p^{\times }$ 的一个生成元。这个群的阶是 合数(composite)，因此由中国剩余定理¹，它有真子群(strict subgroups)。举例来说，设想 $p=11$，于是 $p-1$ 分解为 $5\cdot 2$。这样就存在一个 $5$ 阶子群的生成元 $\beta$ 和一个 $2$ 阶子群的生成元 $\gamma$。因此 ${\mathbb{F}}_p^{\times }$ 中的所有元素都可以唯一地写成 ${\beta }^i\cdot {\gamma }^j$，其中 $i$（模 $5$）、$j$（模 $2$）。

如果我们有 $a={\beta }^i\cdot {\gamma }^j$，注意当我们计算

$$a^5=({\beta }^i\cdot {\gamma }^j{)}^5={\beta }^{i\cdot 5}\cdot {\gamma }^{j\cdot 5}={\beta }^0\cdot {\gamma }^{j\cdot 5}={\gamma }^{j\cdot 5};$$

时会发生什么；我们实际上"杀死"了 $5$ 阶子群分量，产生了一个 $2$ 阶子群中的值。

拉格朗日定理（群论）(Lagrange's theorem (group theory)) 指出，有限群 $G$ 的任意子群 $H$ 的阶整除 $G$ 的阶。因此，${\mathbb{F}}_p^{\times }$ 任意子群的阶必定整除 $p-1.$

像 Halo 2 这样基于 PLONK 的证明系统，更便于在具有大量乘法子群且其分布"光滑(smooth)"的域上使用（这使得随着电路规模增大，性能悬崖更小、更细粒度）。Pallas 和 Vesta 曲线特别地具有如下形式的素数

$$T\cdot 2^S=p-1$$

其中 $S=32$ 且 $T$ 为奇数（即 $p-1$ 有 32 个低位零比特）。这意味着对所有 $k\le 32$，它们都有 $2^k$ 阶的乘法子群。这些 2-adic 子群非常适合 高效的 FFT，同时也支持种类繁多的电路规模。

平方根(square roots)

在域 ${\mathbb{F}}_p$ 中，恰好一半的非零元素是平方数(squares)；其余的是非平方数，或称"二次非剩余(quadratic non-residues)"。为了理解原因，考虑一个生成 ${\mathbb{F}}_p^{\times }$ 的 $2$ 阶乘法子群的 $\alpha$（之所以存在，是因为 $p$ 是大于 $2$ 的素数，所以 $p-1$ 能被 $2$ 整除），以及一个生成 ${\mathbb{F}}_p^{\times }$ 的 $t$ 阶乘法子群的 $\beta$，其中 $p-1=2t$。那么每个元素 $a\in {\mathbb{F}}_p^{\times }$ 都可以唯一地写成 ${\alpha }^i\cdot {\beta }^j$，其中 $i\in {\mathbb{Z}}_2$ 且 $j\in {\mathbb{Z}}_t$。所有元素中有一半满足 $i=0$，另一半满足 $i=1$。

让我们考虑 $p\equiv 3(\mathrm{mod}4)$ 的简单情形，此时 $t$ 为奇数（如果 $t$ 为偶数，那么 $p-1$ 就能被 $4$ 整除，这与 $p$ 为 $3(\mathrm{mod}4)$ 矛盾）。如果 $a\in {\mathbb{F}}_p^{\times }$ 是平方数，那么必定存在 $b={\alpha }^i\cdot {\beta }^j$ 使得 $b^2=a$。但这意味着

$$a=({\alpha }^i\cdot {\beta }^j{)}^2={\alpha }^{2i}\cdot {\beta }^{2j}={\beta }^{2j}.$$

换言之，在这个特定的域中所有平方数都不生成 $2$ 阶乘法子群，于是由于一半的元素生成 $2$ 阶子群，那么至多一半的元素是平方数。事实上恰好一半的元素是平方数（因为把每个非平方元素平方都给出一个唯一的平方数）。这意味着我们可以假定所有平方数都可以写成 ${\beta }^m$（对某个 $m$），因此求平方根的问题就归结为做 $2^{-1}(\mathrm{mod}t)$ 的幂运算。

在 $p\equiv 1(\mathrm{mod}4)$ 的情形下，事情变得更复杂，因为 $2^{-1}(\mathrm{mod}t)$ 不存在。我们把 $p-1$ 写成 $2^k\cdot t$，其中 $t$ 为奇数。$k=0$ 的情形不可能，$k=1$ 的情形就是我们已经描述过的，所以考虑 $k\ge 2$。$\alpha$ 生成一个 $2^k$ 阶乘法子群，$\beta$ 生成奇数阶 $t$ 阶乘法子群。那么每个元素 $a\in {\mathbb{F}}_p^{\times }$ 都可以写成 ${\alpha }^i\cdot {\beta }^j$，其中 $i\in {\mathbb{Z}}_{2^k}$ 且 $j\in {\mathbb{Z}}_t$。如果该元素是平方数，那么存在某个 $b=\sqrt{a}$，它可以写成 $b={\alpha }^{i^{\prime }}\cdot {\beta }^{j^{\prime }}$，其中 $i^{\prime }\in {\mathbb{Z}}_{2^k}$ 且 $j^{\prime }\in {\mathbb{Z}}_t$。这意味着 $a=b^2={\alpha }^{2i^{\prime }}\cdot {\beta }^{2j^{\prime }}$，因此我们有 $i\equiv 2i^{\prime }(\mathrm{mod}{2}^k)$，且 $j\equiv 2j^{\prime }(\mathrm{mod}t)$。在这种情形下 $i$ 必须为偶数，否则就不可能对任何 $i^{\prime }$ 都有 $i\equiv 2i^{\prime }(\mathrm{mod}{2}^k)$。在 $a$ 不是平方数的情形下，$i$ 为奇数，所以一半的元素是平方数。

为了计算平方根，我们可以先把元素 $a={\alpha }^i\cdot {\beta }^j$ 升到 $t$ 次幂以"杀死" $t$ 阶分量，得到

$$a^t={\alpha }^{it(\mathrm{mod}{2}^k)}\cdot {\beta }^{jt(\mathrm{mod}t)}={\alpha }^{it(\mathrm{mod}{2}^k)}$$

然后把这个结果升到 $t^{-1}(\mathrm{mod}{2}^k)$ 次幂，以撤销原来的幂运算对 $2^k$ 阶分量的影响：

$$({\alpha }^{it\mathrm{mod}{2}^k}{)}^{t^{-1}(\mathrm{mod}{2}^k)}={\alpha }^i$$

（因为 $t$ 与 $2^k$ 互素）。这就裸露出 ${\alpha }^i$ 值，我们可以平凡地处理它。我们可以类似地杀死 $2^k$ 阶分量以得到 ${\beta }^{j\cdot 2^{-1}(\mathrm{mod}t)}$，再把这些值组合起来得到平方根。

事实证明，在 $k=2,3$ 的情形下，有更简单的算法把其中几个幂运算合并在一起以提高效率。对于其他的 $k$ 值，已知唯一的方法是通过反复平方来手动提取 $i$，直到对 $i$ 的每一位都得到单位元为止。这就是 Tonelli-Shanks 平方根算法(Tonelli-Shanks square root algorithm) 的精髓，描述了通用策略。（还有另一种使用二次扩域的平方根算法，但直到素数变得相当大之前，它在效率上都不划算。）

单位根(roots of unity)

在前面几节中，我们把 $p-1$ 写成 $2^k\cdot t$，其中 $t$ 为奇数，并说明了元素 $\alpha \in {\mathbb{F}}_p^{\times }$ 生成了 $2^k$ 阶子群。为方便起见，记 $n:=2^k.$ 元素 $\{1,\alpha ,\dots ,{\alpha }^{n-1}\}$ 被称为 $n$ 次 单位根(roots of unity)。

本原单位根(primitive root of unity) $\omega ,$ 是这样一个 $n$ 次单位根：除非 $i\equiv 0(\mathrm{mod}n)$，否则 ${\omega }^i\ne 1$。

重要说明：

• 如果 $\alpha$ 是 $n$ 次单位根，$\alpha$ 满足 ${\alpha }^n-1=0.$ 如果 $\alpha \ne 1,$ 那么 $$1+\alpha +{\alpha }^2+\cdots +{\alpha }^{n-1}=0.$$

• 等价地，单位根是方程 $$X^n-1=(X-1)(X-\alpha )(X-{\alpha }^2)\cdots (X-{\alpha }^{n-1}).$$ 的解。

• $\boxed{{\omega }^{\frac{n}{2}+i}=-{\omega }^i}$（"取负引理(Negation lemma)"）。证明： $$\begin{array}{rl}{\omega }^n=1& ⟹{\omega }^n-1=0\\ & ⟹({\omega }^{n/2}+1)({\omega }^{n/2}-1)=0.\end{array}$$ 由于 $\omega$ 的阶是 $n$，${\omega }^{n/2}\ne 1.$ 因此，${\omega }^{n/2}=-1.$

• $\boxed{({\omega }^{\frac{n}{2}+i}{)}^2=({\omega }^i{)}^2}$（"减半引理(Halving lemma)"）。证明： $$({\omega }^{\frac{n}{2}+i}{)}^2={\omega }^{n+2i}={\omega }^n\cdot {\omega }^{2i}={\omega }^{2i}=({\omega }^i{)}^2.$$ 换言之，如果我们把 $n$ 次单位根中每个元素都平方，我们只会得到一半的元素，$\{({\omega }_n^i{)}^2\}=\{{\omega }_{n/2}\}$（即 $\frac{n}{2}$ 次单位根）。元素与其平方之间是二对一的映射。

参考文献

1. Friedman, R. (n.d.) "Cyclic Groups and Elementary Number Theory II" (p. 5). ↩