modular.rar

#include <iostream.h> #include <math.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <time.h> int ModularExponentiation(int a,int b,int n) { int c,d; char bin[64]; int length; c=0; d=1; itoa(b, bin, 2);//转化为2进制并以字符形式存在bin[]数组中 // printf("integer = %d string = %s\n", b, bin); length=strlen(bin); cout<<endl<<bin<<endl; // cout<<length<<endl; for(int i=0;i<length;i++) { c=2*c; d=(d*d)%n; if(bin[i]=='1') { c=c+1; d=(d*a)%n; } // cout<<"b"<<i<<"="<<bin[i]<<endl; } return d; } bool Witness(int a,int n) { int u=0,t=1; int tmp;/*用来暂存2的t次方的值*/ int *x; while(1) { tmp=(int)pow(2,t); if(n-1<tmp) return 1; if((n-1)%tmp==0&&((n-1)/tmp)%2==1) { u=(n-1)/tmp; break; } t++; } x=new int[t+1]; x[0]=ModularExponentiation(a,u,n); for(int i=1;i<=t;i++) { x[i]=x[i-1]*x[i-1]%n; if(x[i]==1&&x[i-1]!=1&&x[i-1]!=n-1) {delete []x;return true;} } if(x[t]!=1) {delete []x;return true;} delete []x; return false; } int MillerRrabin(int n,int s) { int a; srand(time(NULL)); if(n==2) return 1;/*如果是2直接返回1*/ for(int j=1;j<=s;j++) { if((a=rand()%n)==0) a=1; if(Witness(a,n)) return 0;/*不是素数5*/ } return 1;/*是素数*/ } void main() { //int a=4; int n=0; int s=0; while(1) {//为实验方便在死循环中测试 cout<<"n="; cin>>n; cout<<"s="; cin>>s; cout<<"输入了："<<n<<" "<<s<<endl; cout<<"MillerRrabin测定："<<((MillerRrabin(n,s)==1)?"是素数":"是合数")<<endl; cout<<endl<<"重新测试..."<<endl; } }