数学基础-素数

素数，之前在rsa算法当中简单提到过，但是对于素数是如何产生的，如何判断一个大整数是不是素数并没有进行展开，素数作为密码学当中比较重要的一个元素，本文来梳理一下素数的有关知识。

素数定义

「素数」(Prime Number), 也叫质数, 指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

素数的分布

来看一下素数的分布，如下图所示:

具体的素数来源来可以在参考资料的连接当中找到，通过上面可以发现，素数的分布是在固定区间之内逐渐减少的，也就是说越来越稀疏的。这就引发一个问题，素数是有无限多个吗？素数到底会不会没有。

这个答案是素数是无穷多个的，这么说可能读者不信，那么简单来证明一下吧。

「证明:」

假设素数有n个分别为, , ...,, 那么如果构造一个新的数字:

根据算数基本定理可以知道，这一定是一个素数，因为在p之前没有其他的素数的乘积可以表示为他，因此与之前的假设矛盾，所以素数是有无穷多个的，不用担心素数会用光的情况。

那么如何去找到一个素数呢，根据素数定理可以得到, 也就是说平均个整数当中会有一个素数，也就是说，平均测试个整数可以找到一个素数，实际上考虑到偶数一定不是素数，因此平均只需要测试个数字即可。当然，这个只是一个概率的个数，素数并不是均匀分布的。因此对于判定一个数字是不是素数的算法就显得尤为重要了，如果这个算法执行效率不高(对于大整数而言, RSA目前推荐密钥长度是2048)这个查找素数的过程将会异常的缓慢，下面来看一个常用的素数的判定方法。

素性测试(Miller-Rabin算法)

这个算法是一个概率算法，它并不能一定的保证所测试的数字一定准确，但是如果输出是合数，那么这个是一定准确的，下面来具体看一下这个算法。

对于任意的奇数(n > 1)都可以表示为:

的形式，其中k > 0, 并且q为奇数，这一点并不难理解，如果n为奇数，那么n-1一定为偶数，因此n-1可以被2整除, 我们记为，那么对于来说，有两种情况，第一种为奇数，第二种为偶数，对于第一种来说，k = 1, , 对于第二种，我们可以继续重复之前的除以2的操作，直到第一种情况，即可得到。

接下来，来看一下素数的两个性质:

• 如果p是素数，a是小于p的正整数, 则当且仅当或者

• 假设p是大于2的素数，有, 其中k > 0, q为奇数，假设a是整数，并且1 < a < p -1, 则下面两个必有一个成立

2. 整数, , ..., , 即存在某个数字j使得, 其中

来证明一下，如果p是素数，则有(费马定理), 根据, 可以得到, 因此构造如下序列:

可以得到最后一个数字一定为1，前面已经说过了，并且对于前一个数字一定是后一个数字的平方，因此下面必定有一个成立

• 数列的第一个数字为1，那么他后面的所有的数字都为1
• 数列当中某些数字不为1, 但是他们的平方模p之后为1，根据素数的第一个性质，符合这个条件唯一的整数为p-1, 因此数列当中必定有一个数为p-1

然后来看一下具体的判定算法，如果n为素数, 那么在数列()当中，要么第一个数模n为1， 要么某个数模n为n-1, 否则n一定是合数。但是反过来不一定，举一个简单的例子假设可以得到, 然后, 但显然2047不是素数。

因此可以根据上面这个性质来判断一个数字是否为素数，如果n不是素数，那么返回false, 否则返回true.

• 找到整数k, q, 其中k > 0, q为奇数, 使得
• 选取随机数a, 使得1 < a < n - 1
• 如果返回true
• 令j从0开始到k-1
• 测试返回true
• 返回false

可以证明，这个算法的误判率大概为1/4, 因此如果进行t次这个测试算法，那么根据概率理论可以得到误判的概率为, 因此如果t取的足够大, 这个误判率将会足够小，一直达到我们可以认为他是对的即可。

代码实现

采用rust实现一下这个算法吧。

use num_bigint::{BigUint, RandBigInt};


pub fn miller_rabin(n: BigUint, t: usize) -> bool {
    let zero: BigUint = BigUint::from(0u64);
    let one: BigUint = BigUint::from(1u64);
    let two: BigUint = BigUint::from(2u64);
    let three: BigUint = BigUint::from(3u64);

    // n <= 1
    if n <= one {
        return false;
    } else if n == two || n == three {
        return true;
    }

    let n1 = &n - &one;
    let mut k = 0;
    let mut q: BigUint = n.clone() - &one;
    while (&q & &one) == zero {
        q >>= 1;
        k += 1;
    }

    let mut rng = rand::thread_rng();
    for _ in 0..t {
        let a = rng.gen_biguint(n1.bits());
        if a > one && a < n1 {
            // a^q mod n
            let mut x = a.modpow(&q, &n);
            if x == one || x == n1 {
                continue;
            }

            let mut prime: bool = false;
            for _ in 0..k - 1 {
                x = x.modpow(&two, &n);
                if x == n1 {
                    prime = true;
                    break;
                }
            }
            if prime {
                // 疑似素数, 继续判定
                continue;
            } else {
                // 如果非素数判定失效
                return false;
            }
        }
    }

    true
}

#[cfg(test)]
mod test {
    use crate::miller_rabin::miller_rabin;
    use num_bigint::BigUint;

    #[test]
    fn test() {
        assert!(!miller_rabin(BigUint::from(1u64), 0));
        assert!(miller_rabin(BigUint::from(2u64), 0));
        assert!(miller_rabin(BigUint::from(3u64), 0));
        assert!(miller_rabin(BigUint::from(5u64), 100));
        assert!(miller_rabin(BigUint::from(7u64), 100));
        assert!(miller_rabin(BigUint::from(104729u64), 100));
        assert!(!miller_rabin(BigUint::from(65535u64), 100));
        assert!(!miller_rabin(BigUint::from(65536u64), 100));
    }
}

总结

本文简单介绍了素数的一点点性质，以及如何测试一个数字是否是素数, 这个在密码学是经常要用到的，就比如之前聊过的rsa的原理当中就需要生成两个大的素数p和q, 以及接下来要讲的DH的密钥交换协议，Elgamal算法等也都需要生成一个大的素数。

参考资料

• The First 10,000 Primes
• 素数定理 - 维基百科，自由的百科全书
• 密码编码学与网络安全--原理与实践(第六版) 【William Stallings】