## RabinMIller Primality Test

Every one who is interested in programming used deterministic primality testing algorithm but have you ever think if a number is as big as 2^63-1(almost 10^18 ) and sqrt will be 10^9 which will be almost timeout if we have more than 1000 numbers to check primality. Here is the probabilistic method comes into picture. You run this code(Rabin Miller ) and if fails for some input kindly tell me so you check it for other bases.

unsigned long long mulmod(unsigned long long a,unsigned long long b,unsigned long long c) { unsigned long long x=0,y=a%c; for(;b>0;b=b/2) { if(b&1) x=(x+y)%c; y=(y*2)%c; } return x%c; } unsigned long long mul(unsigned long long a,unsigned long long n,unsigned long long c) { unsigned long long ret=1; for(;n>0;n=n/2) { if(n&1) ret=mulmod(ret,a,c); a=mulmod(a,a,c); } return ret%c; } bool Miller(unsigned long long n) { if(n==2) return true; if(n<=1 || n%2==0) return false; unsigned long long p=n-1,s=0,r; while(p%2==0) { s++; p=p/2; } //printf("s=%llu t=%llu\n",s,p); r=p; //for(int i=1;i<=20;i++) { unsigned long long a=(random()%(n-1))+1; unsigned long long y=mul(a,r,n); if(y!=1 && y!=n-1) { unsigned long long j=1; while(j<=s-1 && y!=n-1) { y=mulmod(y,y,n); if(y==1) return false; j++; } if(y!=n-1) return false; } } return true; } int main() { unsigned long long v,t=1LL<<63; //scanf("%llu",&t); int count=0; while(t--) { //scanf("%llu",&v); if(Miller(t)) printf("%llu\n",t),count++; /*else printf("NO\n");*/ if(count==100) break; } }

Advertisements

No comments yet.

## Leave a Reply