跳至內容

安全質數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

安全質數是滿足2p+1形式的一類數,在這裡p也是質數。(相反地,質數p叫做索菲熱爾曼質數。)開始的幾個安全質數是:

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907 (OEIS數列A005385

由來

之所以叫它們是「安全」質數,是因為它們在加密算法中的運用:某些因數分解的演算法(如Pollard Rho演算法英語Pollard's rho algorithm)的計算時間部份取決於被分解數的質因數減去一的因數大小,而若被分解的數以一個安全質數2p+1作為因數,由於此質數減去一有一個大質數p做為因數,計算時間將會變多。但是很容易理解任何一個小於1050的質數都不是真正安全的,因為對於任何一個有著合適算法的現代計算機都能在適當的時間內判斷出它的質性,但是這些小一點的安全質數在加密算法原理的教學中仍然還是很有用的。不過現在對於安全質數還沒有像對費馬質數梅森質數一樣的特別的質性檢測方法。

除了5,沒有既是費馬質數又是安全質數的數了。一個給定的費馬質數F,一個小小的運算就可以證明(F-1)/2會是2的

除了7,沒有既是梅森質數又是安全質數的數了。這個證明有點麻煩,不過仍然在基礎代數的範疇內:p必須是質數,2p-1才有可能是質數,那麼((2p - 1) - 1)/2 = 2p - 1 - 1是個梅森數,因此只有當p=3時p-1才是質數,此時23-1=7。

第一類坎寧安鏈中所有的數除了最後一項都是索菲熱爾曼質數,除了第一項都是安全質數。以7結尾的安全質數必定會出現在坎寧安鏈的尾端,因為其兩倍加一將會以5結尾,而這是5的倍數。

危險質數

所有不是安全質數的質數都稱為「危險質數」或「不安全質數」,也就是說,所有無法滿足2p+1形式的一類質數都是危險質數,在這裡p也是質數。開始的幾個危險質數是:

2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233, 239, 241, 251, 257, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337OEIS數列A059456