2种初等素性测试


(2)之所以想到介绍常用的素性测试,源于与王哲瑫学弟讨论Miller-Rabin算法。特此鸣谢。

(3)我并不轻视应用数学,只要结果是美的,深刻的。当然,通常来说实用与否才是决定性的判据。对此我的辩护词是:解决一个有重大实用价值的难题,这一征服行为本身往往就构成某种美感,所谓pour la gloire de L’esprit humain.

(5)行文中省略的技术细节可以在下面这篇介绍性文章中找到:

Schoof  Four primality testing algorithms

此文还介绍了另外2种常用素性测试:APR算法Atkin-Morain椭圆曲线素性测试。不过,它们背后的数学就远非“初等”的了。有机会的话,我们将另文介绍之。

Wiki上关于素性测试算法的资料经百十人锤炼,同样是可靠的信息源。

这种“提纯”的行为看似毫无必要,实则对己大为有利。而我微薄的愿望,是于人也有些许好处。

(7)\tilde{O}:以f(n)=\tilde{O}(g(n))f(n)=O(g(n)\log^k g(n))k为某常数。

(11)最朴素的素性测试基于Fermat小定理:对于a \in (\mathbb{Z}/n\mathbb{Z})^*a^{n-1} \equiv 1(\mathrm{mod} n)对素数n成立。找到不满足条件的a即排除了n为素数的可能性。利用n-1的二进制分解,对每个a的验证可以在对数级时间内完成。

这个算法的缺陷在于Fermat小定理的逆不真。事实上,存在以a为基的Fermat伪素数甚至绝对Fermat伪素数,后者可以通过一切基于Fermat小定理的测试。

一种可能的改进是Miller-Rabin算法。它基于如下简单事实:给定素数\displaystyle p=2^s d+1\forall a \in (\mathbb{Z}/p\mathbb{Z})^*,(a)对某个r \leq s-1\displaystyle a^{2^r d}=-1或(b)a^d=1

任取a \in (\mathbb{Z}/n\mathbb{Z})^*,若(a)(b)均不成立即可推断出n是合数。反之,能通过这一测试的n称为以a为基的强伪素数。令人欣慰的是不存在绝对强伪素数

这当然仍取决于运气,不过Rabin注意到如下正面结果:n>9时至多有\frac{1}{4}a使得n为以a为基的强伪素数。由此他提出一个随机算法:若n成功通过了十几次随机测试,则有充分的把握断定n为素数。

(13)假定广义Riemann猜想成立,Miller指出只需通过1 <a < 2\log^2(n)的测试即可证明n是素数。这个确定性算法的复杂度为\tilde{O}((\log^4(n)),简单高效。

Miller Riemann’s hypothesis and tests for primality

(17)经典的Solovay-Strassen素性测试基于类似的原理。其数学依据是当n为素数时有Euler恒等式a^{(n-1)/2}=(\frac{a}{n})(\mathrm{mod} n)成立。Euler-Jacobi伪素数出现的概率上界是1/2,因而它远不如Miller-Rabin算法可靠。

(19)2002年,Agrawal, Kayal和Saxena提出了煊赫一时的AKS素性测试。注意到n是素数当且仅当对所有0<k<nn整除\displaystyle \binom{n}{k},换言之,对所有(a,n)=1(x+a)^n \equiv x^n+a (\mathrm{mod} n)。这推广了Fermat小定理。

为降低验证此式的计算量,AKS建议先将左右同时模去某个x^r-1再进行比较。此处的关键是:若素数r选择得当,则仅需验证特定的a即可证明(较弱的)n是素数的幂。确切的条件是:(a)nr的阶至少是\log^2 n;(b)n的素因子均大于r;(c)对0 \leq a<r(x+a)^n \equiv x^n+a (\mathrm{mod} (n,x^r-1))

由此AKS设计了如下算法:(\alpha)若n是某个整数的幂,输出“合数”;(\beta)不断增大r直至满足(a),验证(b),不满足则输出“合数”;(\gamma)若r \geq n,输出“素数”;(\delta)验证(c),满足则输出“素数”,否则输出“合数”。

Agrawal,Kayal & Saxena  PRIMES is in P

(23)结合快速乘法,AKS算法的复杂度为\tilde{O}(\log^{12}(n))。经Lenstra和Pomerance改良后,算法的复杂度为\tilde{O}(\log^{6}(n))

Lenstra,Pomerance  Primality testing with Gaussian periods

AKS算法是第一个(*)不依赖于任何未证明猜想的、(**)多项式复杂度的(***)确定性素性测试算法(对Miller-Rabin算法来说,(*)(***)不可得兼)。3位作者因此赢得了06年的Gödel奖(理论计算机科学)和Fulkerson奖(离散数学)。