有限域曲线的 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 节讨论复杂度、与经典算法的比较以及结论的边界。
本课知识点
曲线点数与局部 zeta function——能写出 \(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 乘积结构。
Weil 猜想与点数公式——能列出 Weil 猜想（曲线情形）的四条结论，用形式对数展开推导 \(N_n=q^n+1-\sum_j\alpha_j^n\)，并证明 Hasse–Weil 界。
Jacobian 群阶公式——能解释 Jacobian 为何与曲线共享 Weil 根，写出 \(|J_C(\mathbb F_{q^n})|=\prod_j(1-\alpha_j^n)\)，并推导群阶的比特长度估计 \(\Theta(gn\log q)\)。
群阶与 cyclic resultant——能由 resultant 的根式定义证明 \(\operatorname{Res}(P_C,T^n-1)=|J_C(\mathbb F_{q^n})|\)，并说明每枚群阶都是 Weil 多项式的非线性指纹。
Jacobian 的黑盒群封装与量子求阶——能解释规范 divisor 表示与约化群运算如何把 \(J_C(\mathbb F_{q^n})\) 装进黑盒群框架，并写出量子 Abel 群分解读出群阶的流程与生成元前提。
从 cyclic resultants 重建 Weil 多项式——能解释有限个 cyclic resultants 不足以确定一般多项式、却能配合整性与 Weil 界钉死 Weil 多项式，并复述三步重建与经典验证流程。
射影直线与椭圆曲线的手算例子——能对 \(\mathbb P^1\) 从定义算出整个 zeta function，并对 \(\mathbb F_5\) 上的 \(y^2=x^3+1\) 逐点数出群阶、读出 \(P_E(T)=1+5T^2\) 并预测扩域点数。
复杂度与结论边界——能把流水线复杂度逐项分解为关于 \(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}\)。
我们关心的基本量是曲线在各扩域上的有理点数
即坐标取自 \(\mathbb F_{q^n}\)、满足曲线方程的（射影）点的个数。因为 \(\mathbb F_{q^n}\) 只有 \(q^n\) 个元素，逐一枚举坐标对总能算出 \(N_n\)，但代价是 \(q^{O(n)}\) 量级的——这正是要被避免的"逐个数点"。
1.2 局部 zeta function 的定义¶
把无穷序列 \(\{N_n\}_{n\ge1}\) 打包成一个形式幂级数：
为什么取这种"指数套对数"的形状，而不是普通的生成函数 \(\sum N_n T^n\)？深层原因是点数本身具有Euler 乘积结构：每个 \(\mathbb F_{q^n}\)-点都由某个"闭点"（Frobenius 轨道）生成，把指数展开后会得到
即 \(Z_C\) 是所有闭点贡献的乘积——这与 Riemann zeta 写成素数乘积 \(\prod_p(1-p^{-s})^{-1}\) 完全平行，"zeta"之名由此而来。\(\exp(\sum N_n T^n/n)\) 正是让这个乘积结构成立的正确打包方式；本课不需要 Euler 乘积的推导，把它当作动机即可。
1.3 Weil 猜想（曲线情形）¶
下面的定理是本课的基石（曲线情形由 Weil 证明）：
定理 1（Weil 猜想，曲线情形）。设 \(C\) 如上，genus 为 \(g\)。则：
有理性：\(Z_C(T)\) 是有理函数，且精确形式为
分子次数与整性：\(P_C(T)\) 是整系数多项式，次数恰为 \(2g\)，常数项为 \(1\)；
Riemann 假设：把 \(P_C\) 在 \(\mathbb C\) 上分解为
则所有根（在任意复嵌入下）满足 \(|\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 界
故每个系数只需 \(O(g\log q)\) 量级的比特来表示——输出只需 \(O(g\log q)\) 量级系数位（对每个系数而言），而不是一个无限点数序列。一个良定义的"计算 zeta function"算法，其目标就是精确输出 \(P_C\) 的全部系数。
1.4 从有理性推出点数公式¶
定理 1 的有理性与定义式放在一起，立刻给出 \(N_n\) 的封闭表达式。推导的核心工具是形式对数展开
对定义式取对数：
另一方面，对有理性表达式取对数（对数和差变乘积商的对数）：
把上面三条 \(\log(1-x)\) 分别展开，合并 \(T^n\) 的系数：
两个展开式逐项相等（形式幂级数系数唯一），于是由对数导数比较得到：
这个公式值得逐端详读：
\(q^n+1\) 是射影直线 \(\mathbb P^1\) 的点数（见第 5 节的例子），可看作"背景项"；
\(-\sum_j\alpha_j^n\) 是曲线相对背景的修正项。由 \(|\alpha_j|=\sqrt q\)，修正项的绝对值至多是 \(2g\,q^{n/2}\)——这正是 Hasse–Weil 界
换句话说，一条曲线的点数永远不会偏离"射影直线的点数"超过 \(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\)"这一条完全保留。
2.2 群阶公式¶
\(\mathbb F_{q^n}\)-有理点恰好是 Frobenius 第 \(n\) 次幂的不动点。用代数几何中"不动点数 = \(\det(1-\text{Frobenius})\)"的标准结论（对 Jacobian 的 Tate 模计数），Frobenius 本征值同为 \(\alpha_j\)，于是其阶满足
先检验两个特例，建立手感。取 \(n=1\)：
即基域上的群阶就是 Weil 多项式在 \(T=1\) 处的取值。取 \(g=1\)（椭圆曲线），\(P_E(T)=1-aT+qT^2\)，则
这正是椭圆曲线教科书里的标准公式（第 5 节会展开）。
再估计群阶的比特长度，第 3 节的复杂度分析要用。由 \(|\alpha_j|=\sqrt q\) 与三角不等式，每个因子满足
全部 \(2g\) 个因子相乘得
取对数：\(\log|J_C(\mathbb F_{q^n})|=\Theta(gn\log q)\)。也就是说，这个群阶是一个大约 \(gn\log q\) 比特的整数——对 Shor 型算法而言是多项式规模的输入。
2.3 与 resultant 的精确关系¶
群阶公式还有另一种代数包装，它把"群阶"和"未知多项式 \(P_C\)"直接焊在一起。回忆两个多项式的 resultant：设 \(f\) 的根为 \(\rho_1,\ldots,\rho_m\)、首项系数为 \(a_f\)，则（一种标准约定下）
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\) 套用定义：
把每个因子改写：
全部乘起来时，分母是 \(\prod_j\alpha_j^n=\bigl(\prod_j\alpha_j\bigr)^n=(q^g)^n\)（再用一次定理 1 第 4 条），恰好与前面的因子 \((q^g)^n\) 抵消：
若采用 resultant 的其它符号/幂次约定，上式至多乘上一个可知的符号或 \(q\) 的幂因子，不影响下文任何推理。定义
序列 \(\{R_n\}\) 称为 cyclic resultants。我们把上面的恒等式重述成一句话：
注意 \(R_n\) 是根 \(\alpha_j\) 的非线性函数（\(2g\) 个因子的乘积），而不是幂和 \(\sum_j\alpha_j^n\) 那样的线性组合。因此每个群阶都是未知 Weil 多项式的一枚非线性指纹：它混入了所有根的信息，不能直接解出单个 \(\alpha_j\)，但多枚指纹合起来可以钉死整个多项式——这正是第 4 节的重建问题。量子算法的分工至此完全清楚：求若干 Jacobian 群阶，就等于获得未知 Weil polynomial 的若干非线性指纹。
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/约化回到规范形式"的含义）：
先在代表元层面做形式和（取负），得到的类再约化回规范代表元。第一步是平凡的多项式拼接；第二步——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 群版本）是：
取群中若干元素 \(g_1,\ldots,g_t\)；
用量子傅里叶变换/相位估计求各元素的阶及元素间关系，把关系整理成整数格；
对关系格做 Smith 标准形分解，读出群的不变量：
于是
这一步的量子代价关于 \(\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})\)。这个"可证明"是本算法模型正确性的关键一环，而不是工程细节。
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 重建流程¶
具体重建分三步：
取足够多的指纹：取关于 \(g\) 多项式多个 \(n\)（即 \(m=\operatorname{poly}(g)\)），对每个 \(n\) 用量子算法求 \(R_n\)。注意 \(R_n\) 本身可达 \(q^{ng}\) 量级，但它是被精确输出的整数，不是近似值；
逐层恢复对称函数：用整数因子/对数界和 Fried cyclic-resultant reconstruction 的有效版本（effective version，即把存在性结论做成带显式界、可实际执行的算法），从 \(\{R_n\}\) 逐步恢复 elementary symmetric polynomials \(e_1,\ldots,e_{2g}\)，从而得到 \(P_C(T)\) 的全部系数。直觉是：\(R_n\) 对不同的 \(n\) 以不同的非线性方式混合诸根，足够多的混合方程加上 4.2 的离散约束，解集合就坍缩到唯一（或一个可有效枚举的小集合）；
经典验证：把候选 \(P_C\) 对所有已求出的 \(R_n\) 逐一验证 \(\operatorname{Res}(P_C,T^n-1)=R_n\)。resultant 可以只从系数多项式时间算出，因此验证是廉价且严格的——即使第 2 步输出的是一个小候选集，也能确定性地筛出正确答案。
这一步没有任何量子成分，但它是整条流水线里最"代数数论"的部分；值得强调的是，它之所以可行，恰恰是因为目标是精确恢复一个整系数多项式，而不是数值逼近某些根。
5. 例子：射影直线与椭圆曲线¶
5.1 射影直线：\(g=0\) 的完整手算¶
\(C=\mathbb P^1\) 的 genus 为 0。它的 \(\mathbb F_{q^n}\)-点由 \(q^n\) 个仿射点加一个无穷远点组成，故
把这个代入 zeta 定义，可以从头算出整个 \(Z_C\)，并与定理 1 对照。先用对数展开（第 1 节用过的恒等式，用两次）：
两边取 \(\exp\)（\(\exp\) 与 \(\log\) 互为逆，\(\exp(a+b)=e^ae^b\)）：
与定理 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 多项式是二次的：
其中整数 \(a\) 称为 Frobenius 迹。由第 2 节，基域点数为
而定理 1 第 3 条给出 Hasse 界
把 \(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\)，则
幂和满足线性递推（因为 \(\alpha,\bar\alpha\) 都是 \(x^2-ax+q=0\) 的根，两边乘 \(x^{n-2}\) 后相加）：\(s_0=2\)，\(s_1=a\)，
所以只要知道 \(a\)，所有扩域点数都由递推唯一确定。而求 \(E(\mathbb F_q)\) 的群阶就得到 \(a\)（单个扩域已足以确定二次 Weil polynomial）；高 genus 时单个 \(R_1\) 不足以钉死 \(2g\) 个根，需要更多 cyclic resultants。
5.3 一个可以完整手算的数值例子¶
取 \(q=5\) 上的椭圆曲线
第一步：逐个数 \(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\)：
Hasse 界检验：\(|a|=0\le2\sqrt5\approx4.47\)，通过。于是
由 \(\alpha+\bar\alpha=0\)、\(\alpha\bar\alpha=5\) 解出 \(\alpha=\pm i\sqrt5\)；模长检验 \(|\alpha|=\sqrt5\)，与定理 1 第 3 条一致。
第三步：预测并验证扩域点数。 用递推：\(s_0=2\)，\(s_1=a=0\)，
故
第四步：对照 resultant 语言。 本曲线的 cyclic resultants 为
两个群阶都来自同一个二次多项式 \(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 节的多指纹重建。
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 节）
基础：写出 \(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\) 次曲线的亏格。
进阶：区分局部 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 节）
基础：列出定理 1 的四条结论，并由 Weil 界 \(|a_k|\le\binom{2g}{k}q^{k/2}\) 说明 \(P_C\) 的每个系数只需 \(O(g\log q)\) 量级比特。
进阶：从 \(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 节）
基础：对椭圆曲线 \(P_E(T)=1-aT+qT^2\)，用群阶公式计算 \(|E(\mathbb F_q)|\)，并写出 \(|J_C(\mathbb F_q)|\) 与 \(P_C(1)\) 的关系。
进阶：用第 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 节）
基础：写出 resultant 的根式定义 \(\operatorname{Res}(f,g)=a_f^{\deg g}\prod_{i=1}^{m}g(\rho_i)\)，并说明它何时为 \(0\)、为什么能在不知根的情况下由系数算出。
进阶：补全正文把 \((q^g)^n\prod_j\bigl((1/\alpha_j)^n-1\bigr)\) 化简为 \(\prod_j(1-\alpha_j^n)\) 的推导，指出哪一步用到了 \(\prod_j\alpha_j=q^g\)。
进阶：在 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 节）
基础：列出黑盒群模型对群的三项要求（唯一编码、群运算与取逆的量子线路、能生成全群的元素），并对每项给出 \(J_C(\mathbb F_{q^n})\) 的对应实现（规范表示、形式相加再约化、可证明近均匀的随机 divisor classes）。
进阶：解释为何 Jacobian 元素必须有唯一/可比较的规范编码：如果同一个 divisor class 允许两个不同的比特串代表，Abel 黑盒群算法的哪一步会出错？
进阶：说明量子求阶流程中"关系格做 Smith 标准形、读出不变因子、\(R_n=\prod_i d_i\)"这一步的作用，并解释：若随机取到的元素都落在某个真子群里会发生什么？为什么 Kedlaya 必须构造可证明近均匀的随机元素？
提示：相位估计要求"群的正则表示"良好定义；真子群的不变因子之积只给出子群的阶。
练习 6【从 cyclic resultants 重建 Weil 多项式】（→ 第 4 节）
基础：列出 Weil 多项式区别于一般 \(2g\) 次多项式的四条额外约束，并各用一句话说明它如何削减候选集合。
进阶：解释为什么对一般多项式，有限个 cyclic resultants 原则上不足以唯一确定它，而在这些约束下却能被钉死；并说明重建流程第 3 步的经典验证 \(\operatorname{Res}(P_C,T^n-1)=R_n\) 为什么是廉价且严格的。
提示：\(R_n\) 是根的非线性对称函数，没有 Newton 恒等式那样的直接反演；验证只需从系数出发多项式时间计算 resultant。
练习 7【射影直线与椭圆曲线的手算例子】（→ 第 5 节）
基础：复核 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\)。
进阶：对椭圆曲线 \(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\)。
进阶：假装 \(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 节）
基础：列出流水线对每个所选 \(n\) 的四项复杂度贡献（域算术、单次群运算、Abel 群分解、经典重建与验证），并据此说明总量子复杂度关于 \(g,\log q\) 是多项式的。
进阶：解释为什么"量子超多项式加速"不能笼统断言、必须按联合参数族（\(g\) 与 \(\log q\) 及特征同时变化）陈述，并举出早有经典多项式算法的参数情形。
进阶：说明本算法输出的是精确的整系数 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.
Zoo 编号 87：Wim van Dam, Quantum Computing and Zeros of Zeta Functions.