强质数查看源代码讨论查看历史
 |
在数学中, 强素数是指具有某些特性的素数[1] 。强素数的定义在密码学和数论中是不同的（但有一定的关联）。
数论上的定义
在数论中，如果一个素数<math>p</math>比它相邻的两个素数的平均数要大，则我们称<math>p</math>为强素数。 换句话说，一个强素数是这样的素数：和它前面的相邻素数比较，它总是更靠近在它后面的下一个素数。 或者用代数的语言来说，对于素数p_n（n是它在所有素数的有序集合中的索引），则p_n为强素数当且仅当p_n > p_{n - 1} + p_{n + 1} \over 2。 下面列出最小的几个强素数：
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 *id=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密码系统的钥匙生成算法中，模数<math>n</math>应该是两个强素数之积。这样，如果用Pollard的p-1质因数分解算法来分解<math>n = pq</math>就会变得不可行。由于这个原因，ANSI X.31标准要求，在为基于RSA的数字签名算法生成钥匙的时候，必须用强素数。但是，强素数并不能保证n在用其它更新的算法来分解时也一样难以分解。例如Lenstra的椭圆分解法|Lenstra elliptic curve factorization和普通数域筛选法。考虑到为了生成强素数需要用去更多的时间，RSA Security目前并不建议在钥匙生成算法中使用强素数。Rivest和Silverman == 密码学中的定义 ==
在密码学中，一个素数<math>p</math>在满足下列条件时被称为强素数：
- p 必须是很大的数。
- p-1 有很大的质因数。也就是说，对于某个整数a_1以及大素数q_1，我们有p = a_1 q_1 + 1。
- q_1-1 有很大的质因数。也就是说，对于某个整数a_2以及大素数q_2，我们有q_1 = a_2 q_2 + 1。
- p+1 有很大的质因数。也就是说，对于某个整数a_3以及大素数q_3，我们有p = a_3 q_3 - 1。
有时，当一个素数只满足上面一部分条件的时候，我们也称它是强素数。而有的时候，我们则要求加入更多的条件。例如，我们可以要求a_1 = 2，或者a_2 = 2。从这个角度上来说，很大的安全素数可以看作是强素数的一种。也给出了类似但更细致的论述。
基于离散对数的密码系统
1978年由 Stephen Pohlig 和 Martin Hellman 证明，如果 p-1 的所有质因数都小于 <math>log^c p</math>，那么解决模数为<math>p</math>的 离散对数 问题就属于 P问题。所以，对于基于离散对数的密码系统，比如数字签名算法（即DSA），我们就要求 p-1 至少要有一个大质因数。
其它
要注意的是，判断一个伪素数是否是强伪素数时，我们看的是它除以某个基数的幂之后的余数，而不是看它和相邻的伪素数的平均数那个较大。
在数论中，如果一个素数刚好等于其相邻素数的平均数，那么我们把这个素数叫做平衡质数。如果它比平均数小，则叫做弱素数。