卡迈克尔素数

基于DASCTF April 2023 babyhash中的proof_of_work,对卡迈克尔素数进行简要探讨。

还想着有什么非预期，结果连proof都过不了，紫砂了😅。

定义

卡迈克尔数的定义是对于合数n，如果对于所有与n互质的正整数b，都有同余式$b^{n-1}≡ 1 (mod n)$成立，则称合数n为Carmichael数。

实现

当然这里我们的$(r_1,r_2,r_3) = (1,2,3)$

def universal_forms(SEED, l):
    coeffs = [6,12,18,36,72,144,288,576,1152,1728]
    coeffs = coeffs[:l]
    while True:
        ps = [c*SEED + 1 for c in coeffs]
        if all(isPrime(p) for p in ps):
            return ps, SEED + 1
        SEED += 1

证明

论文链接 ,在 universal forms这一行。这里我们先讨论一下因子数为3的情形。

定理1，也就是费马小定理。

定理2，以下是定理二的证明。

通过在同余式进行一下简单的代数变换，得到式（5）

得到k的通解

在得到k通解的情况下，我们得到通式

example

如果$(r_1,r_2,r_3) = (1,2,5)$ , $k = 10M -8*17^3 \equiv 10M +6 \mod(10) $

那么我们得到的通式就为$U_3 = (10M+7)(20M+13)(50M+31)$

归纳

那么$n>3$时呢？paper里也给出了派生的性质。

论文这里给出了factor = 4 的情形，有兴趣的可以验算一下。

当然还得要通过二次剩余来简化这条式子。

通过讨论n = 3 ，n = 4，的情形，论文这里把通式归纳到任意factor数的情形,并且我们我们可以通过原有的式子，推导出factor级数更高的式子。

总的来说就是能够通过素性检测的合数。

多看paper，多学习