素性检测 | ZQQ's docs

概念 #

素性检测 (Primality test) 即判定一个数是否为素数。素性检测比质因数分解容易，运行时间与输入数字的size成多项式相关。密码学中常用于快速生成一个大的质数。

判定方法 #

试除法 #

根据质数的性质，若在 [2, sqrt(n)] 中没有可以把它整除的，则能够判定 n 为质数。

Python实现

from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, isqrt(n)+1):
        if n % i == 0:
            return False
    return True

# 测试
num = 341
if is_prime(num):
    print(f"{num} 是素数！")
else:
    print(f"{num} 不是素数！")

威尔逊定理 #

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。对于给定的正整数n，n为素数，当且仅当 (n-1)! ≡ -1 (mod n)

但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

费马小定理 #

定理内容如下：

若 p 是一个质数，则对任意整数 a , a^p - a 能被 p 整除；特别地，如果 a 不是 p 的倍数（即 a 与 p 互质），则 a^(p - 1) ≡ 1 (mod p)

自然而然的疑问是，如果一个数满足以上特征，这个数是质数吗？
答案是有这么一部分伪素数满足以上特点，但却是合数。如2^341 - 2能够整除341，而341 = 11 x 31，341 为最小的以 2 为底的费马伪素数。

费马小定理的逆否命题是：

若存在整数 a , a^p - a 不能被 p 整除，则 p 是一个合数

根据原命题和逆否命题的关系，可知逆否命题成立

费马小定理的逆命题是：

若对任意整数 a , a^p - a 能被 p 整除，则 p 是一个质数

如果逆命题成立，那我们得到了一个整数是否为质数的判定定理。但遗憾的是，这个逆命题不完全成立。上面的341并不算是一个反例，因为逆命题中指明的是对任意整数 a，只考察2为底数是不够的。

这个真正的反例直到1910年，才由美国数学家卡迈克尔证明和发现，它是561。此时已经距离费马提出费马小定理已经有将近300年时间。这些合数对所有底数都符合费马小定理，被称为绝对伪素数或卡迈克尔数。前一亿个自然数中，有255个卡迈克尔数。

庆幸的是，虽然费马小定理的逆定理不完全成立，但在绝大多数情况下还是有效的，所以使用费马小定理进行素数判断属于随机性算法，无法保证完全正确。

总有一类数（卡迈克尔数）不能通过这个测试。当这个数不是卡迈克尔数时，随机从 [2, n-2] 选取一个 a，有小于 1/2 的概率将一个合数检验为一个素数。在重复 k 次成立的情况下，n 为合数的可能性小于 1/(2^k)。

Python实现

import random

def is_prime(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    for _ in range(k):
        a = random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False

    return True

# 测试
num = 17
if is_prime(num):
    print(f"{num} 可能是素数！")
else:
    print(f"{num} 不是素数！")

AKS #

AKS 算法是第一个确定性的、多项式复杂度的、对一般数均适用并且不依赖任何未被证明的猜想的素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。

尽管不实用（虽然复杂度是多项式的，但计算量还是过大，远不如同为多项式复杂度的概率算法Miller-Rabin素性测试），但是有着很大的学术意义。

https://zh.wikipedia.org/zh-cn/AKS%E8%B3%AA%E6%95%B8%E6%B8%AC%E8%A9%A6 https://zhuanlan.zhihu.com/p/346563055

Miller-Rabin #

Miller-Rabin 算法是已知的最简单、最快速的检测算法，基于了如下 二次探测定理 和费马小定理 2个定理作为引理：

若 p 是素数，x < p，x^2 ≡ 1 (mod p)，那么 x = 1 或 x = p - 1 即 x ≡ ±1 (mod p)

即若 p 是素数，1 mod p的平方根只可能是 1 和 -1，如果有x < p，x^2 ≡ 1 (mod p)，但是不满足 x=1 或 x= p - 1（存在非平凡平方根），那么这个 p 一定不是素数

证明过程如下：

x^2 ≡ 1 (mod p) 推出 x^2 - 1 ≡ 0 (mod p)，由 p 为一个素数可以推出 x1 = 1, x2 = p - 1

Miller-Rabin 算法描述如下：

对于给定的奇数 n > 2，可以将 n - 1 写为 d*2^s，其中 s 为整数，d 为奇数。选取一个 a 作为基数，a 和 n 互质，那么当以下 2 个条件满足其中之一时：

a^d ≡ 1 (mod n)
a^(d*2^r) ≡ -1 (mod n) (0 ≤ r < s)

称 n 是以 a 为底的强可能素数(strong probable prime)。如果 n 不是一个强可能素数，则一定为合数，此时 a 被称为 n 复合性的 witness；强可能素数可能为合数，此时 n 被称为强伪素数(strong pseudoprime)，a 被称为 strong liar。

证明如下：
对于给定的奇素数 n > 2，可以将 n - 1 写为 d*2^s，其中 s 为整数，d 为奇数，又根据费马小定理可得
a^(d*2^s) ≡ 1 (mod n)
序列 a^(d*2^s), a^(d*2^s-1), a^(d*2^s-2), ..., a^(2d), a^(d) 中的每项是前一项的平方根。由于第一项同余 1，因此第二项是 1 模 n 的平方根。
根据之前的引理，第二项是同余1或−1，如果 -1 则完毕。如果是1，则继续使用引理，判断第三项，依此类推。最终，对于给定的奇素数，要么其中一项为-1，要么所有都为1，即表现为最后一项 a^(d) 同余1

算法本质是在费马小定理的基础上，加上了二次探测定理进行了近一步的筛选，能够筛选掉卡迈克尔数。基于原本的费马小定理，最小的伪素数是341，最小的卡迈克尔数是561；而使用Miller-Rabin，最小的伪素数是2047，最小的底为2和3的伪素数则是1 373 653。

算法将幂次 n-1 降低为以 2 为阶的各次幂，采用模平方算法降低复杂度，这也是该算法的优势之一，大大提高了效率。

随机从 [2, n-2] 选取一个 a，一般选取2，3，5，7之类的质数，在重复 k 次检测通过的情况下，n 为合数的概率小于 1/(4^k)。相比之下，这样的出错概率远远低于费马素性检测。

Python实现

import random

def is_prime(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # 将 n - 1 表示为 (2^s) * d 的形式
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    # 进行 k 次测试
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

# 测试
num = 1373653
if is_prime(num):
    print(f"{num} 可能是素数！")
else:
    print(f"{num} 不是素数！")