陶哲轩博客写数学问题时，通常先把对象定义清楚，再给直觉、反例和证明轮廓。把「The AKS primality test」改写成可阅读的中文笔记，重点是：问题在问什么、已知到哪一步、下一步最容易走偏在哪。原站广告、分享条和导航已去掉。

问题在问什么

The Agrawal-Kayal-Saxena (AKS) primality test , discovered in 2002, is the first provably deterministic algorithm to determine the primality of a given number with a run time which is guaranteed to be polynomial in the number of digits, thus, given a large number , the algorithm will correctly determine whether that number is prime or not in time . (Many previous primality testing algorithms existed, but they were either probabilistic in nature, had a running time slower than

The AKS test is of some relevance to the polymath project “ Finding primes “, so 一个常见想法是 I would sketch the details of the test (and the proof that it works) here. (Of course, full details can be found in the original paper , which is nine pages in length and almost entirely elementary in nature.) It relies on polynomial identities that are true modulo when is prime, but cannot hold for non-prime as they would generate a large number of additional polynomial identities, event

已知结果和反例

Our starting point is Fermat’s little theorem , which asserts that

for every prime and every . This theorem suggests an obvious primality test: to test whether a number is prime, pick a few values of and see whether . (Note that can be computed in time for any fixed by expressing in binary, and repeatedly squaring .) If the statement fails for some , then would be composite. Unfortunately, the converse is not true: there exist non-prime numbers , known as Carmichael numbers , for which for all coprime to ( is the first example). So Fermat’s

证明或构造的主线

However, there is a stronger version of Fermat’s little theorem which does eliminate all non-prime numbers. Specifically, if is prime and is arbitrary, then one has the polynomial identity

where is an indeterminate variable. (More formally, we have the identity in the ring of polynomials of one variable over the finite field of elements.) This identity (a manifestation of the Frobenius endomorphism ) clearly implies (1) by setting ; conversely, one can easily deduce (2) from (1) by expanding out using the binomial theorem and the observation that the binomial coefficients are divisible by for all . Conversely, if

阅读时建议盯住的点

(i.e. in ) for some coprime to , then by comparing coefficients using the binomial theorem we see that is divisible by for all . But if is divisible by some smaller prime , then by setting equal to the largest power of that divides , one sees that is not divisible by enough powers of to be divisible by , a contradiction. Thus one can use (3) (for a single value of coprime to ) to decide whether is prime or not.

Unfortunately, this algorithm, while deterministic, is not polynomial-time, because the polynomial has coefficients and will therefore take at least time to compute. However, one can speed up the process by descending to a quotient ring of , such as for some . Clearly, if the identity holds in , then it will also hold in , thus

阅读和落地时建议先做的 5 件事

1. 用自己的语言重写定义和结论，不看原文能不能说清对象是什么。
2. 找一个最小反例或边界情形，确认假设少一条会怎样。
3. 把证明拆成可独立检验的引理，每步只保留一个新想法。
4. 若涉及计算或形式化，先写可复现的小例子，再谈一般情形。
5. 记下尚未解决的缺口：缺估计、缺构造，还是缺正确的范畴。

和智能体、形式化工具怎么接

龙虾PRO做 OpenClaw 落地时，数学笔记最有用的部分往往是「可检验的步骤」：定义、反例、引理边界。智能体适合帮忙展开计算和检索，不适合代替你决定哪条假设能扔。

本文侧重全链路风控方法论。落地时请用自身业务单据做回放验证，不要把示例阈值直接当生产策略。 相关：风控体检 · 方案资源