强素数

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

密码学中的定义在密码学中，一个素数{\displaystyle p}在满足下列条件时被称为强素数：1

p 必须是很大的数。

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

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

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

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

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

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的椭圆分解法和普通数域筛选法。考虑到为了生成强素数需要用去更多的时间，RSA Security目前并不建议在钥匙生成算法中使用强素数。Rivest和Silverman也给出了类似但更细致的论述。

基于离散对数的密码系统1978年由 Stephen Pohlig 和Martin Hellman证明，如果p-1的所有质因数都小于 ，那么解决模数为p的离散对数问题就属于P问题。所以，对于基于离散对数的密码系统，比如数字签名算法（即DSA），我们就要求p-1至少要有一个大质因数。

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

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

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所