费马小定理和素性测试

作者: 东方胖 | 来源:发表于2024-02-24 18:07 被阅读0次

素性测试是一个很实用的话题。
在非对称加密中，RSA的实现需要选择两个300位长的大素数，如果素数已经准备好了，写在一张纸上，我们去选择，但是有限的纸导致这个范围太小，如果使用暴力验证的方法，纸上的大素数很快就会被试完。
理智一点的做法是，大素数是随机选的。
朴素的素性测试，是用小于 n(实际上可以缩小到 $\sqrt n$ ) 的素数逐个试除，这个算法的复杂度是 $O(\sqrt n)$ 当n是大小几百位的数时，这个复杂度是不可忍受的。

关于费马小定理的素性测试，可以降低这种复杂度。

生成一个序列，逐个计算 4的k方次，并用 k - 1 去取模

[4**(i - 1) % i for i in range(1, 20)]

得到一个序列

[0, 0, 1, 0, 1, 4, 1, 0, 7, 4, 1, 4, 1, 4, 1, 0, 1, 16, 1]

注意哪些是 1 的项。
如果这个数值是 1 意味着同余式
$4^{p - 1} \equiv 1 \mod p$
成立
上述等于1 的位置序号分别是 3, 5, 7, 11, 13,15, 17, 19
除了 2 以上涵盖了 1-20所有的素数
所以可以猜测
设 a 是正整数, 如果 p 是素数，p > 2 ，那么 $a^{p - 1} \equiv 1 (\mod p)$ 成立
这个猜想是成立的，即费马小定理。

反过来不一定，例如上面的序列中 15 是个例外。

用2做实验的话，最小的一个例外数有点大
1-400 内满足 $2^{p - 1} \equiv 1(\mod p)$ 的数有
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 341, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397]
这些数大部分是素数，但是有例外。341 = 11 * 31,而且是惟一的一个
1000 内我们还能找到 $561 = 3 \times 11 \times 17 , 645 = 3 \times 5 \times 43$ 这些数字满足 $2^{p - 1} \equiv 1(\mod p)$

以上我们大概可以推测出一个素性测试的方法

如果一个数 p 满足 $2^{p - 1} \equiv 1(\mod p)$ 那么 p 极大的可能是素数，如果不满足，那么必定是2 或者合数，2 太平凡几乎不予考虑。
以上的结论可以帮助我们鉴别大多数是合数还是素数
至于像 341 561 这样的能够通过检验但是又不是素数的数，叫做伪素数

伪素数仍然有一些方法进一步判别
一种方法就是换基：341 是以2为基的伪素数，但是变一个基 7 ，341不再能通过费马小定理的检验，这表明 341 是合数。
不幸的是，有一种绝对伪素数，导致我们即便变换费马小定理测试的基，都不能验证它是素数。
上面的 561 就是一个这样的数。

这个叫做卡马克尔数的绝对伪素数是这样定义的，如果一个合数 n 满足，对所有的 b, (n, b) = 1（即n b互素）都有 $b^{n - 1} \equiv 1 (\mod n)$

意味着用费马小定理测试的方法，无法判别 561 是合数。

卡迈尔克数的存在让基于费马小定理的素性检验只能成为一种概率算法——即通过费马小定理检验的数大概率是一个素数，不能通过费马小定理检验的数一定是个合数

为什么用费马小定理检测是比试除法更快的方法

本质上在于整数方幂的同余数计算，有一种很高效的计算方法——模指数运算。
模指数运算可以避免计算指数方幂，一般是一个很大的天文数字。
比如计算 $2^{1000}$ 模 389 的最小正剩余（最小正剩余是介于 0-388中的一个正整数，不管 $2^{1000}的结果是多少，它模389 必然和0-388 中的一个数同余，那个数就是最小正剩余$ )

模指数运算避免直接计算 $2 ^{1000}$ 这个数很大，超乎想象的大，并且有可能不能装进你的计算机内存，即使变成字符串也极难处理。
首先把 1000 拆成一些2 的幂次和，不管什么数都能拆出来，从大到小排列幂次，和数的二进制表示有一定的联系，1000 = 512 + 256 + 128 + 64 + 32 + 8 ，实际上有一个定理表明，任何数都已唯一表示成一个一个基 b 的幂次和，这个唯一性是指将这些幂次按照规定次序排定后，它的项只有一种。

然后把 $2 ^{1}, 2^{2}, ..., 2^{512}, 2^{1024}$ 模 389 的最小正剩余逐个计算出来，这个工作量大不大？
稍微试一下，
直到 $256 = 2^8$ 为止，因为不超过 389 ,它们模 389 的最小正剩余就是自己
即
$2^{1} \equiv 2 (\mod 389) \\ 2^{2} \equiv 4 (\mod 389) \\ 2^{3} \equiv 8 (\mod 389) \\ 2^{4} \equiv 16 (\mod 389) \\ 2^{5} \equiv 32 (\mod 389) \\ 2^{6} \equiv 64 (\mod 389) \\ 2^{7} \equiv 128 (\mod 389) \\ 2^{8} \equiv 256 (\mod 389)$
在指数之间的计算可以在 O(n) 线性时间内完成，n是指数，对应本例子中的 1000
计算 $2^9, 2^{10}，...$

$2^{9} \equiv 2^8 \cdot 2^1 \equiv 256 \cdot 2 \equiv 123(\mod 389) \\ 2^{10} \equiv 2^9 \cdot 2^1 \equiv 123 \cdot 2 \equiv 246(\mod 389) \\ 2^{11} \equiv 2^10 \cdot 2^1 \equiv 246 \cdot 2 \equiv 103(\mod 389) \\ ... \\ 2^{16} \equiv 2^8 \cdot 2^8 \equiv 256 \cdot 256 \equiv 184(\mod 389)\\ 2^{32} \equiv 2^{16} \cdot 2^{16} \equiv 184 \cdot 184 \equiv 13 (\mod 389) \\ 2^{64} \equiv 2^{32} \cdot 2^{32} \equiv 13 \cdot 13 \equiv 169 (\mod 389) \\ 2^{128} \equiv 2^{64} \cdot 2^{64} \equiv 169 \cdot 169 \equiv 164 (\mod 389) \\ 2^{256} \equiv 2^{128} \cdot 2^{128} \equiv 164 \cdot 164 \equiv 55 (\mod 389) \\ 2^{512} \equiv 2^{256} \cdot 2^{256} \equiv 55 \cdot 55 \equiv 302 (\mod 389) \\ ...$

根据1000的拆解计算
$2^{1000} = 2 ^ {512 + 256 + 128 + 64 + 32 + 8} (\mod 389)\\ = 302 \cdot 55 \cdot \cdot 164 \cdot 169 \cdot 13 \cdot 256 (\mod 389) \\ = 272 \cdot 164 \cdot 169 \cdot 13 \cdot 256 (\mod 389) \\ = 262 \cdot 169 \cdot 13 \cdot 256 (\mod 389) \\ = 321 \cdot 13 \cdot 256 (\mod 389) \\ = 283 \cdot 256(\mod 389) \\ = 94 (\mod 389)$

以上算法的复杂度是多少？
假设 $n = 2^{1000}$ , 那么复杂度大约是 $O(log_2 log_2{n}) = O(log_2{1000})$

费马小定理和素性测试

为什么用费马小定理检测是比试除法更快的方法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读