首先先分享我的代码来源博客:
米勒拉宾定理
费马小定理
这两个博客对费马小定理和米勒拉丁定理讲的都是非常清楚的。其中费马小定理那篇博客里面也讲了如何对代码进行优化,我觉得讲的非常的清楚并且很容易理解。大家如果想要对这两个定理有更深的理解的话,可以先去这两篇博客看一下。
下面就是我对这两个定理的理解:
首先是费马小定理:如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。
什么意思呢?
简单来说就是如果p是一个质数的话,那么对于任何一个小于p的数来说,a^(p-1)模p的值为1。
在最上面给的博客里,那位大佬写了他的代码,我截取了大佬的代码,并改了他的输出:
long long fermat(long long a,long long n,long long m){if(m==0){return 1;}else{if(m==1){return a;}else{if(m%2==0)return (fermat(a,n,m/2)%n*fermat(a,n,m/2)%n)%n;elsereturn (fermat(a,n,m/2)%n*fermat(a,n,m/2)%n*a)%n;}}}
这只是费马小定理部分的代码。其中假设p为素数的话,那么p-1(当p!=2时)必须是一个偶数。利用迭代对来对a^m模p计算,得到最后的结果。
而对于米勒拉宾素数定理来说:上面那篇博客也写得非常详细。
按照我的理解就是计算若p为素数,那么对于任何一个a(0<a<p)的数来说,一定有下列定理成立:若a^ 2 ≡ 1(mod p) 的 a的值 只可能等于1或 p-1,如果不是这两个数的话,那a就不是素数。
那么这样是不是就意味着我们必须对于所有小于p的数都要计算一遍了?这样来说运算量会很大,也不利于代码的运行。但是经过了费马小定理我们得知:其中假设p为素数的话,那么p-1(当p!=2时)必须是一个偶数。并且也有:任何一个偶数都可以表示为2^n*q
这样的形式,那么我们对于a的值来说,就会有(a^q)^2^n
,那么这个问题就转换为k=a^q在k的次方运算中,会不会出现k^(z^n-m)
的值模p为一,如果出现,那么不论m的值为多少,k都可以经过偶数次运算来使得最后出现(p-1)^2%p
的值为1。也就是说,我们随便找一个数a只要这个数小于p,并且最后符合这样的条件的话,那么我们就认为这个p是一个素数。对于我们随意找的数,如果p都能满足这样的要求的话,那么p为伪素数的概率就会非常的小,我们就近似的认为他是素数。
下面的也是最上面博客中大佬写出的代码,不过我稍微把代码该的更简单了一点:
bool rabbin(long long a,long long n){long long r=0,s=n-1;while((s&1)==0){ //计算p-1是多少的2次方 s>>=1;r++;}long long k;long long res=1;while(s){if(s&1)res=(res*a)%n;s>>=1;}k=(res+n)%n;if(k==1) return n;for(int i=0;i<r;i++,k=k*k%n){if(k==n-1) {return n;}}return 0;}
那么最后就是全部的代码,其中也包括了我们随机生成数字来自动化生成大素数的功能:
#include <iostream>#include<stdlib.h>#include<time.h>using namespace std;long long fermat(long long a,long long n,long long m){if(m==0){return 1;}else{if(m==1){return a;}else{if(m%2==0)return (fermat(a,n,m/2)%n*fermat(a,n,m/2)%n)%n;elsereturn (fermat(a,n,m/2)%n*fermat(a,n,m/2)%n*a)%n;}}}bool rabbin(long long a,long long n){long long r=0,s=n-1;while((s&1)==0){ //计算p-1是多少的2次方 s>>=1;r++;}long long k;long long res=1;while(s){if(s&1)res=(res*a)%n;s>>=1;}k=(res+n)%n;if(k==1) return n;for(int i=0;i<r;i++,k=k*k%n){if(k==n-1) {return n;}}return 0;} int main(){long long a=0,a1=0;clock_t start,start1,finish,finish1;double totaltime,totaltime1;start=clock();for(long long n=1116500;n<=30000000;n++){srand((unsigned)time(NULL));for(int i=0;i<4;i++){a=a+rand();a=a<<16;}a=a%n;if(a<2)a=2;if(fermat(a,n,n-1)==1){cout<<"素数是 "<<n<<endl;cout<<"a"<<a<<endl; break;}} finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<endl<<"费马小定理的运行时间是"<<totaltime<<endl;a=0;start1=clock();for(long long n=1116500;n<=30000000;n++){srand((unsigned)time(NULL));for(int i=0;i<4;i++){a=a+rand();a=a<<16;}a=a%n;if(a<2)a=2;if(rabbin(a,n)){cout<<"素数是"<<n<<endl;break;}}finish1=clock();totaltime1=(double)(finish1-start1)/CLOCKS_PER_SEC; cout<<endl<<"拉宾定理的运行时间是"<<totaltime1<<endl;return 0;}
最后如果大家想对费马小定理和米勒拉宾定理有更深的理解的话,也想希望对代码进行进一步的优化的话,也可以参考上面两位大佬的博客。