math - 使用 Pari 的卡迈克尔数

Question

尝试编写 Pari 代码来解决上述问题。

Answer 1

我没有使用 Pari 的经验，但这里有一些有用的建议：

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. 取而代之的是 -通过平方使用取幂n，在中间阶段取余数（mod ）。它是一种基于观察结果的分治算法，例如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。首先检查 ifgcd(a,n) == 1注意 if是复合的，那么在达到with的平方根之前你n必须至少有一个。保留一个布尔标志，用于跟踪是否遇到过这样的情况，如果超过平方根而没有找到这样的情况，则返回。对于那些，计算模幂。如果这与 1 不同，则返回。如果您的循环完成以下所有检查而不返回angcd(a,n) > 1aa0agcd(a,n) == 1a^(n-1) (mod n)0an0，那么数字是 Carmichael，所以返回 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 秒的时间来运行并匹配此列表的初始部分。

这可能是一种比较实用的方法，用于检查高达一百万左右的数字是否是卡迈克尔数。对于较大的数字，您可能应该让自己获得一个好的因式分解算法并使用 Korseldt 的标准，如Wikipedia entry on Carmichael numbers 中所述。