先说结论计算数论这门课最容易让人误判的地方在于——它表面上讲的是数论实际上你要花在代码和复杂度分析上的时间比推导公式多得多。我一开始是奔着把初等数论再夯实一遍去的结果前两周就被大整数底层表示和模幂的常数优化按在地上摩擦。所以这篇记录不打算复述教材目录而是把这门课真正想让你掌握的几条主线、我踩过的具体坑、以及课后能自己复现的代码和思路完整摊开讲一遍。内容覆盖计算数论的学习路径、核心算法素数判定、整数分解、模算术、连分数、格约化、工程实现细节与常见误区适合已经学过一点初等数论、会写基础代码、想系统入门算法数论的同学也适合只是想补一补这些算法到底怎么跑起来的工程读者。1. 从纸上数论到机器数论这门课到底想训练什么很多同学对计算数论的第一印象是数论 编程好像把同余方程用代码解一遍就完事了。真上手才发现不是这么回事。传统数论课关心的是存在性和结构比如某个同余方程是否有解、解集长什么样而计算数论关心的是能不能在有限时间内算出来、要多少位运算、误差概率多大。同一个问题两种视角的答案可能完全不在一个频道。1.1 计算数论关心的三件事正确性、复杂度、随机性我把它粗暴地总结为三个问题。第一是正确性算法给出的结果是不是真的对。这在数论里很微妙因为很多东西是概率性的。比如 Miller-Rabin 素数判定单轮判定会说这个数大概率是素数它给你的其实是一个合数会以多大概率被误判的界。你要接受概率正确这个概念而不是像做数学习题那样追求非黑即白。第二是复杂度不是能算而是算多快。同样是分解一个 100 位的整数试除法要跑几万年而某些专门的方法能在可接受时间内跑完。课上会反复让你分析运算次数而且要区分按比特算还是按机器字算这个区别在实际实现里经常是几倍性能的差距。第三是随机性计算数论里大量算法是随机算法Miller-Rabin、Pollards rho、二次筛都带随机成分。理解它们的期望运行时间、失败概率、以及如何控制这些概率是这门课的隐藏重点课本上往往一笔带过真正写代码时才会发现随机种子选错能让你 debug 一下午。1.2 先修门槛数论、算法、编程三条腿都要站得住我当时的准备情况是初等数论学过同余、二次剩余、原根这些概念有印象数据结构与算法基础有Python 熟练、C 能读。事后看这个组合算刚好够用但每一条都不能太虚。数论这条腿至少要能用得上模逆元存在性判据、欧拉函数与欧拉定理、中国剩余定理、二次剩余的勒让德符号、连分数的基本性质。课上不会重新讲这些而是默认你已经会了直接往上叠算法。算法这条腿重点是复杂度分析的习惯。你得能对着一段伪代码说清它的循环次数是关于哪个变量的多项式或指数函数。很多同学数论很强但一让分析这个循环为什么是 O(√n)就卡壳后面整数分解的内容会很吃力。编程这条腿其实是最容易被低估的。算法课上的伪代码是理想化的懂边界条件但在实际写代码时要处理大整数的表示、溢出、位运算的优先级、递归深度、随机数质量、以及性能剖析。1.3 公开资源与自学路径这门课有配套讲义和作业自学的话不一定非要有课堂录播重点是把讲义里的算法自己实现一遍。我的路径大致是先把讲义当大纲读一遍不纠结细节只标出哪些算法我需要手写。对每个核心算法先照着伪代码写最朴素版本跑通小数据。再用 Python 的 int自带大整数跑中等规模观察时间增长。最后用位运算和常数优化重写关键循环。这条路子在我看来比先啃教材证明更有效因为计算数论的手感来自你亲手把算法从能跑调到跑得快的过程。提示如果你完全没有大整数编程经验建议先别直接冲整数分解而是拿模幂 Miller-Rabin这一对组合练手它牵涉到大整数、模算术、随机化三个核心是很好的切入点。2. 大整数运算与模算术所有上层算法的地基第一次看到实现大整数加法这种作业时我是有点不屑的觉得这不是造轮子吗做完才明白这门课让你实现大整数的真正目的是让你对大整数运算的成本形成直觉。后面所有算法的复杂度分析都是建立在这套成本模型上的。2.1 为什么不能直接依赖语言内置的大整数如果只是把算法跑起来Python 的 int 完全够用一行pow(a, b, m)就把模幂解决了。但课程要求你理解底层原因有两个。一是复杂度分析需要成本模型。你在分析算法复杂度时得知道一次 n 比特的乘法大约要 M(n) 时间而 M(n) 在朴素实现里是 O(n²)在更快的实现里可以到接近 O(n log n)。如果你不知道乘法本身的开销就没法估算法整体的开销。二是有些场景内置类型会坑你。Python 的 int 很方便但在某些算法里你需要显式控制位宽、做定长运算、或者用位运算做快速的模约减内置类型的抽象反而会挡住优化路径。课程里讲 Montgomery 乘法时你会看到这层抽象有多贵。2.2 大整数的表示与加减乘的基本套路大整数的标准表示是以某个基 b 拆成数组比如 b 2³² 时一个数就是若干个 32 位字的序列。加法是从低位到高位逐位相加并处理进位减法借位这些都好理解。乘法则分层次。最朴素的是竖式乘法两个 n 位字数相乘需要 n² 次单位乘法所以是 O(n²)。当数很大时会引入分治的 Karatsuba 算法把 n 位乘 n 位拆成三次约 n/2 位的乘法复杂度降到约 O(n^1.585)。再往上还有基于快速傅里叶变换的方法能把复杂度压到接近 O(n log n)不过那是大数库才会实现的级别课程里通常只要求理解 Karatsuba 的分治思想。我实际写的时候竖式乘法 8 位字以内的数感觉不到差别但把位数拉到几千位后Karatsuba 相对竖式的优势就肉眼可见了。这种自己跑一遍看到差异的体验比看十遍复杂度公式都管用。2.3 模幂为什么它撑起了半本书模幂就是计算 a^e mod m。朴素做法是先算 a^e 再取模但 a^e 会是个天文数字根本存不下。正确做法是平方-乘binary exponentiation把指数按二进制展开遇到位是 1 就乘一次当前的底同时每次把底平方全程都取模。def mod_pow(base, exp, mod): result 1 base % mod while exp 0: if exp 1: result (result * base) % mod base (base * base) % mod exp 1 return result它的循环次数是 O(log e)也就是和指数比特数成正比。这个算法太重要了因为 RSA 加密、Miller-Rabin 素数判定、Pollards p-1、离散对数求解背后都靠它。可以说模幂是计算数论里出现频率最高的子程序没有之一。理解它的关键一步是为什么这样算是对的因为 a^e a^(e₀ 2e₁ 4e₂ ...)每个二进制位对应一次底平方相乘就还原出原指数。这个按位组装结果的思想你在后面几乎所有算法里都会反复见到。2.4 扩展欧几里得、模逆与中国剩余定理求模逆元的经典方法是扩展欧几里得算法。普通欧几里得算的是 gcd(a, b)扩展版额外维护一组系数使得 ax by gcd(a, b)。当 gcd(a, m) 1 时x 就是 a 关于 m 的逆元。def egcd(a, b): if b 0: return a, 1, 0 g, x1, y1 egcd(b, a % b) return g, y1, x1 - (a // b) * y1这里有个实现细节递归写法清晰但深度到几千时可能爆栈实际工程里一般改成迭代。这个坑我在做一道需要连续求逆的题时踩过改成迭代后就稳了。中国剩余定理CRT是把若干个模两两互素的同余式合并成一个模它们的乘积的同余式。它在计算数论里的用途非常广RSA 解密的加速、二次筛法里合并同余关系都用得上。实现时要注意合并过程中涉及模逆而模逆要求模数互素所以合并前必须做互素性检查否则结果没意义。2.5 Montgomery 乘法与 Barrett 约减的思路当你要做大量模乘时每次算(a * b) % m里的取模操作其实很贵。Montgomery 乘法的思路是换一种数表示让模约减可以用移位和乘法廉价地完成。它通过引入一个和模数位数相关的参数 R通常是 2 的幂把数字转换到Montgomery 域里做运算最后再转回来。Barrett 约减则是另一种思路预计算 m 的倒数的近似值用乘法估算商再用减法修正。两者都在大数库和硬件实现里扮演重要角色。课程里讲这部分重点不是让你背公式而是让你看到同样的数学运算换个表示法就能大幅降低开销这种工程直觉。3. 素数判定从试除到 Miller-Rabin 再到 AKS 的认知跳跃素数判定是这门课第一个真正意义上的算法味主题。它的精彩之处在于算法从最朴素的试除一路演化到能在多项式时间内确定判定的 AKS中间每一步都在解决前一步的缺陷。把这个演化链条理顺比单独记住每个算法更有价值。3.1 试除法与费马小定理两个看起来很美的起点试除法最直观拿 2 到 √n 之间的数逐个去试。正确性毋庸置疑但复杂度是 O(√n)对 100 位的数根本不现实。它的价值在于告诉我们判定的成本直接和候选因子的搜索空间挂钩要加速就得跳出线性搜索。费马小定理给了一个漂亮的捷径如果 p 是素数那么对任意 a 不被 p 整除都有 a^(p-1) ≡ 1 (mod p)。反过来如果某个 a 满足 a^(p-1) ≢ 1 (mod p)那 n 一定是合数。这看起来能瞬间完成判定。但问题恰恰出在反过来不成立。存在这样一类合数叫做卡迈克尔数Carmichael 数它们对几乎所有和它互素的 a 都满足费马条件。最小的几个是 561、1105、1729。也就是说你拿费马小定理去测 561它会一路表现得像个素数。这是计算数论里最经典的看着对其实错的教训。3.2 Miller-Rabin把费马条件加严Miller-Rabin 的改进思路是光看 a^(p-1) 是否等于 1 不够还要看它怎么等于 1。具体来说把 p-1 写成 2^s · dd 为奇数然后计算 a^d再反复平方。如果过程中出现了 1 之前不是 -1 的情况那这个 a 就是证人说明 n 是合数。这个判定的正确性分析是这门课的难点之一核心结论是如果一个奇合数 n 通过了以 a 为底的 Miller-Rabin 测试那么 a 是强说谎者的概率不超过 1/4。反复用不同的 a 测 k 轮误判概率就降到 4^(-k)。实际工程里选 k 20 到 40 轮误判概率已经低到可以忽略。import random def miller_rabin(n, k20): if n 2: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True有个细节值得强调对小于某个范围比如 2^64的整数存在确定性的底集合比如大家常用的那组 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}。用这组固定的底去测在 2^64 以内是确定正确的不需要随机。这个技巧在竞赛和工程里非常流行因为它把随机算法变成了确定性算法。3.3 为什么工程上几乎只用 Miller-Rabin现实中的大数库判素数首选 Miller-Rabin或它的变体如 Baillie-PSW原因很务实。第一它快期望复杂度约为 O(k log³ n)对大数是可接受的。第二实现简单核心就是模幂代码量很少。第三误判率可以精确控制40 轮下来比硬件出错的概率还低。那为什么还要讲确定性算法因为概率正确在某些场景是不能接受的。比如你写的是数学证明辅助工具输出的每个素数都要能被严格验证或者你要证明某个算法的正确性就不能依赖概率。这就引出了 AKS。3.4 AKS 与确定性判定理论意义大于实用价值AKSAgrawal-Kayal-Saxena是 2002 年提出的第一个能在多项式时间内确定性判定素数的算法。它的核心是一个多项式同余的判据源自费马小定理的推广n 是素数当且仅当 (x a)^n ≡ x^n a (mod n) 对某个合适的 a 成立。它的理论意义巨大——证明了 PRIMES 属于 P 类。但它的实际运行时间常数非常大比 Miller-Rabin 慢得多所以工程上没人用它。这个理论漂亮、实用拉胯的对比正好呼应了这门课的核心张力正确性和效率常常打架你必须在具体场景里权衡。我个人的体会是AKS 最值得学的不是它的实现而是它展示的如何把一个指数级判定问题通过巧妙的数学变换压进多项式时间的思路。这种思路在计算数论里一再出现后面整数分解也会遇到类似的取舍。4. 整数分解比素数判定难上一个数量级的问题如果说素数判定是确认一个数是不是素数那整数分解就是把一个合数拆成它的素因子。是本课最硬的部分。一个反直觉的事实是素数判定可以在多项式时间内完成但整数分解至今没有已知的多项式时间算法严格说是没有多项式时间的经典算法它的困难性正是 RSA 安全的根基。这种判定容易、分解难的不对称本身就是计算数论最有意思的现象之一。4.1 试除、费马方法与搜索空间的基本直觉试除法是最直接的分