Find all the Karmaychel numbers in the given interval [a, b) - C

Question

I work in mathematical software with various functions, one of which is to find all Carmichael numbers in a given interval [a, b)

This is my code, but I don’t know if I did it right or didn’t call it. I can not test it, because the smallest number of Carmichael is 560, which is too large for my computer.

#include <stdio.h>

int main() {

  unsigned int begin, end;

  printf("Write an int (begin):\n");
  scanf("%d", &begin);

  printf("Write an int (end):\n");
  scanf("%d", &end);

  int i;

  for( int i=begin; i<end; i++ ) {

    long unsigned int a_nr = i-1;

    int a[a_nr];

    for( int j=0; j<a_nr; j++ ) {
      a[j] = j;
    }

    unsigned long c_nr[a_nr];

    for( int k=0; k<a_nr; k++ ) {
      unsigned long current_c_nr;
      int mod;
      for( int l=0; l<i; l++ ) {
        current_c_nr= current_c_nr * a[k];
      }
      mod = current_c_nr%i;
      if( mod==a[k] && mod!=a[k] ) {
        c_nr[k] = i;
      }

    }

  }

  return 0;
}

If this is not true, where is the error?

thanks

PS Overflow should be prevented.

Answer 1

" , , , , Carmichael 560, ", - . 561 (560 ) . , , .

n Carmichael , , a 1 < a < n, n, a^(n-1) = 1 (mod n). , :

1) , a n

2) a^(n-1) (mod n)

- . , gcd(a,b) = gcd(b,a%b) gcd(a,0) = a. C :

unsigned int gcd(unsigned int a, unsigned int b){
    return b == 0? a : gcd(b, a%b);
}

- , a^k (mod n), - a^k n. , (mod n) . , , , a^10 = (a^5)^2 a^11 = (a^5)^2 * a. C:

unsigned int modexp(unsigned int a, unsigned int p, unsigned int n){
    unsigned long long b;
    switch(p){
        case 0:
            return 1;
        case 1:
            return a%n;
        default:
            b = modexp(a,p/2,n);
            b = (b*b) % n;
            if(p%2 == 1) b = (b*a) % n;
            return b;
        }
} 

unsigned long long b*b.

, n Carmichael, , n , 0 . , a, 2 n-1. , gcd(a,n) == 1 , n , a, n gcd(a,n) > 1). , , a, , a, 0. a gcd(a,n) == 1 a^(n-1) (mod n). - 1, 0. a n 0, Carmichael, return 1. :

int is_carmichael(unsigned int n){
    int a,s;
    int factor_found = 0;
    if (n%2 == 0) return 0;
    //else:
    s = sqrt(n);
    a = 2;
    while(a < n){
        if(a > s && !factor_found){
            return 0;
        }
        if(gcd(a,n) > 1){
            factor_found = 1;
        }
        else{
            if(modexp(a,n-1,n) != 1){
                return 0;
            }
        }
        a++;
    }
    return 1; //anything that survives to here is a carmichael
}

:

int main(void){
    unsigned int n;
    for(n = 2; n < 100000; n ++){
    if(is_carmichael(n)) printf("%u\n",n);
    }
    return 0; 
}    

:

C:\Programs>gcc carmichael.c

C:\Programs>a
561
1105
1729
2465
2821
6601
8911
10585
15841
29341
41041
46657
52633
62745
63973
75361

2 .

, , , . , , , Wikipedia entry .