目錄
1密碼學中的定義2數論上的定義
3強素數在密碼學上的套用
3.1基於整數分解的密碼系統
3.2基於離散對數的密碼系統
4其它
5參考資料
6外部連結
密碼學中的定義
在密碼學中，一個素數p在滿足下列條件時被稱為強素數[1]：p必須是很大的數。
p−1有很大的質因數。也就是說，對於某個整數a1以及大素數q1，我們有p=a1q1+1。
q1−1有很大的質因數。也就是說，對於某個整數a2以及大素數q2，我們有q1=a2q2+1。
p+1有很大的質因數。也就是說，對於某個整數a3以及大素數q3，我們有p=a3q3−1。
有時，當一個素數隻滿足上面一部分條件的時候，我們也稱它是強素數。而有的時候，我們則要求加入更多的條件。例如，我們可以要求a1=2，或者a2=2。從這個角度上來說，很大的安全素數可以看作是強素數的一種。
[編輯]數論上的定義
在數論中，如果一個素數p比它相鄰的兩個素數的平均數要大，則我們稱p為強素數。換句話說，一個強素數是這樣的素數：和它前面的相鄰素數比較，它總是更靠近在它後面的下一個素數。或者用代數的語言來說，對於素數pn（n是它在所有素數的有序集合中的索引），則pn為強素數若且唯若。下面列出最小的幾個強素數：
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就會變得不可行。由於這個原因，ANSIX.31標準要求，在為基於RSA的數字簽名算法生成鑰匙的時候，必須用強素數。但是，強素數並不能保證n在用其它更新的算法來分解時也一樣難以分解。例如Lenstra的橢圓分解法和普通數域篩選法（NumberFieldSieve）。考慮到為了生成強素數需要用去更多的時間，RSASecurity目前並不建議在鑰匙生成算法中使用強素數。Rivest和Silverman[1]也給出了類似但更細緻的論述。基於離散對數的密碼系統
1978年由StephenPohlig和MartinHellman證明，如果p-1的所有質因數都小於logcp，那么解決模數為p的離散對數問題就屬於P問題。所以，對於基於離散對數的密碼系統，比如數字簽名算法（即DSA），我們就要求p-1至少要有一個大質因數。其它
要注意的是，判斷一個偽素數是否是強偽素數時，我們看的是它除以某個基數的冪之後的餘數，而不是看它和相鄰的偽素數的平均數那個較大。在數論中，如果一個素數剛好等於其相鄰素數的平均數，那么我們把這個素數叫做均衡素數。如果它比平均數小，則叫做弱素數。
盤點密碼學相關知識
| 盤點密碼學相關知識，密碼學是研究編制密碼和破譯密碼的技術科學。 |
