Miller Rabin Primality Testing Algorithm in C language

1. This algorithm is a monte carlo algorithm used for testing whether a given number is a prime or not. 
2. This works much better than fermat's theorem.
3. This algorithm is likely to give false positive in case of Carmichael numbers.
4. The code implementation given below will not work with any number less than three.
5. This code contains a large number of commented out printf statements which i added during debugging. However I decided against removing them as I though it might help some one whose trying to understand the working of the algorithm. 

 

Note

Incase you are using linux and facing this problem:-

gcc prime.c
/tmp/ccV8KwrW.o: In function `correctness':
prime.c:(.text+0x100): undefined reference to `pow'
collect2: error: ld returned 1 exit status

I suggest using
gcc prime.c -lm -o prime

This due to the linking process. Refer :- http://stackoverflow.com/questions/5248919/c-undefined-reference-to-sqrt-or-other-mathematical-functions

Code

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TRUE 1
#define FALSE 0

 int prime( int n,int a){
 int i,temp;
 int power=n-1;
 int z,y,testnum;
 for(i=1;i<=a;i++){
  z=1;y=1;
  testnum=(rand()%(n-2))+2;
  //printf("\ntesting number\t%d",testnum);

  z=testnum;
  while(power>0){
   while(power%2==0){
    //printf("value of even power is %d\n",power);
    //printf("It is div by 2\n");
    temp=z;
    //printf("Value of z is %d",z);
    z=(temp*temp)%n;
    //printf("Updated value of z is%d\n",z);
    power/=2;
    //printf("updated power is %d",power);
    if(z==1&&temp!=n-1&&temp!=1){
     //puts("false here");
     return FALSE;}
   }
   //printf("Value of odd power is %d\n",power);
   power-=1;
   //printf("value of z is %d\n",z);
   //printf("value of y is %d\n",y);
   //printf("Value of y*z is%d\n",(y*z));
   y=(y*z)%n;
   //printf("The value of y currently is %d",power);
  }
  if(y!=1){
   //puts("fffalse");
   return FALSE;} //fermat's theorem
 }
 return TRUE;
}
double correctness(int a){
 return pow(0.5,a);

}

int main(void) {
 long long unsigned int n;
 int a;
 srand((unsigned)time(NULL));
 puts("Prime Number Testing");
 puts("Based upon Rabin-Miller Algorithm");
 puts("A program by Abhishek Munagekar"); /* prints A program by Abhishek Munagekar */
 puts("For Programing Wonders");
 //printf("%llu\n",rand());
 puts("Enter the number for which primality is to be tested");
 scanf("%llu",&n);
 puts("Enter the value for accuracy parameter");
 scanf("%d",&a);
 puts("Probability of false positive is \t="); //it refers to the probability of a number  
 printf("%lf\n",correctness(a));   //not being reported as a prime
 if(prime(n,a)==TRUE)
  puts("it is a prime number");
 else
  puts("not a prime number");

 return EXIT_SUCCESS;
}