強質數

在數學中，強素數是指具有某些特性的素數。強素數的定義在密碼學和數論中是不同的（但有一定的關聯）。

密碼學中的定義

在密碼學中，一個素數$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