强質數

維基媒體消歧義頁

數學中,強質數是指具有某些特性的質數。強質數的定義在密碼學數論中是不同的(但有一定的關聯)。

密碼學中的定義

密碼學中,一個質數 在滿足下列條件時被稱為強質數 [1]

  1.   必須是很大的數。
  2.   有很大的質因數。也就是說,對於某個整數 以及大質數 ,我們有 
  3.   有很大的質因數。也就是說,對於某個整數 以及大質數 ,我們有 
  4.   有很大的質因數。也就是說,對於某個整數 以及大質數 ,我們有 

有時,當一個質數只滿足上面一部分條件的時候,我們也稱它是強質數。而有的時候,我們則要求加入更多的條件。例如,我們可以要求 ,或者 。從這個角度上來說,很大的安全質數可以看作是強質數的一種。

數論上的定義

數論中,如果一個質數 比它相鄰的兩個質數的平均數要大,則我們稱 強質數。 換句話說,一個強質數是這樣的質數:和它前面的相鄰質數比較,它總是更靠近在它後面的下一個質數。 或者用代數的語言來說,對於質數  是它在所有質數的有序集合中的索引),則 為強質數若且唯若 。 下面列出最小的幾個強質數:

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, 499OEIS數列A051634

例如,17是第7個質數。而第6個和第8個質數分別是13和19,加起來是32,平均值是16,小於17。所以17是一個強質數。

在一對孿生質數 )里,當 時,p總是強質數。這是因為 必能被3整除,所以不可能是質數。

有些質數既符合密碼學的強質數定義也符合數論上的強質數定義。比方說, 439351292910452432574786963588089477522344331 就是一個數論意義上的強質數,因為與它相鄰的兩的質數的平均數比它小62。如果沒有電腦的話,這個數也可以是一個密碼學意義上的強質數。這是因為 439351292910452432574786963588089477522344330 有一個大質因數 1747822896920092227343 (而這個質因數減去1後又有一個大質因數 1683837087591611009 ),而 439351292910452432574786963588089477522344332 也有一個大質因數 864608136454559457049 (而它減去1後也有大質因數 105646155480762397 )。 就算是用比較先進的演算法,用紙和筆也很難分解這樣大的數。但對於現代的電腦代數系統來說,分解這樣的數是很容易的事。所以真正的密碼學意義上的強質數比前例中的這些數還要大很多。

強質數在密碼學上的應用

基於整數分解的密碼系統

有人建議在RSA密碼系統的鑰匙生成演算法中,模數 應該是兩個強質數之積。這樣,如果用Pollard的p-1質因數分解演算法英語Pollard's p-1 algorithm來分解 就會變得不可行。由於這個原因,ANSI X.31標準要求,在為基於RSA的數碼簽章演算法生成鑰匙的時候,必須用強質數。但是,強質數並不能保證n在用其它更新的演算法來分解時也一樣難以分解。例如Lenstra的橢圓分解法英語Lenstra elliptic curve factorization普通數體篩選法。考慮到為了生成強質數需要用去更多的時間,RSA Security目前並不建議在鑰匙生成演算法中使用強質數。Rivest和Silverman [1]也給出了類似但更細緻的論述。

基於離散對數的密碼系統

1978年由 Stephen Pohlig 和馬丁·赫爾曼證明,如果 p-1 的所有質因數都小於  ,那麼解決模數 離散對數 問題就屬於 P問題。所以,對於基於離散對數的密碼系統,比如數碼簽章演算法(即DSA),我們就要求 p-1 至少要有一個大質因數。

其它

要注意的是,判斷一個偽質數是否是強偽質數時,我們看的是它除以某個基數的冪之後的餘數,而不是看它和相鄰的偽質數的平均數那個較大。

在數論中,如果一個質數剛好等於其相鄰質數的平均數,那麼我們把這個質數叫做平衡質數。如果它比平均數小,則叫做弱質數

參考資料

  1. ^ 1.0 1.1 Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007頁面存檔備份,存於互聯網檔案館

外部連結