找到给定区间 [a,b) - C 中的所有 Carmichael 数

Question

我正在使用具有不同功能的数学软件工作，其中之一是在给定区间 [a,b)

中查找所有 Carmichael 数

这是我的代码，但我不知道我是否正确地完成了它，因为我无法测试它，因为最小的 Carmichael 数字是 560，这对我的电脑来说太大了，无法处理。

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

如果不正确，错在哪里？

谢谢

P.S 应防止溢出。

Answer 1

当您说 "This is my code, but I don't know if I have done it correctly or not cause I can't test it since the smallest Carmichael number is 560 which is too big for my pc to process" 时，结论是——您没有做对。您应该能够在几分之一秒内处理 561（560 一定是打字错误）。即使您的算法原则上是正确的，但如果它不能处理最小的 Carmichael 数，那么它也是无用的。

n 是 Carmichael 当且仅当它是复合的，并且对于所有 a 和 1 < a < n 与 n 互素，同余 a^(n-1) = 1 (mod n) 成立。要直接使用这个定义，你需要：

1) 一种测试 a 和 n 是否互质的有效方法

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

的有效方法

对于第一个 -- 使用 Euclidean algorithm 作为最大公约数。它在循环中计算最有效，但也可以通过简单的递归 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，然后通过 mod 结果 n。相反——使用 exponentiation by squaring，在中间阶段取余数 (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;
        }
}

注意在b*b的计算中使用unsigned long long防止溢出。

要测试 n 是否是 Carmichael，您不妨先测试 n 是否是偶数，如果是偶数，则 return 0。否则，逐步遍历 2 到 n-1 范围内的数字 a。首先检查是否 gcd(a,n) == 1 请注意，如果 n 是合数，那么在达到 n 与 gcd(a,n) > 1 的平方根之前，您必须至少有一个 a。保留一个布尔标志，它跟踪是否遇到了这样的 a，如果您超过了平方根而没有找到这样的 a、return 0。对于那些 a 和 gcd(a,n) == 1，计算 mod 平方幂 a^(n-1) (mod n)。如果这与 1 不同，则 return 0。如果您的循环完成检查 n 下面的所有 a 而没有 returning 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 秒就可以到达运行并匹配 this 列表的初始部分。

这可能是一种比较实用的方法，用于检查一百万左右的数字是否是卡迈克尔数字。对于更大的数字，您可能应该给自己一个好的因式分解算法，并使用 Wikipedia entry 卡迈克尔数字中描述的 Korseldt 准则。

找到给定区间 [a,b) - C 中的所有 Carmichael 数

find all Carmichael numbers in a given interval [a,b) - C

c

math

number-theory