数论学习笔记(2):米勒-拉宾素性测试

作者:氯化钡和硫酸银

时间:2014年2月4日 11:05

来源:http://blog.sina.cn/dpool/blog/s/blog_a661ecd50101ax7f.html

素性测试,通俗点说就是判断一个正整数是不是素数。

判断素数最朴素的方法当然是去试除,不过这个方法…如果要判断一个正整数 n是不是质数(有可能有几十位,甚至几百位),试除法要尝试大约根号 n 个正整数,看是不是 n 的约数。这显然太慢了。

我们希望能找出一个关于 n 的位数的多项式的算法。当然,我们并不一定要把待判断的数进行分解。

费马小定理的内容是:若 p 为素数,则对任意正整数 a 有

当然,这与a^(p-1)≡1(mod p) 是等价的(后者要求 a,p 互素)。现在我们假设 p 是任意正整数,如果我们发现对于某个特定的 a,这个式子不成立了,那么 p 不可能是素数。

这无疑为判断素数提供了一个很好的方法:对于待判断的数 p ,我们取一个 a 值(比如说 2 ),计算一下 a^p 与 a 是否模 p同余。如果不同余,那么 p 一定不是素数。

计算a^p mod p (因为我们只需要模 p 的余数)并不会很慢,可以用快速幂的方法计算。先将 p表示成 2k 或 2k+1 的形式,其中 k 为非负整数,然后递归计算出 a^k 的值,再平方,如果 p=2k+1 则需要再乘以一个a ,每次递归时指数减半,所以用时大约与 p 的位数成正比(若考虑每次平方约需要 p位数平方的时间,则用时大约与 p 的位数的三次方成正比),这是可以承受的。计算时可以边算边模 p 避免出现很大的数。

下面我们再看一个问题:如果 a^p≡a(mod p) 成立,那么 p是否一定是素数?如果是的话,那就省事了,可惜事实不是这样的。先举出一个反例:下式

是成立的(很容易计算 2^10=1024=3*341+1 ,于是 2^10 除以 341 的余数是 1 ,再算个 34次方也是除以 341 余 1 的数),但是 341=11*31 并不是素数。这种数告诉我们快速的素性测试并没那么简单。

不过我们还有补救的措施:我们多选择几个底数 a ,只要有一个不满足费马小定理的那个式子,就直接判断 p不是素数。这个方法的前提是,对于每个合数 p 都有足够多的可以证明 p是合数(即不满足费马小定理的那个式子)的“证据”,这样我们才可以在找不到证据时很确定地说 p 就是质数。

令人又一次失望的是,居然就有这样的合数 p ,它没有任何证据!比如说, 561=3*11*17 是个合数,但是对于任意整数 a,下式都是成立的:

(可以根据费马小定理验证 a^561 与 a 模 3,11,17 时都是同余的,从而上式成立)这样用这个式子随机取底数 a是没法确定 561 是合数的。如果用另一个式子,即 a^560≡1(mod 561) ,那么如果 a 与 561互质,这个式子也是成立的。

一般我们把不存在任何“证据”(对任意整数 a ,都有 a^n≡a(mod n) )的合数 n 称为卡米歇尔数。

如果 a 与561 不互质,当然就可以判定 561 是合数。看起来这个概率也不小,不过这是因为 561这个数太小了,如果换成三个大素数相乘,乘积也是卡米歇尔数,那么随机取的底数恰好与这个数有公共的素因子的概率就太小了。例如《数论概论》第19 章末尾给的例子: 172947529=307*613*919 是卡米歇尔数。

卡米歇尔数虽然很稀有,但是足以让朴素的费马测试不被广泛应用。

在叙述米勒-拉宾素性测试之前,先来看看卡米歇尔数的一个判别法——考塞特判别法:

设 n是合数,则 n 是卡米歇尔数当且仅当:

1. n 为奇数;

2. n 不是任意奇素数平方的倍数;

3. n 的任意素因子减去 1 都是 n-1 的约数。

我们先证明满足这三个条件的合数均为卡米歇尔数,这是比较简单的:假设 n 的某个素因子为 p ,而 a 是任意整数。如果 a 是 p的倍数,则 a^n≡a(mod p) 显然成立;如果a不是p的倍数,由费马小定理得 a^(p-1)≡1(mod p) ,由 p-1 是 n-1的约数,可得 a^(n-1)≡1(mod p) 即 a^n≡a(mod p) 。

总之,对 n的任意素因子 p ,都有 a^n≡a(mod p) 恒成立。又 n 的各个素因子显然互质,把各个素因子相乘(注意这里用到了第 2条,也就是说 n 的分解中每个素因子仅出现一次),于是 a^n≡a(mod n) 成立。

下面证明所有卡米歇尔数都满足这三个条件,证明的思路是在 a^n≡a(mod n) 中取 a 的特殊值。

对于第一条,取a=-1 ,则有 (-1)^n≡-1(mod n) ,于是 n 只能为奇数。

对于第二条,设 p为 n 的一个素因子,再设 p^(t+1) 为整除 n 的最大的 p 的幂(即 p 的 t+1 次方能整除 n ,但 t+2次方不行)。取 a=p^t ,则有

最后一个式子两边约去 p^t ,得到 p^(nt-t)-1 是 p 的倍数,所以只能有 nt-t=0 ,也就是说 t=0 。这就证明了p^2 不是 n 的约数。

对于第三条,设 p为 n 的一个素因子,由于每个素数都有原根(对于大于 1 的整数 m ,若存在与 m 互素的整数 g 使得g^1,g^2,…,g^φ(m) 两两模 m 不同余,则 g 为 m的一个原根。原根的一个性质是,若它的某个非负整数次方模 m 余 1 ,则指数一定是 φ(m)的倍数。关于原根的问题下一篇文章中会详细讨论),设 p 的一个原根为 g ,并取 a=g ,则 g^n≡g(mod n),进而有 g^n≡g(mod p) ,这样就得到 n-1 一定是 φ(p)(即 p-1 )的倍数。

现在回到米勒-拉宾素性测试。这种测试在费马小定理的基础上做了个小改进:

验证a^(p-1)≡1(mod p) 之后,将指数 p-1 不断除以 2 ,并计算 a 的幂模 p 的余数,若某一步的余数为 1,但再下一步 后的余数不为正负 1 ,则 p 一定为合数。当指数为奇数或余数变为 -1 时结束。

实际上我们利用了一个小结论:若 x^2 模素数 p 的余数为 1 ,则 x 模素数 p 的余数为 1 或 -1 。证明很简单,因为x^2-1 是 p 的倍数,所以 x+1,x-1 必有一个是 p 的倍数(这里用到了 p 是素数),结论就出来了。

这种改进的测试虽然仍然有判断不出合数的可能性,但是我们可以证明:如果 n 为奇合数,则在 1,2,3,…,n-1 中至少有3/4 的数可以作为 n的“拉宾-米勒证据”。证明过程略。这样每次测试时只需随机选取很多个底数,就可以保证判错的可能性很低。

实际运算时我们通常倒着算,每次指数乘 2 。这样只需逐次平方。设待判断的数为 n ,则先将 n-1 不断除以 2,直到变为奇数,即 n-1=2^k*t ,然后每次在 1,2,3,…,n-1 内选取一个底数 a ,并计算 a^t(mod n)的值,若不为正负 1 则平方。如果先得到 1 (而没有经历 -1 这一步)则可以断定 n 为合数。或者平方到最后发现 a^(n-1)模 n 不等于 1 则由费马小定理也可以断定 n 是合数。

下面不妨举几个例子。

以 2 为底数测试341 时,先计算出 341-1=2^2*85 。运算过程如下:

2^85≡32(mod 341)

2^170≡1(mod 341)

于是可以断定341 不是素数。 2 就是 341 的“拉宾-米勒证据”。

以 2 为底数测试561 时,先计算出 561-1=2^4*35 。运算过程如下:

2^35≡263(mod 561)

2^70≡166(mod 561)

2^140≡67(mod 561)

2^280≡1(mod 561)

所以 561也不是素数。

为了说明问题,借用一下《数论概论》的最后一个例子,判断 172947529是不是素数(这个就是上文提到过的某个卡米歇尔数)。 先计算 172947529-1=2^3*21618441 。

接下来先取底数为17 进行测试:

17^21618441≡1(mod 172947529)

所以 17不是“拉宾-米勒证据”。再换一个底数 3 试一试:

3^21618441≡-1(mod 172947529)

所以 3也不是“拉宾-米勒证据”。再用底数 23 试一试:

23^21618441≡40063806(mod 172947529)

(23^21618441)^2≡2257065(mod 172947529)

(23^21618441)^4≡1(mod 172947529)

这时可以断定172947529 不是素数。

相关文章:

发表评论

您的电子邮箱地址不会被公开。