My Weblog

Blog about programming and math

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

February 29, 2008 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: