檢視強質數的原始碼

{| class="wikitable" style="float:right; margin: -10px 0px 10px 20px; text-align:left"
|<center>'''強質數'''<br><img src="https://slidesplayer.com/slide/16314912/95/images/28/RSA+%E5%8F%83%E6%95%B8%E7%9A%84%E9%81%B8%E6%93%87%EF%BC%9A+n%E7%9A%84%E9%81%B8%E6%93%87.jpg" width="280"></center><small>[https://slidesplayer.com/slide/16314912/ 圖片來自slidesplayer]</small> 
|}

在[[数学]]中, '''强素数'''是指具有某些特性的[[素数]]<ref>[https://zhuanlan.zhihu.com/p/43937838 素数]，zhihu</ref> 。强素数的定义在[[密码学]]和[[数论]]中是不同的（但有一定的关联）。

== 数论上的定义 ==

在[[数论]]中，如果一个素数<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>应该是两个强素数之积。这样，如果用[[:en:Pollard's p-1 algorithm|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|Martin Hellman]] 证明，如果 ''p-1'' 的所有质因数都小于 <math>log^c p</math>，那么解决[[模数]]为<math>p</math>的 [[离散对数]] 问题就属于 [[P/NP问题|P问题]]。所以，对于基于离散对数的密码系统，比如[[数字签名算法]]（即[[Digital_Signature_Algorithm|DSA]]），我们就要求 ''p-1'' 至少要有一个大质因数。

== 其它 ==

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

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

== 參考文獻 == 
{{reflist}}
[[Category: 310 數學總論]]