数论概论读书笔记 19.素性测试与卡米歇尔数

素性测试与卡米歇尔数

素数是整数中优美的一部分,辣怎么判别一个大数是不是素数呢?

费马小定理告诉我们$a^p\equiv a \ (\ mod \ p)$

首先,不满足上式的数,一定不是素数。

但当你尝试了许多$a$之后发现都满足上式,也不能断言$p$就是素数。

对于大部分小的合数$n$,你会发现选取的大部分$a(a<n)$,都不满足费马小定理

但是!还是有一些合数,比如$561=31117$ ,对所有的$0\leq a < 561$ ,发现都满足费马小定理!

下面证明一下,要证明$a^{561}\equiv a\ (mod \ 561)$,只要证明 $$ a^{561}\equiv a\ (mod \ 3) ,\quad a^{561}\equiv a\ (mod \ 11) ,\quad a^{561}\equiv a\ (mod \ 17) $$ 为什么呢?因为若第一个式子成立,则$3 \ |\ a^{561}-a$ ,同理11,17也整除,由于3,11,17互质,则561也整除。

对于第一个式子,若3能整除a,则显然成立;否则,由于$a^2\equiv 1\ (mod \ 3)$ ,则$a^{561}=a^{2280+1}=(a^2)^{280}a\equiv 1*a \equiv a \ (mod \ 3)$

后面两个式子同理。

从而$561$很特殊!

类似这样的数,称为卡米歇尔数。 http://oeis.org/A002997/b002997.txt

一些猜想:

  1. 卡米歇尔数都是奇数
  2. 卡米歇尔数是不同素数的乘积

证明1. 由于$a^n\equiv a \ (mod \ n)$,令$a=n-1$,则可得$(-1)^n\equiv -1 \ (mod \ n)$ 则$n$是奇数。

证明2. 假设卡米歇尔数的任意一个素因子(次幂)为$p^{(e+1)}$ ,下面我们努力证明$e=$0,

将$p^e$带入$a^n\equiv a \ (mod \ n)$,得到$p^{en}\equiv p^e \ (mod \ n)$,所以$n \ | \ p^{en}-p^e$,又$p^{e+1} \ | \ n$,所以$p^{e+1} \ | \ p^{en}-p^e$

从而$e=0$。证毕。

定理19.1(卡米歇尔数的考塞特判别法) 设n是合数,则n是卡米歇尔数当且仅当它是奇数,且整除n的每个素数$p$满足下述两个条件:

  • $p^2 $不整除n
  • $p-1$整除$n-1$ (实际上也整除$\frac{n}{p}-1$)

证明:

  • 充分性: 类似上面证明561是卡米歇尔数。
  • 必要性: 前面已经证明卡米歇尔数是奇数且$p^2$不整除$n$,只要说明$p-1 \ | \ n-1$即可。(用原根比较方便?)

存在无穷多个卡米歇尔数(1994年证明)


卡米歇尔数的存在意味着我们需要更好的素性测试方法。

合数的miller_rabin测试是基于以下事实的:

定理19.2(素数的一个性质) 设$p$是奇素数,记$p-1=2^kq$ ,$q$是奇数,设$a$是不被$p$整除的任何数,则下述两个条件之一一定成立,但满足条件之一的数不一定是素数(卡米歇尔数):

  • $a^q$模$p$余1
  • 数$a^q,a^{2q},a^{2^2q},...,a^{2^{k-1}q}$之一模$p$余$-1$

证明: 费马小定理告诉我们$a^{p-1}\equiv 1\ (mod \ p)$。这意味着对于数表$a^q,a^{2q},a^{2^2q},...,a^{2^{k-1}q},a^{2^kq}$ ,最后一个数模$p$余1,且表中的每个数是前一个数的平方。因此下述两种可能之一必成立:

  • 表中的第一个数模$p$余1
  • 表中的一些数模$p$不余1,但是,当平方时它就模$p$余1,所以该数是$-1(mod \ p)$,即表包含$-1(mod \ p)$

证毕。

定理19.3 miller_rabin测试 设$n$是奇素数,记$n-1=2^kq$,$q$是奇数,对不被$n$整除的某个$a$,如果下述两个条件都成立,则$n$一定是合数:(但有不成立的也不一定是素数)

  • $a^q \not\equiv 1 \ (mod \ n)$
  • 对所有的$i=0,1,2,...,k-1 ,\quad a^{2^iq}\not\equiv -1\ (mod \ n)$

和费马小定理测试相比,miller_rabin测试不存在“卡米歇尔型数”,因为可以保证,如果$n$是奇合数,则1~n-1之间至少有75%的数可作为miller_rabin的证据。即这些数作为$a$时,可以说明其合数性。

换句话说,每个合数都有许多证据来说明它的合数性。

例如随机选取$a$的100个值,若其中没有$n$的miller_rabin证据,则$n$是合数的概率小于$0.25^{100}$





评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)