Circle STARKs 是一种新型 zk-STARK 方案，已在 Stwo 和 Plonky3 中实现，并被多个 zkVM 项目所采用。其关键创新点在于能够使用小型的 32 位域（Mersenne 素数 $2^{31}-1$），同时仍然保持高效 FFT 操作所需的数学属性。在这个解释性系列文章中，我们将讨论 Circle STARK 背后的主要算法，即 Circle FFT。

在第 1 部分文章中，我们首先回顾 STARK 友好素数的演变过程，然后通过详细的示例和推导，探索 Circle FFT 的基础概念——即 Circle 曲线、其群结构以及孪生陪集 (twin-cosets) 和标准位置陪集 (standard-position cosets) 的作用。随后，在第 2 部分文章中，我们将详细描述 Circle FFT 算法本身。

我们还结合 Python 脚本提供了对这些核心概念（例如 Circle 群和 Circle FFT）的详细演练，以及针对 $p=31$（指数为 $5$ 的 Mersenne 素数：$2^5 -1$）的明确计算示例。

我们的重点是：即使在 $p-1$ 没有较大的 2-adic 因子的情况下，这些构建模块中的每一个是如何引导出一个完整的类似 FFT 的例程的。

如果您有兴趣自己运行这些示例，完整的 Python 代码可以在这里找到，我们将在后面的部分（如第 4 节和第 6 节）引用它，在这些部分我们将通过代码演练群和域的构建。

本文由 Yugo 与 RareSkills 合作编写。本文由 Soulforge Grant 提供资金支持。我们对他们的支持表示感谢。

0. 从 STARK 友好素数到 Mersenne 31

在深入探讨 STARK 友好素数之前，让我们先回顾一下有限域的基础知识。

域是一个定义了加法、减法、乘法和除法（除数不为零）的集合。当集合的元素是有限的时候，它被称为有限域。$\mathbb{F}_p$ 指的是从 $0$ 到 $p-1$（其中 $p$ 是一个素数）的整数集合，其加法、减法和乘法均在模 $p$ 下进行，除法被定义为模 $p$ 乘法的逆元。

我们用 $\mathbb{F}_p^*$ 表示集合 $\mathbb{F}_p \setminus \{0\}$。$\mathbb{F}_p^*$ 中的每个元素都有一个乘法逆元，因此可以将 $\mathbb{F}_p^*$ 视为一个乘法群。这个群的大小 $|\mathbb{F}_p^*|$ 为 $p-1$。当我们将 $p-1$ 分解为其素因数时，众所周知，如果一个素数 $q$ 出现了 $r$ 次，那么必定存在一个大小为 $q^r$ 的循环子群。

你可以用一个小素数（例如 $p=7$）来简略说明这一点。由于 $p-1=6$ 可分解为 $2\times 3$，因此必定存在大小为 $2$ 和 $3$ 的子群。实际上，在 $\mathbb{F}_7^* = \{1,2,3,4,5,6\}$ 中，元素 $6$ 生成了一个大小为 $2$ 的子群 $\{1,6\}$，元素 $2$ 生成了一个大小为 $3$ 的子群 $\{1,2,4\}$。

在许多 STARK 协议中，数论变换 (NTT) 或快速傅里叶变换 (FFT) 依赖于这样一个子群：其因子是 2 的幂次，从而使该子群的大小为 $2^r$。使得 $2^r$ 能整除 $(p-1)$ 的最大整数 $r$ 被称为 two-adicity。较高的 two-adicity 允许为 FFT/NTT 域设置更大的 2 的幂次大小，这是实现快速多项式求值、插值和多项式乘法的关键。此外，高效实现基于 NTT 的这些操作严重依赖于快速的模乘运算——因为 FFT/NTT 涉及重复地将元素相乘并对 $p$ 取模。

最初，STARKs 使用的素数是 $p = 2^{251} + 17 \cdot 2^{192} + 1$，其 two-adicity 为 $192$。在现代 STARK 实现中，为了通过减小有限域的规模来降低开销，进行了一项改进。例如，Goldilocks 域为 $p = 2^{64} - 2^{32} + 1$，其 two-adicity 为 $32$。至关重要的是，因为 $2^{64} \equiv 2^{32} - 1 \pmod{p}$，两个 64 位数字的乘积可以在基数 $2^{32}$ 下进行拆分，并只需几次加法和减法即可完成归约。

那么 Circle STARKs 呢？如 Circle STARKs 论文 中提出的，它使用了一个 Mersenne 素数，

Mersenne 素数是形式为 $2^n -1$ 的素数，其中 $n$ 为某个整数。在这里，$n=31$ 得到了 $2^{31}-1$，它恰好是素数，因此被归类为 Mersenne 素数。

选择 $2^{31}-1$ 的一个主要原因是它刚好能放入一个 32 位的机器字中，使得模乘运算极其快速。具体来说，当两个 32 位数字相乘时，结果是一个 64 位的值，而对 $2^{31}-1$ 进行模归约只需进行两次加法即可完成。

借助向量化指令，此操作的速度还能大幅提升。现代 CPU 擅长原生处理 32 位整数，而 Mersenne 31 ($2^{31}-1$) 正好契合这种架构，从而允许最佳地利用硬件能力。正如 Eli Ben-Sasson 在 Why I’m Excited By Circle Stark And Stwo 中所讨论的，与原始 STARK 中使用的 256 位素数相比，Mersenne 31 的模乘速度大约快 125 倍，并且比 Baby Bear ($2^{31} - 2^{27} + 1$) 快 1.3 倍。

然而，传统的 FFT 或 NTT 方法要求在 $p-1$ 中存在一个较大的 2-adic 因子，以便在 $\mathbb{F}_p^*$ 中形成足够大的 2 的幂次子群。但在本例中，$|\mathbb{F}_p^*| = p - 1 \;=\; 2^{31} - 2$，其 two-adicity 仅为 1。因此，我们不能直接使用乘法下的较大 2 的幂次子群。

Circle STARK 仍然采用了 Mersenne 素数域 $p = 2^{31} - 1$。然而，我们不再直接在 $\mathbb{F}_p$ 内部操作，而是观察到曲线

这非常关键，因为 $p+1$ 可以包含一个很大的 2 的幂次，从而创建出大小为 $2^n$ 的子群。因此，Circle STARK 没有在 $\mathbb{F}_p$ 中处理单个元素，而是考虑满足 $x^2 + y^2 = 1$ 的坐标对 $(x,y)\in \mathbb{F}_p^2$（即 Circle 曲线上的点）。
通过这种方式，Circle STARK 可以直接在这些 Circle 元素上实现自己专属的快速多项式插值和求值——这通常被称为 Circle FFT。

1. Circle 曲线

让我们进入 Circle STARKs 的核心数学。有限域 $\mathbb{F}_p$ 上的 Circle 曲线是 $\mathbb{F}_p^2$ 的一个子集，由所有满足下式的点 $(x,y)$ 定义：

在 Circle STARKs 中，我们重点关注满足 $p \equiv 3 \pmod{4}$（例如 $p=3,7,11,\dots$）的素数 $p$。在这个条件下，$-1$ 在 $\mathbb{F}_p$ 中不是一个平方数。具体而言，这确保了方程 $x^2 + y^2 = 1$ 在 $\mathbb{F}_p^2$ 中恰好有 $p+1$ 个解，并且没有额外的异常解（即无穷远点）。对于本文来说，我们只需知道在该条件下，$\mathbb{F}_p^2$ 中的 $x^2 + y^2 = 1$ 恰好能给出 $p+1$ 个点。

（不过，对于有兴趣从几何角度理解为何 $p \equiv 3 \pmod{4}$ 会恰好得出 $p + 1$ 个解的读者，请参阅附录。）

1.1 简单示例 $p=7\equiv 3 \pmod{4}$

例如，如果 $p =7$（即 $3 \pmod{4}$），那么 $C(\mathbb{F}_{7})$ 就是所有满足 $x^2 + y^2 = 1$ 的 $(x,y) \in \mathbb{F}_{7}^2$ 构成的集合。

以下是 $\mathbb{F}_{7}^2$ 中满足 $x^2 + y^2 \equiv 1 \pmod{7}$ 的几个 $(x,y)$ 数对示例：

• $(1, 0)$ 和 $(0, 1)$ 是显而易见的，因为 $1^2 + 0^2=1$ 且 $0^2 + 1^2=1$。
• $(5,2)$ 也成立，因为 $5^2 + 2^2 = 25 + 4 = 29$，而 $29 \bmod 7 = 1$。

我们可以看到，对于 $p=7$，恰好有 $8$（即 $p+1$）个这样的数对。

2. Circle 群

这类集合记为 $C(\mathbb{F}_p)$，并且通常被称为 $\mathbb{F}_p$ 上的 Circle 曲线。一个惊人的事实是 $|C(\mathbb{F}_p)| = p + 1$。例如，如果 $p = 7$，那么圆上恰好有 $7 + 1 = 8$ 个点——值得注意的是 $8 = 2^3$。

这很重要，因为在通常的 STARK 设定中，我们经常需要一个大小为 $2^n$ 的域来进行类似于 FFT 的操作。在 $p = 7$ 的情况下，圆上恰好有 8 个点，这意味着我们可以形成大小为 $2^n$ 的子群。稍后，我们将看到 Circle FFT 是如何利用这一属性（即 $p+1$ 中的高 2-adicity）的。

一个关键的属性是，$C(\mathbb{F}_p)$ 可以在其点上赋予一个群运算（本质上是一个二元运算符）。具体来说，我们使用“$\cdot$”来表示这种运算：对于 $C(\mathbb{F}_p)$ 中的两点 $(x_0,y_0)$ 和 $(x_1,y_1)$，

我们可以验证这种群运算仍然保持在 $C(\mathbb{F}_p)$ 内（结果仍然满足 $x^2 + y^2=1$），并使该集合成为一个大小为 $p+1$ 的循环群。

2.1 检验群公理

作为群的公理，我们通常列出以下四个属性：封闭性、单位元、逆元和结合律。让我们仔细看看每一个以确认它们都成立。

2.1.1 封闭性

取圆上的两点 $(x_0, y_0)$ 和 $(x_1, y_1)$；

定义一个新点

我们将通过逐步计算 $(\hat{x}^2 + \hat{y}^2)$ 来证明 $(\hat{x}, \hat{y})$ 也位于圆上：

因为我们已知 $x_0^2 + y_0^2 = 1$ 且 $x_1^2 + y_1^2 = 1$，我们将这些值代入乘积中：

因此 $(\hat{x}, \hat{y})$ 也满足 $(\hat{x}^2 + \hat{y}^2 = 1)$，并因此位于圆上。这证实了集合在如下运算下是封闭的：

2.1.2 单位元

在群运算中，点 $(1,0)$ 充当单位元。具体而言，对于圆上的任何点 $(x,y)$，

有人可能会对点 $(0,1)$ 感到好奇。如果我们试图使用 $(0,1)$ 作为单位元，我们会发现它不成立：

2.1.3 逆元

在一个群中，元素 $(x,y)$ 的逆元是满足下式的唯一解 $(x',y')$：

2.1.4 结合律

最后一个群公理是结合律：对于圆上的任意三点

$(x_0,y_0), (x_1,y_1), (x_2,y_2)$，

这可以通过展开多项式来验证，但由于过程太长，我们不在这里详细讨论。

2.2 一个特殊运算：平方映射 $\pi$

除了这些群公理之外，圆上还有另一个运算，它在后续章节中非常有用，特别是在 Circle FFT 中，即平方映射。该映射将群运算应用于点与其自身：

由于圆满足 $x^2 + y^2 = 1$，我们得到 $x^2 - y^2 = 2x^2 - 1$，因此

在 Circle FFT 中，我们将使用 $\pi$ 以递归的方式将某些求值域减半——每次应用 $\pi$ 都会使域的大小缩小两倍。这是因为 $\pi$ 与群运算是兼容的。具体来说，对于圆上的两点 $P$ 和 $Q$，

这种兼容性意味着 $\pi$ 可以将大小为 $2^n$ 的孪生陪集映射成另一个大小为 $2^{n-1}$ 的孪生陪集。稍后我们将详细讨论这一域减半特性。

2.3 一个特殊运算：对合映射 $J$

除了平方映射之外，还有另一个重要的运算。该运算被称为对合映射 (involution)，定义为

在圆 $x^2 + y^2 = 1$ 上，对合映射 $J(x,y)$ 能够将曲线上的每一个点保持在曲线上（因为取 $y$ 的负值并不影响 $x^2 + y^2$）。然而，$y=0$ 的点在 $J$ 的作用下是固定的，这意味着 $J(x,\,0) = (x,\,0)$。

2.4 $p=31$ 时的 Circle 群具体操作

在之前的具体示例中，我们探讨了 $p = 7$ 时的 $C(\mathbb{F}_p)$，这作为一个有用的简单示例，帮助我们建立直觉。然而，$p = 7$ 太小了，不足以揭示 Circle 群的深层结构特性——例如更长的子群链，或孪生陪集及标准位置陪集的构建。

因此，我们现在转向稍大一些的素数 $p = 31$（其满足 $p = 2^5 - 1$），以便以更有意义的方式展示这些更丰富的行为。

给定符合 $3 \pmod{4}$ 的 $p = 31$，满足方程 $x^2 + y^2 = 1$ 的 $\mathbb{F}_{31}^2$ 中的点集 $(x, y)$ 记作 $C(\mathbb{F}_{31})$，如下图所示：

以下是 $\mathbb{F}_{31}^2$ 中满足 $x^2 + y^2 \equiv 1 \pmod{31}$ 的几个坐标对示例 $(x,y)$：

• $(5,10)$ 也成立，因为 $5^2 + 10^2 = 25 + 100 = 125$，并且 $125 \bmod 31 = 125 - 4\cdot31 = 1$。
• $(7,13)$ 同样是一个解：$7^2 = 49 \equiv 18$ (mod 31) 且 $13^2 = 169 \equiv 14$ (mod 31)，因此 $18 + 14 = 32 \equiv 1$ (mod 31)。
• $(30,0)$ 说明 $30 \equiv -1 \pmod{31}$，因此 $(-1)^2 + 0^2 \equiv 1$ (mod 31)。

为了了解 Circle 群，让我们在 $\mathbb{F}_{31}$ 上进行运算，此时圆 $C(\mathbb{F}_{31})$ 具有 32 个点。假设我们取点

因此 $(18,\,24)$ 也落在圆 $x^2 + y^2 = 1$ 上。
同时，$Q$ 的逆元是

因为

此外，平方映射可以作用于点 $Q=(13,7)$。回想一下

3. Circle 群的子群

我们已经确定 $C(\mathbb{F}_p)$ 是一个大小为 $p+1$ 的循环群。如果 $p + 1$ 是 2 的幂次，假设 $p+1 = 2^m$，那么就存在一条嵌套的子群链

例如，如果 $p = 31$（此时 $p+1 = 32 = 2^5$），我们得到一条链

在下方，我们明确列出了 $C(\mathbb{F}_{31})$ 中的每一个子群。

Copy
Size 1:  [Point(1, 0)]
Size 2:  [Point(1, 0), Point(30, 0)]
Size 4:  [Point(1, 0), Point(0, 30), Point(30, 0), Point(0, 1)]
Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]
Size 16:  [Point(1, 0), Point(7, 13), Point(4, 27), Point(18, 24), Point(0, 30), Point(13, 24), Point(27, 27), Point(24, 13), Point(30, 0), Point(24, 18), Point(27, 4), Point(13, 7), Point(0, 1), Point(18, 7), Point(4, 4), Point(7, 18)]
Size 32:  [Point(1, 0), Point(2, 11), Point(7, 13), Point(26, 10), Point(4, 27), Point(21, 5), Point(18, 24), Point(20, 29), Point(0, 30), Point(11, 29), Point(13, 24), Point(10, 5), Point(27, 27), Point(5, 10), Point(24, 13), Point(29, 11), Point(30, 0), Point(29, 20), Point(24, 18), Point(5, 21), Point(27, 4), Point(10, 26), Point(13, 7), Point(11, 2), Point(0, 1), Point(20, 2), Point(18, 7), Point(21, 26), Point(4, 4), Point(26, 21), Point(7, 18), Point(2, 20)]

4. Python 代码 1：Circle 群

我们现在将通过简单的 Python 实现来回顾 Circle 群代码。这里仅描述了最重要的函数或部分，并且所有代码都可以在这里找到。

在此，我们定义了两个核心类——FieldElement 和 CirclePoint——以分别处理底层有限域中的算术运算和曲线上的群运算。

4.1 FieldElement

首先，FieldElement 类定义了有限域 $\mathbb{F}_{31}$ 中的算术运算，例如模 31 加法、乘法和求逆。这是在 Circle 曲线上进行所有计算的基础。

Copy
# Mersenne 5
MOD = 31

class FieldElement:
    def __init__(self, value):
        """Initialize a field element"""
        self.value = value % MOD

    def __add__(self, other):
        """Add two field elements"""
        return FieldElement((self.value + other.value) % MOD)

    def __mul__(self, other):
        """Multiply two field elements"""
        return FieldElement((self.value * other.value) % MOD)

    def inv(self):
        """Compute the multiplicative inverse"""
        return FieldElement(pow(self.value, MOD - 2, MOD))

    def square(self):
        """Compute the square"""
        return self * self

4.2 CirclePoint

CirclePoint 类代表 Circle 曲线 $x^2+y^2=1$ 上的点。add 方法实现了群运算，而 double 则应用了平方映射。

Copy
class CirclePoint:
    def __init__(self, x, y):
        """Initialize a point on the circle x^2 + y^2 = 1"""
        if (x.square() + y.square()).value != 1:
            raise ValueError("Point does not lie on the circle")
        self.x = x
        self.y = y

    def add(self, other):
       """Perform group operation: (x1,y1)・(x2,y2) = (x1*x2 - y1*y2, x1*y2 + x2*y1)."""
        nx = self.x * other.x - self.y * other.y
        ny = self.x * other.y + other.x * self.y
        return CirclePoint(nx, ny)

    def double(self):
        """Apply squaring map: π(x,y) = (2*x^2 - 1, 2*x*y), since x^2 + y^2 = 1."""
        xx = self.x.square().double() - FieldElement.one()
        yy = self.x.double() * self.y
        return CirclePoint(xx, yy)

    @classmethod
    def identity(cls):
        """Return the identity element (1, 0) of the circle group."""
        return cls(FieldElement.one(), FieldElement.zero())

然后，你可以如第 2.4 节所述，模拟一个 Circle 群运算示例。

例如，将 CirclePoint $(13, 7)$ 和 CirclePoint $(30, 0)$ 相加会得到 Point $(18, 24)$。

Copy
p1 = CirclePoint(FieldElement(13), FieldElement(7))
p2 = CirclePoint(FieldElement(30), FieldElement(0))

# group operation
p3 = p1.add(p2)
print(f"p1・p2 = {p3}")

Copy
p1・p2 = Point(18, 24)

对 $p1=(13,7)$ 进行 double 会产生 $(27, 27)$

Copy
# squaring map
p1_double = p1.double()
print(f"π(p1) = {p1_double}")

Copy
π(p1) = Point(27, 27)

$(13, 7)$ 的逆元是 $(13, 24)$，将它们相加得到单位元 $(1, 0)$

Copy
# Inverse
p1_inv = p1.inverse()
print(f"p1's inverse = {p1_inv}")
p1_plus_inv = p1.add(p1_inv)
print(f"p1・p1_inv = {p1_plus_inv}")

Copy
p1's inverse = Point(13, 24)
p1・p1_inv = Point(1, 0)

4.3 Circle 群

generate_subgroup 函数生成一个阶为 $2^k$ 的子群 $G_k$。它从 get_nth_generator 函数获取适当的生成元，并重复执行群运算 add 来构建该子群。

Copy
def generate_subgroup(k: int) -> list[CirclePoint]:
    """Generate a subgroup of size 2^k using the generator."""
    g_k = get_nth_generator(k)
    p = CirclePoint.identity()
    return [ (p := p.add(g_k)) if i else p
             for i in range(1 << k) ]

例如，你可以获取大小为 8 的子群。

Copy
G3 = generate_subgroup(3)

Copy
Size 8:  [Point(1, 0), Point(4, 27), Point(0, 30), Point(27, 27), Point(30, 0), Point(27, 4), Point(0, 1), Point(4, 4)]

5. 陪集、孪生陪集与标准位置陪集

孪生陪集和标准位置陪集是 Circle STARKs 中的域 (domains)。在理解孪生陪集和标准位置陪集的数学属性之前，让我们简要回顾一下传统 STARKs 中域是如何被使用的。正如第 0 节所讨论的，传统的 STARKs 通常利用表示为 $\mathbb{F}_p^*$ 的乘法（子）群作为它们的域。这些域主要用于两个目的。

首先，当通过 IFFT 从计算轨迹构建多项式时，它们充当求值域 (evaluation domain)，我们需要通过 FFT 使用扩展域来进行低次扩展 (LDE)，并构建约束多项式并在 LDE 上进行求值。

其次，在低次测试中，特别是在使用 FRI 承诺时，必须在域上通过 FFT 对多项式进行求值，并且在递归 FRI 折叠步骤中，这些域会被迭代地减半。

此外，在 FRI 折叠步骤中，随着多项式的度数减半，域的大小也需要减半。将域大小减半是 FRI 和 FFT 的核心。我们在继续学习时请记住这一点。

因为虽然 Circle 群本身已经提供了高 2-adicity，但孪生陪集或标准位置陪集的构建能够确保：在 FFT 的递归平方步骤中，求值域（即孪生陪集或标准位置陪集）的规模同样可以减半，同时保持其陪集结构。这对于在递归的每一层支持基于这些域的类 FFT 操作而言至关重要。

5.1 陪集

让我们回顾一下群论中陪集的定义。假设 $H$ 是群 $\mathcal{G}$ 的子群，且设 $Q \in \mathcal{G}$。那么 $H$ 关于 $Q$ 的左陪集就是集合

如果 $Q \in H$，那么 $Q \cdot H = H$。否则，在 $Q \notin H$ 的情况下，$Q \cdot H$ 是一个与 $H$ 不相交的集合，但仍具有与 $H$ 相同的大小。这之所以成立，是因为如果 $Q \in H$，群运算下 $H$ 的封闭性确保了 $Q \cdot H = H$；而如果 $Q \notin H$，则 $Q \cdot H$ 中的任何元素都不能在 $H$ 中（否则暗示 $Q \in H$），同时双射 $h \mapsto Q \cdot h$ 保证了大小的一致。

在我们特定的设定中，$\mathcal{G} = C(\mathbb{F}_p)$，它是大小为 $p+1$ 的循环群。从上一节我们知道，存在一条子群链 $G_0 \subset G_1 \subset \dots \subset G_m$，其中 $|G_k| = 2^k$。

因此，举例来说，如果我们固定阶为 $2^{n-1}$ 的 $G_{n-1}$，那么对于圆上的任意点 $Q$，陪集

被称为 $G_{n-1}$ 的一个陪集。
该集合将拥有相同的基数 $2^{n-1}$，并且除非 $Q$ 本身已经属于 $G_{n-1}$，否则它与 $G_{n-1}$ 本身是不相交的。

5.1.1 陪集示例

让我们快速说明一下这个示例。在 $p=31$ 的情况下，回想一下 $p+1=32=2^5$，所以存在子群链 $G_1, G_2, \dots, G_5$，其中 $|G_1|=2$。具体而言，

现在取一个不在 $G_1$ 中的点 $Q$。例如，

既然 $Q$ 不在 $G_1$ 中，那么集合

将是 $G_1$ 的一个不同陪集，与 $G_1$ 自身不相交。

• $(2,11)\cdot(1,0) \;=\; (\,2\cdot1 - 11\cdot0,\;\;2\cdot0 + 11\cdot1) \;=\; (2,\,11),$

• $(2,11)\cdot(30,0) \;=\; (\,2\cdot30 - 11\cdot0,\;\;2\cdot0 + 30\cdot11) \;\equiv\; (29,\,20) \;\pmod{31}.$

因此，

其大小确实为 2。这是对应于 $Q=(2,11)$ 的 $G_1$ 的陪集，它显然不同于子群 $G_1$ 本身。

5.2 孪生陪集

现在，我们通过合并两个陪集来定义一个孪生陪集：$Q \cdot G_{n-1}$ 及其逆向陪集 $Q^{-1} \cdot G_{n-1}$。具体来说，设

1. 不相交性 (Disjointness)
   两个陪集 $Q \cdot G_{n-1}$ 和 $Q^{-1} \cdot G_{n-1}$ 是不相交的。
   实际上，这种不相交性等价于确保 $Q^2 \notin G_{n-1}$。这种等价性源于陪集的性质。如果 $Q^2 \in G_{n-1}$，那么 $Q = Q^{-1} \cdot Q^2$ 将同时位于 $Q \cdot G_{n-1}$ 和 $Q^{-1} \cdot G_{n-1}$ 中（出现重叠）。反之，如果两个陪集不重叠，那么 $Q$ 不能被写为 $Q^{-1} \cdot g$（对任意的 $g \in G_{n-1}$），这意味着 $Q^2 \notin G_{n-1}$。

2. 在对合映射 $J$ 下没有不动点
   如果 $f(P) = P$，则点 $P$ 被称为映射 $f$ 的不动点。在我们的案例中，我们考虑的是对合映射 $J(x,y) \;=\; \bigl(x,\;-y\bigr).$
   如果 $D$ 中包含任何 $y=0$ 的点，那么 $J(x,0) = (x,0)$ 将保持不变。这就是一个不动点。我们希望避免在 $D$ 中出现这样的点，因为根据定义，孪生陪集排除了 $J$ 的任何不动点。

在这些条件下，每个陪集 $Q \cdot G_{n-1}$ 和 $Q^{-1} \cdot G_{n-1}$ 都各有 $2^{n-1}$ 个不同的点，这让 $D$ 的总点数达到 $2^n$。直观地说，我们将一个陪集与其逆向陪集合并，从而形成一个拥有 $2^n$ 个元素的域。

5.2.1 孪生陪集示例

接续第 5.1.1 节中的陪集示例（当时我们选择了一个不在 $G_1$ 中的 $Q=(2,11)$），现在我们来构建一个大小为 $2^n = 2^2 = 4$ 的孪生陪集。我们已经看到：

• $(2,20)\cdot(1,0)\;=\;\bigl(2\cdot1 \;-\;20\cdot0,\;\;2\cdot0 \;+\;1\cdot20\bigr)\;=\;(2,\,20).$

• $(2,20)\cdot(30,0)\;=\;\bigl(2\cdot30 \;-\;20\cdot0,\;\;2\cdot0 \;+\;30\cdot20\bigr)\;=\;(60,\,600)\;\equiv\;(29,\,11)\;\pmod{31}.$

因此，

进行并集操作，孪生陪集为：

5.3 标准位置陪集

标准位置陪集是大小为 $2^n$ 的一种特殊类型的孪生陪集 $D$，它同时巧合地等同于子群 $G_n$ 的单个陪集：

在这里，回忆一下 $G_n$ 是 $C(\mathbb{F}_p)$ 中阶为 $2^n$ 的唯一子群，就像第 3 节中介绍的那样。我们拥有如下的子群链：

并且每个 $G_k$ 的大小都为 $2^k$。因此，$G_n$ 包含了 $G_{n-1}$，并且我们将使用一个阶为 $2^{n+1}$ 的点 $Q$ 来关联这些子群的陪集。

让我们逐步拆解：

首先，因为 $G_{n-1} \subset G_n$，我们可以将 $G_n$ 视为由 $G_{n-1}$ 的两个不相交的陪集组成，也就是：

结果表明 $Q \cdot R = Q^{-1}$，因此：

因此，陪集 $Q \cdot G_n$ 可以写作两个不相交陪集的并集：一个基于 $Q$，另一个基于 $Q^{-1}$，且两者都是在较小的子群 $G_{n-1}$ 之上。这恰好就是孪生陪集的定义。

但并非所有的孪生陪集都是这样产生的。为了确保这种构建正常运作，我们需要：

1. 不相交性：$Q^2 \notin G_{n-1}$。否则，这两个陪集会重叠。
2. 对合下没有不动点：生成集合 $D$ 必须避免含有 $y = 0$ 的点，以便让对合映射 $J(x, y) = (x, -y)$ 在 $D$ 中没有不动点。
3. 正确的阶：$Q$ 的阶必须是 $2^{n+1}$，以保证 $Q \cdot G_n$ 能够覆盖整整 $2^n$ 个不同的元素。

当这些条件被满足时，陪集 $D = Q \cdot G_n$ 会给出一个标准位置陪集：它是一个大小为 $2^n$ 的域，同时既是一个孪生陪集，也是一个较大子群的单个陪集。

5.4 手算示例：$p=31$ 时的孪生陪集与标准位置陪集

以下，我们展示在 $p=31$ 时如何应用孪生陪集和标准位置陪集的概念。由于 $p+1=32=2^5$，所以存在子群 $G_1,\,G_2,\,G_3,\,G_4,\,G_5$，其中 $|G_3|=8$ 以及 $|G_2|=4$。我们将展示 $G_3$ 的标准位置陪集为 $D=Q \cdot G_2 \;\cup\; Q^{-1} \cdot G_2=Q \cdot G_3$。

5.4.1 孪生陪集构建

• 设定
  令 $n=3$。那么 $G_2$ 大小为 4。选择一个阶为 16 的点 $Q$（所以 $Q\notin G_3$，但 $Q \in G_4$）。具体来说，我们可以选择 $Q = (13,\,7)$

• 形成孪生陪集
  

  $$D= \bigl(Q \cdot G_2\bigr) \;\cup\; \bigl(Q^{-1}\cdot G_2\bigr).$$

  因为 $G_2$ 有 $(1,0)$, $(0,30)$, $(30,0)$, 和 $(0,1)$ 四个点，每一个点都要乘以 $Q = (13,\,7)$ 或者是 $Q^{-1}=(13,24)$。

  1. $Q \cdot (1,0)=(13,7)$，
  2. $Q \cdot (0,30)=(7,18)$，
  3. $Q \cdot (30,0)=(18,24)$，
  4. $Q \cdot (0,1)=(24,13)$，
  5. $Q^{-1}\cdot(1,0)=(13,24)$，
  6. $Q^{-1}\cdot(0,30)=(24,18)$，
  7. $Q^{-1}\cdot(30,0)=(18,7)$，
  8. $Q^{-1}\cdot(0,1)=(7,13)$。

合并这些点可以给出 8 个不同的点。没有 $D$ 中的元素被 $J$ 所固定，因此 $D$ 是一个大小为 $2^3=8$ 的孪生陪集。合并这些就得到了 8 个不同的点。由于 $D$ 中的所有元素都不在 $J$ 的映射下产生不动点，因此 $D$ 是一个大小为 $2^3 = 8$ 的孪生陪集。

在下方图表中，🔴 红点表示 $Q \cdot G_2$，而 🔵 蓝点表示 $Q^{-1} \cdot G_2$。它们合在一起形成了 8 个点的孪生陪集 $D$。

5.4.2 检查标准位置陪集

对于某个大小为 8 的子群 $G_3$，这个相同的 $D$ 同样也等于 $Q\cdot G_3$，这意味着 $D$ 是一个标准位置陪集。

$G_3$ 是子群 $\{(1,0),(4,27),(0,30),(27,27),(30,0),(27,4),(0,1),(4,4)\}$，那么将它的每个元素与 $Q=(13,7)$ 相乘正好产生 $D$ 中的这 8 个点。