首先先分享我的代码来源博客：
米勒拉宾定理
费马小定理
这两个博客对费马小定理和米勒拉丁定理讲的都是非常清楚的。其中费马小定理那篇博客里面也讲了如何对代码进行优化，我觉得讲的非常的清楚并且很容易理解。大家如果想要对这两个定理有更深的理解的话，可以先去这两篇博客看一下。
下面就是我对这两个定理的理解：
首先是费马小定理：如果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;}
最后如果大家想对费马小定理和米勒拉宾定理有更深的理解的话，也想希望对代码进行进一步的优化的话，也可以参考上面两位大佬的博客。
