费马小定理(算法)

1、费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a(p-1) （mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1费马小定理的历史皮埃尔德费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求，但是这个要求实际上是不存在的。与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2(p-1)1(mod p)，p是一个质数。 假如p是一个质数的话，则2(p-1)1(mod p)成立（这是费马小定理的一个特殊情况）是对的。

2、但反过来，假如2(p-1)1(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了，但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。费马小定理的证明一、准备知识： 引理1剩余系定理2 若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当acbc(mod m)时，有ab(mod m) 证明：acbc(mod m)可得acbc0(mod m)可得(a-b)c0(mod m)因为(m,c)=1即m,c互质，c可以约去，ab0(mod m

3、)可得ab(mod m) 引理2剩余系定理5 若m为整数且m1,a1,a2,a3,a4,am为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。 证明：构造m的完全剩余系（0,1,2,m-1），所有的整数必然这些整数中的1个对模m同余。取r1=0,r2=1,r3=2,r4=3,r=i-1,1i1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,am是模m的一个完全剩余系，则ba1,ba2,ba3,ba4,bam也构成模m的一个完全剩余系。 证明：若存在2个整数ba和baj同余即babaj(mod m)，根据引理2则有aaj(mod m)。根据完全剩余系的

4、定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数ba和baj同余。由引理5可知ba1,ba2,ba3,ba4,bam构成模m的一个完全剩余系。 引理4同余定理6 如果a,b,c,d是四个整数，且ab(mod m),cd(mod m),则有acbd(mod m) 证明：由题设得acbc(mod m),bcbd(mod m)，由模运算的传递性可得acbd(mod m) 二、证明过程： 构造素数p的完全剩余系P=1,2,3,4(p-1)，因为(a,p)=1，由引理3可得A=a,2a,3a,4a,(p-1)a也是p的一个完全剩余系。令W=1*2*3*4*(p

5、-1)，显然WW(mod p)。令Y=a*2a*3a*4a*(p-1)a,因为a,2a,3a,4a,(p-1)a是p的完全剩余系，由引理2以及引理4可得a*2a*3a*(p-1)a1*2*3*(p-1)(mod p)即W*a(p-1)W(modp)。易知(W,p)=1，由引理1可知a(p-1)1(modp） 费马小定理在数论中的地位费马小定理是数论四大定理（威尔逊定理，欧拉定理(数论中的欧拉定理，即欧拉函数)，中国剩余定理和费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（见于词条“欧拉函数”）。 费马小定理的实际应用如上所述，中国猜测只有一半是正确的

6、，符合中国猜测但不是质数的数被称为“伪质数”。 对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法： 如果对于任意满足1 b p的b下式都成立： b(p-1)1(mod p) 则p必定是一个质数。 这个定理告诉我们，判定一个数是否为质数，没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。 事实上，测试小于p的平方根的所有质数就可以了。 这个算法的缺点是它非常慢，但是实现简单；很适合在计算机上面运行程序进行验算一个数是否是质数，不过这种方法并不是实际工程中采用的判定方法。C语言中实现Miller-Rabin素性判定的算法#include #include #inclu

7、de bool Btest(int a,int n) int i,d=1,x; for(i=(int)ceil(log(double)n-1)/log(2.0)-1;i=0;-i) x=d; d=(d*d)%n; if(1=d)&(x!=1)&(x!=n-1)return 1; if(n-1)&(10)d=(d*a)%n; return(d!=1); bool Rabin_Miller(int n,int s) int j,a; for(j=0;js;+j) a=rand()*(n-2)/RAND_MAX+1; if(Btest(a,n)return false; return true; i

8、nt main() int a,n; bool result; result=Rabin_Miller(a,n); if (result) printf(yes); else printf(No); 附：若此算法要求以不超过e的概率出错，那么main()中n的值（测试次数）应为n=lg(1/e)/2向上取整。 Pascal版本的MillerRabbin 方法：如果a(n-1)=1 (mod n) （a为任意0 do begin if (p and 1=1) then ans:=(ans mod k)*(t mod k) mod k; t:=(t mod k)*(t mod k) mod k; p:=p1; end; exit(ans); end; function miller_rabbin(n:longint):boolean; var i:longint; begin if n=1