FermatPrimalityTest

FermatPrimalityTest.c

#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

// Test primality of number
//
// n - Number to test primality
// k - Number of times to test n
//     If k <= 0 then the prime number theorem (1/ln(n)) is used 
//     to give best guess without checking 
//
// Example 
//    FermatPrimalityTest(7,2);
//    # => 0.75
//
// Returns probability of primality


float FermatPrimalityTest(int n, int k ){
  // If k < 0 then 1/ln(n) is my best guess without checking
  if ( k <= 0)
    return 1/log(n);

  float p = 0.5;
  srand(time(NULL)); // Set the seed

  int i;
  for(i=0; (i<k)&&(p!=0); i++){
    int ran = (rand() % (n-1))+1;
    int a = pow(ran,n);
    if( a%n == (ran%n) ) 
     p *= p;
    else
      p = 0; 
  }
  return (p==0) ? 0 : (1-p);
}