结果族 142：Deterministic polynomial factorization over prime fields · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
在”模 @@M@@p@@ 算术世界”里把一个大多项式拆成不可再分的”质因式”，是计算代数的看家任务。靠掷硬币的随机算法几十年前就会了；这篇论文的震撼在于：一枚硬币都不掷、不假设任何未证明的猜想，也能在多项式时间内拆完任何素域上的任何多项式。
关键词卡片
@@M@@\mathbf F_p@@（prime field）：只有 @@M@@0,1,\dots,p-1@@、加减乘除全模 @@M@@p@@ 的算术世界看个具体例子
算法的输入输出长这样（公式卡）：
@@M@@Dp=3,\quad f(x)=x^3+2x^2+2x+1\ \Longrightarrow\ f=(x+1)\,(x+2)^2@@
验算：@@M@@x=1@@ 与 @@M@@x=2@@ 都是根，且 @@M@@x+2@@ 是二重因子。算法读入 @@M@@p@@ 的二进制和系数表，输出全部不可约因子连同重数；位运算量 @@M@@O\bigl(((n+1)\lceil\log_2 p\rceil)^{10^{12}}\bigr)@@——指数大得离谱，但要点是对一切次数 @@M@@n@@ 与一切素数 @@M@@p@@ 一致地多项式。随机算法靠”抽签抽中分离元素”碰运气，本文则用解析数论（Hecke L 函数的零点自由带）确定性地造出替代品。
为什么值得关心
“有限域多项式的确定性分解”是计算数论悬挂三十余年的基本难题，本文将其无条件解决（解析部分由姊妹篇提供）。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”模 p 算术世界拆质因式”的比喻可以精确落地：对象是素域上的一个多项式，操作是把它拆成不可再分的”质多项式”之积。随机算法的”掷硬币”是在乘积代数里随机抽一个元素，指望它在不同分量上表现不同从而撕开因子；本文的操作是给每个随机选择配一个确定性的替身——从解析数论里”无中生有”地造出一组辅助素数，由它们供给原本靠运气获得的所有乘法信息。
第二级台阶
关键概念有三个。Berlekamp 代数：商代数中 Frobenius 不动元构成的线性空间，其维数等于因子个数，把完全分解化归为”分裂一个根全在域中却未知的无平方多项式”。辅助素数：对每个不超过次数的素数 q，取满足 ℓ≡1 (mod 12q) 且 p 不是模 ℓ 的 q 次幂的素数 ℓ，它给出含 q 次单位根的扩张及其 q-准素子群的生成元。复杂度参数是 (n+1)·log p——对 p 本身多项式的算法不算数，因为 p 以二进制给出。
第三级台阶
定理 1.1 在如下语境陈述：输入二进制素数 p 与稠密系数表，输出全部不可约因子及重数，位复杂度 O(((n+1)⌈log₂p⌉)^{10¹²})。指数刻意放宽，要点是对一切次数与特征一致；无随机、无整数分解或原根预言机、不假设 GRH。归约定理（1.2）挡住两桩麻烦：辅助素数的数值须被 B=20+(n+1)(L+1) 的固定幂控制，否则代数部分超时；运行时间指数不得依赖曲线亏格（亏格随次数增长）。结论的解析来源是姊妹篇的一致 Hecke L 函数零点自由定理，它无条件地造出足够小的辅助素数；奇次情形的分裂机制则是循环覆盖曲线的雅可比上”λ=1−σ 满射与单射不对称”这一格障碍。
论文给出一致确定性算法，在 @@M@@(n+1)\log p@@ 的多项式位复杂度内完全分解素域 @@M@@\mathbf F_p@@ 上任一 @@M@@n@@ 次多项式（含重数）；不使用随机数、整数分解或原根预言机，也不依赖 GRH，唯一的解析输入是姊妹篇的一致 Hecke @@M@@L@@ 函数零点自由定理。
有限域多项式分解是计算代数的基本构造性问题。Berlekamp 于 1967 年把线性代数推到台前：商代数 @@M@@\mathbf F_p[X]/h@@ 中 Frobenius 不动元构成的线性空间编码了全部不可约因子；Cantor–Zassenhaus 类随机算法靠随机抽取分离元素达到期望多项式时间。确定性情形却卡了几十年：Shoup 的算法对特征有 @@M@@p^{1/2+o(1)}@@ 依赖；Rónyai 在 GRH 假设下处理因子个数有界的情形；Evdokimov 的一般确定性界 @@M@@(n^{\log n}\log p)^{O(1)}@@ 对次数只是拟多项式。门槛在于：素数 @@M@@p@@ 以二进制给出，复杂度必须同时是 @@M@@n@@ 与 @@M@@\log p@@ 的多项式——对 @@M@@p@@ 本身多项式的算法不算数；而随机分离元素要有确定性的替身，往往需要额外的算术信息。本文正是把这份信息从解析数论中取来。
主定理（Theorem 1.1）：存在一致确定性算法，输入二进制素数 @@M@@p@@ 与稠密系数表给出的非零多项式 @@M@@f\in\mathbf F_p[x]@@（@@M@@n=\deg f@@），输出首项系数 @@M@@c@@ 与全部互异首一不可约因子 @@M@@g_i@@ 及重数 @@M@@e_i@@，使 @@M@@f=c\prod_i g_i^{e_i}@@，位运算量为 @@M@@O(((n+1)\lceil\log_2p\rceil)^{10^{12}})@@。指数刻意放宽，要点是对一切次数与特征有一致的多项式界；不使用随机性、整数分解预言机（oracle）、原根预言机，也不假设广义黎曼猜想（GRH）。结构上，论文先证归约定理（Theorem 1.2）：只要为每个素数 @@M@@q\le n@@ 配一个辅助素数 @@M@@\ell@@——满足 @@M@@\ell\equiv1\pmod{12q}@@ 且 @@M@@p^{(\ell-1)/q}\not\equiv1\pmod\ell@@，即 @@M@@p@@ 模 @@M@@\ell@@ 不是 @@M@@q@@ 次幂——且诸 @@M@@\ell@@ 的数值被 @@M@@B@@ 的固定幂控制（@@M@@B=20+(n+1)(L+1)@@，@@M@@L=\lceil\log_2p\rceil@@），代数部分便多项式时间完成；第 10 节再用姊妹篇的定理无条件造出这样的小辅助素数。
整体是”先归约、再分裂、后补解析”三步走。
先归约：递归驱动器以 @@M@@h=g^p@@ 与 @@M@@\gcd(h,h')@@ 剥离 @@M@@p@@ 次幂与重数，Berlekamp 代数的维数 @@M@@r@@ 给出因子个数；若 @@M@@r\ge2@@，取一组基 @@M@@b_0,\dots,b_{r-1}@@，令 @@M@@b(t)=\sum_j t^jb_j@@，使任两分量重合的坏参数少于 @@M@@r^3@@ 个，特征大时逐一试验 @@M@@t@@，即得完全分裂且无平方的特征多项式 @@M@@F_t@@——问题化归为分裂一个根全在域中却未知的 @@M@@F@@。计算在积代数 @@M@@A=k[T]/(F)\simeq\prod_i k@@ 里同时执行（动态求值，dynamic evaluation）：零测试一旦在不同分量分叉，@@M@@\gcd@@ 立即产出真因子。
偶次 @@M@@N@@ 用 Rónyai 式锦标赛论证：由 @@M@@\mathbf F_p^*@@ 的 2-准素子群（2-primary subgroup）生成元给根的两两差定向，每个无序对恰选中一个方向；若各行得分全等，公共值必为 @@M@@(N-1)/2@@，偶数下不是整数——得分不同即得分裂。
奇次 @@M@@N@@ 是实质贡献。取奇素数 @@M@@q\mid N@@，记 @@M@@r=v_q(N)@@、@@M@@m=1+(q-1)r@@，构造循环覆盖曲线 @@M@@C:\ Y^q=F(X)@@（亏格 @@M@@(q-1)(N-2)/2@@）：其分歧点 @@M@@P_i=(x_i,0)@@ 恰对应未知根，另有 @@M@@q@@ 个无穷远点。令 @@M@@\sigma(X,Y)=(X,\zeta_qY)@@、@@M@@\lambda=1-\sigma@@。核心不对称在于：@@M@@\lambda@@ 在几何雅可比（Jacobian）@@M@@J@@ 上满射，在无穷远点格 @@M@@\Lambda\simeq\mathbf Z[\xi]@@ 上却单而不满。先把每个类 @@M@@[P_i-\infty_0]@@ 连续作 @@M@@\lambda@@-除法提升 @@M@@m-1@@ 次；一组滤过模 @@M@@T_t@@ 与 Frobenius 论证保证提升链全部有理于 @@M@@q^r@@ 次扩张 @@M@@k@@ 上，扩张次数始终多项式有界。再对诸提升求和得 @@M@@d_m@@，满足 @@M@@\lambda^m d_m=[Ne]@@。最后依次做标签测试 @@M@@l_{i,t}=v_{P_i}(D_t)-\log_\zeta(h_t(P_i)/\gamma_t)\pmod q@@：若每次测试标签都全同，格元素 @@M@@Ne@@ 就能再多被 @@M@@\lambda@@ 整除一次，与 @@M@@Ne\in\lambda^{m-1}\Lambda\setminus\lambda^m\Lambda@@（因 @@M@@N=q^ra@@、@@M@@q\nmid a@@）矛盾，故必有一次测试区分两个根。@@M@@\lambda@@-除法的算法实现化为 @@M@@k(C)/k(X)@@ 的范数方程（norm equation）：在分裂循环代数中构造极大阶，以秩一幂等元经线性代数求解；Riemann–Roch 约化控制除子规模，大系数的无穷除子用加法–倍乘电路存储。
后补解析：辅助素数的界 @@M@@\ell\le c_0B^{20000000}@@ 出自姊妹篇的一致零点自由定理——固定宽度 @@M@@\delta=10^{-6}@@ 的无零点带给出平滑素理想估计，比较 @@M@@K=\mathbb Q(\mu_{12q})@@ 与 @@M@@M=K(p^{1/q})@@ 的素理想计数：若无辅助素数，相应一次素理想在 @@M@@M@@ 中完全分裂、两侧贡献恰好抵消，与主项矛盾。GRH 亦给出同样的带，故归约在 GRH 下独立成立，姊妹篇把这最后一步变成无条件。小特征 @@M@@p\le B^{200000}@@ 时直接枚举标量，代价仍是 @@M@@B@@ 的多项式。
论文主结果暂无形式化证明，请以社区核验为准。文章把代数归约与解析输入严格隔离：全文仅第 10 节引用姊妹篇《Primitive roots for every admissible integer base》的零点自由定理，两篇需一并审读；即便搁置该定理，GRH 下的多项式界仍独立成立。注意 OpenAI 官方声明：未经形式化的结果可能有问题。指数 @@M@@10^{12}@@ 只求一致多项式，远非实用。
问 1：证明中最关键、最脆弱的一步是什么？
（答：奇次次数的分裂器，论文自认的”实质性步骤”。在循环覆盖曲线 Y^q=F(X) 的雅可比上，λ=1−σ 在几何雅可比上满射、在无穷远点格 Λ≅Z[ξ] 上单而不满；把分歧点类 [P_i−∞₀] 连续作 λ-除法提升 m−1 次再求和，若所有标签测试都给出同一标签，格元素 Ne 就会被 λ 多整除一次，与 N=q^r·a（q∤a）的格赋值矛盾。这个”单而不满”的格论证是全文枢纽：滤过模与 Frobenius 论证须保证提升链全部有理于 q^r 次扩张、扩张次数始终多项式有界——这是最可能藏错的一环。）
问 2：辅助素数为什么不能省？12q 里的 12 是什么？
（答：辅助素数供给 K_q=F_p(ζ_q) 的 q-准素子群生成元，使”承诺的 q 次根提取”能靠小素数离散对数确定性地完成；没有它，随机分离元素没有确定替身。同余 ℓ≡1 (mod 12q) 只是为第 10 节的解析构造方便，代数构造只需要 mod q 的同余——假设强度有明确冗余。）
问 3：与 Shoup、Rónyai、Evdokimov 相比真正的新意是什么？
（答：Shoup 对特征有 p^{1/2+o(1)} 依赖；Rónyai 在 GRH 下处理因子个数有界的情形；Evdokimov 的一般界 (n^{log n}·log p)^{O(1)} 对次数只是拟多项式。本文首次对一切次数与特征给出 (n+1)·log p 的一致多项式界，且不用随机性与任何预言机。值得注意：本文归约配上 Hecke GRH 立得的多项式界在 GRH 下早已成立，真正的新是把零点自由带无条件化的姊妹篇。）
问 4：λ-除法的算法实现有多脆弱？
（答：这是算法侧最重的部分：几何存在性只给分裂元素，还要能算。λ-除法化归为 k(C)/k(X) 的范数方程，须在分裂循环代数中构造极大序、以秩一幂等元经线性代数求解，Riemann–Roch 约化控制除子规模、加法–倍乘电路存储大系数无穷除子。且全程均匀：亏格 (q−1)(N−2)/2 随 N、q 增长，任何依赖亏格的指数都会摧毁定理。）
问 5：作为 AI 生成证明，最可能的出错模式是什么？
（答：本文未形式化，且解析输入完全外包给姊妹篇（第 10 节是唯一接口）——错误可能藏在 Hecke 零点自由定理而非本文。文本自身的高危处：滤过论证的扩张次数账、无穷远格的赋值计算、以及 B^{20000000}/ℓ≤c₀B^{20000000} 这类天文常数的推导。指数 10¹² 刻意放宽说明作者自知常数账不精，审稿恰应盯紧被放宽掩盖的量级错误。）
问 6：谁会用它？实用价值如何？
（答：计算数论与计算机代数系统把分解当基本构件，确定性版本消除随机性对可复现性与恶意输入的顾虑。但 10¹² 次方的指数意味着纯理论意义：它解决的是三十余年悬而未决的”能不能多项式时间”问题，而非给出可用算法；实用中随机算法与 Schoof 类方法仍是主力。）
总评
这是计算数论核心难题的一次无条件解决，”代数归约＋解析输入”的隔离设计干净漂亮、便于分块审查；最大风险是它把宝押在姊妹篇零点自由定理上，且自身未形式化，两篇必须一并通过审读才能宣告落定。