本文由 莫潇羽@无忆研习社(www.wuyi.wiki)撰写,转载请注明出处。
快速摘要
2026年9月25日,Anthropic 正式发布研究博客,公开了一项理论物理计算(配套的九圈结果数据页面,页面底部落款日期为9月16日):Claude(Fable 5.1 模型,跑在 Claude Science 科研工作台上)在几乎没有人工指导的情况下,连续工作数天,算出了"平面 N=4 超对称杨-米尔斯理论"中六胶子 MHV 散射振幅的九圈结果。此前这一振幅的公开纪录是2023年发表的八圈。Claude 用两条互相独立的路线各算一遍:一条是在六边形函数空间里直接"自举",一条是先算更简单的三点形状因子、再借"对跖对偶"翻译回振幅,两边在十万多个系数上逐一吻合。八圈结果的主要完成者、美国 SLAC 国家加速器实验室的一位资深教授花了约两周独立核验,确认结果成立。按普通用户价格估算,单条路线的花费在一两千美元量级,其中纯计算部分约100美元,相当于96个 CPU 跑一周。几乎同一时间,中国科学院理论物理研究所的一个研究团队也在9月17日公开了二到九圈的振幅符号数据,他们用 AI 辅助了部分约束计算,整体框架由人完成。
我的判断是:这件事真正的分量不在"AI 超过了人",而在于一个流程极其脆弱、容错极低的前沿计算,第一次被模型端到端地、可验证地做完了;它用的全是人类已经发展好的方法,没有提出新物理。
下面我会从"九圈到底难在哪"讲起,把自举法、符号字母表、对跖对偶这些概念用白话拆开,再用我自己跑的一个缩小版实验演示"素数域求解 + 有理数重构"是怎么回事,最后聊聊这件事的边界,以及普通科研人和技术爱好者能从中学到什么。
想看完整拆解,往下翻。
一、先把题目看懂:九圈振幅是个什么量级的活
这两天我在无忆研习社的读者群里看到不少人转这条新闻,标题一个比一个吓人。可真要问一句"九圈是什么、为什么难",大多数转发的朋友其实答不上来。我自己是做技术内容出身的,物理只能算半路出家的爱好者,所以这一章我尽量用最朴素的语言,把题目本身讲清楚。题目看不懂,后面所有的"厉害"都是空的。
1.1 散射振幅:粒子对撞的"概率说明书"
先解释一个词:散射振幅。
白话说,两个粒子迎面撞上,撞完以后会飞出什么、往哪个方向飞、各带多少能量,都不是确定的,只能给出概率。散射振幅就是算这个概率用的那个数学表达式,把它取绝对值再平方,就得到某种结果出现的可能性。大型强子对撞机每天记录海量碰撞事件,物理学家就是拿理论算出来的振幅,去和实验测到的分布对照。对得上,说明理论没问题;对不上,就可能意味着有新东西,比如暗物质的线索,或者正反物质不对称的解释。
所以振幅算得越准,实验能"抓出"新物理的灵敏度就越高。这是整个领域的原动力。
1.2 "圈"是什么,为什么每加一圈就难一截
振幅没法一口气精确算出来,物理学家用的是"逐级修正"的思路:先算最粗糙的近似,再一层一层往上叠加修正项。每一层修正,在费曼图里表现为图中多出一个闭合的圈,所以行话里叫"一圈""两圈""三圈"。
你可以把它想成算一个无限级数:
振幅 = 树图(最粗近似)
+ g² × 一圈修正
+ g⁴ × 两圈修正
+ g⁶ × 三圈修正
+ ……
这里的 g 是耦合常数,衡量相互作用有多强。在本文讨论的理论里,常用的约定是 g² = λ/(16π²),λ 叫 't Hooft 耦合。g 越小,高阶项贡献越小,所以只要往后多算几圈,结果就越来越逼近真值。
麻烦在于代价。每多一圈,需要处理的数学对象数量不是线性增加,而是指数级甚至阶乘级膨胀。这次出题的是一位转行做科普写作的前理论物理学家,他在自己的物理博客上明确写过这一点。落到现实中,情况大致是这样:
|
计算场景 |
常见能做到的圈数 |
说明 |
|
真实对撞机的大多数过程 |
两圈,少数三圈 |
粒子种类多、质量不为零,难度极大 |
|
电子反常磁矩(最著名的高精度预言) |
五圈 |
纯电磁过程,结构相对干净 |
|
平面 N=4 超对称杨-米尔斯六胶子振幅 |
2023年到八圈,2026年到九圈 |
"玩具理论",结构极度规整 |
数据来源:Anthropic 官方研究博客原文,写稿时的公开情况。
看这张表你就明白了,九圈这个数字放在真实世界里几乎是天方夜谭,它只可能出现在一个极其"整齐"的理论里。
1.3 杨-米尔斯理论:现代粒子物理的地基
标题里的"杨-米尔斯",指的是杨振宁先生和罗伯特·米尔斯在1954年提出的规范场理论框架。它有多重要?自然界四种基本相互作用里,电磁力、强相互作用(把原子核里的质子中子粘在一起的力)、弱相互作用(引起放射性衰变的力),三种都是用杨-米尔斯型理论描述的。说它是标准模型的骨架一点也不为过。
作为中国读者,看到这个名字多少会有点亲切感。不过得说句实在话:这次计算用的并不是描述真实世界的那个杨-米尔斯理论,而是它的一个"超对称加强版"。
1.4 为什么偏偏挑 N=4 这个"玩具理论"
超对称是一种假想的对称性:它设想每种粒子都有一个"超伴子",电荷相同,但自旋类型不同,把物质粒子和传递力的粒子配成对。N=1 的超对称曾经被寄予厚望,被认为可能解释暗物质。而 N=4 意味着每个粒子有四个超伴子,粒子种类多到离谱,显然不是我们这个宇宙。
那为什么大家还爱用它?原因反直觉:粒子太多,彼此抵消得太干净,计算反而变简单了。它有很多额外对称性,比如所谓的"对偶共形不变性"(可以理解为在动量空间里也有一种缩放、旋转不变的规律),这些对称性把答案可能长成的样子大大收窄。
平面是另一个限定,意思是只考虑色荷数目趋于无穷大时占主导的那部分费曼图,画出来能平铺在纸面上不交叉。这一步又砍掉了一大块复杂度。
所以这个领域的研究者(圈内自嘲叫 amplitudeologist,"振幅学家")把平面 N=4 理论当作试验场:新方法先在这里压力测试,看能推多远,再想办法移植到真实的量子色动力学里去。九圈,就是这块试验场上的一个新标杆。
1.5 六胶子振幅这条线,人类走了多少年
我查了一下这条研究线的公开论文,按时间顺序整理成下面这张图,方便大家对"八圈"和"九圈"有个时间感:
timeline
title 平面 N=4 六胶子 MHV 振幅的圈数推进(公开论文)
2008 : 两圈结果(与 Wilson 圈对偶的检验)
2011 : 三圈,自举法首次用于六边形振幅
2016 : 五圈
2019 : 六圈、七圈
2022 : 三点形状因子推到八圈,对跖对偶正式发表
2023 : 借对跖对偶得到振幅八圈
2026 : 九圈(Claude 与中科院理论物理所团队几乎同期)
从三圈到八圈,一个国际合作圈子用了大约十二年。每前进一圈,都伴随着新的约束条件被发现、新的数学结构被理解。这也是为什么大多数业内人士原本以为,第九圈要么得靠一种全新的思路,要么得砸下远超学术预算的算力。
结果两样都没用上。这就是这次事件最耐人寻味的地方,后面我会反复回到这一点。
二、这道题的门道:自举法其实是一门"先列候选、再逐条排除"的手艺
我第一次读到"bootstrap"这个词在振幅领域的用法时,也是一头雾水。这个词本义是"提着自己的鞋带把自己拎起来",引申为"不依赖外部输入、靠自身约束把答案逼出来"。放在这里,意思是:不去算那成千上万个费曼图,而是先猜答案"长什么样",再用各种物理要求把错误的可能性逐一删掉。
打个我自己觉得更贴切的比方:这像刑侦里的排除法。嫌疑人名单先拉得很长,然后拿不在场证明、监控记录、证人口供一条条去核,最后名单上只剩一个人。更关键的是,侦探手里最好还剩几条没用上的线索,拿来反过来检验这个结论,确认没冤枉人。
自举法就是这么干的。下面拆成三块来讲:候选名单怎么拉、排除规则有哪些、为什么还需要"对跖对偶"这个外援。
2.1 候选名单:符号、字母表与"权重"
平面 N=4 理论里这类振幅有个很漂亮的性质:它们可以写成一类叫"多重对数"的特殊函数的组合。多重对数你可以理解为普通对数 ln(x) 的高阶推广,层层嵌套积分得到。
处理这类函数,物理学家有一个很好用的工具叫符号(symbol)。它把一个复杂函数"拆"成一串串有序的"字母"组成的"单词",每个单词前面配一个系数。比如一个权重为 3 的函数,它的符号可能长这样:
S[f] = 2·(a ⊗ b ⊗ c) − 1/2·(b ⊗ b ⊗ a) + ……
↑单词 ↑单词
这里有几个术语,我用白话过一遍:
- 字母(letter):由粒子动量拼出来的一小组基本变量。六胶子振幅用到的字母表一共只有 9 个字母,这是经过多年研究确认的。
- 单词(word):若干字母按顺序排成的一串,⊗ 可以读作"接着"。
- 权重(weight):单词的长度。L 圈振幅对应的权重是 2L,所以九圈就是长度 18 的单词。
这就引出了第一个震撼的数字。9 个字母、每个位置随便挑,长度 18 的单词一共有多少种?
9¹⁸ = 150,094,635,296,999,121 ≈ 1.5 × 10¹⁷
这个数我是用 Python 直接算出来的。一千五百亿亿个候选单词,每个都要确定一个系数,显然不可能硬来。自举法的全部功夫,就在于用物理约束把这个天文数字压到计算机能处理的规模。
2.2 排除规则:物理要求如何一刀一刀砍候选
这些年研究者积累了一整套"答案必须满足的条件"。我把公开论文里常见的几类整理成表,并尽量用人话说明它们在干什么:
|
约束名称 |
白话解释 |
起到的作用 |
|
第一项条件(first entry) |
单词的第一个字母只能取特定几个 |
源自物理上"奇点只能出现在哪",一刀砍掉大半 |
|
Steinmann 关系及其扩展 |
相邻字母不能随意搭配,某些组合必须避开 |
来自散射理论里关于"重叠通道"的老结论,效果极强 |
|
末项条件(final entry) |
单词结尾的字母也受限制 |
来自超对称带来的特殊微分方程 |
|
共线极限 |
两个粒子动量趋于平行时,答案要退化成已知的更简单结果 |
相当于"边界条件" |
|
近共线展开(通量管 / 五边形 OPE 数据) |
用另一套完全独立的方法算出的展开系数来对答案 |
这是最硬的外部证据 |
|
原点附近的行为 |
在特定运动学点上答案必须呈现已知的简单形式 |
固定残余自由参数 |
|
对称性 |
粒子重新编号、镜像翻转后答案不变 |
减少独立未知数 |
这张表里的条件,有的是几十年前的老物理(比如 Steinmann 关系,最早出自上世纪六十年代),有的是近十年在这条研究线上逐步发现的。你会发现一个规律:每发现一个新约束,就能多往上推一两圈。这也解释了为什么这条研究线的进展是一阶一阶的,而不是连续的。
用流程图来表示自举法的整体套路,大概是这样:
flowchart TD
A[确定字母表<br/>9 个字母] --> B[列出所有可能的单词<br/>长度 = 2 × 圈数]
B --> C[用第一项、Steinmann 等<br/>结构性约束构造"函数空间"]
C --> D[写出候选答案<br/>= 函数空间里的线性组合<br/>系数全部未知]
D --> E[代入物理约束<br/>得到一个超大线性方程组]
E --> F{解是否唯一?}
F -- 否 --> G[引入更多外部数据<br/>如近共线展开]
G --> E
F -- 是 --> H[用剩余未使用的约束<br/>做交叉检验]
H --> I[输出 L 圈振幅]
这里有个概念需要单独说一下,就是图里的函数空间。它是一个"候选答案的集合":满足结构性约束的所有函数,彼此可以线性叠加。空间维度越低,说明约束越紧,未知系数越少。比如这次公开数据里提到,满足扩展 Steinmann 条件的六边形符号空间,到权重 13 时维度是 5431。也就是说,在那一层上,只需要确定几千个独立方向,而不是天文数字般的单词个数。这种"从 10¹⁷ 压到几千"的压缩,正是这门手艺的精髓。
2.3 为什么还需要"对跖对偶"这个外援
2021年底,八圈结果背后的那个国际合作团队在比对两类计算结果时,注意到一个怪现象:六胶子振幅和另一个叫"三点形状因子"的物理量,在某个特殊的运动学曲面上,数字几乎一样,只是单词的字母顺序是倒过来的。
先解释形状因子(form factor):它可以理解为一种"半个振幅",描述的是一个复合算符(这里是应力张量多重态里的一个成员)变成几个粒子的过程。在同样的圈数下,它比六胶子振幅简单不少,所以能先算到更高圈。
再解释对跖映射(antipode):在多重对数的数学结构里,这个操作在符号层面的效果,就是把每个单词前后颠倒。名字借用了地理上的"对跖点",也就是地球上正对面的那一点。
这个对应关系后来被称为对跖对偶。Quanta 杂志2022年报道时提到,它已经在九千三百万项的规模上得到验证。至于它为什么成立,到现在也没有人能从第一性原理解释清楚。这件事本身就很迷人:一个没人理解的对称性,被实打实地当成了计算工具。
它的实用价值在于:
第 1 步:先用自举法算出 L 圈"三点形状因子"(相对容易)
第 2 步:把形状因子的每个单词倒过来读,再做一个简单的变量替换
第 3 步:得到 L 圈六胶子振幅在"Δ = 0 曲面"上的完整信息
第 4 步:把振幅从这个曲面"抬"到一般运动学,剩余少量自由度用其他约束定死
这里的 Δ = 0 曲面,是运动学空间里一个"宇称保持"的特殊切面,可以想成一张大地图上的一条特殊公路,对偶关系只在这条公路上成立。2023年,这个团队就是沿着这四步拿到了八圈振幅。
说到这里,整道题的地形图就画完了。有两条路可以通向九圈:一条是硬着头皮在六边形函数空间里直接自举,业内普遍觉得太重;另一条是沿用2023年的形状因子加对跖对偶路线再推一圈,这个团队自己这两年就在朝这个方向努力,还准备借助他们自训练的 transformer 小模型来预测高圈结构。
而 Claude 的做法是:两条路都走了一遍,而且都走通了。
三、复盘 Claude 的计算过程:一道题,两条路,互相对账
弄懂了地形,再来看 Claude 是怎么走的。这一章我主要依据三份一手公开材料:Anthropic 研究博客上由出题人撰写的长文(含核验教授的附记)、Anthropic 研究员公开的完整结果与验证记录页面,以及中科院理论物理所团队在 Zenodo 上发布的数据集说明。凡是具体数字,我都会标明出处;本章涉及的成本、时间与项数等数据,均可在 Anthropic 官方博客原文或上述结果页面中查到。
3.1 起因:一次"有预算上限"的公开挑战
2026年8月7日,这位出题人在自己的博客上发了一篇文章,大意是:AI 在数学上的进展他看到了,但数学靠的是灵感,灵感难不难找只有找到了才知道;他更想看的是一类"计算上难"的问题,也就是方法大家都知道、但普遍认为算力和时间不够、所以没人做得动的问题。他给出了两个具体目标:N=8 超引力推到七圈,或者 N=4 超对称杨-米尔斯推到九圈。关键附加条件是:只能用一个普通学者负担得起的计算资源。
这个"预算上限"的设定我特别欣赏。它把问题从"谁的机房大"拉回到了"谁更会组织计算"。一个月不到,Anthropic 内部的两位物理学家就联系了他。
3.2 工作方式:一句话题目,加上一句"继续"
根据出题人在官方博客中的描述,两位研究员先问了 Claude 一句:这几个挑战里你最有把握做哪个?然后只给了一个很短的题目描述,大意就是"计算平面 N=4 SYM 中六粒子(六边形)振幅的九圈结果"。之后的主要"指导",就是在下班或睡觉前告诉它:接下来几个小时我不在,你继续干,每隔四到六个小时汇报一次进展。
跑这个任务的环境是 Anthropic 推出的科研工作台 Claude Science。它不是一个新模型,而是套在大模型外面的一层工程外壳,行话叫 harness,核心能力包括持久化的计算内核、可追溯的代码与运行记录,以及把作业提交到集群并调度管理的能力。这类境外服务的使用需遵守国内网络与内容管理相关规定,我这里只做科普层面的介绍。
我自己的体会是,这次成功的一半功劳属于这层工程外壳。一个语言模型本身再聪明,连续工作几天、管理几十 GB 的中间文件、在出错后自己回滚重来,这些都得靠外壳提供的"记忆"和"纪律"。
3.3 路线 A:在六边形函数空间里直接自举
第一条路就是业内原本觉得"太重"的那条:不借助形状因子,直接在六边形函数空间里把九圈符号解出来。
根据 Anthropic 官方博客原文中的数据,这条路线是用 Python 加开源符号计算库 SymPy 完成的,纯计算开销约100美元,相当于 96 个 CPU 连续跑一周。这里有个细节值得玩味:该领域的前辈们习惯用 Maple 或 Mathematica 这类商业符号计算软件。出题人自己也坦言,Claude 可能部分得益于换了工具链、采用了更好的软件工程习惯,但他并不认为这算"超级智能"式的突破。
公开结果页面的描述是:这条直接自举路线得到的单词系数,是在五个不同素数下分别计算、再重构成精确分数,然后用第六个素数做了额外核对。素数计算是怎么回事,我在第四章会用自己跑的实验演示。
这条路线的最终产出,是按照八圈团队早年约定的格式整理的"七重余积"文件(结果页面上的原文名称是 septuple coproducts,即把长度 18 的单词切成一个权重 11 的函数加上后面 7 个单独字母)。余积(coproduct)这个词解释一下:它是把一个长单词从某个位置切开,前半段打包成一个已知的低权重函数、后半段逐字母列出的表示方法。这样既能完整定义结果,又不用把天文数字般的单词逐个写出来。九圈这份文件解压后约 232MB。
3.4 路线 B:先算形状因子,再"翻"成振幅
第二条路是沿着2023年八圈的思路再往上推一圈。公开结果页面上对流程的描述很具体,我按自己的理解整理如下:
flowchart LR
A[九圈三点形状因子<br/>自举求解] -->|三个 31 位素数下<br/>验证为精确有理数| B[形状因子符号<br/>约 2.95 亿项]
B -->|对跖映射<br/>单词倒序 + 变量替换| C[振幅在 Δ=0 曲面上的符号<br/>完整展开约 300 亿项]
C -->|抬离 Δ=0 曲面| D[剩余少量自由方向]
D -->|原点行为 + 双胶子<br/>通量管数据定死| E[九圈振幅符号<br/>424 个五重余积]
图中的几个硬数字,都来自公开结果页面:
- 形状因子符号以 279 个权重为 10 的"八重余积"分量给出,合计 295,186,924 项。
- 映射到振幅一侧、在 Δ=0 曲面上全部展开成长度 18 的单词,非零系数的单词数为 30,024,320,034 个,也就是约 300 亿项。
- 最终振幅符号表示为 424 个五重余积,落在维度 5431 的权重 13 函数空间上,这 424 个分量的秩在两个素数下都是 400。
这里我想特别点一下"抬离曲面"这一步。对跖对偶只在 Δ=0 这条"公路"上成立,要得到振幅在整张"地图"上的样子,还得确定曲面之外的部分。八圈时,这一步最后剩下一个自由方向;九圈时剩下五个方向。Claude 用的是振幅在原点附近的已知行为,外加从有限耦合通量管公式生成的近共线展开数据,把这几个方向全部定死。
这个流程还有一个很重要的"对照实验":公开页面显示,同一套程序先被拿去重做了八圈,抬升结果与2023年已发表的八圈振幅在 1000 个随机非零单词上逐一比对,全部一致。
先复现已知,再挑战未知,这是任何做数值计算的人都该刻在脑门上的纪律。模型自己也遵守了它。
3.5 两条路的交叉验证
两条路线的结果最后对上了没有?公开页面给的答案是:直接自举得到的七重余积文件,由 107,053 个非零系数完全确定;把这十万多个系数和形状因子路线的五重余积表示逐一比对,全部吻合。其中 3,401 个系数只在两个素数的取模意义下比对(因为五重余积那一侧还有少量系数没能重构成精确分数),其余都是精确有理数的比对。
两套方法,底层逻辑不同,中间文件格式不同,数据路径完全独立,最后十万多个数字一个不差。说实话,读到这里我才真正服气。
我把两条路线的对比整理成一张表,方便收藏:
|
对比项 |
路线 A:直接自举 |
路线 B:形状因子 + 对跖对偶 |
|
思路来源 |
2019年六、七圈的方法 |
2023年八圈的方法 |
|
业内原本的预期 |
普遍认为到九圈太重 |
八圈团队正在准备走这条路 |
|
主要工具 |
Python + SymPy |
大规模有限域线性代数 |
|
精确性保障 |
五个素数重构,第六个素数核对 |
形状因子在三个素数下确认为有理数,振幅在两个素数下分别计算 |
|
自检方式 |
多余约束方程 |
先重做八圈并与已发表结果比对 |
|
产出格式 |
七重余积文件,约 232MB |
五重余积表示及大量辅助数据 |
|
估算成本 |
单条路线一两千美元量级,其中计算约100美元 |
同样一两千美元量级 |
成本数据来自 Anthropic 官方博客原文,是按普通用户价格估算的,费用大头是模型长时间运行的开销而非 CPU。相关服务的价格变动较快,这里只是写稿时公开报道的量级,请以官方实时定价为准。
3.6 还有一块"函数层"的结果,需要打个问号
很多报道没提到一个细节,我觉得值得说。
上面讲的都是"符号"层面的结果。符号能决定函数的大部分信息,但会丢掉一些和 π、ζ 值(黎曼 ζ 函数在整数点的取值,比如 ζ(3))相关的项。要得到完整的"函数",还需要把这部分补回来。公开页面也给出了九圈振幅作为完整函数的定义文件,甚至给出了它在特殊点 (1,1,1) 的数值,约为 6.738 亿,九圈与八圈在该点的比值约为 −14.11。
但页面自己写得很坦率:函数层的结果只算了一次,没有第二个独立计算与之对照;并且它依赖一个额外假设,即符号层面成立的某些关系在函数层面也成立。
我特别喜欢这种写法。它没有把所有结果包装成"同样可靠",而是清楚标出了哪部分被交叉验证过、哪部分还只是单次计算。会标注自己不确定的地方,是可信计算的标志,这一点无论是人写论文还是模型交付结果,都一样。
四、我自己跑了一个缩小版:素数域求解和有理数重构到底是怎么回事
前面反复出现"在几个素数下计算,再重构成分数"这种说法,很多读者可能第一次见。我自己一开始也只是字面上懂,后来干脆写了个几十行的小脚本跑了一遍,才算真正理解。这一章就把这个实验原样分享出来,你有 Python 环境的话,五分钟就能复现。
4.1 为什么不用小数或精确分数直接算
自举法最终会得到一个超大线性方程组,未知数是那些单词前面的系数,而真实答案的系数都是分数,比如 −105757/65536 这种(这个数字就是公开页面里给出的一个真实九圈系数)。
如果用浮点小数去解,几万、几十万个未知数的消元过程中,舍入误差会一路累积,最后你根本分不清一个 0.0000001 到底是真的零还是误差。如果用精确分数去解,分子分母在消元过程中会膨胀到几百几千位,内存和时间都扛不住。
业内的标准做法是折中:在素数域上算。白话说,就是所有运算都"对一个大素数 p 取余数"。比如 p = 2147483647(这是 2³¹ − 1,一个常用的 31 位素数),那么所有数都落在 0 到 p−1 之间,永远是一个整数,不会有舍入误差,也不会膨胀。除法怎么办?用"模逆元"代替,也就是找一个数 y,使得 x·y 除以 p 余 1。
4.2 我的玩具实验
我设计了一个极简版本:假装真实答案是一个关于 x、y 的四次多项式,系数是几个我事先设好的分数,但在"求解"时假装不知道它们。然后我只提供两类约束:
- 对称性约束:x 和 y 互换后多项式不变(对应自举法里的"对称性")。
- 边界数据:在十个点上已知多项式的值(对应"其他方法给出的外部数据")。
未知数一共 15 个(四次以内所有单项式的系数),约束方程 16 条,比未知数多一条,多出来的那条就留着做自检。核心代码如下:
def solve(rows, n, p): # 在素数 p 下做高斯消元,所有运算取余
A = [r[:] for r in rows]; rank = 0; pivots = []
for col in range(n):
pr = next((k for k in range(rank, len(A)) if A[k][col] % p), None)
if pr is None:
continue
A[rank], A[pr] = A[pr], A[rank]
inv = pow(A[rank][col], -1, p) # 模逆元代替除法
A[rank] = [a * inv % p for a in A[rank]]
for k in range(len(A)):
if k != rank and A[k][col]:
f = A[k][col]
A[k] = [(a - f * b) % p for a, b in zip(A[k], A[rank])]
pivots.append(col); rank += 1
# 多出来的方程如果化简后不是 0 = 0,说明约束之间有矛盾
conflicts = [r for r in A[rank:] if r[-1] % p]
return A, pivots, rank, conflicts
跑出来的结果是:
未知数 15,约束方程 16,秩 15
多余可用于自检的方程 1,自检失败数 0
秩等于未知数个数,说明解唯一;多余的一条方程化简后是 0 = 0,说明约束之间没有矛盾。这一步对应的就是核验者所说的"算完还要留几条约束检验自己有没有出错"。
4.3 从余数"变回"分数
在素数 p₁ = 2147483647 下,我拿到的 x²y² 项系数是一个看上去毫无意义的大整数:
x²y² 的系数 mod p₁ = 771751934
怎么知道它其实是 −105/64?这就要用到有理数重构:已知一个分数 a/b 除以大数 M 的余数,只要分子分母都比 √(M/2) 小,就能用扩展欧几里得算法把 a 和 b 唯一地找回来。
单个 31 位素数给的空间有限,分子分母稍大就重构不出来。所以做法是在两个(或更多)不同素数下各算一遍,再用中国剩余定理把两个余数拼成一个模 p₁ × p₂ 的数,空间一下子扩大到 6