查看“︁强素数”︁的源代码

{{noteTA|G1=Math|G2=IT|T=zh:强素数;zh-cn:强素数;zh-tw:強質數;zh-hk:强質數;|1=zh:素数;zh-cn:素数;zh-tw:質數;zh-hk:質數;}}
在[[数学]]中，'''强素数'''是指具有某些特性的[[素数]]。强素数的定义在[[密码学]]和[[数论]]中是不同的（但有一定的关联）。

== 密码学中的定义 ==

在[[密码学]]中，一个素数<math>p</math>在满足下列条件时被称为''强素数''
<ref name="rivest">Ron Rivest and Robert Silverman, ''Are 'Strong' Primes Needed for RSA?'', Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007 {{Wayback|url=http://eprint.iacr.org/2001/007 |date=20070906083807 }}</ref>：

# <math>p</math> 必须是很大的数。
# <math>p-1</math> 有很大的[[质因数]]。也就是说，对于某个整数<math>a_1</math>以及大素数<math>q_1</math>，我们有<math>p = a_1 q_1 + 1</math>。
# <math>q_1-1</math> 有很大的[[质因数]]。也就是说，对于某个整数<math>a_2</math>以及大素数<math>q_2</math>，我们有<math>q_1 = a_2 q_2 + 1</math>。
# <math>p+1</math> 有很大的[[质因数]]。也就是说，对于某个整数<math>a_3</math>以及大素数<math>q_3</math>，我们有<math>p = a_3 q_3 - 1</math>。

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

== 数论上的定义 ==

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

[[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|id=A051634}}

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

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

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

== 强素数在密码学上的应用 ==

=== 基于整数分解的密码系统 ===

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

=== 基于离散对数的密码系统 ===

1978年由 Stephen Pohlig 和[[馬丁·赫爾曼]]证明，如果 ''p-1'' 的所有质因数都小于 <math>log^c p</math>，那么解决[[模数]]为<math>p</math>的 [[离散对数]] 问题就属于 [[P/NP问题|P问题]]。所以，对于基于离散对数的密码系统，比如[[数字签名算法]]（即[[数字签名算法|DSA]]），我们就要求 ''p-1'' 至少要有一个大质因数。

== 其它 ==

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

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

== 参考资料 ==

<references />

== 外部链接 ==

* [http://www.isg.rhul.ac.uk/ugcs/Companion_v1.21.pdf Guide to Cryptography and Standards] {{Wayback|url=http://www.isg.rhul.ac.uk/ugcs/Companion_v1.21.pdf |date=20060925134546 }}
* [https://web.archive.org/web/20130425010834/http://www.rsa.com/rsalabs/node.asp?id=2217 RSA Lab's explanation on strong vs weak primes]

{{質數}}

[[Category:密码学|Q]]
[[Category:素數| ]]