Primality test using Fermat little theorem

Question

code:

void prime()    
{    
    int i,N;    
    scanf("%d",&N);    
    for(i=2;i<N;i++)            
    {    
        if (((i^(N-1))%N )==1);     
        else{    
            printf("not prime");   
            return;
        }     
    }    
    printf("prime");    
    return;    
}    

This program is based on Fermat's Theorem on prime numbers. N is number to be tested as prime. This program is not showing correct result for '11'. Maybe due to some mistake which is not identified by me.

Answer 1

You are running into overflow if this is pseudo-code or
If C code, use of ^ as power operator is not valid.

Working with large integers quickly becomes a problem in C. The are various BigInt libraries available.

Using floating point is challenging with large integer computation. Recommend avoiding double, pow(), etc.

Since the problem is all >= 0, suggest using unsigned integers. Also use the largest integer type available - typically unsigned long long. As overflow is a real possibility, detect it.

unsigned long long upower(unsigned i, unsigned N) {
  unsigned long long power = 1;
  if (i <= 1) return i;
  while (N-- > 0) {
    unsigned long long power_before = power;
    power *= i;
    if (power < power_before) {
      printf("Overflow\n");
      return 0;
    }
  }
  return power;
}

void prime() {
  unsigned i, N;
  scanf("%u", &N);
  for (i = 2; i < N; i++) {
    if ((upower(i, N - 1) % N) != 1) {
      printf("not prime");
      return;
    }
  }
  printf("prime");
  return;
}

In lieu of huge integers, the Chinese remainder theorem may offer an alternative to (upower(i, N - 1) % N) != 1.