# 有限域曲线的 Zeta 函数：Jacobian 群阶、循环 Resultant 与 Weil 多项式

本课的主题是**有限域上代数曲线的 zeta function**。先澄清一个几乎必然的误会：这里的 zeta function **不是** Riemann zeta 函数 $\zeta(s)=\sum_{n\ge1}n^{-s}$，而是记录一条代数曲线在**所有**有限扩域上点数的一个生成函数。它为什么会出现在量子算法教程里？原因在于下面这个对比：

- **经典一侧**：逐个数出曲线在 $\mathbb F_{q^n}$ 上的点数，朴素做法是枚举所有可能的坐标对并代入曲线方程检验，代价随 $q^n$ 指数增长。对椭圆曲线（genus $1$），Schoof 等人的 $\ell$-进方法给出了关于 $\log q$ 多项式的算法；对一般 genus，也有若干 $p$-进方法，但其复杂度对域特征、genus 的依赖各不相同。
- **量子一侧**：Kedlaya（Zoo 编号 64）观察到，点数的全部信息被压缩在一个 $2g$ 次多项式（**Weil 多项式**）里，而这个多项式的"指纹"恰好是曲线 Jacobian 群在若干扩域上的**群阶**——而求 Abel 群的阶，正是 Shor 型黑盒群算法（ch04）的拿手好戏。整条流水线关于 genus $g$ 与 $\log q$ 都是多项式的。

这个问题的意义不止于"又一个大数难算问题被量子拿下"。有限域曲线的点数直接等于椭圆曲线密码中群的阶（选曲线、验参数都要数点），也决定代数几何码的参数；而 zeta function 的有理性、函数方程与"曲线的 Riemann 假设"正是 20 世纪代数几何的核心成就（Weil 猜想的曲线情形由 Weil 本人证明，一般情形的有理性由 Dwork 证明，Riemann 假设部分由 Deligne 证明）。Kedlaya 的量子算法展示了一条颇具代数数论风味的路线：**不逐个数点，而是把数点问题翻译成 Abel 群阶问题，量子求解后再经典地把答案拼回去**。文末 van Dam 的工作（Zoo 编号 87）则从另一角度研究用量子过程获取 zeta zeros 的谱信息，两者不能混为一谈（见第 6 节）。

**预备知识**。本课默认读者熟悉本站前几章：量子态与测量（ch01）、相位估计与 Shor 型阶求算法（ch03、ch04）、有限域的基本概念。涉及的代数几何对象（曲线、divisor、Jacobian、Riemann–Roch 定理）我们会在用到的层面给出定义与直觉，引用其标准结论但不重新证明。

**路线图**。第 1 节定义局部 zeta function 并用 Weil 猜想推出点数公式；第 2 节证明 Jacobian 扩域群阶就是 Weil 多项式与 $T^n-1$ 的 resultant；第 3 节把 Jacobian 包装成 Abel 黑盒群并给出量子求阶；第 4 节讲如何从有限个"指纹"经典重建 Weil 多项式；第 5 节是两个可以完整手算的例子；第 6 节讨论复杂度、与经典算法的比较以及结论的边界。

:::{admonition} 本课知识点
:class: tip

1. **[曲线点数与局部 zeta function](#curve-zeta-definition)**——能写出 $N_n=|C(\mathbb F_{q^n})|$ 与 $Z_C(T)=\exp\!\bigl(\sum_{n=1}^\infty N_n\frac{T^n}{n}\bigr)$ 的定义、列出亏格的典型取值，并比较它与 Riemann zeta 的 Euler 乘积结构。
2. **[Weil 猜想与点数公式](#weil-conjecture-point-count)**——能列出 Weil 猜想（曲线情形）的四条结论，用形式对数展开推导 $N_n=q^n+1-\sum_j\alpha_j^n$，并证明 Hasse–Weil 界。
3. **[Jacobian 群阶公式](#jacobian-order-formula)**——能解释 Jacobian 为何与曲线共享 Weil 根，写出 $|J_C(\mathbb F_{q^n})|=\prod_j(1-\alpha_j^n)$，并推导群阶的比特长度估计 $\Theta(gn\log q)$。
4. **[群阶与 cyclic resultant](#cyclic-resultant)**——能由 resultant 的根式定义证明 $\operatorname{Res}(P_C,T^n-1)=|J_C(\mathbb F_{q^n})|$，并说明每枚群阶都是 Weil 多项式的非线性指纹。
5. **[Jacobian 的黑盒群封装与量子求阶](#blackbox-jacobian)**——能解释规范 divisor 表示与约化群运算如何把 $J_C(\mathbb F_{q^n})$ 装进黑盒群框架，并写出量子 Abel 群分解读出群阶的流程与生成元前提。
6. **[从 cyclic resultants 重建 Weil 多项式](#reconstruct-weil-polynomial)**——能解释有限个 cyclic resultants 不足以确定一般多项式、却能配合整性与 Weil 界钉死 Weil 多项式，并复述三步重建与经典验证流程。
7. **[射影直线与椭圆曲线的手算例子](#worked-examples)**——能对 $\mathbb P^1$ 从定义算出整个 zeta function，并对 $\mathbb F_5$ 上的 $y^2=x^3+1$ 逐点数出群阶、读出 $P_E(T)=1+5T^2$ 并预测扩域点数。
8. **[复杂度与结论边界](#complexity-limits)**——能把流水线复杂度逐项分解为关于 $g,\log q$ 的多项式，并说明"超多项式加速"须按联合参数族陈述、结论不可外推到 Riemann zeta。

:::

## 1. 定义与有理性

### 1.1 曲线与点数

固定一个有限域 $\mathbb F_q$（$q$ 是素数幂），记 $\mathbb F_{q^n}$ 为它的 $n$ 次扩域。设 $C$ 是定义在 $\mathbb F_q$ 上的一条**光滑、射影、几何连通曲线**。三个修饰词各自的直觉是：

- **射影 (projective)**：曲线包含"无穷远点"，就像把仿射平面直线 $\mathbb A^1$ 补全成射影直线 $\mathbb P^1$；这保证点数是干净的有限数，也使下面的理论形式整齐；
- **光滑 (smooth)**：曲线没有尖点、自交等奇点，每一点都有良好定义的切线；
- **几何连通 (geometrically connected)**：在代数闭包上看仍是一整块，不会分裂成几条互不相干的曲线。

对每条这样的曲线有一个数值不变量——**亏格 (genus)** $g$，可直观理解为"洞的数量"：射影直线 $g=0$，椭圆曲线 $g=1$，一般的光滑平面 $d$ 次曲线 $g=\frac{(d-1)(d-2)}{2}$。

我们关心的基本量是曲线在各扩域上的**有理点数**

$$
N_n=|C(\mathbb F_{q^n})|,
$$

即坐标取自 $\mathbb F_{q^n}$、满足曲线方程的（射影）点的个数。因为 $\mathbb F_{q^n}$ 只有 $q^n$ 个元素，逐一枚举坐标对总能算出 $N_n$，但代价是 $q^{O(n)}$ 量级的——这正是要被避免的"逐个数点"。

(curve-zeta-definition)=
### 1.2 局部 zeta function 的定义

把无穷序列 $\{N_n\}_{n\ge1}$ 打包成一个形式幂级数：

$$
Z_C(T)=
\exp\!\left(
\sum_{n=1}^\infty N_n\frac{T^n}{n}.
\right)
$$

为什么取这种"指数套对数"的形状，而不是普通的生成函数 $\sum N_n T^n$？深层原因是点数本身具有**Euler 乘积**结构：每个 $\mathbb F_{q^n}$-点都由某个"闭点"（Frobenius 轨道）生成，把指数展开后会得到

$$
Z_C(T)=\prod_{P\ \text{闭点}}\frac{1}{1-T^{\deg P}},
$$

即 $Z_C$ 是所有闭点贡献的乘积——这与 Riemann zeta 写成素数乘积 $\prod_p(1-p^{-s})^{-1}$ 完全平行，"zeta"之名由此而来。$\exp(\sum N_n T^n/n)$ 正是让这个乘积结构成立的正确打包方式；本课不需要 Euler 乘积的推导，把它当作动机即可。

(weil-conjecture-point-count)=
### 1.3 Weil 猜想（曲线情形）

下面的定理是本课的基石（曲线情形由 Weil 证明）：

**定理 1**（Weil 猜想，曲线情形）。设 $C$ 如上，genus 为 $g$。则：

1. **有理性**：$Z_C(T)$ 是有理函数，且精确形式为

$$
Z_C(T)=
\frac{P_C(T)}{(1-T)(1-qT)};
$$

2. **分子次数与整性**：$P_C(T)$ 是**整系数**多项式，次数恰为 $2g$，常数项为 $1$；
3. **Riemann 假设**：把 $P_C$ 在 $\mathbb C$ 上分解为

$$
P_C(T)=\prod_{j=1}^{2g}(1-\alpha_jT),
$$

则所有根（在任意复嵌入下）满足 $|\alpha_j|=\sqrt q$；
4. **函数方程**：根集在 $\alpha\mapsto q/\alpha$ 下封闭，等价地 $\prod_{j=1}^{2g}\alpha_j=q^g$，即 $P_C$ 的 $T^{2g}$ 项系数固定为 $q^g$。

多项式 $P_C$ 称为曲线 $C$ 的 **Weil 多项式**；诸 $\alpha_j$ 称为它的 **Weil 根**（它们正是 Frobenius 在 $\ell$-进上同调上的本征值，本课只需要把它们当作满足定理 1 的 $2g$ 个复数）。

这个定理直接改变了问题的性质。原本"计算 zeta function"意味着确定无穷序列 $\{N_n\}$；定理 1 说明全部信息都装在 $P_C$ 的 $2g$ 个整系数里。**输出规模**因此是有限的：由第 3 条，$P_C(T)=\sum_k a_kT^k$ 的系数是 $\alpha_j$ 的初等对称函数，满足 **Weil 界**

$$
|a_k|\le\binom{2g}{k}\,q^{k/2},
$$

故每个系数只需 $O(g\log q)$ 量级的比特来表示——输出只需 $O(g\log q)$ 量级系数位（对每个系数而言），而不是一个无限点数序列。一个良定义的"计算 zeta function"算法，其目标就是**精确输出 $P_C$ 的全部系数**。

### 1.4 从有理性推出点数公式

定理 1 的有理性与定义式放在一起，立刻给出 $N_n$ 的封闭表达式。推导的核心工具是形式对数展开

$$
\log(1-x)=-\sum_{n=1}^\infty\frac{x^n}{n}\qquad(\text{形式幂级数恒等式}).
$$

对定义式取对数：

$$
\log Z_C(T)=\sum_{n=1}^\infty N_n\frac{T^n}{n}.
$$

另一方面，对有理性表达式取对数（对数和差变乘积商的对数）：

$$
\log Z_C(T)=\sum_{j=1}^{2g}\log(1-\alpha_jT)-\log(1-T)-\log(1-qT).
$$

把上面三条 $\log(1-x)$ 分别展开，合并 $T^n$ 的系数：

$$
\log Z_C(T)
=\sum_{n=1}^\infty\left(-\sum_{j=1}^{2g}\alpha_j^n+1+q^n\right)\frac{T^n}{n}.
$$

两个展开式逐项相等（形式幂级数系数唯一），于是由对数导数比较得到：

$$
\boxed{\,N_n=q^n+1-\sum_{j=1}^{2g}\alpha_j^n\,}
$$

这个公式值得逐端详读：

- $q^n+1$ 是射影直线 $\mathbb P^1$ 的点数（见第 5 节的例子），可看作"背景项"；
- $-\sum_j\alpha_j^n$ 是曲线相对背景的**修正项**。由 $|\alpha_j|=\sqrt q$，修正项的绝对值至多是 $2g\,q^{n/2}$——这正是 **Hasse–Weil 界**

$$
|N_n-(q^n+1)|\le 2g\,q^{n/2}.
$$

换句话说，一条曲线的点数永远不会偏离"射影直线的点数"超过 $2g\sqrt{q^n}$。修正项编码了曲线全部有趣的算术信息，而它又由 $2g$ 个 Weil 根的幂和完全决定。已知 $P_C$ 就能算出一切 $N_n$；反过来，Kedlaya 算法的任务就是在不逐个数任何 $N_n$ 的前提下求出 $P_C$。

## 2. Jacobian 群阶编码同一根

### 2.1 Jacobian：曲线自带的 Abel 群

每条（光滑射影几何连通）曲线 $C$ 都伴随一个 $g$ 维 Abel 簇——它的 **Jacobian** $J_C$。对不熟悉的读者，可以暂时只接受以下三条事实，它们足以支撑全课：

- $J_C$ 的 $\mathbb F_{q^n}$-有理点 $J_C(\mathbb F_{q^n})$ 构成一个**有限 Abel 群**；
- 群元素可以具体地实现为曲线上的 **degree-zero divisor class**（下一节详述），因此是可以用有限域元素编码、可以实际做群运算的对象；
- 定义 $Z_C$ 时出现的 Weil 根 $\alpha_1,\ldots,\alpha_{2g}$，同时是 **Frobenius 自同态作用在 $J_C$ 上的本征值**——曲线与它的 Jacobian 共享同一组 $\alpha_j$。

椭圆曲线是最好的直觉来源：$g=1$ 时 $J_C$ 就是 $C$ 自己（椭圆曲线上的点本身在弦切法下成群），Weil 根就是 Frobenius 的两个本征值。高 genus 时 $J_C$ 不再是曲线本身，但"Frobenius 本征值同为 $\alpha_j$"这一条完全保留。

(jacobian-order-formula)=
### 2.2 群阶公式

$\mathbb F_{q^n}$-有理点恰好是 Frobenius 第 $n$ 次幂的不动点。用代数几何中"不动点数 = $\det(1-\text{Frobenius})$"的标准结论（对 Jacobian 的 Tate 模计数），Frobenius 本征值同为 $\alpha_j$，于是其阶满足

$$
\boxed{\;|J_C(\mathbb F_{q^n})|
=\prod_{j=1}^{2g}(1-\alpha_j^n)\;}
$$

先检验两个特例，建立手感。取 $n=1$：

$$
|J_C(\mathbb F_q)|=\prod_{j=1}^{2g}(1-\alpha_j)=P_C(1),
$$

即**基域上的群阶就是 Weil 多项式在 $T=1$ 处的取值**。取 $g=1$（椭圆曲线），$P_E(T)=1-aT+qT^2$，则

$$
|E(\mathbb F_q)|=P_E(1)=1-a+q=q+1-a,
$$

这正是椭圆曲线教科书里的标准公式（第 5 节会展开）。

再估计群阶的**比特长度**，第 3 节的复杂度分析要用。由 $|\alpha_j|=\sqrt q$ 与三角不等式，每个因子满足

$$
q^{n/2}-1\le|1-\alpha_j^n|\le q^{n/2}+1,
$$

全部 $2g$ 个因子相乘得

$$
\bigl(q^{n/2}-1\bigr)^{2g}\ \le\ |J_C(\mathbb F_{q^n})|\ \le\ \bigl(q^{n/2}+1\bigr)^{2g}.
$$

取对数：$\log|J_C(\mathbb F_{q^n})|=\Theta(gn\log q)$。也就是说，这个群阶是一个大约 $gn\log q$ 比特的整数——对 Shor 型算法而言是多项式规模的输入。

(cyclic-resultant)=
### 2.3 与 resultant 的精确关系

群阶公式还有另一种代数包装，它把"群阶"和"未知多项式 $P_C$"直接焊在一起。回忆两个多项式的 **resultant**：设 $f$ 的根为 $\rho_1,\ldots,\rho_m$、首项系数为 $a_f$，则（一种标准约定下）

$$
\operatorname{Res}(f,g)=a_f^{\deg g}\prod_{i=1}^{m}g(\rho_i).
$$

resultant 是两个多项式的系数的整系数多项式，且为 $0$ 当且仅当两多项式有公共根；它可以在不知根的情况下由系数高效算出。

另一方面，若把 reciprocal polynomial 约定处理好（$P_C$ 的根是 $1/\alpha_j$，且由定理 1 第 4 条其首项系数为 $\prod_j\alpha_j=q^g$），对 $f=P_C$、$g(T)=T^n-1$ 套用定义：

$$
\operatorname{Res}(P_C,T^n-1)
=(q^g)^{n}\prod_{j=1}^{2g}\Bigl(\bigl(\tfrac1{\alpha_j}\bigr)^n-1\Bigr).
$$

把每个因子改写：

$$
\bigl(\tfrac1{\alpha_j}\bigr)^n-1=\frac{1-\alpha_j^n}{\alpha_j^n},
$$

全部乘起来时，分母是 $\prod_j\alpha_j^n=\bigl(\prod_j\alpha_j\bigr)^n=(q^g)^n$（再用一次定理 1 第 4 条），恰好与前面的因子 $(q^g)^n$ 抵消：

$$
\operatorname{Res}(P_C,T^n-1)
=(q^g)^n\cdot\frac{\prod_{j=1}^{2g}(1-\alpha_j^n)}{(q^g)^n}
=\prod_{j=1}^{2g}(1-\alpha_j^n)
=|J_C(\mathbb F_{q^n})|.
$$

若采用 resultant 的其它符号/幂次约定，上式至多乘上一个可知的符号或 $q$ 的幂因子，不影响下文任何推理。定义

$$
R_n=\operatorname{Res}(P_C(T),T^n-1),
$$

序列 $\{R_n\}$ 称为 **cyclic resultants**。我们把上面的恒等式重述成一句话：

$$
\text{求出群阶 } |J_C(\mathbb F_{q^n})| \quad\Longleftrightarrow\quad \text{求出未知 } P_C \text{ 的第 } n \text{ 个 cyclic resultant } R_n.
$$

注意 $R_n$ 是根 $\alpha_j$ 的**非线性**函数（$2g$ 个因子的乘积），而不是幂和 $\sum_j\alpha_j^n$ 那样的线性组合。因此每个群阶都是未知 Weil 多项式的一枚**非线性指纹**：它混入了所有根的信息，不能直接解出单个 $\alpha_j$，但多枚指纹合起来可以钉死整个多项式——这正是第 4 节的重建问题。量子算法的分工至此完全清楚：**求若干 Jacobian 群阶，就等于获得未知 Weil polynomial 的若干非线性指纹。**

(blackbox-jacobian)=
## 3. 如何把 Jacobian 做成黑盒群

Shor 型 Abel 群算法（ch04 的阶求与离散对数是它的特例）并不直接吃"几何对象"，它吃的是一个**黑盒群**：群元素有唯一的比特串编码，群运算与取逆有量子线路实现，并且能生成一组覆盖整个群的元素。本节把 $J_C(\mathbb F_{q^n})$ 逐项装进这个框架。

### 3.1 元素：divisor class 的规范表示

**Divisor** 是曲线上点的形式和 $D=\sum_P m_P P$（系数 $m_P\in\mathbb Z$，只有有限项非零），其**次数**为 $\deg D=\sum_P m_P$。两个 degree-zero divisor 若相差一个有理函数的零点减极点（称**线性等价**），则视为同一个群元素；等价类称为 degree-zero divisor class，它们在"形式和相加"下构成群——这正是 $J_C$ 的点的具体化身。直观地说：Jacobian 的元素是"曲线上加减抵消后的点丛"，而 $g$ 控制着每个类需要多少个点来表示。

直接操作等价类不行：同一个类有无穷多个代表元，黑盒群要求**每个群元素有唯一的编码**，否则连"两个元素是否相等"都无法判定。算法的解决办法是选择**可计算规范表示**（canonical representation）：每个类里挑出一个唯一确定的代表元。对超椭圆曲线，这就是经典的 **Mumford 表示**（一对次数受控的多项式）；对一般曲线，可以用 **reduced divisor**：Riemann–Roch 定理保证每个 degree-zero 类都存在约化代表，且在 genus 固定/输入给定时可以取到唯一规范的版本。无论哪种，每个群元素最终都是 $\mathbb F_{q^n}$ 上 $O(g)$ 个域元素的比特串。

### 3.2 群运算：加完再约化

群运算分两步（这正是"后通过 Riemann–Roch/约化回到规范形式"的含义）：

$$
[D_1]+[D_2]=[D_1+D_2],\qquad-[D]=[-D]
$$

先在代表元层面做形式和（取负），得到的类再约化回规范代表元。第一步是平凡的多项式拼接；第二步——**divisor reduction**——是计算的核心，经典算法（超椭圆情形即 Cantor 算法）在指定曲线模型和固定/输入 genus 条件下用 $\operatorname{poly}(g)$ 次域运算完成。

复杂度逐项盘点：$\mathbb F_{q^n}$ 上的域算术（加、乘、求逆、多项式因式分解）代价为 $\operatorname{poly}(n\log q)$ 比特操作；每次群运算是 $\operatorname{poly}(g)$ 次域运算；全部用量子可逆电路实现只引入常数开销。因此对扩域 $\mathbb F_{q^n}$，域算术、因式分解与 divisor reduction 在指定曲线模型和固定/输入 genus 条件下为 $\operatorname{poly}(g,n,\log q)$——黑盒群的"单次查询"是多项式代价的。

### 3.3 量子求阶：分解整个群

Abelian 黑盒群 order algorithm 的标准流程（ch04 工具的 Abel 群版本）是：

1. 取群中若干元素 $g_1,\ldots,g_t$；
2. 用量子傅里叶变换/相位估计求各元素的阶及元素间关系，把关系整理成整数格；
3. 对关系格做 Smith 标准形分解，读出群的不变量：

$$
J_C(\mathbb F_{q^n})
\cong\mathbb Z_{d_1}\times\cdots\times\mathbb Z_{d_s},
$$

于是

$$
R_n=|J_C(\mathbb F_{q^n})|=\prod_{i=1}^{s}d_i.
$$

这一步的量子代价关于 $\log|J_C(\mathbb F_{q^n})|=\Theta(gn\log q)$ 为多项式——这正是 Shor 算法相对经典群阶算法的加速点，全部"量子性"都集中在这一格。

但整个流程有一个容易忽略的前提：**第 1 步取的元素必须能（高概率）生成整个群**。如果随机取来的 $g_i$ 都落在某个真子群里，分解出的就是子群而非 $J_C$ 本身，得到的"群阶"会系统性地偏小。这里不能拍脑袋假设"随便在曲线上选几个点就生成 Jacobian"——Kedlaya 构造的是**可证明近均匀**的随机 divisor classes：利用约化表示的参数空间做随机取样，并证明其分布与均匀分布的统计距离足够小，从而收集足够元素后高概率生成整个 $J_C(\mathbb F_{q^n})$。这个"可证明"是本算法模型正确性的关键一环，而不是工程细节。

(reconstruct-weil-polynomial)=
## 4. 从 cyclic resultants 重建 $P_C$

现在假设量子部分已经交出了 $R_1,R_2,\ldots,R_m$（$m$ 待定）。剩下的是一个纯经典问题：

> 已知未知根 $\alpha_1,\ldots,\alpha_{2g}$ 的若干 cyclic resultants $R_n=\prod_j(1-\alpha_j^n)$，恢复初等对称函数，从而恢复 $P_C(T)=\prod_j(1-\alpha_jT)$。

### 4.1 为什么不是直接的反演

$R_n$ 是根的对称函数，但是**高度非线性**的：展开后是诸 $\alpha_j$ 幂的交错乘积和，而不是幂和 $p_n=\sum_j\alpha_j^n$。如果手里是幂和，Newton 恒等式会立刻给出初等对称函数；cyclic resultant 没有这样的直接反演公式。更糟的是，对**一般**多项式，确实存在不同的根集合产生部分相同 resultants 的现象——有限个 $R_n$ 原则上不足以唯一确定一个任意的 $2g$ 次多项式。

### 4.2 Weil 多项式的额外约束

出路在于 $P_C$ 不是任意多项式，而是 Weil 多项式，额外满足：

- **整系数与固定的首项系数 $q^g$**（原文表述为"固定常数项 $q^g$"，指在 reciprocal/首一化约定下：由定理 1 第 4 条，$P_C$ 的 $T^{2g}$ 项系数为 $\prod_j\alpha_j=q^g$，等价地其倒互反多项式的常数项为 $q^g$）；
- **reciprocal functional equation**：根在 $\alpha\mapsto q/\alpha$ 下成对出现，系数因而回文对称（$a_{2g-k}=q^{g-k}a_k$），未知系数实际只有约 $g$ 个；
- **所有根绝对值 $\sqrt q$**（定理 1 第 3 条）；
- **系数有 Weil bounds**：$|a_k|\le\binom{2g}{k}q^{k/2}$（第 1 节）。

每一条都在大幅削减候选。整性 + Weil 界把每个系数限制在一个**有限**的整数集合里；函数方程把独立未知量减半；根的模长条件是一个强的 Archimedes 约束，与 $R_n$ 的大小信息互相印证。合在一起，这些约束把候选压到**有限且可有效区分**的集合。

### 4.3 重建流程

具体重建分三步：

1. **取足够多的指纹**：取关于 $g$ 多项式多个 $n$（即 $m=\operatorname{poly}(g)$），对每个 $n$ 用量子算法求 $R_n$。注意 $R_n$ 本身可达 $q^{ng}$ 量级，但它是被**精确**输出的整数，不是近似值；
2. **逐层恢复对称函数**：用整数因子/对数界和 Fried cyclic-resultant reconstruction 的有效版本（effective version，即把存在性结论做成带显式界、可实际执行的算法），从 $\{R_n\}$ 逐步恢复 elementary symmetric polynomials $e_1,\ldots,e_{2g}$，从而得到 $P_C(T)$ 的全部系数。直觉是：$R_n$ 对不同的 $n$ 以不同的非线性方式混合诸根，足够多的混合方程加上 4.2 的离散约束，解集合就坍缩到唯一（或一个可有效枚举的小集合）；
3. **经典验证**：把候选 $P_C$ 对所有已求出的 $R_n$ 逐一验证 $\operatorname{Res}(P_C,T^n-1)=R_n$。resultant 可以只从系数多项式时间算出，因此验证是廉价且严格的——即使第 2 步输出的是一个小候选集，也能确定性地筛出正确答案。

这一步没有任何量子成分，但它是整条流水线里最"代数数论"的部分；值得强调的是，它之所以可行，恰恰是因为目标是**精确恢复一个整系数多项式**，而不是数值逼近某些根。

(worked-examples)=
## 5. 例子：射影直线与椭圆曲线

### 5.1 射影直线：$g=0$ 的完整手算

$C=\mathbb P^1$ 的 genus 为 0。它的 $\mathbb F_{q^n}$-点由 $q^n$ 个仿射点加一个无穷远点组成，故

$$
N_n=q^n+1.
$$

把这个代入 zeta 定义，可以从头算出整个 $Z_C$，并与定理 1 对照。先用对数展开（第 1 节用过的恒等式，用两次）：

$$
\sum_{n=1}^\infty N_n\frac{T^n}{n}
=\sum_{n=1}^\infty\frac{(qT)^n}{n}+\sum_{n=1}^\infty\frac{T^n}{n}
=-\log(1-qT)-\log(1-T).
$$

两边取 $\exp$（$\exp$ 与 $\log$ 互为逆，$\exp(a+b)=e^ae^b$）：

$$
Z_C(T)=\exp\!\bigl(-\log(1-qT)\bigr)\cdot\exp\!\bigl(-\log(1-T)\bigr)=\frac1{(1-T)(1-qT)}.
$$

与定理 1 的有理性形式对比：分子 $P_C(T)=1$，次数 $0=2g$，与 $g=0$ 一致；没有 Weil 根，Hasse–Weil 界的修正项恒为 $0$，$N_n=q^n+1$ 精确成立——一切都自洽。Jacobian 是平凡的（$g=0$ 时 $J_C$ 是一个点），群阶公式给出空乘积 $|J_C(\mathbb F_{q^n})|=1$，也与 $R_n=\operatorname{Res}(1,T^n-1)=1$ 吻合。

### 5.2 椭圆曲线：一般公式

椭圆曲线 $E$ 的 genus 为 1，Weil 多项式是二次的：

$$
P_E(T)=1-aT+qT^2,
$$

其中整数 $a$ 称为 **Frobenius 迹**。由第 2 节，基域点数为

$$
|E(\mathbb F_q)|=P_E(1)=q+1-a,
$$

而定理 1 第 3 条给出 Hasse 界

$$
|a|=|\alpha_1+\alpha_2|\le|\alpha_1|+|\alpha_2|=2\sqrt q.
$$

把 $P_E$ 分解为 $(1-\alpha T)(1-\bar\alpha T)$，比较系数得 $\alpha+\bar\alpha=a$、$\alpha\bar\alpha=q$。扩域点数由第 1 节的公式给出：记幂和 $s_n=\alpha^n+\bar\alpha^n$，则

$$
|E(\mathbb F_{q^n})|=q^n+1-s_n.
$$

幂和满足线性递推（因为 $\alpha,\bar\alpha$ 都是 $x^2-ax+q=0$ 的根，两边乘 $x^{n-2}$ 后相加）：$s_0=2$，$s_1=a$，

$$
s_n=a\,s_{n-1}-q\,s_{n-2}\qquad(n\ge2).
$$

所以**只要知道 $a$，所有扩域点数都由递推唯一确定**。而求 $E(\mathbb F_q)$ 的群阶就得到 $a$（单个扩域已足以确定二次 Weil polynomial）；高 genus 时单个 $R_1$ 不足以钉死 $2g$ 个根，需要更多 cyclic resultants。

### 5.3 一个可以完整手算的数值例子

取 $q=5$ 上的椭圆曲线

$$
E:\ y^2=x^3+1.
$$

**第一步：逐个数 $E(\mathbb F_5)$ 的点。** $\mathbb F_5$ 中的平方只有 $0,1,4$。对每个 $x$ 计算 $x^3+1\bmod 5$ 并数平方根：

| $x$ | $x^3+1\bmod 5$ | 是否为平方 | $y$ 的个数 |
|---|---|---|---|
| 0 | 1 | 是 | 2（$y=1,4$） |
| 1 | 2 | 否 | 0 |
| 2 | 4 | 是 | 2（$y=2,3$） |
| 3 | 3 | 否 | 0 |
| 4 | 0 | 是 | 1（$y=0$） |

加上唯一一个无穷远点，共 $|E(\mathbb F_5)|=2+0+2+0+1+1=6$。

**第二步：读出 Weil 多项式。** 由 $|E(\mathbb F_q)|=q+1-a$：

$$
a=q+1-|E(\mathbb F_q)|=5+1-6=0,
$$

Hasse 界检验：$|a|=0\le2\sqrt5\approx4.47$，通过。于是

$$
P_E(T)=1+5T^2.
$$

由 $\alpha+\bar\alpha=0$、$\alpha\bar\alpha=5$ 解出 $\alpha=\pm i\sqrt5$；模长检验 $|\alpha|=\sqrt5$，与定理 1 第 3 条一致。

**第三步：预测并验证扩域点数。** 用递推：$s_0=2$，$s_1=a=0$，

$$
s_2=a s_1-q s_0=0-5\cdot2=-10,
$$

故

$$
|E(\mathbb F_{25})|=25+1-s_2=36.
$$

**第四步：对照 resultant 语言。** 本曲线的 cyclic resultants 为

$$
R_1=|E(\mathbb F_5)|=(1-i\sqrt5)(1+i\sqrt5)=1+5=6=P_E(1),\qquad
R_2=|E(\mathbb F_{25})|=(1-\alpha^2)(1-\bar\alpha^2)=(1+5)^2=36,
$$

两个群阶都来自同一个二次多项式 $1+5T^2$。如果假装 $P_E$ 未知：由 $R_1=P_E(1)=6$、$q=5$ 与 Hasse 界 $|a|\le4$，方程 $6=6-a$ 直接钉死 $a=0$——这就是"单个 resultant 确定 genus 1 的 Weil 多项式"在最小规模上的样子。genus $\ge2$ 时 $R_1$ 只留下一个方程而未知数有 $g$ 个（利用函数方程回文对称后），这才需要第 4 节的多指纹重建。

(complexity-limits)=
## 6. 速度提升与限制

**量子复杂度的来源逐项拆解。** 整条流水线对每个被选中的 $n$（共 $\operatorname{poly}(g)$ 个）执行：

- 域算术：$\operatorname{poly}(n\log q)$（$\mathbb F_{q^n}$ 元素是 $n\log q$ 比特的对象）；
- 单次群运算（含约化）：$\operatorname{poly}(g)$ 次域运算；
- Abel 群分解：$\operatorname{poly}(\log|J_C(\mathbb F_{q^n})|)=\operatorname{poly}(gn\log q)$ 量子门（第 3.3 节）；
- 经典重建与验证：$\operatorname{poly}(g,\log q)$（第 4 节）。

把所有因子乘起来、再对 $n$ 的多项式上界求和，总量子复杂度关于 $g,\log q$ 为多项式——注意这个结论依赖两端的"多项式性"同时成立：一端是高效曲线/Jacobian 算术与可证明近均匀的随机元素构造（保证单次黑盒查询便宜且生成元可靠），另一端是 Weil 多项式的输出规模本身只有 $O(g)$ 个系数、每系数 $O(g\log q)$ 比特（保证"求出整个 zeta"是个有限任务）。

**与经典算法的比较需要谨慎陈述。** 已知经典通用算法在某些参数（特别是域特征、genus）有不同表现：例如椭圆曲线（$g=1$）早有关于 $\log q$ 多项式的经典 $\ell$-进算法，固定小特征下也有高效的 $p$-进方法；因此"量子超多项式加速"不应笼统断言，而应按论文所比较的**联合参数族**陈述——即 $g$ 与 $\log q$（及特征）同时变化的特定序列上，已知最佳经典算法的复杂度增长超过多项式，而本算法保持多项式。这一限定是原论文结论的一部分，引用时不应省略。

**结论的边界。** 还有两点不能越界：

- 算法输出**完整的 zeta rational function**（即精确的整系数 Weil 多项式 $P_C$），而不是零点的浮点近似。得到 $P_C$ 之后当然可以在经典机器上数值求根到任意精度，但那是后处理，不是算法的一部分；
- van Dam 的相关工作（Zoo 编号 87）研究的是用**量子过程**（谱估计类思路）获取 zeta zeros/谱信息，问题设定与本课不同。尤其重要的是：本课一切结果都关于**有限域曲线**的 zeta function——Weil 根模长 $\sqrt q$、有理性、函数方程是这个世界的定理；不能把有限域曲线结果外推到计算 **Riemann zeta 非平凡零点**。两者的相似是类比层面的（Euler 乘积、"Riemann 假设"的措辞），不是算法层面的。

## 7. 本课小结

- 曲线 zeta function 由 $2g$ 次 Weil polynomial $P_C$ 完全决定：有理性把无穷点数序列压缩成有限个整系数，Weil 界保证每个系数只需 $O(g\log q)$ 量级比特；
- 点数公式 $N_n=q^n+1-\sum_j\alpha_j^n$ 把"数点"翻译成"Weil 根的幂和"，Hasse–Weil 界是它的直接推论；
- Jacobian 扩域群阶是 Weil 根的 cyclic resultant：$|J_C(\mathbb F_{q^n})|=\prod_j(1-\alpha_j^n)=\operatorname{Res}(P_C,T^n-1)$，群阶即指纹；
- 把 Jacobian 包装成 Abel 黑盒群（规范 divisor 表示 + Riemann–Roch 约化 + 可证明近均匀的随机元素），量子 Abel 群分解高效求这些群阶，经典重建恢复多项式；
- 整性、functional equation 和 Weil bounds 是从有限指纹唯一恢复的关键——没有这些离散约束，cyclic resultants 不能唯一确定一般多项式；
- 复杂度关于 $g,\log q$ 多项式的结论依赖曲线算术、随机元素构造与重建算法的多项式性同时成立；"超多项式加速"须按联合参数族陈述，且结果不可外推到 Riemann zeta。

## 练习题

**练习 1【曲线点数与局部 zeta function】**（→ [1.2 节](#curve-zeta-definition)）

1. 基础：写出 $N_n=|C(\mathbb F_{q^n})|$ 与局部 zeta function $Z_C(T)=\exp\!\bigl(\sum_{n=1}^\infty N_n\frac{T^n}{n}\bigr)$ 的定义，并写出射影直线、椭圆曲线、光滑平面 $d$ 次曲线的亏格。
2. 进阶：区分局部 zeta function 与 Riemann zeta：各在什么域/环上定义、各自的"Euler 乘积"遍历什么对象、各自的"Riemann 假设"分别断言什么？为什么说 Kedlaya 算法与 Riemann zeta 非平凡零点的计算没有关系？

> 提示：把 $\prod_{P\ \text{闭点}}(1-T^{\deg P})^{-1}$ 与 $\prod_p(1-p^{-s})^{-1}$ 逐项对照；结论边界见第 6 节。

**练习 2【Weil 猜想与点数公式】**（→ [1.3 节](#weil-conjecture-point-count)）

1. 基础：列出定理 1 的四条结论，并由 Weil 界 $|a_k|\le\binom{2g}{k}q^{k/2}$ 说明 $P_C$ 的每个系数只需 $O(g\log q)$ 量级比特。
2. 进阶：从 $P_C(T)=\prod_{j=1}^{2g}(1-\alpha_jT)$ 的根表达与 $Z_C$ 的定义出发，补全第 1.4 节推导 $N_n=q^n+1-\sum_j\alpha_j^n$ 的全部中间步骤，并进一步推出 Hasse–Weil 界 $|N_n-(q^n+1)|\le2g\,q^{n/2}$。

> 提示：对 $(1-\alpha_jT)$、$(1-T)$、$(1-qT)$ 三处分别用 $\log(1-x)=-\sum_{n\ge1}x^n/n$ 展开，再比较 $T^n/n$ 的系数。

**练习 3【Jacobian 群阶公式】**（→ [2.2 节](#jacobian-order-formula)）

1. 基础：对椭圆曲线 $P_E(T)=1-aT+qT^2$，用群阶公式计算 $|E(\mathbb F_q)|$，并写出 $|J_C(\mathbb F_q)|$ 与 $P_C(1)$ 的关系。
2. 进阶：用第 2.2 节的群阶估计证明 $\log|J_C(\mathbb F_{q^n})|=\Theta(gn\log q)$，并据此说明：为什么求单个 $R_n$ 的量子代价关于 $g,n,\log q$ 是多项式的？如果改为要求 $n$ 大到 $q^{ng}$ 超过输入规模，会在哪一步破坏多项式性？

> 提示：每个因子满足 $q^{n/2}-1\le|1-\alpha_j^n|\le q^{n/2}+1$；量子 Abel 群分解的代价按 $\log|J_C(\mathbb F_{q^n})|$ 的多项式计。

**练习 4【群阶与 cyclic resultant】**（→ [2.3 节](#cyclic-resultant)）

1. 基础：写出 resultant 的根式定义 $\operatorname{Res}(f,g)=a_f^{\deg g}\prod_{i=1}^{m}g(\rho_i)$，并说明它何时为 $0$、为什么能在不知根的情况下由系数算出。
2. 进阶：补全正文把 $(q^g)^n\prod_j\bigl((1/\alpha_j)^n-1\bigr)$ 化简为 $\prod_j(1-\alpha_j^n)$ 的推导，指出哪一步用到了 $\prod_j\alpha_j=q^g$。
3. 进阶：在 5.3 节的例子（$E:y^2=x^3+1$，$q=5$）中，改用 resultant 定义直接计算 $\operatorname{Res}(1+5T^2,T-1)$ 与 $\operatorname{Res}(1+5T^2,T^2-1)$，验证它们分别等于 $R_1=6$ 与 $R_2=36$。

> 提示：$1+5T^2$ 的根是 $\pm i/\sqrt5$、首项系数为 $5$；化简时把每个因子改写成 $(1/\alpha_j)^n-1=\frac{1-\alpha_j^n}{\alpha_j^n}$ 后通分。

**练习 5【Jacobian 的黑盒群封装与量子求阶】**（→ [第 3 节](#blackbox-jacobian)）

1. 基础：列出黑盒群模型对群的三项要求（唯一编码、群运算与取逆的量子线路、能生成全群的元素），并对每项给出 $J_C(\mathbb F_{q^n})$ 的对应实现（规范表示、形式相加再约化、可证明近均匀的随机 divisor classes）。
2. 进阶：解释为何 Jacobian 元素必须有唯一/可比较的规范编码：如果同一个 divisor class 允许两个不同的比特串代表，Abel 黑盒群算法的哪一步会出错？
3. 进阶：说明量子求阶流程中"关系格做 Smith 标准形、读出不变因子、$R_n=\prod_i d_i$"这一步的作用，并解释：若随机取到的元素都落在某个真子群里会发生什么？为什么 Kedlaya 必须构造可证明近均匀的随机元素？

> 提示：相位估计要求"群的正则表示"良好定义；真子群的不变因子之积只给出子群的阶。

**练习 6【从 cyclic resultants 重建 Weil 多项式】**（→ [第 4 节](#reconstruct-weil-polynomial)）

1. 基础：列出 Weil 多项式区别于一般 $2g$ 次多项式的四条额外约束，并各用一句话说明它如何削减候选集合。
2. 进阶：解释为什么对一般多项式，有限个 cyclic resultants 原则上不足以唯一确定它，而在这些约束下却能被钉死；并说明重建流程第 3 步的经典验证 $\operatorname{Res}(P_C,T^n-1)=R_n$ 为什么是廉价且严格的。

> 提示：$R_n$ 是根的非线性对称函数，没有 Newton 恒等式那样的直接反演；验证只需从系数出发多项式时间计算 resultant。

**练习 7【射影直线与椭圆曲线的手算例子】**（→ [第 5 节](#worked-examples)）

1. 基础：复核 5.3 节的计数表：对 $\mathbb F_5$ 上 $E:y^2=x^3+1$ 逐个 $x$ 数出 $y$ 的个数，确认 $|E(\mathbb F_5)|=6$，并由 $a=q+1-|E(\mathbb F_q)|$ 读出 $P_E(T)=1+5T^2$。
2. 进阶：对椭圆曲线 $P(T)=1-aT+qT^2$，用递推 $s_n=as_{n-1}-qs_{n-2}$ 写出 $|E(\mathbb F_{q^2})|$ 与 $|E(\mathbb F_{q^3})|$ 的显式公式（答案只含 $a$ 与 $q$），并代入 $a=0$、$q=5$ 验证 $|E(\mathbb F_{25})|=36$。
3. 进阶：假装 $P_E$ 未知：已知 $q=5$、$R_1=|E(\mathbb F_5)|=6$ 与 Hasse 界 $|a|\le2\sqrt5$，确定唯一的候选 $a$ 与 $P_E$；再说明 genus $\ge2$ 时为什么单个 $R_1$ 不再够用。

> 提示：递推从 $s_0=2$、$s_1=a$ 起步；联立 $R_1=P_E(1)=6-a$ 与整数 $a$ 的有限候选。

**练习 8【复杂度与结论边界】**（→ [第 6 节](#complexity-limits)）

1. 基础：列出流水线对每个所选 $n$ 的四项复杂度贡献（域算术、单次群运算、Abel 群分解、经典重建与验证），并据此说明总量子复杂度关于 $g,\log q$ 是多项式的。
2. 进阶：解释为什么"量子超多项式加速"不能笼统断言、必须按联合参数族（$g$ 与 $\log q$ 及特征同时变化）陈述，并举出早有经典多项式算法的参数情形。
3. 进阶：说明本算法输出的是精确的整系数 Weil 多项式而非零点的浮点近似，并解释它与 van Dam 获取 zeta zeros 谱信息的工作（Zoo 编号 87）在问题设定上的区别。

> 提示：椭圆曲线（$g=1$）早有关于 $\log q$ 多项式的经典 $\ell$-进算法；数值求根只是得到 $P_C$ 之后的经典后处理。

## 参考文献

- Zoo 编号 64：Kiran Kedlaya, [Quantum Computation of Zeta Functions of Curves](https://arxiv.org/abs/math/0411623).
- Zoo 编号 87：Wim van Dam, [Quantum Computing and Zeros of Zeta Functions](https://arxiv.org/abs/quant-ph/0405081).