强つよ素数そすう

在ざい数学すうがく中なか，强つよ素数そすう是ぜ指ゆび具有ぐゆう某ぼう些特性せい的てき素数そすう。强つよ素数そすう的てき定てい义在密みつ码学和わ数かず论中ちゅう是ぜ不同ふどう的てき（但ただし有ゆう一定いってい的てき关联）。

密みつ码学中ちゅう的てき定てい义

在ざい密みつ码学中ちゅう，一いち个素数すう$p$在ざい满足下か列れつ条件じょうけん时被称しょう为强つよ素数そすう ：

1. $p$ 必须是ぜ很大的てき数すう。
2. $p-1$ 有ゆう很大的てき质因数すう。也就是ぜ说，对于某ぼう个整数すう$a_{1}$以及大だい素数そすう$q_{1}$，我わが们有$p=a_{1}q_{1}+1$。
3. $q_{1}-1$ 有ゆう很大的てき质因数すう。也就是ぜ说，对于某ぼう个整数すう$a_{2}$以及大だい素数そすう$q_{2}$，我わが们有$q_{1}=a_{2}q_{2}+1$。
4. $p+1$ 有ゆう很大的てき质因数すう。也就是ぜ说，对于某ぼう个整数すう$a_{3}$以及大だい素数そすう$q_{3}$，我わが们有$p=a_{3}q_{3}-1$。

有ゆう时，当とう一个素数只满足上面一部分条件的时候，我わが们也称しょう它是强きょう素数そすう。而有的てき时候，我わが们则要求ようきゅう加入かにゅう更さら多た的てき条件じょうけん。例れい如，我わが们可以要求ようきゅう$a_{1}=2$，或ある者もの$a_{2}=2$。从这个角度ど上じょう来らい说，很大的てき安全あんぜん素数そすう可か以看作さく是ぜ强きょう素数そすう的てき一いち种。

数かず论上的てき定てい义

在ざい数かず论中なか，如果一いち个素数すう$p$比ひ它相邻的两个素数そすう的てき平均へいきん数すう要よう大だい，则我们称$p$为强つよ素数そすう。 换句话说，一个强素数是这样的素数：和かず它前面めん的てき相しょう邻素数すう比ひ较，它总是ぜ更さら靠もたれ近在きんざい它后面めん的てき下か一いち个素数すう。 或ある者もの用よう代数だいすう的てき语言来らい说，对于素数そすう$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 （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 和わ馬丁ばてい·赫爾曼证明，如果 p-1 的てき所有しょゆう质因数すう都と小しょう于 $log^{c}p$，那な么解决模も数すう为$p$的てき 离散对数 问题就属于 P问题。所以ゆえん，对于基もと于离散对数的てき密みつ码系统，比ひ如数字すうじ签名算法さんぽう（即そくDSA），我わが们就要求ようきゅう p-1 至いたり少しょう要よう有ゆう一いち个大质因数すう。

其它

要注意ようちゅうい的てき是ぜ，判断はんだん一いち个伪素数すう是ぜ否いや是これ强つよ伪素数すう时，我わが们看的てき是ぜ它除以某个基数すう的てき幂之后きさき的てき余あまり数すう，而不是ぜ看み它和相しょう邻的伪素数すう的てき平均へいきん数すう那な个较大だい。

在ざい数すう论中，如果一个素数刚好等于其相邻素数的平均数，那な么我们把这个素数そすう叫さけべ做平衡へいこう質しつ数すう。如果它比平均へいきん数すう小しょう，则叫做弱じゃく素数そすう。

外部がいぶ链接

• Guide to Cryptography and Standards （页面存そん档备份，存そん于互联网档案あん馆）
• RSA Lab's explanation on strong vs weak primes