Primary test using Fermat's 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 prime number theorem. N is the number that should be verified as simple. This program does not show the correct result for "11". Perhaps due to some error that is not identified by me.

Answer 1

You use overflow if it is pseudocode or
If the code is C, use ^as a power statement is not allowed.

Working with large integers is quickly becoming a problem in C. There are various libraries available BigInt.

. double, pow() ..

>= 0, . - unsigned long long. , .

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

(upower(i, N - 1) % N) != 1.

Answer 2

, .

10^10 , 2^31 -1, int. N=11, longs, , - .

, , .

, C, , ^ XOR, . pow(). .

Answer 3

, ,

(i ^ (N-1))% N,

^ (N-1) . (N-1) 2. , .

, , N = 58.

,

N - 1 = 57

57 :

57 = 1 + 8 + 16 + 32

,

57 = 2 ^ 0 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5

, N-1,

(i ^ (2 ^ 0 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5))% 58

,

((i ^ 1) × (i ^ 8) × (i ^ 16) × (i ^ 32))% 58

, , :

((i ^ 1)% 58 × (i ^ 8)% 58 × (i ^ 16)% 58 × (i ^ 32)% 58) mod 58 --- (1)

,

(i ^ 1)% 58 = i% 58

, .

, ,

(i ^ 2)% 58 = ((i ^ 1)% 58 × (i ^ 1)% 58)% 58

(i ^ 1)% 58, (i ^ 2)% 58.

, (i ^ 4)% 58 (i ^ 32)% 58. , , (1), , .

---

Note that there are other modular exponientation methods . This was just an example to demonstrate how modular mathematical methods can be used to implement a small Fermat strength test.

Hurrah!