数学中的定义

密码学中的定义

数论上的定义

数学中的定义

在数学中, 强素数是指具有某些特性的素数。强素数的定义在密码学和数论中是不同的（但有一定的关联）。

密码学中的定义

在密码学中，一个素数p在满足下列条件时被称为强素数 [1]：

p 必须是很大的数。

p − 1 有很大的质因数。也就是说，对于某个整数a1以及大素数q1，我们有p = a1q1 + 1。

q1 − 1 有很大的质因数。也就是说，对于某个整数a2以及大素数q2，我们有q1 = a2q2 + 1。

p + 1 有很大的质因数。也就是说，对于某个整数a3以及大素数q3，我们有p = a3q3 − 1。

有时，当一个素数只满足上面一部分条件的时候，我们也称它是强素数。而有的时候，我们则要求加入更多的条件。例如，我们可以要求a1 = 2，或者a2 = 2。从这个角度上来说，很大的安全素数可以看作是强素数的一种。

数论上的定义

在数论中，如果一个素数p比它相邻的两个素数的平均数要大，则我们称p为强素数。 换句话说，一个强素数是这样的素数：和它前面的相邻素数比较，它总是更靠近在它后面的下一个素数。 或者用代数的语言来说，对于素数pn（n是它在所有素数的有序集合中的索引），则pn为强素数当且仅当。 下面列出最小的几个强素数：

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499 （OEIS中的数列A051634）

例如，17是第7个素数。而第6个和第8个素数分别是13和19，加起来是32，平均值是16，小于17。所以17是一个强素数。

在一对孪生素数（p,p + 2）里，当p > 5时，p总是强素数。这是因为p − 2必能被3整除，所以不可能是素数。

有些素数既符合密码学的强素数定义也符合数论上的强素数定义。比方说， 439351292910452432574786963588089477522344331 就是一个数论意义上的强素数，因为与它相邻的两的素数的平均数比它小62。如果没有电脑的话，这个数也可以是一个密码学意义上的强素数。这是因为 439351292910452432574786963588089477522344330 有一个大质因数 1747822896920092227343 （而这个质因数减去1后又有一个大质因数 1683837087591611009 ），而 439351292910452432574786963588089477522344332 也有一个大质因数 864608136454559457049 （而它减去1后也有大质因数 105646155480762397 ）。 就算是用比较先进的算法，用纸和笔也很难分解这样大的数。但对于现代的计算机代数系统来说，分解这样的数是很容易的事。所以真正的密码学意义上的强素数比前例中的这些数还要大很多。

基于整数分解的密码系统

有人建议在RSA密码系统的钥匙生成算法中，模数n应该是两个强素数之积。这样，如果用Pollard的p-1质因数分解算法来分解n = pq就会变得不可行。由于这个原因，ANSI X.31标准要求，在为基于RSA的数字签名算法生成钥匙的时候，必须用强素数。但是，强素数并不能保证n在用其它更新的算法来分解时也一样难以分解。例如Lenstra的椭圆分解法和普通数域筛选法（Number Field Sieve）。考虑到为了生成强素数需要用去更多的时间，RSA Security目前并不建议在钥匙生成算法中使用强素数。Rivest和Silverman [1]也给出了类似但更细致的论述。

要注意的是，判断一个伪素数是否是强伪素数时，我们看的是它除以某个基数的幂之后的余数，而不是看它和相邻的伪素数的平均数那个较大。

在数论中，如果一个素数刚好等于其相邻素数的平均数，那么我们把这个素数叫做均衡素数。如果它比平均数小，则叫做弱素数。