MillerRabin素数测试

#include <iostream> #include "mmath.h" #include "random.h" using namespace std; bool witness(int n,int a) { int m = n-1,t = 0,u; while(m%2==0) t++,m/=2; u = m; int x = MMath::power(a,n,u); int y; for(int i=1;i<=t;i++){ y = (x*x)%n; if(y==1&&x!=1&&x!=n-1) return true; x = y; } if(y==1) return false; else return true; } bool mr(int n,int t) { while(--t!=0){ Random *r = new Random(); if(witness(n,r->random(2,n-1))) return false; } return true; } int main() { while(1){ int n; scanf("%d",&n); if(mr(n,10)) printf("n is a prime\n"); else printf("n is not a prime\n"); } return 0; }