# My Weblog

## 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;
}
}
```